python - 如何使此列表功能更快？

Question

def removeDuplicatesFromList(seq): 
    # Not order preserving 
    keys = {}
    for e in seq:
        keys[e] = 1
    return keys.keys()

def countWordDistances(li):
    '''
    If li = ['that','sank','into','the','ocean']    
    This function would return: { that:1, sank:2, into:3, the:4, ocean:5 }
    However, if there is a duplicate term, take the average of their positions
    '''
    wordmap = {}
    unique_words = removeDuplicatesFromList(li)
    for w in unique_words:
        distances = [i+1 for i,x in enumerate(li) if x == w]
        wordmap[w] = float(sum(distances)) / float(len(distances)) #take average
    return wordmap

如何使此功能更快？

Answer 1

import collections
def countWordDistances(li):
    wordmap = collections.defaultdict(list)
    for i, w in enumerate(li, 1):
        wordmap[w].append(i)
    for k, v in wordmap.iteritems():
        wordmap[k] = sum(v)/float(len(v))

    return wordmap

这使得只通过列表一次，并将操作保持在最低限度。我在一个有 110 万个条目、29k 个不同单词的单词列表上计时，它的速度几乎是帕特里克回答的两倍。在 10k 单词的列表中，2k 唯一，它比 OP 的代码快 300 倍以上。

为了让 Python 代码运行得更快，有两条规则要牢记:使用最好的算法，避免使用 Python。

在算法方面，将列表迭代一次而不是 N+1 次(N= 唯一单词的数量)是加快速度的主要因素。

在“避免使用 Python”方面，我的意思是:您希望您的代码尽可能多地在 C 中执行。因此，使用 defaultdict 比明确检查 key 是否存在的字典要好。 defaultdict 会为您进行检查，但是是在 C 中，在 Python 实现中进行的。 enumerate 优于 for i in range(len(li))，同样是因为它的 Python 步骤更少。 enumerate(li, 1) 使计数从 1 开始，而不必在循环中的某处使用 Python +1。

已编辑:第三条规则:使用 PyPy。我的代码在 PyPy 上的运行速度是在 2.7 上的两倍。