这个Java算法如何更快

Question

我有一个循环，它将布尔 LinkedList 按 8 位分割并返回缓冲区中每个字节的 ASCII 值。该函数返回字符串缓冲区。

如果 LinkedList 的大小很大，那么这段代码会非常慢。我尝试用简单的循环来更改迭代器，但它仍然很慢。

这个算法怎么能真正快呢？也许使用多线程？

注意： linkedList 的大小并不总是能被 8 整除。

public String toString(){

        String buffer = "";
        String output = "";

        LinkedList<Boolean> bits = this.bits;

        for(Iterator it = this.bits.iterator(); it.hasNext();){
            if(buffer.length() >= 8){
                output += (char)Integer.parseInt(buffer, 2);
                buffer = "";
            }

            buffer += ((Boolean)it.next() == false) ? "0" : "1";
        }

        if(buffer != "")
            output += (char)Integer.parseInt(buffer, 2);

        return output;
}

Answer 1

这些建议将为您提供足够的性能，同时保持代码简单和可读。首先使用这些更改进行测试，如果不满足您的性能要求，则慢慢引入其他答案中建议的优化技术

1. 使用 BitSet 而不是 LinkedList
2. 使用 StringBuilder输出;而不是字符串输出;
3. 使用StringBuilder缓冲区;而不是字符串缓冲区;
4. 使用Integer.valueOf() 而不是Integer.parseInt。我认为 valueOf 对低于 128 的值使用缓存。

Answer 2

1. 使用使用预期输出容量初始化的StringBuilder：

   StringBuilder out = new StringBuilder(bits.size() / 8 + 1);
   

2. 使用按位运算而不是parseInt()，如下所示：

   int i = 0;          
   整数c=0；
   for(布尔值 b: 位){
       if (i > 0 && i % 8 == 0){
           out.append((char) c);
           c = 0;
       }
       c = (c << 1) | (b?1:0)；
       我++；
   }
   out.append((char) c); // 不确定这里想要的行为
   

Answer 3

字符串连接速度很慢，尤其是对于大型列表（因为字符串是不可变的，因此必须复制它们，这需要一些时间，并且每个副本也需要更多空间）。使用 StringBuilder 而不是 String 进行追加。换句话说：buffer和output应该是StringBuilder实例。

Answer 4

正如其他人建议的那样 - 使用 BitSet。对于其余的，我认为下面的方法非常有效：

    public String toString() {
        char[] bytes = new char[bits.size() / 8 + ((bits.size() % 8 > 0) ? 1 : 0)];
        int bitCounter = 0;
        int word = 0;
        int byteCounter = 0;
        for (boolean b : bits) {
            word = (word << 1) | (b ? 1 : 0);
            if (bitCounter == 7) {
                bytes[byteCounter] = (char) word;
                ++byteCounter;
                bitCounter = 0;
                word = 0;
            } else {
                ++bitCounter;
            } // else
        } // foreach
        bytes[byteCounter] = (char) word;
        return new String(bytes);
    } // toString() method

这可能是一个不使用字节计数器的更好的替代方案：

        public String toString() {
            int size = bits.size() / 8 + ((bits.size() % 8 > 0) ? 1 : 0);
            if (size == 0) {
                return "";
            } // if
            char[] bytes = new char[size];
            int bitCounter = 0;
            int word = 0;
            for (boolean b : bits) {
                if (bitCounter % 8 == 0
                        && bitCounter > 0) {
                    bytes[(bitCounter - 1) / 8] = (char) word;
                    word = 0;
                } // if
                word = (word << 1) | (b ? 1 : 0);
                ++bitCounter;
            } // foreach
            bytes[size - 1] = (char) word;
            return new String(bytes);
        } // toString() method

Answer 5

尝试将缓冲区保持为 int。我的意思

 buffer = buffer << 1 + (((Boolean)it.next() == false) ? 0 : 1);

是代替

 buffer += ((Boolean)it.next() == false) ? "0" : "1";

Also use StringBuilder 进行输出。这是一个很小的变化，但总是一点点。

Answer 6

请尝试以下操作：

 StringBuilder b = new StringBuilder();
 int ch = 0;
 int n = 0;

 for (Boolean bit : bits) {
   ch <<= 1;
   if (bit) {
     ch++;
   }
   if (++n == 8) {
     b.append((char)ch);
     n = 0;
     ch = 0;
   }
 }

 if (n > 0) {
   b.append((char)ch);
 }  

 System.out.println(b.toString());

Answer 7

使用 StringBuffer 或 stringBuilder 而不是 String 作为缓冲区和输出变量。

字符串变量是不可变的，因此每个操作都会在堆中创建一个新实例，而 StringBuilder 和 StringBuffer 则不然。