Jupyter[duplicate]中Python iter()函数行为的差异

顺序不是任意的,而是取决于字典或集合的插入和删除历史,以及特定的Python实现。对于这个答案的其余部分,对于“dictionary”,您还可以读取“set”;set被实现为只有键而没有值的字典。

下一个 基于已经存在的东西的插槽。

目前

'foo' 和 'bar' ,例如,假设表大小为8个插槽。在Python2.7中, hash('foo') -4177197833195190597 , hash('bar') 是 327024216814240868 . 模8,这意味着这两个键在插槽3和4中开槽,然后:

>>> hash('foo')
-4177197833195190597
>>> hash('foo') % 8
3
>>> hash('bar')
327024216814240868
>>> hash('bar') % 8
4

这将通知他们的上市顺序:

>>> {'bar': None, 'foo': None}
{'foo': None, 'bar': None}

除了3和4以外的所有插槽都是空的,在表上循环首先列出插槽3,然后列出插槽4,所以 '福' 在之前列出 .

bar 和 baz 4 :

>>> hash('bar')
327024216814240868
>>> hash('baz')
327024216814240876
>>> hash('bar') % 8
4
>>> hash('baz') % 8
4

现在,它们的顺序取决于第一个槽中的键;第二个槽中的键必须移动到下一个槽中:

>>> {'baz': None, 'bar': None}
{'bar': None, 'baz': None}
>>> {'bar': None, 'baz': None}
{'baz': None, 'bar': None}

CPython(最常用的Python实现)使用的底层结构的技术名称是 hash table ,一种使用开放寻址的方法。如果你很好奇,并且对C有足够的了解,可以看看 C implementation Pycon 2010 presentation by Brandon Rhodes 关于CPython dict Beautiful Code ,其中包括由Andrew Kuchling编写的关于实现的一章。

也

其他实现可以自由地为字典使用不同的结构,只要它们满足文档化的Python接口,但是我相信到目前为止所有实现都使用散列表的变体。

CPython 3.6引入了 新的 保持插入顺序的实现,启动速度更快,内存效率更高。新的实现没有在每一行引用存储的散列值以及键和值对象的地方保留一个大型稀疏表,而是添加一个较小的散列 阵列 它只引用稠密表中的索引(一个只包含与实际键值对一样多的行的索引),而正是稠密表按顺序列出了包含的项。见 proposal to Python-Dev for more details 实施细节 ,Python语言没有指定其他实现必须保持顺序。这在Python3.7中发生了变化,这里的细节是 elevated to be a language specification ;使任何实现与Python3.7或更新版本正确兼容 必须 复制此保序行为。

OrderedDict class ,的一个子类 迪克特 post by Raymond Hettinger outlining the idea . 请注意 set 类型仍然无序。

如果您想要一个有序的集合,可以安装 oset package ;适用于Python2.5及更高版本。

Python 3.41 A set 在它作为副本关闭之前。

也就是说,有 你可以依赖的东西:

list(myset) == list(myset)

也就是说,顺序是 稳定的

理解为什么 秩序需要理解以下几点:

• Python使用的 ,

• CPython的散列集如何存储在内存中,以及

从顶部:

Hash集 是一种存储随机数据的方法,查找时间非常快。

它有一个后备阵列:

# A C array; items may be NULL,
# a pointer to an object, or a
# special dummy object
_ _ 4 _ _ 2 _ _ 6

我们将忽略特殊的虚拟对象,它只用于使移除更容易处理,因为我们不会从这些集合中移除。

为了快速查找,您可以使用一些魔术从对象中计算散列。唯一的规则是两个相等的对象具有相同的哈希值。(但如果两个对象具有相同的哈希值,则它们可能不相等。)

hash(4) % len(storage) = index 2

这使得访问元素变得非常快。

散列只是故事的大部分,因为 hash(n) % len(storage) 和 hash(m) % len(storage) 在槽的左边 在找其他地方之前,最多可以找9个地方。

• 哈希集可以是 . 如果有20个元素,并且备份数组的长度为30个元素,则备份存储的大小将调整为更大。这是因为你经常与小的后备商店发生冲突,而冲突会减慢一切。

所以当你创建一个数组时,后备存储器的长度是8。当它是5个满的并且您添加了一个元素时,它将简短地包含6个元素。 6 > ²⁄₃·8 因此,这会触发一个大小调整,而后备存储器的大小是32的四倍。

hash(n) 只是回来 n -1 这很特别)。

v_set = {88,11,1,33,21,3,7,55,37,8}

len(v_set) 是10,所以后备存储器至少是15(+1) 添加所有项目后

__ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __

我们有

hash(88) % 32 = 24
hash(11) % 32 = 11
hash(1)  % 32 = 1
hash(33) % 32 = 1
hash(21) % 32 = 21
hash(3)  % 32 = 3
hash(7)  % 32 = 7
hash(55) % 32 = 23
hash(37) % 32 = 5
hash(8)  % 32 = 8

__  1 __  3 __ 37 __  7  8 __ __ 11 __ __ __ __ __ __ __ __ __ 21 __ 55 88 __ __ __ __ __ __ __
   33 ← Can't also be where 1 is;
        either 1 or 33 has to move

所以我们希望

{[1 or 33], 3, 37, 7, 8, 11, 21, 55, 88}

有一个或33个不是在别的地方开始的。这将使用线性探测,因此我们将:

       ↓
__  1 33  3 __ 37 __  7  8 __ __ 11 __ __ __ __ __ __ __ __ __ 21 __ 55 88 __ __ __ __ __ __ __

       ↓
__ 33  1  3 __ 37 __  7  8 __ __ 11 __ __ __ __ __ __ __ __ __ 21 __ 55 88 __ __ __ __ __ __ __

你可能会认为33是因为1已经存在而被替换的,但是由于在创建集合时发生的大小调整,事实并非如此。每次重新生成集合时,已添加的项都会有效地重新排序。

现在你知道为什么了

{7,5,11,1,4,13,55,12,2,3,6,20,9,10}

__ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __

前13个插槽中有1到13个哈希值。20进20号槽。

__  1  2  3  4  5  6  7  8  9 10 11 12 13 __ __ __ __ __ __ 20 __ __ __ __ __ __ __ __ __ __ __

55进槽 hash(55) % 32 即23:

__  1  2  3  4  5  6  7  8  9 10 11 12 13 __ __ __ __ __ __ 20 __ __ 55 __ __ __ __ __ __ __ __

如果我们选择50,我们会期待

__  1  2  3  4  5  6  7  8  9 10 11 12 13 __ __ __ __ 50 __ 20 __ __ __ __ __ __ __ __ __ __ __

你瞧:

{1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 12, 13, 20, 50}
#>>> {1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 12, 13, 50, 20}

pop 只是通过事物的外观来实现:它遍历列表并弹出第一个列表。

这是所有实现细节。

“武断”和“不确定”不是一回事。

他们所说的是字典迭代顺序没有“在公共接口中”的有用属性。几乎可以肯定的是,迭代顺序的许多属性完全由当前实现字典迭代的代码决定,但是作者并没有向您承诺它们是可以使用的。这使他们可以更自由地在Python版本之间(甚至只是在不同的操作条件下,或者在运行时完全随机地)更改这些属性,而不必担心程序会崩溃。

因此,如果您编写的程序依赖于 任何财产 对于dictionary-order,那么您就“违反了”使用dictionary类型的约定,而Python开发人员并没有承诺这将始终有效,即使在您测试dictionary类型时它现在似乎可以工作。这基本上相当于在C语言中依赖“未定义的行为”。

这个问题的其他答案都很好,写得很好。操作询问“如何”,我将其解释为“他们如何逃脱”或“为什么”。

Python文档说 dictionaries abstract data type associative array . 正如他们所说

返回绑定的顺序可能是任意的

换句话说,计算机科学的学生不能假设一个关联数组是有序的。同样的道理也适用于 math

集合元素的排列顺序无关紧要

computer science

集合是一种抽象的数据类型,它可以存储某些值,而不需要任何特定的顺序

使用哈希表实现字典是 implementation detail 有趣的是,就顺序而言,它与关联数组具有相同的属性。

Python使用 hash table 用于存储字典,因此字典或其他使用哈希表的iterable对象中没有顺序。

但是对于hash对象中项的索引,python根据以下代码计算索引 within hashtable.c :

key_hash = ht->hash_func(key);
index = key_hash & (ht->num_buckets - 1);

因此,由于整数的散列值是整数本身 索引是以数字为基础的( ht->num_buckets - 1 是一个常数),所以 按位和 之间 (ht->num_buckets - 1) 数字本身 (对于散列为-2的-1和具有散列值的其他对象除外)。

考虑下面的例子 set

>>> set([0,1919,2000,3,45,33,333,5])
set([0, 33, 3, 5, 45, 333, 2000, 1919])

对于数字 33 我们有:

33 & (ht->num_buckets - 1) = 1

'0b100001' & '0b111'= '0b1' # 1 the index of 33

注意 在这种情况下 (ht->数量桶-1) 8-1=7 或 0b111 .

1919 :

'0b11101111111' & '0b111' = '0b111' # 7 the index of 1919

为了 333

'0b101001101' & '0b111' = '0b101' # 5 the index of 333

有关python散列函数的更多详细信息,可以从 python source code :

函数,在模拟随机性的意义上。Python没有:最多 案例:

>>> map(hash, (0, 1, 2, 3))
  [0, 1, 2, 3]
>>> map(hash, ("namea", "nameb", "namec", "named"))
  [-1658398457, -1658398460, -1658398459, -1658398462]

这不一定是坏事!相反,在2号**i的表格中 对于由一个连续的整数范围索引的dict,根本没有冲突。 在一般情况下比随机行为好,这是非常可取的。

哈希表使得良好的冲突解决策略至关重要。只服用 名单 [i << 16 for i in range(20000)] 作为一组钥匙。 全部的 映射到同一表索引。

但处理不寻常的案子不应该拖慢通常的案子,所以我们就 最后一个我咬了。剩下的要看碰撞解决方案了。如果 我们 通常 在第一次尝试时找到我们要找的钥匙 通常情况下,表的负载系数保持在2/3以下,所以 对我们有利),那么保持初始指数

_{*类的哈希函数 int :}

class int:
    def __hash__(self):
        value = self
        if value == -1:
            value = -2
        return value

从Python 3.7开始 already in CPython 3.6 stay in the order they were inserted .