列表中元素的相对顺序

Question

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

也就是说，如果我将 [1, 5, 4] 输入到该函数中，则输出将为 [0, 2, 1]，因为1是最小元素，5是最高元素，4在中间，所有元素都是唯一值，或者说是一个set()。

但是，代码才是王道，我目前拥有的函数是：

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

这个函数是可以工作的，但由于我将大量列表发送到该函数中，并且在每次迭代中必须将每个元素与所有元素进行比较，因此在包含10,000个元素的列表中需要约5秒钟。

我的问题是如何提高该函数的速度，或许更加符合Pythonic的方式，我尝试使用了推导式列表，但我的Python技能不足，只想出了一种命令式的实现方法。

- Ólafur Aron

Answer 1

这可以写成一个列表推导式，如下所示：

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

这里有另一个测试，使用@frb的例子：

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

- Óscar López

---

公平地说，使用这个方法速度从4.54秒提高到了0.52秒。 - Ólafur Aron

@HashCollision 不客气！有点棘手，但是这里给你。 - Óscar López

刚回来看到这个 - 我删除了我的答案，因为frb表明它是不正确的。我之前的评论表述得非常糟糕 - 我的意思是说我不喜欢这个答案的性能（但我非常喜欢答案本身 - 它的概念很清晰，这非常重要）。为了弥补一下，你得到了一个+1 :) 这个答案的运行时间是O(n^2)，对于大型列表来说相当糟糕。如果性能很重要，我可能会使用decorate-sort-undecorate构造，但我不确定在Python中它的性能如何。 - orlp

关于“踩”的问题，我已经决定坚持这个方法，并给JonClements的答案+1，因为他的方法避免了昂贵的索引操作，应该更加突出。 - akk

@akk，虽然我很感谢你的点赞，但我也想指出，即使它不是最有效的版本，给一个有效答案投负票有些违背SO的精神 - 如果你认为这个答案不值得点赞，你不需要点赞它，但我确实看不出将它投负票的理由。难道我需要指出你的答案实际上是错误的（在这个问题中有几个已删除答案也做出了类似的假设 - 包括我自己）- 然而没有人选择对你的回答进行负评... - Jon Clements

Answer 2

以下是更高效的解决方案，与其每次使用.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]

- Jon Clements

---

+1：比我的答案更高效。但我宁愿使用这个而不是“map”：[indexed[x] for x in a]。 - Óscar López

@ÓscarLópez 没错 - 我只是使用了map，因为使用内置函数应该比列表推导式快。 - Jon Clements

@JonClements 列表推导式比 map 函数更自由，Python peephole 优化器可以更好地优化它们 - 实际上，使用列表推导式胜过 map 函数的情况非常普遍。 - orlp

map(indexed.get, a) 耗时 87.7 微秒，[indexed[x] for x in a] 耗时 104 微秒，[s.index(x) for x in a] 耗时 9.2 毫秒... 这是基于一个包含1000个唯一整数（随机洗牌）的范围。 - Jon Clements

@JonClements 哈哈！大O又获胜了。 - orlp

Answer 3

你现在使用的方法需要 n^2 的时间复杂度。

以下方法应该能够在 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])

这仍然是O(log n)的顺序，因此也适用于您的大型列表。

编辑：

在lambda之外。

- Anon

---

这不是O(log(n))。 - user2357112

排序的时间复杂度为O(n log n)。 - Óscar López

这个答案失败到了极点。 - Anon

Answer 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]

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

- Dyno Fu

Answer 5

你的问题是关于排序的。我建议使用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]

我还基于一个大小为50000的数组添加了分析器输出。根据之前的答案，它显示这种方法比使用Python的sorted函数要快（大约4倍）。

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}

警告： 评论建议答案与作者的函数不符。这是正确的。我想argsort的整个重点在于：

sorted_array = input_array[sorted_indices] 

给你一个已排序的数组。

在我看来，OP正在询问一个需要通过已排序数组获得结果的问题：

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

- akk

---

这个答案是不正确的。np.argsort(np.array([10, 2, 3, 9])) 返回 array([1, 2, 3, 0])，但正确的答案应该是 array([3, 0, 1, 2])。 - Óscar López

你没有回答正确，看一下并运行其他答案。看：如果输入列表已排序，则10将位于索引3处，2将位于索引0处，3将位于索引1处，9将位于索引2处。这就是OP所问的，也是我的答案所做的。 - Óscar López

谢谢，我已经修改了我的答案。 - akk

糟糕，我实际上正在寻找在numpy中执行此操作的方法。 - oulenz