如何提高这个列表函数的速度？

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

我不确定这样做是否比使用集合更快，但它只需要遍历列表一次：

def countWordDistances(li):
    wordmap = {}
    for i in range(len(li)):
        if li[i] in wordmap:
            avg, num = wordmap[li[i]]
            new_avg = avg*(num/(num+1.0)) + (1.0/(num+1.0))*i
            wordmap[li[i]] = new_avg, num+1
        else:
            wordmap[li[i]] = (i, 1)

    return wordmap

这段代码返回了一个修改过的wordmap，里面每个键对应的值是一个元组，包含了平均位置和出现次数。你当然可以很容易地把它转换成原始输出的形式，不过这会花费一些时间。

这段代码基本上是在遍历列表的同时保持一个运行的平均值，每次都通过加权平均来重新计算。

Answer 2

这个内容是基于 @Ned Batchelder 的解决方案，但没有创建虚假的列表：

import collections
def countWordDistances(li):
    wordmap = collections.defaultdict(lambda:[0.0, 0.0])
    for i, w in enumerate(li, 1):
        wordmap[w][0] += i
        wordmap[w][1] += 1.0
    for k, (t, n) in wordmap.iteritems():
        wordmap[k] = t / n
    return wordmap

Answer 3

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万条记录的单词列表上测试过，里面有29000个独特的单词，结果这个方法几乎比Patrick的答案快了一倍。在一个有10000个单词、2000个独特单词的列表上，这个方法比原作者的代码快了300多倍。

要让Python代码运行得更快，有两个原则要记住：使用最好的算法，尽量避免使用Python。

在算法方面，遍历列表一次而不是N+1次（N是独特单词的数量）是加速的关键。

在“避免Python”方面，我的意思是：你希望你的代码尽可能在C语言中执行。所以使用defaultdict比使用普通的字典要好，因为后者需要你手动检查键是否存在。defaultdict会为你做这个检查，而且是在C语言中完成的，速度更快。使用enumerate比用for i in range(len(li))要好，因为这样可以减少Python的操作步骤。而且enumerate(li, 1)可以让计数从1开始，而不需要在循环中再加1。

补充：第三条原则是：使用PyPy。我的代码在PyPy上运行的速度是2.7版本的两倍。