Сравнение строк в огромных списках, но не может использовать набор в Python - PullRequest
Новая
       24

Сравнение строк в огромных списках, но не может использовать набор в Python

0 голосов
/ 05 июля 2018

У меня есть текстовый файл с 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). (Я вхожу правильно?)

И поскольку мне нужно получить всю запись, я не могу использовать set для их сравнения. Есть ли эффективный способ сделать работу?

Ответы [ 3 ]

0 голосов
/ 05 июля 2018

Итак, здесь был другой ответ, который использовал 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']}}

Мы можем получить доступ к комбо-слову / языку, просто набрав 

d['AAA']['UK']
# --> ['ADJ', 'N']
0 голосов
/ 05 июля 2018

Реализация того, что я говорил в комментариях. Я не вижу, где первый файл вступает в игру. 

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()}
0 голосов
/ 05 июля 2018

Вот решение, не требующее наборов: 

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']]}

Сложность будет линейной по общей длине списков.

...