这个Java算法怎么能更快

我有这个循环，它将布尔LinkedList分成8位，并返回缓冲区中每个字节的ASCII值。该函数返回字符串缓冲区。这个Java算法怎么能更快

如果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; 
}

来源

2012-01-24 Pier-Alexandre Bouchard

的最后一个非8位缓冲区将转换其ascii值并将该值连接到输出。 –

使用StringBuilder初始化预计容量输出：

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

使用位操作而不是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

来源

2012-01-24 15:50:23 axtavt

哇，我用我的代码压缩的演示文件花了超过1分钟，你的时间少于1秒。我只是不明白你为什么做我％8！= 1。模可以是2,3,4 ..？内部代码必须在字符串构建器中附加非8位char值。 –

@ Pier-alexandreBouchard：是的，这段代码包含一个错误的错误，请等一下。 – axtavt

@ Pier-alexandreBouchard：现在看起来很好。 – axtavt

字符串连接是慢，尤其是对大名单（因为字符串是不可变的，他们必须围绕其复制需要一些时间而且每个副本也需要更多的空间）。使用StringBuilder而不是String来追加到。换句话说：buffer和output应该是StringBuilder实例。

来源

2012-01-24 15:48:22 Thomas

这些建议将给你足够的性能，仍然保持代码简单易读。通过这些变化，如果不能满足您的性能需求再慢慢介绍在其他的答案提出的LinkedList<Boolean>

使用StringBuilder output;代替String output;

使用StringBuilder buffer;

使用BitSet，而不是优化技术，而不是String buffer;第一次测试使用Integer.valueOf()代替Integer.parseInt。 valueOf使用缓存值低于128我认为。

来源

2012-01-24 15:49:50

@ beny23 OP正在创建整数字符串，他可以使用valueOf –

所以它是...我没有意识到，有一个字符串版本的valueOf ... – beny23

尽量保持缓冲区作为int。我的意思是

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

，而不是

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

还可以使用StringBuilder输出。这是一个小变化，但总是有点变化。

来源

2012-01-24 15:51:18

我虚心地建议你在第一个代码示例中使用'buffer * 2'或缓冲区=（buffer << 1）| （（布尔）it.next（）？1：0）;'。在一个表达式中，最好不要混合算术和位操作，即使它们相同。 –

尝试以下操作：

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());

来源

2012-01-24 16:01:55 beny23

用StringBuffer或StringBuilder的，而不是字符串为您的缓冲区和输出瓦尔。

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

来源

2012-01-24 16:04:29

正如其他人所建议的 - 使用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

来源

2012-01-24 16:39:29 DejanLekic

这个Java算法怎么能更快

回答

相关问题