非常大的元组列表中的部分匹配列表

2024-03-29 00:14:30 发布

您现在位置:Python中文网/ 问答频道 /正文

我是python新手,我必须感谢大家在这里的精彩讨论,但我有一个问题,我没有看到任何建议。(或者太复杂了,我无法理解。)

我有两个列表(元组?)每个都有大约一百万个条目。它们都按第一个条目(单词)排序,格式相同。在每个列表中,单词/页面组合都是唯一的。你知道吗

List1=  [('word1', 'page1'), ('word1', 'page2'), ('word3', 'page1'),...]
List2 = [('word1', 'page4'), ('word2', 'page2'), ('word3', 'page1'),...]

我需要找到列表1中出现在列表2中的每个“单词”。这个例子的输出应该是

[('word1', 'page1'), ('word1', 'page2'), ('word1', 'page4'),('word3','page1')]

我已经看了这么多,我现在完全混淆了集合,列表,元组,字典,…我可能可以做一个for循环,但似乎有更好的选择在这里某处。你知道吗


Tags: 列表排序格式条目页面单词建议元组
1条回答
网友
1楼 · 发布于 2024-03-29 00:14:30

看起来是个大数据问题。您可能需要使用特定的工具,例如numpypandas。如果内存中有足够的RAM来容纳这两个数据,可以在numpy中完成:

In [103]:
import numpy as np
List1=  [('word1', 'page1'), ('word1', 'page2'), ('word3', 'page1')]
List2 = [('word1', 'page4'), ('word2', 'page2'), ('word3', 'page1')]

In [104]:
arr1 = np.array(List1)
arr2 = np.array(List2)

In [105]:
arr3=np.vstack((arr1, arr2)) #stack two dataset together
arr3

Out[105]:
array([['word1', 'page1'],
       ['word1', 'page2'],
       ['word3', 'page1'],
       ['word1', 'page4'],
       ['word2', 'page2'],
       ['word3', 'page1']], 
      dtype='|S5')

In [106]:
np.in1d(arr3[:,0], arr1[:,0]) 
#for each item in arr3, is the first value appears in the 1st position of arr1?

Out[106]:
array([ True,  True,  True,  True, False,  True], dtype=bool)

In [107]:
arr3[np.in1d(arr3[:,0], arr1[:,0])] #Boolean indexing

Out[107]:
array([['word1', 'page1'],
       ['word1', 'page2'],
       ['word3', 'page1'],
       ['word1', 'page4'],
       ['word3', 'page1']], 
      dtype='|S5')

In [108]:
set(map(tuple, arr3[np.in1d(arr3[:,0], arr1[:,0])]))

Out[108]:
{('word1', 'page1'),
 ('word1', 'page2'),
 ('word1', 'page4'),
 ('word3', 'page1')}
网友
2楼 · 发布于 2024-03-29 00:14:30

如果需要将单词映射到页面,可以使用dict将单词映射到页面。你知道吗

from collections import defaultdict
word_pages_1 = defauldict(list)
for w, p in List1:
   word_pages_1[w].append(p) 

然后可以对dict键执行set操作,以便在它们之间进行比较

网友
3楼 · 发布于 2024-03-29 00:14:30

我相信有很多方法可以实现你的目标。由于您的数据非常大,您必须考虑性能、时间或空间还是性能?下面是一些例子。你知道吗

#!/usr/bin/python
#-*- coding:utf-8 -*-

L1 = [('word1', 'page1'), ('word1', 'page2'), ('word3', 'page1'), ]
L2 = [('word1', 'page4'), ('word2', 'page2'), ('word3', 'page2'), ]

def func1():
    '''
    Time Complexity is O(n^2) 
    '''
    res = []
    for i in L1:
        for k in L2:
            if i[0] == k[0]:
                res.append(i)
                res.append(k)
    return list(set(res))

def func2():
    '''
    Time Complexity is O(n)
    '''
    d1 = {}
    for i in L1:
        if d1.has_key(i[0]):
            d1[i[0]].append(i[1])
        else:
            d1[i[0]] = [i[1]]
    d2 = {}
    for i in L2:
        if d2.has_key(i[0]):
            d2[i[0]].append(i[1])
        else:
            d2[i[0]] = [i[1]]
    d3 = {}
    for key in d1.keys():
        if d2.has_key(key):
            d3[key] = d2[key] + d1[key]

    return [(m,n) for m in d3.keys() for n in d3[m]]



if __name__ == '__main__':
    print func1()
    print func2()

    import timeit
    t = timeit.Timer(func1)
    print t.timeit(10000)
    t = timeit.Timer(func2)
    print t.timeit(10000)

相关问题 更多 >