2

我希望我能够清楚地解释这个问题。我是一名 python 实验者（以防下面的查询显得幼稚）

假设我有一个形式的数据集：

a = ( ('309','308','308'), ('309','308','307'), ('308', '309','306', '304'))

让我把每一个都('309','308','308')称为一条路径。

我想找到以下计数：

一个。Count('309','308', <any word>)

湾。Count('309',<any word>,'308')

和所有可能的排列。

我在想它是某种正则表达式，可以帮助我实现这个搜索。而且，我拥有的路径数达到 50000。

谁能建议我如何在 python 中进行这种操作？我探索了 trie，radix，但我认为这对我没有帮助。

谢谢，萨加尔

4

3 回答 3

2

您可以使用它collections.Counter来执行此操作：

>>> from collections import Counter
>>> a = ( ('309','308','308'), ('309','308','307'), ('308', '309','306', '304'))
>>> Counter((x, y) for (x, y, *z) in a)
Counter({('309', '308'): 2, ('308', '309'): 1})
>>> Counter((x, z) for (x, y, z, *w) in a)
Counter({('308', '306'): 1, ('309', '308'): 1, ('309', '307'): 1})

我在这里也使用了扩展元组解包，它在 Python 3.x 之前不存在，只有当你有不确定长度的元组时才需要它。在 python 2.x 中，您可以改为：

Counter((item[0], item[1]) for item in a)

但是，我不能说这会有多有效。我不相信它应该是坏的。

ACounter有一个类似dict的语法：

>>> count = Counter((x, y) for (x, y, *z) in a)
>>> count['309', '308']
2

编辑：您提到它们的长度可能大于一，在这种情况下，您可能会遇到问题，因为如果它们短于所需长度，它们将无法解包。解决方案是更改生成器表达式以忽略任何不符合要求的格式：

Counter((item[0], item[1]) for item in a if len(item) >= 2)

例如：

>>> a = ( ('309',), ('309','308','308'), ('309','308','307'), ('308', '309','306', '304'))
>>> Counter((x, y) for (x, y, *z) in a)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/usr/lib/python3.2/collections.py", line 460, in __init__
    self.update(iterable, **kwds)
  File "/usr/lib/python3.2/collections.py", line 540, in update
    _count_elements(self, iterable)
  File "<stdin>", line 1, in <genexpr>
ValueError: need more than 1 value to unpack
>>> Counter((item[0], item[1]) for item in a)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/usr/lib/python3.2/collections.py", line 460, in __init__
    self.update(iterable, **kwds)
  File "/usr/lib/python3.2/collections.py", line 540, in update
    _count_elements(self, iterable)
  File "<stdin>", line 1, in <genexpr>
IndexError: tuple index out of range
>>> Counter((item[0], item[1]) for item in a if len(item) >= 2)
Counter({('309', '308'): 2, ('308', '309'): 1})

如果您需要可变长度计数，最简单的方法是使用列表切片：

start = 0
end = 2
Counter(item[start:end] for item in a if len(item) >= start+end)

当然，这只适用于连续运行，如果你想单独选择列，你必须做更多的工作：

def pick(seq, indices):
    return tuple([seq[i] for i in indices])

columns = [1, 3]
maximum = max(columns)
Counter(pick(item, columns) for item in a if len(item) > maximum)
于 2012-04-20T09:27:03.960 回答
2

如果您想以 CS 风格的高效方式执行此操作，您应该查看Trys。您需要稍作修改才能将每个子树的大小存储在其根上，但这应该不会太难。

于 2012-04-20T09:50:02.687 回答
0

如果您是 Python 2.7 之前的版本，则可以使用列表推导：

#Number of: ('309','308', <any word>)
>>> len([i[0] for i in a if i[0]=='309' and i[1]=='308'])
2
#Number of:('309',<any word>,'308')
>>> len([i[0] for i in a if i[0]=='309' and i[-1]=='308'])
1

使用列表理解似乎也比使用快一些Counter，虽然元组解包很好，但它也会减慢速度。defaultdict可以更快地完成类似的事情：

from collections import Counter, defaultdict

a = []
for i in range(500000):
    a.append(('309','308','308'))

def ww(a):
    return Counter((item[0], item[1]) for item in a)

def xx(a):
    return len([i[0] for i in a if i[0]=='309' and i[1]=='308'])

def yy(a):
    g = defaultdict(int)
    for i in a:
        g[(i[0],i[1])] += 1
    return g

def zz(a):
    return Counter((i, j) for (i, j, *k) in a)

from timeit import timeit
print('Counter..:',timeit("ww(a)", "from __main__ import ww, a", number=100))
print('compreh..:',timeit("xx(a)", "from __main__ import xx, a", number=100))
print('defdict..:',timeit("yy(a)", "from __main__ import yy, a", number=100))
print('Count+un.:',timeit("zz(a)", "from __main__ import zz, a", number=100))
#output:
Counter..: 8.411258935928345
compreh..: 2.8653810024261475
defdict..: 4.256785154342651
Count+un.: 18.45333218574524
于 2012-04-20T09:28:11.500 回答