排序映射更有效的Python排序解决方案？

Question

我得到了一些数据，需要创建一个排序映射。实际的排序是由C代码完成的，它从我的代码中获取整数列表flt_neworder。这是我目前的解决方案：

# Demo data
data = [
    "Option A",  # 0
    "Option B",  # 1
    "Blabla",    # 2
    "Some text"  # 3
]

class Item:
    def __init__(self, label):
        self.label = label

col = [Item(d) for d in data]

# Create sorting mapping
flt_neworder = [
   x[1] for x in sorted(
       zip(
           [x[0] for x in sorted(enumerate(col), key=lambda x: x[1].label)],
           range(len(col))
       )
   )
]

# Output: [1,2,0,3]
print(flt_neworder)

• 所需输出：[1,2,0,3]，不[2,0,1,3]！

• Position inflt_neworder=项目在col中的原始索引

• 整数值=新位置

什么是更有效的，或者至少是可读性更好的解决方案？你知道吗

我成功地测试了这一行：

tuple({k: i for i, (k, v) in enumerate(sorted(enumerate(data), key=operator.itemgetter(1)))}.values())

但是它仍然很难阅读，我相信我正在利用一个事实，即在CPython实现中dict是被排序的。。。你知道吗

编辑

我想出了另一个解决办法：

flt_neworder = [None] * len(col)
for j, (_, i) in enumerate(sorted(zip((item.label for item in col), range(len(col))))): flt_neworder[i] = j

还有一个，但很慢：

flt_neworder = list(map(get(0), sorted(enumerate(sorted(enumerate(item.label for item in col), key=get(1))), key=get(1))))

感谢Ryan p提供了替代解决方案和测试时间的脚本！你知道吗

我在一个大数据集（1k个唯一字符串，full script）上测试了这些解决方案，与Ryan的小数据集相比，它们在计时上有着惊人的差异：

orig: 2.116799074272876
origmod: 2.118176033553482
orignew: 1.1691872433702883
orig3: 1.4400411206224817
orig4: 2.0643228139915664
rewrite: 26.06907118537356
rewriteop: 25.91357442379376
rewriteuniq: 10.783081019086694

赢家是orignew()，而rewriteuniq()对于小型数据集来说速度很快，但对于大型数据集来说却不是很好。你知道吗

Answer 1

这比原始代码更快，更易于阅读：

data = [
    'Option A',
    'Option B',
    'Blabla',
    'Some text'
]
idata = list(enumerate(data))  # add indexes to uniquely identify items
sdata = sorted(idata, key=lambda x: x[1])  # sort the items by label
flt_neworder = [sdata.index(x) for x in idata]  # find the position to move to

timeit结果：

orig: 12.3757910728
origmod: 7.85222291946
orignew: 6.15745902061
rewrite: 6.31552696228

（origmod类似于原始代码，但是没有Item类，因为它看起来不像您使用它；orignew是您的一行代码）

你的一行稍微快一点，但我觉得读起来更难。你知道吗

---

好的，这次我将包含完整的测试代码。我把Item的创建从orig移走了，因为创建这些只是为了模拟真实世界的数据。除了orig3（您的新代码）和rewriteop（rewrite与operator.itemgetter）之外，我还添加了一个额外的测试rewriteuniq，以避免字符串是唯一的。你知道吗

结果：

orig: 7.641715765
origmod: 7.38071417809
orignew: 5.82565498352
orig3: 5.67061495781
rewrite: 5.95284795761
rewriteop: 5.61896586418
rewriteuniq: 1.90719294548

代码：

import operator
from timeit import timeit

data = [
    'Option A',
    'Option B',
    'Blabla',
    'Some text',
]

desired_output = [1, 2, 0, 3]

class Item:
    def __init__(self, label):
        self.label = label

col = [Item(d) for d in data]


def orig():
    flt_neworder = [
        x[1] for x in sorted(
            zip(
                [x[0] for x in sorted(enumerate(col), key=lambda x: x[1].label)],
                range(len(col))
            )
        )
    ]

    assert flt_neworder == desired_output

def origmod():
    flt_neworder = [
        x[1] for x in sorted(
            zip(
                [x[0] for x in sorted(enumerate(data), key=lambda x: x[1])],
                range(len(data))
            )
        )
    ]

    assert flt_neworder == desired_output

def orignew():
    flt_neworder = list({k: i for i, (k, v) in enumerate(sorted(enumerate(data), key=operator.itemgetter(1)))}.values())
    assert flt_neworder == desired_output

def orig3():
    flt_neworder = [None] * len(col)
    for j, (_, i) in enumerate(sorted(zip((item.label for item in col), range(len(col))))): flt_neworder[i] = j

    assert flt_neworder == desired_output

def rewrite():
    idata = list(enumerate(data))
    sdata = sorted(idata, key=lambda x: x[1])
    flt_neworder = [sdata.index(x) for x in idata]

    assert flt_neworder == desired_output

def rewriteop():
    idata = list(enumerate(data))
    sdata = sorted(idata, key=operator.itemgetter(1))
    flt_neworder = [sdata.index(x) for x in idata]

    assert flt_neworder == desired_output

def rewriteuniq():
    sdata = sorted(data)
    flt_neworder = [sdata.index(x) for x in data]

    assert flt_neworder == desired_output

for fn in (orig, origmod, orignew, orig3, rewrite, rewriteop, rewriteuniq):
    print fn.__name__ + ':', timeit(fn)