比较大列表中的字符串但不能使用 Python 中的集合

Question

我有一个包含 11965 个条目的文本文件，如下所示：

AAA
BBB
CCC
DDD

Which I transformed into:
list_1 = ['AAA', 'BBB', 'CCC', ...]

我需要将它与另一个包含 2221545 个条目的文本文件进行比较，如下所示：

AAA,.ADJ UK
AAA,.N UK
AAA,.N ES
B,.ADV UK
BB,.ADV UK
BBB,.N IT

Which I transformed into:
list_2 = ['AAA\tADJ\tUK', 'AAA\tN\tUK', 'AAA\tN\tES', 'B\tADV\UK', 'BB\tADV\tUK', ...]

所以我必须得到一个看起来像这样的字典：

result_dict = {'AAA':[[UK, ADJ, N], [ES,N]], 'BBB':[[IT,N]], ...}

由于第二个列表的大小，如果我们逐一比较条目，时间复杂度将为O(11965*2221545)。（我进去对了吗？）

而且因为我必须得到整个条目，所以我不能用集合来比较它们。有什么有效的方法来完成工作吗？

Answer 1

这是不需要集合的解决方案：

result_dict = {}

for item in list_1:
    result_dict.setdefault(key, [])

for item in list_2:
    value_list = item.split('\t')
    key, values = value_list[0], value_list[1:]
    result_dict.setdefault(key, []).append(values)

print result_dict
# {'B': [['ADV\UK']], 'AAA': [['ADJ', 'UK'], ['N', 'UK'], ['N', 'ES']], 'BB': [['ADV', 'UK']]}

复杂度与列表的总长度呈线性关系。

Answer 2

所以这里有另一个答案使用了defaultdict。我的更进一步，使用我在评论中给出的结果格式，并在线性时间内工作。

list_2 = ['AAA\tADJ\tUK', 'AAA\tN\tUK', 'AAA\tN\tES', 'B\tADV\tUK', 'BB\tADV\tUK']

import collections

d = collections.defaultdict(lambda: collections.defaultdict(list))

for line in list_2:
    word, wordtype, lang = line.split('\t')
    d[word][lang].append(wordtype)

d 是

defaultdict(<function __main__.<lambda>>,
            {'AAA': defaultdict(list, {'ES': ['N'], 'UK': ['ADJ', 'N']}),
             'B': defaultdict(list, {'UK': ['ADV']}),
             'BB': defaultdict(list, {'UK': ['ADV']})})

我们可以像这样转换成标准的字典：

{k: dict(v) for k, v in d.items()}

# {'AAA': {'ES': ['N'], 'UK': ['ADJ', 'N']},
#  'B': {'UK': ['ADV']},
#  'BB': {'UK': ['ADV']}}

我们可以简单地通过

访问 word/lang 组合

d['AAA']['UK']
# --> ['ADJ', 'N']

Answer 3

实现我在评论中所说的内容。我看不到第一个文件在哪里发挥作用。

list_2 = ['AAA\tADJ\tUK', 'AAA\tN\tUK', 'AAA\tN\tES', 'B\tADV\tUK', 'BB\tADV\tUK']

from collections import defaultdict
collect_dict = defaultdict(lambda: defaultdict(list))
for line in list_2:
    word, pos, country = line.split()
    collect_dict[word][country].append(pos)
result_dict = { word: [[country] + poss for country, poss in country_pos.items()]
                for word, country_pos in collect_dict.items()}
# => {'AAA': [['UK', 'ADJ', 'N'], ['ES', 'N']], 'B': [['UK', 'ADV']], 'BB': [['UK', 'ADV']]}

编辑：我实际上同意 FHTMitchell 的评论 - 只有在您真的喜欢问题中发布的格式时才进行最后一次转换，但 collect_dict 中的格式可能更有用。

编辑：根据评论中的说明（列表 1 用于限制列表 2 的元素）：

list_2 = ['AAA\tADJ\tUK', 'AAA\tN\tUK', 'AAA\tN\tES', 'B\tADV\tUK', 'BB\tADV\tUK']

from collections import defaultdict
valid_set = set(list1)
collect_dict = defaultdict(lambda: defaultdict(list))
for line in list_2:
    word, pos, country = line.split()
    if word in valid_set:
        collect_dict[word][country].append(pos)
result_dict = { word: [[country] + poss for country, poss in country_pos.items()]
                for word, country_pos in collect_dict.items()}

比较大列表中的字符串但不能使用 Python 中的集合

Comparing strings in huge lists but cannot use set in Python

python

performance

nlp

list-comprehension

string-comparison