位向量与布尔值性能列表

库尔特·鲍巴基(Kurt Bourbaki)

我试图在Python中重现我在书中找到的两个示例(最初是用Java编写的)。

这两个函数检查字符串是否包含重复的字符。第一个函数使用整数(checker)作为位向量,而第二个函数仅使用布尔值列表。我期望使用带位的功能会获得更好的性能,但实际上它的性能较差。

这是为什么?从Java转换为Python时,我写错了吗?

注意:为简单起见,我们仅使用小写字母(az),尤其是对于位向量函数。

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;
}
塔玛斯·赫格杜斯(Tamas Hegedus)

那是因为整数是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] 删除。

编辑于
0

我来说两句

0条评论
登录后参与评论

相关文章

来自分类Dev

将4位整数转换为布尔值列表

来自分类Dev

布尔值的按位运算

来自分类Dev

按位与如何与布尔值交互?

来自分类Dev

R-布尔值:for循环(向量中的向量)

来自分类Dev

基于布尔值的排序列表

来自分类Dev

在Python列表中处理布尔值

来自分类Dev

Python列表附加True布尔值

来自分类Dev

空列表和布尔值

来自分类Dev

按整数或布尔值过滤的数据库性能?

来自分类Dev

复合布尔值与不太可能/可能的性能

来自分类Dev

布尔值的大大小小的列表和字节数组的相对性能

来自分类Dev

基于成员布尔值的向量中的C ++排序对象

来自分类Dev

按位运算结果和布尔值

来自分类Dev

将位掩码转换回9个布尔值

来自分类Dev

C ++中带有布尔值的^(按位XOR)

来自分类Dev

将位掩码转换回9个布尔值

来自分类Dev

Java Stream迭代列表中的列表并计算布尔值

来自分类Dev

列表评估为布尔值但作为列表返回

来自分类Dev

列表中列表的长度并返回布尔值

来自分类Dev

如何检查布尔值列表中是否包含值?

来自分类Dev

SQL:无法创建函数返回表。“表在此位置无效,期望:位,布尔值,布尔值,...。”

来自分类Dev

位操作;将16位值转换为16个布尔值的数组?C语言

来自分类Dev

比较布尔值

来自分类Dev

更改布尔值?

来自分类Dev

IsFlush布尔值

来自分类Dev

重置布尔值?

来自分类Dev

useState与布尔值

来自分类Dev

布尔值是必需的

来自分类Dev

布尔值零