如何在Python中不区分大小写且确定性地对文本字符串进行排序

Question

我有对文本字符串列表进行不区分大小写排序的标准要求。然而，此外这种排序需要是确定性的，因为两个包含相同元素的列表应该产生相同的排序列表。

为了解释这个问题，请考虑以下两个列表：

l1 = ['alfred', 'Berta', 'berta', 'carl']
l2 = ['alfred', 'berta', 'carl', 'Berta']

显然两个列表具有相同的元素：

>>> set(l1) == set(l2)
True

为了对这些列表进行排序，我第一次尝试使用了 内置函数

sorted

函数，并以

str.casefold

作为

key

参数。但这会导致两个不同结果列表：

>>> sorted(l1, key=str.casefold)
['alfred', 'Berta', 'berta', 'carl']
>>> sorted(l2, key=str.casefold)
['alfred', 'berta', 'Berta', 'carl']

但是我在这两种情况下都需要相同的输出

['alfred', 'Berta', 'berta', 'carl']

我怎样才能实现这个目标？

我的方法的问题是

key

函数“吃掉了要排序的元素的一些信息”。那么是否可以使用特定的

key

函数来实现

sorted

呢？此函数需要保留完整的大小写信息，但仍对等效小写字母旁边的大写字母进行排序......

---

额外问题：

如何使这种排序完全独立于区域设置，以便在具有不同国家/地区设置的计算机上从相同文件读取列表时，最终列表始终以完全相同的方式排序。

Answer 1

您可以先对它们进行区分大小写的排序，然后再次排序，忽略大小写

>>> sorted(sorted(l1), key=str.casefold)
['alfred', 'Berta', 'berta', 'carl']
>>> sorted(sorted(l2), key=str.casefold)
['alfred', 'Berta', 'berta', 'carl']

Answer 2

您可以使用一个 key 函数，该函数返回一个包含大小写折叠字符串的元组，然后返回原始字符串。这将导致首先比较大小写折叠的字符串，从而使排序不区分大小写。然后，如果大小写折叠的字符串相同，则将比较原始字符串，确保结果是确定性的。

def deterministic_casefold(s):
    return s.casefold(), s

sorted(l1, key=deterministic_casefold)
sorted(l2, key=deterministic_casefold)

Answer 3

我的看法：

def prepare_stable_sort(x):
    return (x.casefold(), id(x))

list(sorted(l1, key=prepare_stable_sort))
list(sorted(l2, key=prepare_stable_sort))

这使用普通的

casefold

，但还添加了哈希值，以区分

casefold

给出相同结果的情况。注意：这仅在相同处理器上稳定。为了消除哈希攻击，我认为现在哈希是部分随机的。

对于完整的解决方案，我将使用 Unicode 字符串比较（因此它适用于所有语言环境，但也是以一种合理的方式，尽管对于特定语言不是 100% 正确），并且我还会添加一个可重现的哈希函数。