兩個單詞之間的最小距離（python）

Question

這裏有兩個我能想到的版本。當兩個單詞都是共同的（比如說「is」和「the」，版本1的n1 * n2縮放會成爲一個問題），並且對惡意輸入（比如只有兩個單詞的文件）更健壯時，V2更爲可取。但是對於更有趣的查詢（比如「大」和「動物」），v1的速度一樣快，我可以考慮更實際的語義問題，因爲v2根本不起作用，但是v1會起作用。有沒有辦法加快速度？

進口timeit T1 = timeit.default_timer（）

DEF距離（版本，文件名，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