Python 设置会员测试
Python set memebership test
在一门算法课程中，我们的老师介绍了“虚拟初始化”，您可以在其中为操作分配内存，但不要初始化所有值，因为问题 space 与实际值相比可能太大了需要计算（例如字典或集合），这会浪费大量时间来设置默认值。基本原理是让两个数组相互指向（相互索引）并跟踪分配了多少变量。假设我们有一个数组 a 并且我们想要查找 a[i] 是否包含有效值，我们可以使用数组 b 作为 a 的索引，如下所示：
我查看了 https://wiki.python.org/moin/TimeComplexity 的 python 时间复杂度 table，它提到在最坏情况下的集合成员测试可以是 O(n)。我不确定在哪里可以找到 set 函数的确切实现，但经过一些谷歌搜索后，大多数人提到它使用哈希 table。我的主要问题是：
如何使用散列 table 来检查值是否有效？我们可以散列每个值并读取结果，但这并不意味着输出不是垃圾（我们可以读取调用 malloc 时写入该地址的任何内容）。
虚拟初始化完全避免了散列中的冲突问题table，为什么它不是比使用散列更好的解决方案table？
当您使用数组实现散列 table 时，您需要在每个条目中使用一个标志来指示它当前是否正在使用。这是处理散列函数冲突所必需的——如果两个值具有相同的散列码，则不能将它们都放在数组的同一元素中。
这意味着当你分配数组时，你必须遍历它，初始化所有这些标志。每当你增加哈希 table.
时，你都必须再次执行此操作
“虚拟初始化”避免了这种情况。您粘贴的算法用于判断 a[k] 是否正在使用。它使用第二个数组 b，其中包含 a 的索引。插入元素时，a[k].p包含b中的索引j，b[j]包含k。如果这两个匹配，并且 j 低于所有索引的限制，则知道数组元素正在使用中。
要清除条目，只需设置 a[k].p = 0，因为所有有效条目在 1 和 n 之间都有 p。
这是算法设计中 time-space 权衡的一个例子。为了避免花在初始化数组上的时间，我们分配了第二个数组。如果您有大量可用内存，这可能是一个 acceptable 权衡。
在一门算法课程中，我们的老师介绍了“虚拟初始化”，您可以在其中为操作分配内存，但不要初始化所有值，因为问题 space 与实际值相比可能太大了需要计算（例如字典或集合），这会浪费大量时间来设置默认值。基本原理是让两个数组相互指向（相互索引）并跟踪分配了多少变量。假设我们有一个数组 a 并且我们想要查找 a[i] 是否包含有效值，我们可以使用数组 b 作为 a 的索引，如下所示：
我查看了 https://wiki.python.org/moin/TimeComplexity 的 python 时间复杂度 table，它提到在最坏情况下的集合成员测试可以是 O(n)。我不确定在哪里可以找到 set 函数的确切实现，但经过一些谷歌搜索后，大多数人提到它使用哈希 table。我的主要问题是：
如何使用散列 table 来检查值是否有效？我们可以散列每个值并读取结果，但这并不意味着输出不是垃圾（我们可以读取调用 malloc 时写入该地址的任何内容）。
虚拟初始化完全避免了散列中的冲突问题table，为什么它不是比使用散列更好的解决方案table？
当您使用数组实现散列 table 时，您需要在每个条目中使用一个标志来指示它当前是否正在使用。这是处理散列函数冲突所必需的——如果两个值具有相同的散列码，则不能将它们都放在数组的同一元素中。
这意味着当你分配数组时，你必须遍历它，初始化所有这些标志。每当你增加哈希 table.
时，你都必须再次执行此操作“虚拟初始化”避免了这种情况。您粘贴的算法用于判断 a[k] 是否正在使用。它使用第二个数组 b，其中包含 a 的索引。插入元素时，a[k].p包含b中的索引j，b[j]包含k。如果这两个匹配，并且 j 低于所有索引的限制，则知道数组元素正在使用中。
要清除条目，只需设置 a[k].p = 0，因为所有有效条目在 1 和 n 之间都有 p。
这是算法设计中 time-space 权衡的一个例子。为了避免花在初始化数组上的时间，我们分配了第二个数组。如果您有大量可用内存，这可能是一个 acceptable 权衡。