java - 数字が 2 で始まるかどうかを調べるより速い方法は?

Question

Java - 数値を文字列に変換せずに、指定された整数が数字の 2 で始まっているかどうかを調べるより高速な方法は何ですか?

String.valueOf(number).charAt(0) == '2'

Answer 1

文字列への変換を避けたい場合は、10 で割り続けて最上位桁を見つけることができます。

int getMostSignificantDigit(int x)
{
    // Need to handle Integer.MIN_VALUE "specially" as the absolute value can't
    // represented. We can hard-code the fact that it starts with 2 :)
    x = x == Integer.MIN_VALUE ? 2 : Math.abs(x);
    while (x >= 10)
    {
        x = x / 10;
    }
    return x;
}

これが Husman の log/pow アプローチよりも高速かどうかはわかりません。

Answer 2

私はこのようなことをしたくなるでしょう：

  x = Math.abs(x);
  if ( ((int) Math.floor(x / Math.pow(10, Math.floor(Math.log10(x))))) == 2 )
  {
     ... // x equals 2
  }

Answer 3

Sean Eron Anderson による Bit Twiddling Hacksから派生

/*
 * Log(2) of an int.
 * 
 * See: http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogLookup
 */
private static final int[] Log256 = new int[256];

static {
  for (int i = 0; i < 256; i++) {
    Log256[i] = 1 + Log256[i / 2];
  }
  Log256[0] = -1;
}

public static int log2(int v) {
  int t, tt;
  if ((tt = v >> 16) != 0) {
    return (t = tt >> 8) != 0 ? 24 + Log256[t] : 16 + Log256[tt];
  } else {
    return = (t = v >> 8) != 0 ? 8 + Log256[t] : Log256[v];
  }
}

/*
 * Log(10) of an int.
 * 
 * See: http://graphics.stanford.edu/~seander/bithacks.html#IntegerLog10
 */
private static int PowersOf10[] = {1, 10, 100, 1000, 10000, 100000,
                                   1000000, 10000000, 100000000, 1000000000};

public static int log10(int v) {
  int t = (log2(v) + 1) * 1233 >> 12;
  return t - (v < PowersOf10[t] ? 1 : 0);
}

// Returns the top digit of the integer.
public static int topDigit(int n) {
  return n / PowersOf10[log10(n)];
}

私はこれをテストしましたが、うまくいくようです - どのようにベンチマークしますか?

Answer 4

もう 1 つの可能性 - 分割が明らかにボトルネックであるため (それとも?):

// Pairs of range limits.
// Reverse order to put the widest range at the top.
static final int [] limits = new int[] {
  // Can hard-code this one to avoid one comparison.
  //2000000000, Integer.MAX_VALUE,
  200000000, 300000000-1,
  20000000, 30000000-1,
  2000000, 3000000-1,
  200000, 300000-1,
  20000, 30000-1,
  2000, 3000-1,
  200, 300-1,
  20, 30-1,
  2, 3-1,
};

public static boolean firstDigitIsTwo(int v) {
  // All ints from there up start with 2.
  if ( v >= 2000000000 ) return true;
  for ( int i = 0; i < limits.length; i += 2 ) {
    // Assumes array is decreasing order.
    if ( v > limits[i+1] ) return false;
    // In range?
    if ( v >= limits[i] ) return true;
  }
  return false;
}

Answer 5

テストコードと結果を投稿できるように、ここで回答しています。

public class NumberStart extends AbstractBenchmark {

private static final int START = 10000000;
private static final int END = 50000000;

private static int result;

@Test
@BenchmarkOptions(benchmarkRounds = 1, warmupRounds = 1)
public void divide() {
    for (int x = START; x < END; x++) {
        int i = x;
        while (i > 10) {
            i = i / 10;
        }
        result = i;
    }
}

@Test
@BenchmarkOptions(benchmarkRounds = 1, warmupRounds = 1)
public void math() {
    for (int x = START; x < END; x++) {
        result = (int) Math.floor(x / Math.pow(10, Math.floor(Math.log10(x))));
    }
}

@Test
@BenchmarkOptions(benchmarkRounds = 1, warmupRounds = 1)
public void string() {
    for (int x = START; x < END; x++) {
        result = (int) Integer.toString(x).charAt(0);
    }
}

@Test
@BenchmarkOptions(benchmarkRounds = 1, warmupRounds = 1)
public void bitmath() {
    for (int x = START; x < END; x++) {
        result = (int) BitMath.topDigit(x);
    }
}
}

bitmath()メソッドは、OldCurmudgeon によって投稿されたコードを使用します。

結果は次のとおりです。

NumberStart.divide: [measured 1 out of 2 rounds, threads: 1 (sequential)]
 round: 0.36 [+- 0.00], round.block: 0.00 [+- 0.00], round.gc: 0.00 [+- 0.00], GC.calls: 0, GC.time: 0.00, time.total: 0.71, time.warmup: 0.36, time.bench: 0.35
NumberStart.string: [measured 1 out of 2 rounds, threads: 1 (sequential)]
 round: 1.64 [+- 0.00], round.block: 0.00 [+- 0.00], round.gc: 0.00 [+- 0.00], GC.calls: 147, GC.time: 0.08, time.total: 3.31, time.warmup: 1.68, time.bench: 1.64
NumberStart.bitmath: [measured 1 out of 2 rounds, threads: 1 (sequential)]
 round: 0.22 [+- 0.00], round.block: 0.00 [+- 0.00], round.gc: 0.00 [+- 0.00], GC.calls: 0, GC.time: 0.00, time.total: 0.45, time.warmup: 0.23, time.bench: 0.22
NumberStart.math: [measured 1 out of 2 rounds, threads: 1 (sequential)]
 round: 4.93 [+- 0.00], round.block: 0.00 [+- 0.00], round.gc: 0.00 [+- 0.00], GC.calls: 0, GC.time: 0.00, time.total: 9.89, time.warmup: 4.95, time.bench: 4.93

bitmath()メソッドは、これまでのところ最速のメソッドです。