Наименьшее расстояние между двумя словами (python)

Question

Вот две версии, о которых я мог думать. V2 предпочтительнее, когда оба слова являются общими (скажем, «is» и «the», для которых будет проблемой масштабирование n1 * n2 версии 1) и более надежным для вредоносного ввода (скажем, файл с двумя словами). Но для более интересных запросов (например, «большой» и «животный») v1 работает так же быстро, и я могу думать о более реалистичных семантических проблемах, для которых v2 не будет работать вообще, кроме v1. Есть ли способ ускорить его?

импорт timeit t1 = timeit.default_timer()

Защиту расстояние (версия, имя файла, wordOne, wordTwo):

f = open(filename, 'rU') 
text = f.read() 
f.close() 
index = 0 
distance = index 
version = int(version) 
print 'inputs', filename, wordOne, wordTwo 
countOne = 0 
countTwo = 0 

print 'version', version 

if version == 1: 
    word_pos = {} 
    for word in text.split(): 
     if word in [wordOne, wordTwo]: 
      if word in word_pos.keys(): 
       word_pos[word].append(index) 
      else: 
       word_pos[word] = [index] 

     index += 1 

    countOne = len(word_pos[wordOne]) 
    countTwo = len(word_pos[wordTwo]) 

    distances = [] 
    low = 0 
    high = index 
    for posOne in word_pos[wordOne]: 
     for posTwo in word_pos[wordTwo]: 
      #shrink innner loop by distance?: 
      #for posTwo in range(int(posOne-distance), (posOne+distance)): 
      #if abs(posOne-posTwo) < distance: 
      #distance = abs(posOne-posTwo) 
      distances.append(abs(posOne-posTwo)) 
    distance = min(distances) 

elif version == 2: 
    switch = 0 
    indexOne = 0 
    indexTwo = 0 
    distance = len(text) 
    for word in text.split(): 

     if word == wordOne: 
      indexOne = index 
      countOne += 1 
     if word == wordTwo: 
      indexTwo = index 
      countTwo += 1 

     if indexOne != 0 and indexTwo != 0: 
      if distance > abs(indexOne-indexTwo): 
       distance = abs(indexOne - indexTwo) 

     index += 1 

t2 = timeit.default_timer() 
print 'Delta t:', t2 - t1 

print 'number of words in text:', index 
print 'number of occurrences of',wordOne+':', countOne 
print 'number of occurrences of',wordTwo+':', countTwo 
if countOne < 1 or countTwo < 1: 
    print 'not all words are present' 
    return 1 

print 'Shortest distance between \''+wordOne+'\' and \''+wordTwo+'\' is', distance, 'words' 
return distance 

Answer 1

дорогостоящая часть в v2 является if indexOne != 0 ... блок. Он называется столько раз, сколько осталось в тексте текста, как только будут найдены wordOne и wordTwo. Используя переменную переключения (я вижу, что у вас есть намерение использовать ее), можно переместить это, если блокировать как if word == wordOne, так и if word == wordTwo. В этом случае блок называется меньше n1 + n2 раз.

Вот код. Обратите внимание, что нам больше не нужно проверять индексы.

elif version == 3: 
    last_word_is_one = None 
    indexOne = 0 
    indexTwo = 0 
    countOne = 0 
    countTwo = 0 
    distance = len(text) 
    for word in text.split(): 

     if word == wordOne: 
      indexOne = index 
      countOne += 1 

      if last_word_is_one == False: 
       if distance > abs(indexOne-indexTwo): 
        distance = abs(indexOne - indexTwo) 

      last_word_is_one = True 

     if word == wordTwo: 
      indexTwo = index 
      countTwo += 1 

      if last_word_is_one == True: 
       if distance > abs(indexOne-indexTwo): 
        distance = abs(indexOne - indexTwo) 

      last_word_is_one = False 

     index += 1