我试图在Python中重现我在书中找到的两个示例(最初是用Java编写的)。
这两个函数检查字符串是否包含重复的字符。第一个函数使用整数(checker
)作为位向量,而第二个函数仅使用布尔值列表。我期望使用带位的功能会获得更好的性能,但实际上它的性能较差。
这是为什么?从Java转换为Python时,我写错了吗?
注意:为简单起见,我们仅使用小写字母(a到z),尤其是对于位向量函数。
import sys
import timeit
def is_unique_chars_bit(my_str):
checker = 0
for char in my_str:
val = ord(char) - ord('a')
if ((checker & (1 << val)) > 0):
return False
checker |= (1 << val)
return True
def is_unique_chars_list(my_str):
if len(my_str) > 128:
# Supposing we use ASCII, which only has 128 chars
return False
char_list = [False] * 128
for char in my_str:
val = ord(char)
if char_list[val]:
return False
char_list[val] = True
return True
if __name__ == '__main__':
alphabet = "abcdefghijklmnopqrstuvwxyz"
t_bit = timeit.Timer("is_unique_chars_bit('"+ alphabet +"')", "from __main__ import is_unique_chars_bit")
t_list = timeit.Timer("is_unique_chars_list('"+ alphabet +"')", "from __main__ import is_unique_chars_list")
print(t_bit.repeat(3, 200000))
print(t_list.repeat(3, 200000))
结果:
[1.732477278999795, 1.7263494359995093, 1.7404333820004467]
[0.6785205180003686, 0.6759967380003218, 0.675434408000001]
原始的Java函数如下:
boolean isUniqueCharsBoolArray(String str) {
if (str.length() > 128) return false;
boolean[] char_set = new boolean[128];
for (int i = 0; i < str.length(); i++) {
int val = str.charAt(i);
if (char_set[val]) {
return false;
}
char_set[val] = true;
}
return true;
}
boolean isUniqueCharsBits(String str) {
for (int i = 0; i < str.length(); i++) {
int val = str.charAt(i) -'a';
if ((checker & (1 << val)) > 0) {
return false;
}
checker |= (1 << val);
}
return true;
}
那是因为整数是python中不可变的引用类。这意味着整数运算通常很慢。(即使对于python2 ints也是如此)请看以下行:
checker |= (1 << val)
如果扩展任务,我们将得到:
checker = checker | (1 << val)
这一行在内存中分配了两个新的整数。一为1 << val
和一为按位或。
另一方面,分配数组元素不需要分配对象,这就是它更快的原因。
如果您正在寻找确定字符串是否具有重复字符的最快方法,则此函数比前两个函数短且快(取自“检查列表中的重复项”):
def is_unique_chars_set(my_str):
return len(my_str) != len(set(my_str))
Timeit显示3倍加速(最后一行是新速度):
>python3 test.py
[2.398782472571393, 2.3595238689519626, 2.37358552995787]
[1.0055455609592512, 1.007462347465074, 1.012826469701654]
[0.32564058749026437, 0.3303359144351621, 0.31772896318809885]
注意:如果您使用另一个python运行时,例如IronPython,结果可能会有很大差异
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句