sorted()命令在某些条件下不稳定.这是故意的吗？

Question

sorted() 文件(强调我的):

内置的sorted()函数保证稳定.如果保证不改变 比较相等的元素的相对顺序,则排序是稳定的[...]

在下面的代码中,键8和16具有相同的值,即它们将通过以下方式进行比较key=lambda x: d[x]:

d = {8: 0, 16: 0, 'a': 1}    

for i in range(200):    
    print(sorted(d, key=lambda x: d[x]))

# Prints always the same 
# [8, 16, 'a']
# [8, 16, 'a']
# [8, 16, 'a']
# ......

现在让我们尝试对字典进行一些小修改:

例1:

for i in range(10):

    if i == 5:

        del d[8]
        del d[16]

        d.update({16: 0})
        d.update({8: 0})

    print(sorted(d, key=lambda x: d[x]))

# Prints: 
# [8, 16, 'a']
# [8, 16, 'a']
# [8, 16, 'a']
# [8, 16, 'a']
# [8, 16, 'a'] 
# [16, 8, 'a']    <----- it changed the order
# [16, 8, 'a']
# [16, 8, 'a']
# [16, 8, 'a']
# [16, 8, 'a']

id(d)保持不变.内容保持不变.密钥插入的顺序有什么变化.

注意:
选择这些密钥以便它们导致哈希冲突:

是否占据一个位置或16个是由哪一个首先到达该方

---

例2:

d = {8: 0, 16: 0, 'a': 1}
c = {16: 0, 8: 0, 'a': 1}

print(sorted(d, key=lambda x: d[x]))
print(sorted(c, key=lambda x: d[x]))

我知道,d和c这里是不同的对象:

id(d)  # 140067442777736
id(c)  # 140067442811016

但我希望sorted()对待的对象d == c完全相同.

---

示例3: 不同的示例如下:

d = {'a': 0, 'b': 0, 'c': 0, 'd': 1}

print(sorted(d, key=lambda x: d[x]))

在多个不同的运行(运行此不带for环)将每次给不同的顺序.

注意:这是假设您使用Python 3.3或更高版本和您的PYTHONHASHSEED=random

---

问题:
订单不稳定:

• 对于修改其订单的同一对象(示例1).
• 对于2个比较相等的对象(例2).
• 对于完全相同代码的不同运行(例3).

上面提到的订单不稳定是一个错误还是我错过了什么？我是否因为期望所有3个示例都有稳定的订单而误解了文档？

编辑:这不是重复.副本中没有答案可以回答这种行为是否sorted()是故意的. 我知道为什么排序行为的方式(我甚至故意引起了这种行为).我不知道的是文档是否遗漏了什么,以及我在阅读时是否得出了错误的结论.

Answer 1

这不是一个错误,你错过了一些东西.你操纵字典改变了迭代的顺序,它是那个保持稳定的顺序sorted().换句话说,对sorted()保持输入顺序稳定,你通过改变字典改变了输入顺序.

请注意,sorted()这里没有"看到"字典.它传递了一系列键,就像你list()先在字典中使用一样.在这种情况下,既8与16散列到相同的哈希表槽.首先列出哪一个取决于插入的顺序:

>>> d1 = {}
>>> d1[8] = None
>>> d1[16] = None
>>> d1
{8: None, 16: None}
>>> list(d1)
[8, 16]
>>> d2 = {}
>>> d2[16] = None
>>> d2[8] = None
>>> d2
{16: None, 8: None}
>>> list(d2)
[16, 8]

调用list()两个词典表明键以不同的顺序列出.sorted()只是在字典上迭代时保持该顺序,因为它们都按值分类在同一位置.这正是文档告诉您会发生的事情.

请注意,字典相等根本没有任何作用.这不是文档的比较等同部分所指的.这仅是指元件在序列 ; 如果元素相等(或者在这种情况下,如果key(element)值相等),那么这些元素保持它们的相对顺序.

所以要关注你错过的可能的东西:

• 该方法的签名是sorted(iterable[, key][, reverse]); 关键词有iterable.文档的第一行:

  返回一个新的排序列表从项目的迭代.

  强调我的; 它是来自可迭代的项目,已排序.Python术语表定义iterable为:

  能够一次返回其成员的对象.iterables的实例包括所有类型的序列(如list,str,和tuple)和一些非序列类型,如dict,文件对象,你用定义任何类的对象__iter__()或__getitem__()方法.[...]当可迭代对象作为参数传递给内置函数时iter(),它返回对象的迭代器.这个迭代器适用于一组值的一次传递.

  任何采用迭代的东西基本上都会调用iter()它来循环生成的序列.

• 字典碰巧是可迭代的,迭代为你提供了密钥.请参阅映射类型文档:

  iter(d)
  在字典的键上返回一个迭代器.这是一个捷径iter(d.keys()).

  然后,dict.keys()文档指向字典视图部分,其中指出:

  iter(dictview)
  在字典中的键,值或项(表示为(键,值)的元组)上返回一个迭代器.

  键和值以任意顺序迭代,这是非随机的,在Python实现中各不相同,并且取决于字典的插入和删除历史.如果迭代键,值和项视图而没有对字典的干预修改,则项的顺序将直接对应.这允许使用zip():创建(值,键)对pairs = zip(d.values(), d.keys()).创建相同列表的另一种方法是pairs = [(v, k) for (k, v) in d.items()].

  再次,强调我的.所以sorted()迭代,把项目排序.字典,迭代时,产生键,其顺序是不是稳定.

• 最后,你引用的部分,从不与此相矛盾:

  内置sorted()功能保证稳定.如果排序保证不改变比较相等的元素的相对顺序,则排序是稳定的.

  因此迭代序列中的元素不会改变顺序.这没有说明字典在迭代时不能产生不同的顺序.

  换句话说,如果iterable_a == iterable_b在这里并不重要,它与可迭代相等无关,只有元素相等对排序顺序稳定性很重要.如果迭代顺序不同,则该顺序保持稳定.