мой инверсный индекс очень медленный любые предложения?

Question

У меня есть текстовый файл, где каждая строка содержит кучу текста. (В самом файле нет номера строк), как это:

 
line#:  text: 
0   This is some text 
1   More text 
2   whats for lunch 

Я хочу функцию, которая возвращает словарь отображения каждого слово его номер строки вхождения в основном проектировании inverseindex.

т.е. {'This':{1}, 'text':{0,1}, 'for':{2} ... }

После сканирования текстового файла (это занимает .18 секунд) Я положил строки в список списков, таким образом, что каждая позиция в списке сохраняет разделительную линию. т.е .:

[['This', 'is', 'some', 'text'], ['More', ...] ...]

После чего я использую enumerate() извлечь позицию и создать словарь. У меня уже есть решение, но оно настолько уродливое, и мне потребовалось столько времени, что я хочу увидеть еще одно элегантное решение.

Для справки мой алгоритм работает в течение 882,28 секунд, т. Е. 15 минут на 1099 строк ислов. Другими словами, явно не пифонов.

def invidx(strlist): 
    # return algoritm execution time 
    start = time.time() 

    f = open(strlist, 'r') 
    wordLoc = [] 
    for line in f:  
     s = line.split() 
     wordLoc.append(list(s)) 
    f.close() 

    # benchmark 
    print 'job completed in %.2fs' % (time.time() - start) 

    try: 
     q = {} 
     for a, b in enumerate(wordLoc): 
      l = set() 
      for w in b : 
       if w not in q: 
        l = {a for a, b in enumerate(wordLoc) if w in b} 
        q[w] = l 
    except KeyboardInterrupt: 
     print 'Interrupt detected: aborting...' 
     print 'Failed to complete indexing, ran for %.2fs' % \ 
      (time.time() - start) 
     exit(0)     

    return q 

РЕДАКТИРОВАТЬ:

согласно запросу код выше. Поймите меня, ребята.

Answer 1

Вы можете получить номера строк, используя enumerate, когда вы сначала сканируете файл, и добавьте номера строк в адрес set s, как вы идете.

myfile.txt:

a b c 
b x y 
a c b 

индексироваться:

index = {} 
with open('myfile.txt') as F: 
    for line_num, line in enumerate(F): 
     for word in line.split(): 
      index.setdefault(word, set()).add(line_num) 

index 
=> {'a': set([0, 2]), 
'b': set([0, 1, 2]), 
'c': set([0, 2]), 
'x': set([1]), 
'y': set([1])} 

Answer 2

Вы можете использовать collections.defaultdict:

from collections import defaultdict 
dic = defaultdict(set) 
with open('abc') as f: 
    for i,line in enumerate(f): #enumerate returns the line number as well as the line 
     words = line.split() #splt the line using str.split() 
     for word in words:  #iterate over words and add to it's corresponding set 
      dic[word.lower()].add(i) 
print dic 

выход:

defaultdict(<type 'set'>, 
{'whats': set([2]), 
'for': set([2]), 
'this': set([0]), 
'text': set([0, 1]), 
'is': set([0]), 
'some': set([0]), 
'lunch': set([2]), 
'more': set([1])}) 

Answer 3

линия отвечает за замедление это одна:

l = {a for a, b in enumerate(wordLoc) if w in b} 

Каждый раз, когда вы найдете слово, которое вы еще не видели, вы повторно перечислить каждую строку и посмотреть, если содержит слово. Это будет включать операции O (NumberOfUniqueWords * NumberOfLines) в целом, которые являются квадратичными по размеру ввода.

Вы уже перечисляете каждое слово каждой строки. Почему бы просто не добавить их, когда идете?

for w in b : 
    if w not in q: q[w] = [] 
    q[w].append(a) 

Это займет O (NumberOfWords) время, которое является линейным размером входного вместо квадратичной (ISH). Вы касаетесь каждой вещи один раз, а не раз за уникальное слово.

Answer 4

Это похоже на работу, и я абсолютно уверен, что это быстрее, чем версия:

from time import time 

def invidx(strlist): 
    # return algoritm execution time 
    start = time() 

    wordLocs = [] 
    unique_words = set() 
    with open(strlist, 'r') as f: 
     for line in f: 
      words = line.split() 
      unique_words.update(words) 
      wordLocs.append(set(words)) 

    # benchmark 
    print 'job completed in %.2fs' % (time() - start) 

    try: 
     q = {} 
     for unique_word in unique_words: 
      occurrences = set() 
      for line, words in enumerate(wordLocs): 
       if unique_word in words: 
        occurrences.add(line) 
      q[unique_word] = occurrences 

    except KeyboardInterrupt: 
     print ('Interrupt detected: aborting...\n' 
       ('Failed to complete indexing, ran for %.2fs' % (time() - start))) 
     exit(0) 

    return q 

from pprint import pprint 
pprint(invidx('strlist.txt')) 

выход из вашего тривиального тестового файла:

job completed in 0.00s 
{'More': set([1]), 
'This': set([0]), 
'for': set([2]), 
'is': set([0]), 
'lunch': set([2]), 
'some': set([0]), 
'text': set([0, 1]), 
'whats': set([2])}