实时两次连续使用项目之间的不同项目数

Question

我正在解决一个问题，该问题会实时找到距离- 连续两次使用某个项目之间的不同项目的数量。输入是从一个大文件 (~10G) 中读取的，但为了说明，我将使用一个小列表。

from collections import OrderedDict
unique_dist = OrderedDict()
input = [1, 4, 4, 2, 4, 1, 5, 2, 6, 2]

for item in input:
    if item in unique_dist:
        indx = unique_dist.keys().index(item) # find the index
        unique_dist.pop(item)                 # pop the item
        size = len(unique_dist)               # find the size of the dictionary
        unique_dist[item] = size - indx       # update the distance value
    else:
        unique_dist[item] = -1                # -1 if it is new
print input
print unique_dist

正如我们所见，对于每个项目，我首先检查该项目是否已存在于字典中，如果是，我更新距离值，否则我将其插入到末尾，值为 -1 .问题是随着尺寸变大，这似乎非常低效。内存不是问题，但 pop 功能似乎是。我这么说是因为，如果我这样做的话：

for item in input:
        unique_dist[item] = random.randint(1,99999)

程序运行得非常快。我的问题是，有什么方法可以使我的程序更高效（更快）？

编辑：

看来真正的罪魁祸首是indx = unique_dist.keys().index(item)。当我用 indx = 1 替换它时。该程序快了几个数量级。

Answer 1

这个怎么样：

from collections import OrderedDict
unique_dist = OrderedDict()
input = [1, 4, 4, 2, 4, 1, 5, 2, 6, 2]

for item in input:
    if item in unique_dist:
        indx = unique_dist.keys().index(item)
        #unique_dist.pop(item)                # dont't pop the item
        size = len(unique_dist)               # now the directory is one element to big
        unique_dist[item] = size - indx - 1   # therefor decrement the value here
    else:
        unique_dist[item] = -1                # -1 if it is new
print input
print unique_dist

[1, 4, 4, 2, 4, 1, 5, 2, 6, 2]
OrderedDict([(1, 2), (4, 1), (2, 2), (5, -1), (6, -1)])

请注意 unique_dist 中的条目现在按输入中首次出现的条目排序；你的是在最后一次出现时订购的：

[1, 4, 4, 2, 4, 1, 5, 2, 6, 2]
OrderedDict([(4, 1), (1, 2), (5, -1), (6, -1), (2, 1)])

Answer 2

根据我对 cProfile 模块所做的简单分析，到目前为止最昂贵的操作是 OrderedDict.__iter__() 和 OrderedDict.keys()。

下面的实现大约是你的 7 倍（根据我所做的有限测试）。

它通过维护项目列表 keys 来避免调用 unique_dist.keys()。我不完全确定，但我认为这也避免了对 OrderedDict.__iter__().
它通过在必要时递增 size 变量来避免调用 len(unique_dist)。（我不确定 len(OrderedDict) 的操作有多昂贵，但无论如何）

def distance(input):
    dist= []
    key_set= set()
    keys= []
    size= 0
    for item in input:
        if item in key_set:
            index= keys.index(item)
            del keys[index]
            del dist[index]
            keys.append(item)
            dist.append(size-index-1)
        else:
            key_set.add(item)
            keys.append(item)
            dist.append(-1)
            size+= 1
    return OrderedDict(zip(keys, dist))

Answer 3

我修改了@Rawing 的答案以克服由 set 数据结构所花费的查找和插入时间引起的开销。

from random import randint
dist = {}
input = []
for x in xrange(1,10):
    input.append(randint(1,5))
keys = []
size = 0
for item in input:
    if item in dist:
        index = keys.index(item)
        del keys[index]
        keys.append(item)
        dist[item] = size-index-1
    else:
        keys.append(item)
        dist[item] = -1
        size += 1
print input
print dist

实时两次连续使用项目之间的不同项目数

Number of distinct items between two consecutive uses of an item in realtime

python

algorithm

performance