这个Java算法怎么能更快呢

Question

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

如果LinkedList的大小很大，则此代码会非常慢。我尝试用一个简单的循环来更改Iterator，但它仍然很慢。

这个算法怎么可能真的很快？也许使用多线程？

注意：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<Boolean>
2. 使用StringBuilder output;而不是String output;
3. 使用StringBuilder buffer;而不是String buffer;
4. 使用Integer.valueOf()而不是Integer.parseInt。valueOf对128以下的值使用缓存

Answer 2

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

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

2. 使用按位操作而不是parseInt()，类似于以下内容：

   int i = 0;          
   int c = 0;
   for(Boolean b: bits){
       if (i > 0 && i % 8 == 0){
           out.append((char) c);
           c = 0;
       }
       c = (c << 1) | (b ? 1 : 0);
       i++;
   }
   out.append((char) c); // Not sure about the desired behaviour here
   

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";

同时使用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则不是。