根据多个值和权重快速排名项的方法

Question

我有一组键值对，像这样：

{ 
   'key1': [value1_1, value2_1, value3_1, ...], 
   'key2': [value1_2, value2_2, value3_2, ...],
   ...
 }

还有一个列表，这个列表的顺序和上面值的顺序是一样的，里面包含了每个变量应该有的权重。也就是说，它看起来像这样：[weight_1, weight_2, weight_3, ...]。

我的目标是根据每个值的总分，得到一个有序的键列表。需要注意的是，这些值并不是都经过标准化的，比如value1_x的范围可能是1到10，而value2_x的范围可能是1到100000。这对我来说是个难点，因为我需要以某种方式对数据进行标准化。

我想让这个算法能够处理很多不同的值，这样无论是处理1个值还是100个值，所需的时间都差不多（或者至少是以对数的方式增加）。这可能吗？有没有什么高效的方法可以做到这一点？

Answer 1

这里有一个归一化的函数，它会把你的数值线性转换到 [0,1] 的范围内。

def normalize(val, ilow, ihigh, olow, ohigh):
    return ((val-ilow) * (ohigh-olow) / (ihigh - ilow)) + olow

现在，使用 normalize 来计算一个新的字典，这个字典里的值都是经过归一化处理的。接着，根据加权总和进行排序：

def sort(d, weights, ranges):
    # ranges is a list of tuples containing the lower and upper bounds of the corresponding value

    newD = {k:[normalize(v,ilow, ihigh, 0, 1) for v,(ilow, ihigh) in zip(vals, ranges)] for k,val in d.iteritems()}  # d.items() in python3
    return sorted(newD, key=lambda k: sum(v*w for v,w in zip(newD[k], weights)))

Answer 2

你不能做到线性时间的复杂度，但你可以做得更快；我觉得这看起来像是矩阵乘法，所以我建议你使用 numpy：

import numpy as np

keys = ['key1', 'key2', 'key3']

values = np.matrix([
    [1.1, 1.2, 1.3, 1.4],
    [2.1, 2.2, 2.3, 2.4],
    [3.1, 3.2, 3.3, 3.4]
])

weights = np.matrix([[10., 20., 30., 40.]]).transpose()

res = (values * weights).transpose().tolist()[0]

items = zip(res, keys)
items.sort(reverse=True)

这样就能得到

[(330.0, 'key3'), (230.0, 'key2'), (130.0, 'key1')]

编辑： 感谢 @Ondro 提供的 np.dot 和 @unutbu 提供的 np.argsort，这里有一个完全使用 numpy 的改进版本：

import numpy as np

# set up values
keys = np.array(['key1', 'key2', 'key3'])
values = np.array([
    [1.1, 1.2, 1.3, 1.4],    # values1_x
    [2.1, 2.2, 2.3, 2.4],    # values2_x
    [3.1, 3.2, 3.3, 3.4]     # values3_x
])
weights = np.array([10., 20., 30., 40.])

# crunch the numbers
res = np.dot(values, -weights)   # negative of weights!

order = res.argsort(axis=0)  # sorting on negative value gives
                             # same order as reverse-sort; there does
                             # not seem to be any way to reverse-sort
                             # directly
sortedkeys = keys[order].tolist()

最终结果是 ['key3', 'key2', 'key1']。