0

考虑到每个集合的长度完全相同并且每个集合中的每个项目的长度相同，循环遍历set数字 Python 或字母 Python 是否更快？set为什么？

我认为会有所不同，因为字母 [a-zA-Z] 比数字 [0-9] 具有更多可能的字符，因此会更加“随机”并且可能在一定程度上影响散列。

numbers = set([00000,00001,00002,00003,00004,00005, ... 99999])

letters = set(['aaaaa','aaaab','aaaac','aaaad', ... 'aaabZZ']) # this is just an example, it does not actually end here

for item in numbers:
  do_something()

for item in letters:
  do_something()

其中 len（数字）== len（字母）

更新：我对 Python 的特定散列算法以及此实现在幕后发生的事情感兴趣。

4

2 回答 2

6

Python 可能有一些特定的实现细节，我不知道我在这里的一般论点很混乱，但是：

  • 创建字符串集可能会比创建整数集慢一点（其他条件相同），因为对字符串的散列操作需要一些（小）时间来运行，而对整数的散列操作是微不足道的。
  • 迭代一个集合不执行任何散列操作，因此散列的时间在那里无关紧要。
  • 迭代一个集合取决于集合中元素的数量以及支持该集合的哈希表中的桶数。所以散列函数的分布只有在它导致散列表增加桶数时才有意义。对于一些不可能的哈希表实现（因为桶计数仅在负载因子超过阈值时增加，而不仅仅是因为冲突）。当有很多冲突时，其他哈希表实现会调整大小。我不知道哪个 CPython 是。
  • 无论如何，您给出的一组整数的特定示例将生成分布良好的哈希值。
  • 有一种方法可以找出在 Python 中哪个更快，即timeit使用您关心的数据的实际示例。猜测通常是浪费时间。

你可以看到 Python 的散列算法的结果，如下所示：

>>> foo = 3
>>> foo.__hash__()
3
>>> foo = 1856348
>>> foo.__hash__()
1856348
>>> foo = "\x00"
>>> foo.__hash__()
1
>>> foo = "\x01"
>>> foo.__hash__()
128000384
>>> foo = "\x02"
>>> foo.__hash__()
256000771

所以在我的 Python 副本上，这些哈希结果与这些报告的 Python 哈希算法相匹配。与 CPython 一样，您可以查看源代码以确认算法。

于 2012-09-10T08:23:22.040 回答
2

你不能知道，直到你配置文件！这是一些粗略的数据：

% python -mtimeit -s 'import string;import random;s=set("".join(random.sample(string.printable, 5))for _ in range(10000))' 'for foo in s: bar=foo'
1000 loops, best of 3: 376 usec per loop

% python -mtimeit -s 'import random;s=set(int("".join(map(str,random.sample(range(10),5))))for _ in range(10000))' 'for foo in s: bar=foo'                     
1000 loops, best of 3: 322 usec per loop

看起来你是对的，有细微的差别，但你需要做更多的测试才能自信地说出很多。

于 2012-09-10T08:19:40.563 回答