Car*_*arl 5 java bit-manipulation
我正在将一个长的分解为长的单个长的[]
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;
}
但我觉得可能有更快的方法来做到这一点,因为似乎有一些重复的步骤.例如,计算这些位应该已经非常接近于获得填充结果所需的所有信息.
有什么建议？我熟悉过早优化的口头禅,因此为什么我不再在我的时间推进我的解决方案,但也许其他人之前已经看过这个或沉迷于优化...编辑:请通过测试运行任何建议马克马克提供如下.我的第一次暗示实际上是在坚持,我感到有些惊讶.
测试代码,它位于JUnit方法中:
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;
然后比较base和base2
这是我目前正在使用的安全带。 我始终使问题（方法 1）中的代码执行速度明显更快。 目前，马克·彼得斯的答案通常是最快的，但卡尔的答案在-server设置标志后更快。此外，mikera 在服务器模式下变得更具竞争力（尽管仍然比 Carl/Mark 慢）。
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;
}
}
}
哪种方法最好取决于具体情况。
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
获奖者：马克·彼得斯
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
注意：据我所知，没有可比的 64 位 JVM 可以在非服务器模式下运行。 看这里：
-client 和 -server VM 模式在 64 位 Java 中都可用吗？
目前，只有 Java HotSpot Server VM 支持 64 位操作，并且 -server 选项是隐式使用 -d64 的。这可能会在未来版本中发生变化。