位摆弄在java中 - 分解成很长很长位屏蔽[] [英] bit twiddling in java - decomposing long into long[] of bitmasks
问题描述
我分解一条长成一个长按
I am decomposing a single long into a long[] of single bit longs by
public static int decompose(long[] buffer, long base) {
int count = Long.bitCount(base);
for (int i=0; i<count; i++) {
base ^= (buffer[i] = Long.lowestOneBit(base));
}
return count;
}
但我觉得有可能是做这一个更快的方法，因为它看起来像有一些重复的步骤。例如，计数位应该已经接近前来pretty，这是让填充结果所需的所有信息。
but I feel like there might be a faster way to do this, since it seems like there are some repeated steps. For example, counting the bits should already come pretty close to getting all the info needed to populate the result.
有什么建议？我熟悉的premature优化的口头禅，因此为什么我没有推我的解决方案的任何进一步的我的时间，但在此之前也许别人已经看到了这一点，或者沉迷于优化...编辑：请运行任何建议通过<一个href=\"http://stackoverflow.com/questions/3961443/bit-twiddling-in-java-decomposing-long-into-long-of-bitmasks/3962404#3962404\">test线束马克下面提供。我比有些意外的是我的第一个暗示实际上是持股待涨。
Any suggestions? I'm familiar with the premature optimization mantra, hence why I'm not pushing my solution any further on my time, but perhaps someone else has seen this before or is addicted to optimization... please run any suggestions through the test harness Mark provided below. I am more than a bit surprised that my first inkling is actually holding up.
测试code，这是一个JUnit方法中：
test code, which is inside a JUnit method:
Random rng = new Random();
long size = 0;
long[] hold = new long[Long.SIZE];
System.out.println("init:"+Long.toBinaryString(BitTwiddling.bitmask(rng.nextInt(Long.SIZE)))); //initialize BitTwiddling internals
long start = System.currentTimeMillis();
for (int i=0; i<compareIterations; i++) size+= BitTwiddling.decompose(hold,rng.nextInt(Integer.MAX_VALUE));
long delta = System.currentTimeMillis() - start;
double base = (double)size/delta;
size = 0;
start = System.currentTimeMillis();
for (int i=0; i<compareIterations; i++) size += BitTwiddling.decomposeAlt(hold, rng.nextInt(Integer.MAX_VALUE));
long delta2 = System.currentTimeMillis() - start;
double base2 = (double)size/delta2;
然后比较基地和BASE2
then compare base and base2
推荐答案
下面是我目前使用的线束。 <罢>我一直得到问题的code（方法1）显著更快地执行目前，马克·彼得斯的回答通常是最快的，但卡尔的是更快的 - 服务器标志设置。此外，mikera的得到大大服务器模式更具竞争力的（不过仍低于卡尔慢/马克）。
Here's the harness I'm using at the moment. I consistently get the code in the question (Method 1) to perform significantly faster. Currently Mark Peters' answer is the fastest normally, but Carl's is faster with the -server flag set. Also, mikera's gets considerably more competitive in server mode (though still slower than Carl/Mark's).
import java.util.Random;
public abstract class Harness {
public static void main(String[] args) {
while (true) {
long[] randomData = new long[4096];
Random r = new Random();
for (int i = 0; i < randomData.length; i++) {
randomData[i] = r.nextLong();
}
long[] buffer = new long[64];
Harness[] versions = new Harness[] {
new Control(randomData, buffer),
new Carl(randomData, buffer),
new MarkPeters(randomData, buffer),
new MarkPetersServer64Bit(randomData, buffer),
// new Rsp1(randomData, buffer),
new Rsp2(randomData, buffer),
new Mikera(randomData, buffer)
};
for (Harness v : versions) {
v.doTest();
}
}
}
private final long[] buffer;
private final long[] randomData;
protected Harness(long[] randomData, long[] buffer) {
this.randomData = randomData;
this.buffer = buffer;
}
public void doTest() {
long start = System.nanoTime();
long count = 0;
for (int times = 0; times < 1000; times++) {
for (int i = 0; i < randomData.length; i++) {
count = decompose(buffer, randomData[i]);
}
}
long end = System.nanoTime();
//verify decomposition of last item
long l = 0;
for ( int i = 0; i < count; i++ ) {
l |= buffer[i];
}
System.out.println(getClass().getSimpleName() + " took " + (end - start)
/ 1000000.0 + " ms - last base: " + l);
}
protected abstract int decompose(long[] buffer, long base);
private static class Control extends Harness {
protected Control(long[] randomData, long[] buffer) {
super(randomData, buffer);
}
@Override
protected int decompose(long[] buffer, long base) {
return 0;
}
}
private static class Carl extends Harness {
protected Carl(long[] randomData, long[] buffer) {
super(randomData, buffer);
}
@Override
protected int decompose(long[] buffer, long base) {
final int count = Long.bitCount(base);
for (int i = 0; i < count; i++) {
base ^= (buffer[i] = Long.lowestOneBit(base));
}
return count;
}
}
private static class Mikera extends Harness {
protected Mikera(long[] randomData, long[] buffer) {
super(randomData, buffer);
}
@Override
protected int decompose(long[] buffer, long base) {
int count = 0;
while (base != 0) {
long mask = base & (-base);
base &= ~mask;
buffer[count++] = mask;
}
return count;
}
}
private static class Rsp1 extends Harness {
protected Rsp1(long[] randomData, long[] buffer) {
super(randomData, buffer);
}
@Override
protected int decompose(long[] buffer, long base) {
int count = 0;
if (0 != (base & 1)) {
buffer[count++] = 1;
}
base >>>= 1;
for (long bit = 1; 0 < bit && bit <= base; ) {
if (0 < (base & bit)) {
buffer[count++] = (bit <<= 1);
}
}
return count;
}
}
private static class Rsp2 extends Harness {
protected Rsp2(long[] randomData, long[] buffer) {
super(randomData, buffer);
}
@Override
protected int decompose(long[] buffer, long base) {
int count = 0;
for (long bit = 1; 0 != base; bit <<= 1, base >>>= 1) {
if (0 < (base & 1)) {
buffer[count++] = bit;
}
}
return count;
}
}
private static class MarkPeters extends Harness {
protected MarkPeters(long[] randomData, long[] buffer) {
super(randomData, buffer);
}
@Override
protected int decompose(long[] buffer, long base) {
int count = Long.bitCount(base);
for (int i = 0; i < count; i++) {
base -= (buffer[i] = Long.lowestOneBit(base));
}
return count;
}
}
private static class MarkPetersServer64Bit extends Harness {
protected MarkPetersServer64Bit(long[] randomData, long[] buffer) {
super(randomData, buffer);
}
@Override
protected int decompose(long[] buffer, long base) {
int count = 0;
while ( 0 != (base ^= (buffer[count++] = Long.lowestOneBit(base))));
return count;
}
}
}
示例输出
哪种方法最好是视情况而定。
Sample output
Which method is best depends on the situation.
Control took 41.175272 ms - last base: 0
Carl took 691.966919 ms - last base: 5852835112840111303
MarkPeters took 642.230253 ms - last base: 5852835112840111303
MarkPetersServer64Bit took 742.594626 ms - last base: 5852835112840111303
Rsp2 took 3886.203787 ms - last base: 5852835112840111303
Mikera took 1044.451494 ms - last base: 5852835112840111303
得奖者： MarkPeters
Winner: MarkPeters
Control took 2.354383 ms - last base: 0
Carl took 508.687401 ms - last base: 338317437500027646
MarkPeters took 521.831297 ms - last base: 338317437500027646
MarkPetersServer64Bit took 727.052206 ms - last base: 338317437500027646
Rsp2 took 3811.75662 ms - last base: 338317437500027646
Mikera took 665.252599 ms - last base: 338317437500027646
得奖者：卡尔
Control took 0.007186 ms - last base: 0
Carl took 543.701859 ms - last base: -8898262206218882664
MarkPeters took 439.706079 ms - last base: -8898262206218882664
MarkPetersServer64Bit took 391.831055 ms - last base: -8898262206218882664
Rsp2 took 1861.40449 ms - last base: -8898262206218882664
Mikera took 435.964319 ms - last base: -8898262206218882664
得奖者： MarkPetersServer64Bit
Winner: MarkPetersServer64Bit
注意：没有可比性的64位JVM可以在无服务器模式，据我所知运行。 见这里：
Note: there is no comparable 64-bit JVM that can run in non-server mode to my knowledge. See here:
在使用这两种-client和-server VM模式的64位Java？
目前仅在Java HotSpot的服务器虚拟机支持64位运算，-server选项是隐式与使用-d64。这是在将来的版本中改变。
Currently only the Java HotSpot Server VM supports 64-bit operation, and the -server option is implicit with the use of -d64. This is subject to change in a future release.
这篇关于位摆弄在java中 - 分解成很长很长位屏蔽[]的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
