5

所以在 Python 2 中你可以使用类似的东西

>>> items = [[1, 2], [3], [3], 4, 'a', 'b', 'a']
>>> from itertools import groupby
>>> [k for k, g in groupby(sorted(items))]
[4, [1, 2], [3], 'a', 'b']

效果很好，O(N log N)及时。然而 Python 3 惊呼TypeError: unorderable types: int() < list(). 那么在 Python 3 中最好的方法是什么？（我知道最好是一个主观术语，但根据 Python 确实应该有一种方法）

编辑：它不必使用排序，但我猜这将是最好的方法

4

2 回答 2

6

在 2.x 中，两种无法比较的内置类型的值按类型排序。类型的顺序没有定义，除非它在解释器的一次运行期间是一致的。所以，2 < [2]可能是真或假，但它始终是真或假。

在 3.x 中，不可比较的内置类型的值是不可比较的——这意味着TypeError如果您尝试比较它们，它们会引发 a。所以，2 < [2]是一个错误。而且，至少从 3.3 开始，这些类型本身甚至没有可比性。但是，如果您只想重现 2.x 的行为，那么它们id的 s 绝对是可比的，并且在解释器运行期间是一致的。所以：

sorted(items, key=lambda x: (id(type(x)), x))

对于您的用例，这就是您所需要的。

但是，这不会与 2.x 完全相同，因为这意味着，例如，1.5 < 2可能是False（因为float> int）。如果您想复制确切的行为，您需要编写一个键函数，首先尝试比较值，然后TypeError回退到比较类型。

cmp这是旧式函数比新式函数更容易阅读的少数情况之一key，所以让我们编写其中一个，然后使用cmp_to_key它：

def cmp2x(a, b):
    try:
        if a==b: return 0
        elif a<b: return -1
        elif b<a: return 1
    except TypeError:
        pass
    return cmp2x(id(type(a)), id(type(b)))
sorted(items, key=functools.cmp_to_key(cmp2x))

这仍然不能保证 2.x 给出的不同类型的两个值之间的顺序相同，但是由于 2.x 没有定义任何这样的顺序（只是它在一次运行中是一致的），所以它不可能。

但是，仍然存在一个真正的缺陷：如果您定义的类的对象不是完全排序的，那么它们最终将排序为相等，我不确定这是否与 2.x 在这种情况下会做的事情相同。

于 2013-04-15T11:51:01.357 回答
2

让我们退后一步。

你想使一个集合唯一化。

如果这些值是可散列的，您将使用 O(N)set解决方案。但他们不是。如果你能想出某种散列函数，你可以等效地使用 a dictof myhash(value): value。如果您的用例确实是“只有可散列值和可散列值的平面lists”，您可以通过trying to 来做到这一点hash，然后回退到hash(tuple()). 但总的来说，这是行不通的。

如果它们是完全排序的，您将使用 O(N log N)sorted解决方案（或等效的基于树的解决方案或类似的解决方案）。如果你能想出某种全排序函数，你可以将 a 传递key给sorted函数。我认为这将适用于您的用例（因此我的其他答案）。但是，如果不是，则没有 O(N log N) 解决方案将起作用。

如果两者都不是，您可以回退到 O(N**2) 线性搜索解决方案：

unique = []
for value in items:
    if value not in unique:
        unique.append(value)

如果您找不到某种方法来为您的值定义全排序或散列函数，那么这是您能做的最好的事情。

于 2013-04-15T12:05:18.513 回答