Python的位移运算速度真的很慢吗？

Question

我一定是忽略了某些东西，但真的看不出为什么Python代码会这么慢......

在一个元素范围为[−1,000,000..1,000,000]的数组中计算唯一元素，并使用位向量来完成。使用BitSet的Java代码大约比Python快50倍，Python需要9秒钟。

这可能是因为当我初始化 bitvector = 0 时，Python没有预留足够的内存，随着位向量的增长，它需要被复制吗？

Python:

def solution(array):
    bitvector = 0
    count = 0
    for element in array:
        # transform -1,000,000 to 0 etc
        element_transformed = element + 1000000
        if bitvector >> element_transformed & 1 == 0:
            count += 1
            bitvector = bitvector | 1 << element_transformed

    return count

测试：

import unittest
import random

from .file1 import solution

class MySolutionTests(unittest.TestCase):
    def test_solution_random_all_unique(self):
        a = random.sample(range(-1000000, 1000001), 100000)
        self.assertEqual(100000, solution(a))

在Java中：

package mypackage;

import java.util.ArrayList;
import java.util.BitSet;
import java.util.List;


public class MyClass {

    public static int solution(List<Integer> array) {
        BitSet bitvector = new BitSet();
        int count = 0;

        for(int i = 0; i < array.size(); i++) {
            int elementTransformed = array.get(i) + 1000000;
            if(bitvector.get(elementTransformed) != true) {
                count++;
                bitvector.set(elementTransformed, true);
            }
        }
        return count;
    }

    public static void main(String[] args) {
        // TODO code application logic here
    }
}

测试：

package mypackage;

import java.util.ArrayList;
import java.util.Collections;
import org.junit.Test;
import static org.junit.Assert.*;

public class MyClassTest {

    public MyClassTest() {
    }

    @Test
    public void testSolutionLong_RandomAllUnique() {
        ArrayList array = new ArrayList();
        for(int i = -1000000; i < 1000000; i++) {
            array.add(i);
        }
        Collections.shuffle(array);
        assertEquals(100000, MyClass.solution(array.subList(0, 100000)));

    }  
}

- M3RS

---

你的 bitvector 可以有多大？它不仅仅是一个简单的位向量，而是一个完整的任意精度整数，因此它不像简单的向量那样高效。而且 CPython 的算术运算速度并不快，特别是当数字大于机器整数时。如果你真的需要速度，那么还有其他各种选项，例如使用某种字节数组。 - PM 2Ring

是的，它可以达到两百万位。好吧，也许我这样编码有点愚蠢 :) - M3RS

你为什么在Python测试中使用random.sample？为什么不用shuffle？ - Daniel Roseman

@Daniel Roseman 谢谢，我会看一下的。 - M3RS

没问题。顺便说一下，扩展你的测试以查看数据存在重复项时会发生什么是个好主意。 - PM 2Ring

Answer 1

我尝试直接回答你提出的问题。为什么Python需要9秒，而Java快50倍，这不是一个简单的问题。在这里，您可以深入了解之前的讨论 Is Python slower than Java/C#?

我喜欢看待的方式是，Java是一种面向对象的语言，而Python是基于对象的。当观察位运算时，Java使用原始数据类型，这些类型由于没有装箱拆箱操作和包装器作为抽象层而被认为更快。因此，在每次迭代中查看您的代码时，Python会将整数重新包装为整数类型的对象，而Java则不会。

但是，再次强调，我不会认为Java总是比Python更快。这取决于您使用的库以及您尝试解决的问题！

- Mazzespazze

Answer 2

这个问题的Pythonic方式是：

def solution(array):
    return len(set(array))

它的速度更快，但可能会使用更多内存。

对于来自2*10**6范围内的10**6个样本，set解决方案运行时间约为100毫秒。我甚至没有计时位数组，因为它需要几秒钟。

当涉及到数量级为10**6的列表时，这是一种值得权衡的方法。使用sys.getsizeof，我测量了中间set使用4.2倍于list的内存。相当的int位数组比list的内存小约1/30。这是在64位Linux系统上。

- jpkotta