如何将下面的元组转化为字典，元组中第一个元素作为键，第二个作为值？

来源：蜘蛛抓取(WebSpider) 时间：2022-05-14 14:48 标签： 元组可以作为字典的键

比如现有一个dict如下：

所以如何在不改变元素类型的情况下转？

写高性能程序最重要的就是了解查询数据的方式，选择一个能够迅速响应这个查询的数据结构。

当数据有一个内在次序时，使用列表和元组作为数据结构可以让速度更快、开销更低。数据的内在次序可以回避在这些数据结构内部查询的问题：如果次序已知，那么查询操作是O(1)，避免了昂贵的O(n)的线性搜索。

列表是动态的数组，列表可变并且可以重设长度。列表可以改变大小和内容，这种可变性的代价在于它们需要额外的内存以及使用它们需要额外的计算。

这是因为动态数组支持resize操作，可以增加数组的容量。当一个大小为N的列表第一次需要添加数据时，Python会创建一个新的列表，足够存放原来的N个元素以及额外需要添加的元素。为了给未来的添加预留空间,实际分配会分配N+M个元素(M>N)，然后旧列表的数据被复制到新列表中，旧列表则被销毁。

超额分配发生在第一次往列表里添加元素时。在一个列表被直接创建时，如前例，分配的元素数量是完全按需的。

一个列表在多次添加时的变化例子

另外，即使创建的列表没有使用append（也就是并没有append 操作导致的额外空间），它占用的内存依然大于保存同样数据的元组。因为列表需要记住更多关于它们自身状态的信息（一个额外元素）来进行高效的resize。

元组是静态的数组，其内部数据一旦创建便无法改变，缓存于Python运行时的环境，所以每次使用元组时无需访问内核分配内存。元组适合保存不会改变的对象，这种不可改变性使起成为一个非常轻量级的数据结构。

虽然元组不能改变大小，但可以通过两个元组合并得到一个新元组：

它的复杂度为O(n)而不是O(1)，这是因为对元组每添加一个新的元素都会有分配和复制操作，而不是像列表那样仅在额外的空间耗尽时发生的。

Python是一门垃圾收集语言，这意味着当一个变量不再被使用时，Python会将该变量使用的内存释放回操作系统，以供其他程序（或变量）使用。但对于长度为1～20的元组，即使不再被使用，其空间也不会立刻被还给系统，而是留待未来使用。所以当未来需要一个同样大小的新元组时，我们不再需要向操作系统申请一块内存来存放数据，因为已经有了预留的内存。

因此元组可以被轻松迅速地创建，因为元组不必向操作系统申请空间。初始化列表和元组的时间对比：

对于无序数据，集合和字典就是理想的数据结构。索引对象被称为“键”，而数据被称为“值”。字典和集合几乎一模一样，只是集合实际上并不包含值：一个集合只不过是一堆键的组合。字典和集合基于键的查询和查询都为O(1)。

字典和集合会占用更多的内存。此外，实际查询和插入速度极大取决于使用的散列函数。如果散列函数对某个数据类型不具有O(1)的计算时间，那么包含该数据类型的字典和集合都不具有O(1)保证。所以散列表极其重要。

对于散列表，我们必须首先弄清楚数据在这个连续内存块中的位置才能插入。新插入数据的位置取决于数据的两个属性：键的散列值以及该值如何跟其他对象比较。这是因为当插入数据时，首先需要计算键的散列值并掩码来得到一个有效的数组索引。掩码是为了保证一个可能是任意数字的散列值最终能落入分配的指针中。

为了找到新的索引，我们用一个简单的线性函数计算出一个新的索引，这一方法称为嗅探。Python的嗅探机制使用了原始散列值的高位比特（还记得对于之前那个长度为8的散列表，由于使用的掩码mask=0b111=bin(8-1)，我们只用了最后3个bit作为初始索引）。使用这些高位比特使得每一个散列值生成的下一可用散列序列都是不同的，这样就能帮助防止未来的碰撞。

但时，线性嗅探仅使用了散列值的最后几个字节而没有考虑其余字节（比如，对于一个8元素字典，我们只查看了最后3个比特，因为当前的掩码是0x111）。这意味着如果两个键的散列值最后3个比特相等，那么不仅产生了一个碰撞，同时其后的嗅探索引序列也都是一样的。

在查询某个键时也有一个类似的过程：给出的键会被转化为一个索引进行检索。如果和该索引指向的位置中的键符合（在插入操作时我们会保存原始的键），那么我们就会返回那个值。如果不符合，我们用同一个方案继续创建新的索引，直至我们找到数据或找到一个空内存。如果找到一个空内存，可以认为表里不存在该数据。

对于下列的散列函数与字典：

return ord(self[0])#ord函数将输入的第一个字符转成一个整型（散列函数必须返回整型）。

当一个值从散列表中被删除时，不能简单地写一个NULL到内存的那个指针中。这是因为我们已经用NULL作为嗅探散列碰撞的终止值。所以必须写一个特殊的值表示该指针虽空，但其后可能还有别的因散列碰撞而插入的值。这些空的指针可以在未来被写入或在散列表改变大小时被删除。

当越来越多的项目被插入散列表时，表本身必须改变大小来适应。一个不超过三分之二满的表在具有最佳空间节约的同时依然具有不错的散列碰撞避免率。因此当一个表到达关键点时，它就会增长。为了做到这一点，需要分配一个更大的表（也就是在内存中预留更多的指针），将掩码调整为适合新的表，旧表中的所有元素被重新插入新表。这需要重新计算索引，因为改变后的掩码会改变索引计算结果。所以改大散列表的代价非常昂贵。

字典或集合默认的最小长度是8（即使只保存3个值，Python仍然会分配8个元素）。每次改变大小时，指针的个数增加到原来的4倍，直至达到50000个元素，之后每次增加到原来的2倍。如果散列表中足够多的元素被删除，表可能会被改小。但是，改变大小仅发生在插入时。

一个用户自定义的散列函数需要让散列值均匀分布以避免散列碰撞。碰撞太频繁会降低散列表的性能：如果大多数键都有碰撞，那么我们需要经常“嗅探”其他索引值，有可能需要在字典中访问很大一片区域来寻找需要的键。最坏情况下，字典中所有的键都碰撞，字典查询的性能变成O(n)，就跟搜索一个列表一样。

如果我们在创建散列函数时知道我们要在字典中存储5000 个值，我们必须注意整个字典将被存储在一个大小为32768 的散列表中，所以我们的散列值只有最后15个比特参与了索引的创建（对于这个大小的散列表，掩码是bin(32768-1) =0b111）。

衡量“我的散列函数分布均匀程度”的标准被称为散列函数的熵。熵的定义是：

p(i)是散列函数给出散列值为i的概率，当所有的散列值都具有同样的被选中概率时熵最大。一个令熵最大的散列函数被称为完美散列函数，因为它保证了最低的碰撞次数。

对于无穷大字典，整数的散列函数就是完美散列函数。对于有限大字典，不存在一个最佳的散列函数。

为了找到大小为N 的字典的掩码，我们首先找到能令该字典保持三分之二满的最低桶数（N * 5 / 3），然后找到能满足这个数字的最小字典大小（8; 32; 128; 512; 2048; 等等）并找到足以保存这一数字的bit 的位数。比
如，如果N=1039，那么我们至少需要1731 个桶，这意味着我们的字典有2048 个桶。那么掩码就是bin(2048 - 1) = 0b。

比如要在字典中存储676个双小写字母组合（aa，ab，…）则下面就是一个好的散列函数：

当掩码为0b时（一个具有676个元素的字典将被保存在一个长度为2048的散列表中，其掩码是bin(b），这个散列函数对于任意两个双小写字母都不会发生散列碰撞。

这里也展示一个好坏散列函数的区别，坏的散列函数使得查询变慢了21.8倍：

每当Python 访问一个变量、函数或模块时，都有一个体系来决定它去哪里查找这些对象。首先，Python 查找locals()数组，其内保存了所有本地变量的条目。如果它不在本地变量里，那么会搜索globals()字典。如果对象也不在那里，则搜索__builtin__对象。locals()和globals()是显式的字典而__builtin__则是模块对象，在搜索__builtin__中的一个属性时，其实是在搜索它的locals()字典。

第一个函数test1显示查询math库来调用sin。生成的字节码的证据表明：首先一个math模块的引用必须被调入，然后在模块上进行属性查询,直到找到sin函数。整个步骤经过了两次字典查询：一次查找math模块，一次在模块中查找sin函数。

另一方面，test2从math模块显式导入了sin函数，因此该函数可在全局命名空间中被直接访问。这意味着可以避免查询math模块以及后续的属性查询。不过，我们还是要在全局命名空间查找sin函数。这也是另一个要从模块中显式导入函数的原因。这样做不仅让代码更可读，因为我们可以知道到底需要外部资源中的什么函数，而且也加速了代码！

最后，test3定义了sin函数为一个参数关键字，其默认值是math模块的sin函数的引用。虽然我们依然需要在模块中查找这一函数，但仅在test3函数第一次被定义时查找。之后，这一引用以默认参数关键字的形式作为一个本地变量被保存在函数的定义中。之前提到过，本地变量无须字典查询；它们被保存在一个十分微小的数组中，具有很快的查询速度。因此，找到这个函数非常快。

在调用函数时我们依然会进行一次全局查询，但在循环内对函数的每次调用都会变快。下面的例子可以看到，只需要在循环前讲sin函数本地化就能获得速度提升：

我要回帖

更多关于 元组可以作为字典的键 的文章

 

随机推荐