9

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

也就是说，如果我对所述函数的输入是[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

它确实有效，但是由于我将大列表发送到此函数中，并且我必须将每个元素与每次迭代中的所有元素进行比较，因此需要约 5 秒的时间来处理包含 10.000 个元素的列表。

我的问题是如何提高所述功能的速度，并且可能更加 Pythonic，我尝试了理解列表，但我的 Python 技能缺乏，我只想出了实现这个问题的命令式方法。

4

5 回答 5

12

这可以写成这样的列表推导：

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]
于 2013-07-20T23:23:46.150 回答
11

这是另一个应该更有效.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]
于 2013-07-21T00:04:06.380 回答
1

你有 a̶n̶d̶̶t̶h̶e̶̶c̶u̶r̶r̶e̶n̶t̶̶a̶n̶s̶w̶e̶r̶ 的方法需要 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])

它仍然是 order log(n)，因此也适用于您的大型列表。

编辑：

在 lambda 之外。

于 2013-07-20T23:55:22.533 回答
1 
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]

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

于 2013-07-21T00:18:57.407 回答
-1

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

我还添加了基于 size 数组的分析器输出50000。它表明这种方法比使用 Pythonsorted函数快（大约 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]
于 2013-07-21T04:06:52.557 回答