找到所有常见的N大小的元组的元组

的名单我要创建一个，做如下操作的应用（我有一次解析数据，并将它们存储在数据库中）：找到所有常见的N大小的元组的元组

我给ķ元组（具有K超过1000000）和每个元组是在

(UUID, (tuple of N integers))

形式，例如，假设N等于20，用于每k元组，并且每20大小的元组被排序。我在以下两种形式（2个不同的表）救了我的所有数据在数据库中，这样我可以更容易地处理它们：

_id，UUID，tuple.as_a_string（）
_id， UUID，1st_elem，2nd_elem，3rd_3lem，... 20th_elem

的目标是从元组的列表，如那些元组的每一个到一个以上的20大小的存在找到所有10级的元组元组**。**

例如，如果我们给出两个关注荷兰国际集团20大小的元组：

(1, (1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,161,17,18,19,20)) 
(2, (1,3,5,7,9,11,13,15,17,19,21,23,25,27,29,31,33,35,37,39))

共用元组是：（1,3,5,7,9,11,13,15,17,19）

这是一个10大小的元组，所以结果是类似以下内容：

(1, 2, (1,3,5,7,9,11,13,15,17,19))

为了做到这一点，有什么我目前做的是（在Python 3）：

创建一组与20的元素-si数据库中第一行的元组。
使用数据库中其余行的20个元组的元素为每一行创建一个集合。
对于第二组列表中的每个集合，我都与第一组相交。
然后，我创建了交叉点与10个元素（在Python中是itertools.combinations（new_set，10））的组合，它给了我想要的结果。

但是这个程序是很慢。即使使用多处理技术来充分利用我的8个CPU内核，每个计算都需要一个不同的编号，但这需要花费很长时间。我现在有2天的计划，只有20％。

您对如何优化流程有任何建议吗？ NumPy阵列可以帮助执行速度吗？ SQL中有什么方法可以计算每行所需的内容，即使是每行一行？

在此先感谢。

来源

2016-10-01 TIMace

为什么这个标记的SQL？你的数据表示是什么？ –

对不起。我的意思是只用SQLite标记。我错过点击。我的数据是大小为20的整数的元组，每个元组都有唯一的ID分配给元组。 – TIMace

如果它是sqlite的，你不应该写SQL来做到这一点，而不是python？ – deltaskelta

似乎没有成为这么多的希望：忘记combinations()一部分，你需要检查每对K元组的交集。有choose(K, 2) = K*(K-1)/2对，所以有一百万个元组有近5000亿对。

你可以玩的一个低级别技巧是将一个元组表示为一个整数而不是一个整数，其中位2**i设置为整数，当且仅当i位于元组中时。既然你在评论中说，一个元组包含没有重复，每个元组元素是range(1, 100)，100位的整数是足够了（它可能被削减到99位，但不值得理会）。

点是一个整数的不同位“&”云快了很多比交集。在我的盒子上，快了大约7倍。下面是一些代码来说明这个概念，有些马虎的时序结果（一台机器同时做很多其他的东西上运行）：

def build(K, values, N): 
    from random import sample 
    sets = [] 
    ints = [] 
    for i in range(K): 
     t = sample(values, N) 
     sets.append(set(t)) 
     ints.append(sum(1 << i for i in t)) 
    return sets, ints 

def run(K, values, N): 
    from time import time 
    as_sets, as_ints = build(K, values, N) 
    for meth, collection in [("sets", as_sets), 
          ("ints", as_ints)]: 
     s = time() 
     for i in range(K-1): 
      base = collection[i] 
      for j in range(i+1, K): 
       x = base & collection[j] 
     t = time() 
     print("K", K, meth, t-s) 

for K in 5000, 10000, 20000: 
    run(K, range(1, 100), 20)

输出：

K 5000 sets 7.322501182556152 
K 5000 ints 1.0357279777526855 
K 10000 sets 30.60071086883545 
K 10000 ints 4.150524377822876 
K 20000 sets 128.24610686302185 
K 20000 ints 15.933331727981567

需要注意的是，符合市场预期，运行时间因为任何一种方法在K中都是二次的（所以K的加倍大约需要4倍;而使K大10倍会使运行时间增加大约10 ** 2 = 100）。

虽然交点的整数更快，但确定结果的基数较慢。有很多方法可以做到这一点，但“最好的”取决于期望的分布和对编码疼痛的容忍度;-)下面是major methods的概述。

来源

2016-10-02 03:54:16

我选择使用bitsets，结合您推荐的和我已经完成的工作，我看到了50倍的性能提升。我用bitsets来表示我的集合，并使用AND运算符。 0代表不存在的号码，而1代表现有的号码。简单而高效。 – TIMace

看来您可以将元组放入矩阵的行中，并从行号到UUID进行映射。然后将所有的元组存储在一个numpy数组中是可行的，因为元组的元素很小。 numpy具有能够计算这种数组的行之间的交集的代码。这段代码生成组合以首先处理元组，然后进行比较。

from itertools import combinations 
import numpy as np 
from time import time 

minInt=1 
maxInt=100 
tupleSize=20 
intersectionSize=10 

K=100 
rows=np.zeros((K,tupleSize),dtype=np.int8) 
print ('rows uses', rows.nbytes, 'bytes') 

for i,c in enumerate(combinations(range(minInt,maxInt),tupleSize)): 
    if i>=K: 
     break 
    for j,_ in enumerate(c): 
     rows[i,j]=_ 

t_begin=time() 
for i in range(K-1): 
    for j in range(i+1,K): 
     intrsect=np.intersect1d(rows[i],rows[j],True) 
     if intrsect.shape[0]==intersectionSize: 
      print (i,j,intrsect) 
t_finish=time() 

print ('K=', K, t_finish-t_begin, 'seconds')

这里是在家里我的老双核心P4难有起色做了一些样品测量。

行使用200个字节 K = 100.0009770393371582031秒

行使用1000个字节 K = 500.0410161018371582秒

行使用2000个字节 K = 1000.15625秒

行使用10000个字节 K = 500 3.610351085662842秒

行使用20000字节 K = 100014.931640863418579秒

行使用100000个字节 K = 5000379.5498049259186秒

如果你运行你的机器上的代码，你可以推断。我不知道这是否会让你的计算变得可行。

也许我就把一堆反对票！

来源

2016-10-01 21:45:08

这个解决方案并不是我想要实现的改进，因为数据集非常庞大，这让我的生活变得艰难。然而，numpy数组中的组织实际上给了我一些性能改进，因为访问时间，虽然不是很大的提升。谢谢您的输入！ – TIMace

非常欢迎。我认为，至少它可以回答一两个问题，并提示其他人发表评论。 –

比尔，我想这将创建一个更随意的搭配。您的组合版本系统地通过选择步骤。小K的交点大小接近tupleSize。

choices = np.arange(minInt, maxInt) 
for i in range(K): 
    rows[i,:] = np.random.choice(choices, tupleSize, replace=False)

使用sets约4倍比np.intersect1d更快。

sets = [set(row) for row in rows] 
dd = collections.defaultdict(int) 
for i in range(K-1): 
    for j in range(i+1,K): 
     intrsect=sets[i].intersection(sets[j]) 
     dd[len(intrsect)] += 1

我切换到收集交集大小，因为它对迭代策略更有趣且不太敏感。

随着K = 5000：

K= 5000 221.06068444252014 seconds 
{0: 77209, 1: 514568, 2: 1524564, 3: 2653485, 4: 3044429, 5: 2436717, 6: 1408293, 7: 596370, 8: 188707, 9: 44262, 10: 7783, 11: 1012, 12: 93, 13: 8}

越小时间是只是为sets创建步骤;这非常快。

K= 5000 0.058181047439575195 46.79403018951416 seconds 
{0: 77209, 1: 514568, 2: 1524564, 3: 2653485, 4: 3044429, 5: 2436717, 6: 1408293, 7: 596370, 8: 188707, 9: 44262, 10: 7783, 11: 1012, 12: 93, 13: 8}

当k比较大

K= 10000 818.3419544696808 seconds 
{0: 309241, 1: 2058883, 2: 6096016, 3: 10625523, 4: 12184030, 5: 9749827, 6: 5620209, 7: 2386389, 8: 752233, 9: 176918, 10: 31168, 11: 4136, 12: 407, 13: 18, 14: 2} 
K= 10000 0.09764814376831055 151.11484718322754 seconds

来源

2016-10-02 02:02:59 hpaulj

Paul，感谢您的回复。对我们中的许多人来说，像这样突出显示的比较将是有益的。但是哪里？ –

找到所有常见的N大小的元组的元组

回答

相关问题