列表中元素的相对顺序。

I'm writing a function that takes in a list of integers and returns a list of relative positioned elements.

我正在编写一个函数，它接收一个整数列表，并返回一个相对位置元素的列表。

That is to say, if my input into said function is [1, 5, 4] the output would be [0, 2, 1], since 1 is the lowest element, 5 is the highest and 4 in the middle, all elements are unique values, or a set()

也就是说，如果我对这个函数的输入是[1,5,4]那么输出将是[0,2,1]，因为1是最低的元素，5是最高的，4在中间，所有的元素都是唯一的值，或者集合()

But code speaks, the function i have so far is

但是代码说，我到目前为止的功能是

def relative_order(a):
    rel=[]
    for i in a:
        loc = 0
        for v in a:
            if i > v:
                loc += 1
        rel.append(loc)
    return rel

It does work, but since i'm sending big lists into this function, and i have to compare each element to all elements in each iteration it's taking ~5sec with a list of 10.000 elements.

它确实起作用，但由于我将大列表发送到这个函数中，并且我必须将每个元素与每个迭代中的所有元素进行比较，它将使用一个包含10,000个元素的列表来进行~5sec。

My question is how can i improve the speed on said function and maybe be a bit more Pythonic, i tried comprehension lists, but my Python skills are lacking and i only came up with an imperative way of implementing this problem.

我的问题是如何提高上述函数的速度，也许更符合Python语言，我尝试了理解列表，但是我的Python技能是缺乏的，我只找到了实现这个问题的必要方法。

5 个解决方案

#1

This can be written as a list comprehension like this:

这可以写成这样的列表理解:

lst = [1, 5, 4]
s = sorted(lst)    
[s.index(x) for x in lst]
=> [0, 2, 1]

And here's another test, using @frb's example:

下面是另一个测试，使用@frb的例子:

lst = [10, 2, 3, 9]
s = sorted(lst)    
[s.index(x) for x in lst]
=> [3, 0, 1, 2]

#2

Here's another go that should be more efficient that keeping .index'ing into the list as it's stated that no duplicate values will occur, so we can do the lookup O(1) instead of linear... (and actually meets the requirements):

还有一种方法应该更有效地将.index保存到列表中，因为它声明不会出现重复的值，所以我们可以查找O(1)而不是线性的……(实际符合要求):

>>> a = [10, 2, 3, 9]
>>> indexed = {v: i for i, v in enumerate(sorted(a))}
>>> map(indexed.get, a)
[3, 0, 1, 2]

#3

The method you have a̶n̶d̶ ̶t̶h̶e̶ ̶c̶u̶r̶r̶e̶n̶t̶ ̶a̶n̶s̶w̶e̶r̶ takes order n^2 time.

方法有一个d n̶̶̶̶e t h̶̶̶̶̶̶c u r t n e r̶̶̶̶̶̶̶̶n s r w e̶̶̶̶需要n ^ 2时间。

This should work in log(n) time:

这应该在log(n)时间内工作:

def relative_order(a):
    positions = sorted(range(len(a)), key=lambda i: a[i])
    return sorted(range(len(a)), key = lambda i: positions[i])

It's still order log(n) and so should work for your large lists too.

它仍然是o (log(n)，所以对于大列表也是一样的。

Edit:

编辑:

Outside of lambda.

外的λ。

#4

def relative_order(a):
    l = sorted(a)
    # hash table of element -> index in ordered list
    d = dict(zip(l, range(len(l))))
    return [d[e] for e in a]

print relative_order([1, 5, 4])
print relative_order([2, 3, 1])
print relative_order([10, 2, 3, 9])

[0, 2, 1]
[1, 2, 0]
[3, 0, 1, 2]

the algorithm should be as efficient as sort, but use additional space.

算法应该和排序一样有效，但要使用额外的空间。

#5

-1

Your question is about sorting. I would recommend the use of Numpy or 'Numeric Python'. Numpy is a Python module that is optimised for "fast, compact, multidimensional array faciliities". It is the package of choice for scientific computing in Python. http://www.numpy.org/

你的问题是排序。我建议使用Numpy或'Numeric Python'。Numpy是一个Python模块，它被优化为“快速、紧凑、多维数组设施”。它是Python中科学计算的首选包。http://www.numpy.org/

import numpy as np

input_array = np.array([1, 5, 4])
sorted_indices = np.argsort(input_array)

print sorted_indices
#[0 2, 1]

I have also added profiler output based on an array of size 50000. It shows this method is (around 4x) faster than using the Python sorted function as per earlier answers.

我还添加了基于50000大小的数组的分析器输出。它显示这个方法(大约是4x)比按照前面的答案使用Python排序函数要快。

ncalls  tottime  percall  cumtime  percall filename:lineno(function)

    1    0.009    0.009    0.009    0.009 {method 'argsort' of 'numpy.ndarray' objects}
    1    0.034    0.034    0.034    0.034 {sorted}

Warning: Commentary suggested the answer is not inline with the authors function. This is true. I guess the whole point of argsort is that:

警告:评论认为答案与作者功能不一致。这是正确的。我想argsort的重点是:

sorted_array = input_array[sorted_indices]

gives you a sorted array.

给出一个排序数组。

The OP is, curious to my mind, asking for a result which requires a sorted array to be available via:

令我好奇的是，OP要求通过以下方式获得一个需要排序的数组的结果:

for i, val in enumerate(sorted_indices):
    sorted_array[val] = input_array[i]

#1