按嵌套元组的值对列表进行排序

Question

有没有更好的方法来按嵌套元组值对列表进行排序，而不是编写一个itemgetter替代方案来提取嵌套元组值：

def deep_get(*idx):
  def g(t):
      for i in idx: t = t[i]
      return t
  return g

>>> l = [((2,1), 1),((1,3), 1),((3,6), 1),((4,5), 2)]
>>> sorted(l, key=deep_get(0,0))
[((1, 3), 1), ((2, 1), 1), ((3, 6), 1), ((4, 5), 2)]
>>> sorted(l, key=deep_get(0,1))
[((2, 1), 1), ((1, 3), 1), ((4, 5), 2), ((3, 6), 1)]

我考虑使用compose，但它不在标准库中:

sorted(l, key=compose(itemgetter(1), itemgetter(0))

有没有我在库中遗漏的内容可以使这段代码更好？

该实现应该能够合理地处理100k个项目。

背景：我想对一个直方图字典进行排序。键是元组(a,b)，值是计数。最终，项目应按计数、a和b降序排序。另一种方法是展平元组并直接使用itemgetter，但这样会生成很多元组。

- Thomas Jung

---

据我所知，没有任何一个。在我看来，你的方法很不错。 - Jeff Mercado

“实现应该在处理10万个项目时表现合理。”--这行文字是不必要的；所有使用sort的实现都可以在处理10万个项目时表现合理。 - ninjagecko

@ninjagecko 如果你要对3个项目、100k个项目或1T个项目进行排序，实现方式会有所不同。 - Thomas Jung

Answer 1

是的，你可以只使用 key=lambda x: x[0][1]

- ninjagecko

---

我认为itemgetter比lambda更快，因为它是用C编写的。你为什么认为lambda更快呢？ - utdemir

@utdmr，所有的东西都经过C处理，但你仍然转向Python; 只有在大多数计算在C中完成并且通过避免开销来获得C的某种重大优势时，才能期望加速。此外，“compose”是使用“lambda”（实际上与函数相同）实现的，因此您不会节省任何东西。您可以自行测试此功能。您会发现“compose”方法运行速度慢50％。不过，“deep_get”我预计将以大致相同的时间运行（实际上确实如此）。您始终可以使用“dis.dis”查看编译代码的内容。 - ninjagecko

“compose()是用lambda实现的”这个说法有些奇怪。你怎么知道呢？我的compose()版本可能是用C扩展编写的……” - Sven Marnach

@Sven 我看到你在扮演恶魔的代言人=)如果你要用C实现一切，那么你也可以一切都用C来写，而且假设你还是用Python编写程序，你仍然需要“overhead”与C中的Python调用约定进行接口交互。你可以实现自己的compose作为一个C模块，看看它是否更快;事实上，我很好奇它是否会产生任何影响。尽管如此，我认为人们在错误的地方优化得太多了，设计决策占据更多的因素，并且程序员的时间比微小的优化更有价值。 - ninjagecko

@Sven 是的，这就是为什么我提前说了“(实际上与函数相同)”来预防这个讨论 =)，因为types.FunctionType==types.LambdaType，而且def f(x):return x; dis.dis(f)和dis.dis(lambda x:x)产生相同的操作码（如果你用*args,**kw调用它们也是一样的）。 - ninjagecko

Answer 2

你的方法非常好，考虑到了你所拥有的数据结构。

另一种方法是使用另一种数据结构。

如果你想要速度，事实上标准的NumPy是最好的选择。它的作用是高效地处理大型数组。它甚至有一些很好的排序例程，适用于像你这样的数组。以下是如何对计数进行排序，然后再对（a，b）进行排序：

>>> arr = numpy.array([((2,1), 1),((1,3), 1),((3,6), 1),((4,5), 2)],
                  dtype=[('pos', [('a', int), ('b', int)]), ('count', int)])
>>> print numpy.sort(arr, order=['count', 'pos'])
[((1, 3), 1) ((2, 1), 1) ((3, 6), 1) ((4, 5), 2)]

这是非常快的（它是用C实现的）。

如果您想坚持使用标准Python，一个包含（计数，a，b）元组的列表将会被Python自动按照您需要的方式排序（它在元组上使用字典序）。

- Eric O. Lebigot

Answer 3

我比较了两个类似的解决方案。第一个使用了简单的lambda表达式：

def sort_one(d):
    result = d.items()
    result.sort(key=lambda x: (-x[1], x[0]))
    return result

注意在 x[1] 上的减号，因为你想要按计数降序排序。

第二个例子利用了 Python 中的 sort 是稳定的这一事实。首先，我们按 (a, b)（升序）排序。然后，我们按计数降序排序：

def sort_two(d):
    result = d.items()
    result.sort()
    result.sort(key=itemgetter(1), reverse=True)
    return result

第一个方法在小型和大型数据集上都比较快，速度可以提高10-20％。对于100k个项目，在我的Q6600上（只使用一个核心），两种方法的运行时间都不到0.5秒。因此，避免创建元组似乎并没有太大帮助。

- Dzinx

Answer 4

这可能是您方法的更快版本：

l = [((2,1), 1), ((1,3), 1), ((3,6), 1), ((4,5), 2)]

def deep_get(*idx):
    def g(t):
        return reduce(lambda t, i: t[i], idx, t)
    return g

>>> sorted(l, key=deep_get(0,1))
[((2, 1), 1), ((1, 3), 1), ((4, 5), 2), ((3, 6), 1)]

这个可以缩短为：

def deep_get(*idx):
    return lambda t: reduce(lambda t, i: t[i], idx, t)

或者甚至只是简单地写出来：

sorted(l, key=lambda t: reduce(lambda t, i: t[i], (0,1), t))

- martineau