Python 近似分组依据

Question

我想根据值对字典的键进行分组。但是，这些值仅近似相等。在这种情况下进行 groupby 的最佳方法是什么。我有:

buckets = defaultdict(list)
for k, v in my_dict.iteritems():
    closest = next((rep for rep in buckets if abs(rep - v) < 1e-3), None)
    if closest:
        buckets[closest].append(k)
    else:
        buckets[v].append(k)

任何 itertools 魔术或其他可以简化这个/使它更像 pythonic 的东西，或者这是我能做的最好的？

Answer 1

您的算法是 O(n**2) 因为它在 O(n) 循环内执行 O(n) 操作:

for k, v in my_dict.iteritems():
    closest = next((rep for rep in buckets if abs(rep - v) < 1e-3), None)

您可以通过按值对 my_dict.items() 进行排序，然后遍历排序后的项目，使其成为 O(n log n)。请注意，如果 buckets 是 OrderedDict，而不是 for rep in buckets ，您只需查看最后一个存储桶，因为 OrderedDict 的键将按排序顺序排列。所以如果下一个值接近任何桶，它必须接近最后一个桶。因此，通过使用 OrderedDict，您无需遍历所有存储桶。与上一个比较一下:

import random
random.seed(123)
N = 10
my_dict = dict(zip(range(N), [random.randint(0, 10)/10.0 for k in range(N)]))
print(my_dict)    
# {0: 0.0, 1: 0.0, 2: 0.4, 3: 0.1, 4: 0.9, 5: 0.0, 6: 0.5, 7: 0.3, 8: 0.9, 9: 0.1}

import operator
import collections
items = sorted(my_dict.items(), key=operator.itemgetter(1))
buckets = collections.OrderedDict([(items[0][1], [items[0][0]])])
for k, v in items[1:]:
    last_val = next(reversed(buckets))
    closest = last_val if abs(last_val - v) < 1e-3 else v
    buckets.setdefault(closest, []).append(k) 

print(buckets)

打印

OrderedDict([(0.0, [0, 1, 5]), (0.1, [3, 9]), (0.3, [7]), (0.4, [2]), (0.5, [6]), (0.9, [4, 8])])