确定一个Python列表是否有95%相似度？

Question

这个问题询问如何确定列表中的每个元素是否相同。如果要以相对高效的方式确定列表中95％的元素是否相同，应该怎么做？例如：

>>> ninety_five_same([1,1,1,1,1,1,2,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1])
True
>>> ninety_five_same([1,1,1,1,1,1,2,1]) # only 80% the same
False

这需要有一定的效率，因为列表可能非常大。

- davidscolgan

---

@Tim：找出哪个元素是期望的有点棘手。 - Thilo

好的，预期元素必然是分布的模式。没有其他值能够达到95%。 - Tim McNamara

不确定计算完整分布是否能满足效率要求。 - Thilo

在第二个例子中，你是怎么得到80%这个数字的？我不明白你试图计算什么。根据我的理解，第二个例子应该是87.5%相同。（8个中有7个） - recursive

Answer 1

>>> from collections import Counter
>>> lst = [1,1,1,1,1,1,2,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
>>> _, freq = Counter(lst).most_common(1)[0]
>>> len(lst)*.95 <= freq
True

- SilentGhost

---

Python确实有一些隐藏在其后台的不错技巧。 - Tim McNamara

需要注意的是，这需要Python 2.7版本，这是在collections模块中添加Counter子类时引入的。 - martineau

@martineau：它已被添加到py3.1，然后回溯到2.7，也就是说它已经存在一段时间了。此外，Python 2.7是Python的当前稳定版本。 - SilentGhost

@martineau：你可以在Python ≥2.5中使用http://code.activestate.com/recipes/576611/。 - kennytm

需要注意的是，此解决方案要求所有元素都是可哈希的。 - kennytm

Answer 2

实际上，对于类似问题有一个简单的线性解决方案，仅使用50％约束而不是95％。 查看这个问题，只需要几行代码。

它也适用于你，只需要在最后检查所选元素是否满足95％的阈值，而不是50％。（尽管，正如Thilo所指出的那样，如果currentCount>= n * 0.95，则这不是必要的。）

我还会发布st0le答案中的Python代码，向所有人展示它有多难。

currentCount = 0
currentValue = lst[0]
for val in lst:
   if val == currentValue:
      currentCount += 1
   else:
      currentCount -= 1

   if currentCount == 0:
      currentValue = val
      currentCount = 1

如果你正在寻找解释，我认为Nabb提供了最好的解释。

- Nikita Rybak

---

+1. O(N)。查看所有其他答案应该解决这个问题是否“琐碎”的争论。 - Thilo

这里有一个精彩的动画演示：http://www.cs.utexas.edu/~moore/best-ideas/mjrty/index.html - Thilo

之后，您需要再次检查确保大多数确实达到了95％（除非可以从currentCount的最终值中推断出此结果）。 - Thilo

@larsmans 是的，没有完美的解决方案。（我已经在帖子中提到需要检查是否满足给定的频率。）你的算法也很好，尽管它使用了相当数量的额外内存，并且可能会更慢一些。 - Nikita Rybak

@larsmans 我同意你的解决方案是一个好的解决方案（在没有花哨的定理和教科书算法的情况下，这是最好的解决方案）。不过，我认为第二次遍历输入列表比调用哈希n次更快。（假设输入列表可用） - Nikita Rybak

Answer 3

def ninety_five_same(lst):
    freq = collections.defaultdict(int)
    for x in lst:
        freq[x] += 1
    freqsort = sorted(freq.itervalues())
    return freqsort[-1] >= .95 * sum(freqsort)

假设哈希表的性能完美并且排序算法良好，此程序运行时间为O(n + m lg m)，其中m是不同项的数量。最坏情况下为O(n lg n)。 编辑：这里有一个O(n + m)的单次遍历版本（假设m << n）：

def ninety_five_same(lst):
    freq = collections.defaultdict(int)
    for x in lst:
        freq[x] += 1
    freq = freq.values()
    return max(freq) >= .95 * sum(freq)

内存使用为O(m)。max和sum可以用单个循环替代。

- Fred Foo

---

你可以将lambda: 0替换为int，它保证被初始化为0。 - Björn Pollex

@Nikita Rybak 提出的 Boyer-Moore 算法具有O(N)时间复杂度。 - Thilo

虽然这是一个正确的解决方案，但我认为 Thilo 提出的尽早中断的解决方案更好。 - Hannes Ovrén

Answer 4

这比检查每个元素是否相同的效率还要低。算法大致相同，需要遍历列表中的每个元素，并计算与预期值不匹配的数量（还要知道哪个是预期值）。但是，这次遇到第一个不匹配时不能直接返回false，必须继续直到有足够的不匹配来构成5％的错误率。

想一想，找出哪个元素是“正确”的可能并不那么容易，需要计算每个值，直到确定5％的元素被错放的位置。

考虑一个包含10,000个元素的列表，其中99％为42：

  (1,2,3,4,5,6,7,8,9,10, ... , 100, 42,42, 42, 42 .... 42)

所以我认为，你需要先建立一个频率表，至少要覆盖前5%的表格。

- Thilo

---

我喜欢这个想法。它很容易理解，而且应该非常快。棘手的部分将是找到停止条件，但我认为那相当容易。 - Hannes Ovrén

忘记我的答案吧，使用Nikita概述的Boyer-Moore大多数投票算法。 - Thilo

Answer 5

def ninety_five_same(l):
  return max([l.count(i) for i in set(l)])*20 >= 19*len(l)

同时还解决了浮点数除法精度的问题。

- Rok

---

否则的话，对于加集合生产的每个值，您需要完成整个列表的完整计数。这是非常繁重的工作，因为列表很大，有许多不同的值，但总长度只占其中的一小部分。 - Tony Veijalainen

Answer 6

lst = [1,1,1,1,1,1,2,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
#lst = [1, 2, 1, 4, 1]
#lst = [1, 2, 1, 4]

length = len(lst)
currentValue = lst[0]
lst.pop(0)
currentCount = 1

for val in lst:
   if currentCount == 0:
      currentValue = val

   if val == currentValue:
      currentCount += 1
   else:
      currentCount -= 1

percent = (currentCount * 50.0 / length + 50)
epsilon = 0.1
if (percent - 50 > epsilon):
    print "Percent %g%%" % percent
else:
    print "No majority"

注意：epsilon具有“随机”值，根据数组长度选择某些内容等。 Nikita Rybak的解决方案currentCount >= n*0.95不起作用，因为currentCount的值取决于元素的顺序，但上述方法确实有效。

C:\Temp>a.py
[2, 1, 1, 4, 1]
currentCount = 1

C:\Temp>a.py
[1, 2, 1, 4, 1]
currentCount = 2

- Andrei Damian-Fekete

Answer 7

把你的列表想象成一个装有红色和黑色球的桶。

如果在十个球的桶中有一个红球，你随机取出一个球并放回桶中，然后重复这个样本替换步骤一千次，你期望在一千次中平均观察到多少次红球？

查看二项式分布和置信区间。如果你有一个非常长的列表，并且想要相对高效地完成任务，采样是一个好方法。

- Alex Reynolds

---

问题在于你不仅有红球和黑球（而且可能还有数百种不同的颜色）。而采样看起来非常不可靠，考虑到存在一个O（N）的精确解决方案。 - Thilo

如果你知道颜色的数量，你可以扩展到一个多项式。如果您的列表有数十亿个元素或更多，例如，采样几千个“球”比需要通过列表中的每个元素传递的O(n)方法更具吸引力。 - Alex Reynolds

你如何知道颜色的数量？ - Thilo

如果您预先知道哪些球（“对象”）放入桶（“列表”）中，那么您可以适当地进行建模。 - Alex Reynolds

Answer 8

将排序作为一般解决方案可能会很耗费时间，但考虑到Python中tim sort的卓越平衡性质，它利用了列表的现有顺序。我建议先对列表进行排序（或使用sorted复制），但这样做会影响性能。从前面和后面扫描找到相同的元素或达到扫描长度 > 5%，否则列表与找到的元素相似度为95%。

随机选取元素作为候选项，并按频率降序计数，直到发现计数 > 95%或总计数超过5%，应该也不错。

- Tony Veijalainen