位向量与布尔值列表性能
Bit vector vs list of boolean values performance
我试图在 Python 中重现我在一本书中找到的两个示例(最初写在 Java 中)。
这两个函数检查字符串是否包含重复字符。第一个函数使用整数 (checker
) 作为位向量,而第二个函数仅使用布尔值列表。
我期望使用带有位的函数会有更好的性能,但实际上它的性能更差。
这是为什么? "translating" 从 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 个整数也是如此)查看以下行:
checker |= (1 << val)
如果我们展开分配,我们得到:
checker = checker | (1 << val)
这一行在内存中分配了两个新的整数。一种用于 1 << val
,另一种用于按位或。
另一方面,分配数组元素不需要分配对象,这就是它更快的原因。
如果您正在寻找确定字符串是否具有重复字符的最快方法,此函数比前两个
(取自"check duplicates in list"):
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
,结果可能会有很大差异
我试图在 Python 中重现我在一本书中找到的两个示例(最初写在 Java 中)。
这两个函数检查字符串是否包含重复字符。第一个函数使用整数 (checker
) 作为位向量,而第二个函数仅使用布尔值列表。
我期望使用带有位的函数会有更好的性能,但实际上它的性能更差。
这是为什么? "translating" 从 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 个整数也是如此)查看以下行:
checker |= (1 << val)
如果我们展开分配,我们得到:
checker = checker | (1 << val)
这一行在内存中分配了两个新的整数。一种用于 1 << val
,另一种用于按位或。
另一方面,分配数组元素不需要分配对象,这就是它更快的原因。
如果您正在寻找确定字符串是否具有重复字符的最快方法,此函数比前两个 (取自"check duplicates in list"):
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
,结果可能会有很大差异