最快排名具有多个值和权重的物品的方式 [英] Fastest way to rank items with multiple values and weightings

问题描述

我有键值对的集合是这样的：

I have a collection of key value pairs like this:

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

和还列表这是在相同的顺序值列表，其中包含各变量应施加的重量。因此，它看起来像 [weight_1，weight_2，weight_3，...] 。

and also a list which is in the same order as the values list, which contains the weight each variable should have applied. So it looks like [weight_1, weight_2, weight_3, ...].

我的目标是结束与键的有序列表按照到具有价值的最高分。请注意，这些值是不是所有的标准化/归一化，所以value1_x范围可以从1 - 10，但价值2_x范围可以从1 - 100000。这一直是棘手的部分对我来说，我必须以某种方式将数据标准化

My goal is to end up with an ordered list of keys in accordance to which has the highest overall score of values. Note that the values aren't all standardized / normalized, so value1_x could range from 1 - 10 but value 2_x could range from 1 - 100000. This has been the tricky part for me as I have to normalize the data somehow.

我试图使这个算法的运行规模为许多不同的值，所以它会采取相同的时间量为1或100（或者至少是对数更多的时间）。那可能吗？有没有真正有效的方法，我可以去吗？

I'm trying to make this algorithm run to scale for many different values, so it would take the same amount of time for 1 or for 100 (or at least logarithmically more time). Is that possible? Is there any really efficient way I can go about this?

推荐答案

您不能得到线性时间，但你可以做得更快;这看起来像一个矩阵乘法给我，所以我建议你使用 numpy的：

You can't get linear-time, but you can do it faster; this looks like a matrix-multiply to me, so I suggest you use 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')]

编辑：与<一个href="http://stackoverflow.com/questions/22122856/numpy-how-to-sort-an-array-of-value-key-pairs-in-descending-order#22124985">thanks以@Ondro 的np.dot和<一href="http://stackoverflow.com/questions/22122856/numpy-how-to-sort-an-array-of-value-key-pairs-in-descending-order#22122985">to @unutbu为np.argsort ，这里是一个改进版本完全numpy的：

with thanks to @Ondro for np.dot and to @unutbu for np.argsort, here is an improved version entirely in 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'，'密钥2，KEY1'] 。

这篇关于最快排名具有多个值和权重的物品的方式的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！