1

我有一个巨大的 python 列表（A）列表。列表 A 的长度约为 90,000。每个内部列表包含大约 700 个(datetime.date,string). 现在，我正在分析这些数据。我正在做的是我在内部列表中采用大小为 x 的窗口，x = len(inner list) * (some fraction <= 1)并且我正在保存每个有序对 (a,b)，其中 a 出现在该窗口中的 b 之前（实际上，内部列表是按时间排序的）。我将这个窗口移动到最后一个元素，一次从一端添加一个元素，然后从另一个元素中删除，这需要O(window-size)时间，因为我只考虑新的元组。我的代码：

for i in xrange(window_size):
        j = i+1;
        while j<window_size:
            check_and_update(cur, my_list[i][1], my_list[j][1],log);
            j=j+1

    i=1;
    while i<=len(my_list)-window_size: 
        j=i;
        k=i+window_size-1;
        while j<k:
            check_and_update(cur, my_list[j][1], my_list[k][1],log);  
            j+=1
        i += 1

这cur实际上是一个 sqlite3 数据库游标，my_list是一个包含元组的列表，我为 A 中的所有列表迭代此代码，并且log是一个打开的日志文件。在方法check_and_update()中，我正在查找我的数据库以查找元组（如果存在），否则我将其插入，以及到目前为止的出现总数。代码：

def check_and_update(cur,start,end,log):    
    t = str(start)+":"+ str(end)
    cur.execute("INSERT OR REPLACE INTO Extra (tuple,count)\
                 VALUES ( ? , coalesce((SELECT count +1 from Extra WHERE tuple = ?),1))",[t,t])

正如预期的那样，这个元组的数量是巨大的，我之前曾尝试过很快耗尽内存的字典。所以，我求助于 SQLite3，但现在它太慢了。我尝试过索引但没有帮助。可能我的程序花费大量时间查询和更新数据库。你对这个问题有什么优化思路吗？可能会更改算法或一些不同的方法/工具。谢谢！

编辑：我的目标是找到在窗口中出现的字符串元组的总数，按它们出现的不同内部列表的数量分组。我用这个查询提取这些信息：

for i in range(1,size+1):       
        cur.execute('select * from Extra where count = ?',str(i))
        #other stuff

例如（我忽略了日期条目并将它们写为'dt'）：

My_list = [
            [ ( dt,'user1') , (dt, 'user2'), (dt, 'user3') ]
            [ ( dt,'user3') , (dt, 'user4')]
            [ ( dt,'user2') , (dt, 'user3'), (dt,'user1') ]
          ]

在这里，如果我取分数 = 1，则结果：

only 1 occurrence in window: 5 (user 1-2,1-3,3-4,2-1,3-1)
only 2 occurrence in window: 2 (user 2-3)
4

2 回答 2

2

让我说清楚。

您有多达大约 220 亿个潜在元组（对于 90000 个列表，700 个中的任何一个，以下任何条目，平均 350 个），这可能会更少，具体取决于窗口大小。您想查找它们出现的内部列表的数量，有多少元组。

这种大小的数据必须保存在磁盘上。由于大小而存在于磁盘上的数据的规则是“永远不要随机访问，而是生成然后排序”。

所以我建议你把每个元组写到一个日志文件中，每行一个元组。对该文件进行排序。现在任何给定元组的所有实例都在一个地方。然后运行文件，并为每个元组发出它出现的次数（即它在多少内部列表中）的计数。对第二个文件进行排序。现在运行该文件，您可以提取出现 1x、2x、3x 等的元组数量。

如果您有多台机器，很容易将其转换为 MapReduce。（这在道德上是相同的方法，但是你可以并行化很多东西。）

于 2012-05-30T06:51:45.050 回答
1

Apache Hadoop是适合此类问题的 MapReduce 实现之一：

于 2012-05-30T10:00:28.157 回答