两个单词之间的最小距离（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