6

在Java中 - 查找给定整数是否以数字2开头而无需将数字转换为字符串的更快方法是什么？

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

9 回答 9

18

如果您想避免将其转换为字符串，则可以继续除以 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 方法更快。

于 2013-08-05T08:51:22.490 回答
9

我已经将各种解决方案相互竞争：

public class FirstDigit
{
  static int digit;
  @GenerateMicroBenchmark public void string() {
    for (int i = 200_000_000; i < 400_000_000; i += 999961)
      digit = Integer.toString(i).charAt(0);
  }
  @GenerateMicroBenchmark public void math() {
    for (int i = 200_000_000; i < 400_000_000; i += 999961) {
      digit = (int) floor(i / pow(10, floor(log10(i))));
    }
  }
  @GenerateMicroBenchmark public void divide() {
    for (int i = 200_000_000; i < 400_000_000; i += 999961) {
      int x = i;
      while (x > 10) x /= 10;
      digit = x;
    }
  }
  @GenerateMicroBenchmark public void brokenDivide() {
    for (int i = 200_000_000; i < 400_000_000; i += 999961) {
      int x = i;
      while (x > 10) x >>= 3;
      digit = x;
    }
  }
  @GenerateMicroBenchmark public void bitTwiddling() {
    for (int i = 200_000_000; i < 400_000_000; i += 999961) {
      digit = i/powersOf10[log10(i)];
    }
  }
  @GenerateMicroBenchmark public boolean avoidDivide() {
    boolean b = true;
    for (int i = 200_000_000; i < 400_000_000; i += 999961) {
      b ^= firstDigitIsTwo(i);
    }
    return b;
  }


  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;
  }
  private static int powersOf10[] = {1, 10, 100, 1000, 10_000, 100_000,
    1_000_000, 10_000_000, 100_000_000, 1_000_000_000};

  public static int log2(int v) {
    int t, tt;
    return ((tt = v >> 16) != 0)?
        (t = tt >> 8) != 0 ? 24 + log256[t] : 16 + log256[tt]
      : (t = v >> 8) != 0 ? 8 + log256[t] : log256[v];
  }
  public static int log10(int v) {
    int t = (log2(v) + 1) * 1233 >> 12;
    return t - (v < powersOf10[t] ? 1 : 0);
  }

  static final int [] limits = new int[] {
    2_000_000_000, Integer.MAX_VALUE,
    200_000_000, 300_000_000-1,
    20_000_000, 30_000_000-1,
    2_000_000, 3_000_000-1,
    200_000, 300_000-1,
    20_000, 30_000-1,
    2000, 3000-1,
    200, 300-1,
    20, 30-1,
    2, 3-1,
  };
  public static boolean firstDigitIsTwo(int v) {
    for ( int i = 0; i < limits.length; i+= 2) {
      if ( v > limits[i+1] ) return false;
      if ( v >= limits[i] ) return true;
    }
    return false;
  }
}

结果：

Benchmark                   Mode Thr    Cnt  Sec         Mean   Mean error    Units
FirstDigit.avoidDivide     thrpt   1      3    5     2324.271       58.145 ops/msec
FirstDigit.bitTwiddling    thrpt   1      3    5      716.453        6.407 ops/msec
FirstDigit.brokenDivide    thrpt   1      3    5      578.259        7.534 ops/msec
o.s.FirstDigit.divide      thrpt   1      3    5      125.509        2.323 ops/msec
o.s.FirstDigit.string      thrpt   1      3    5       78.233        2.030 ops/msec
o.s.FirstDigit.math        thrpt   1      3    5       14.226        0.034 ops/msec
  • 该math方法显然是失败者；
  • 该方法以六倍的string速度节拍；math
  • 最简单的divide算法比这快 60%；
  • OldCurmudgeon 的算法又比;bitTwiddling快六倍。divide
  • OldCurmudgeon 的特殊情况avoidDivide方法（它直接给出是/否的答案，不像所有其他方法，它实际上确定第一个数字）比算法快三倍bitTwiddiling，是无可争议的赢家；
  • 对于诊断，我还包括了一个brokenDivide算法。它没有除以十，而是移动了三，给出了错误的答案。重点是强调divide算法的瓶颈在哪里：brokenDivide比 快 4.6 倍，比divide慢 0.2 倍bitTwiddling。

请注意，我使用了相当大的数字；相对速度随大小而变化。

于 2013-08-05T09:02:56.413 回答
8

我很想做这样的事情：

  x = Math.abs(x);
  if ( ((int) Math.floor(x / Math.pow(10, Math.floor(Math.log10(x))))) == 2 )
  {
     ... // x equals 2
  }
于 2013-08-05T08:50:28.780 回答
7

源自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)];
}

我已经对此进行了测试，它似乎有效 - 它如何进行基准测试？

于 2013-08-05T09:34:13.503 回答
4

更新：我现在在每次迭代中使用不同的数字进行测试，并添加了 OldCurmudgeon 的解决方案（源自 Sean Eron Anderson 的 Bit Twiddling Hacks 的解决方案）。

我对不同的解决方案进行了基准测试，包括 Jon Skeet 的 :)：

这是我用于此测试的主要方法：

public static void main(String[] args){

  long tip = System.currentTimeMillis();

  //Call the test method 10 000 000 times.
  for(int i= 0 ; i< 10_000_000 ; i++){
    //Here I call the method representing the algorithm.
    foo3(i);
  }

  long top = System.currentTimeMillis();

  System.out.println("Total time : "+(top-tip));

}

1）使用OP的解决方案：

public static boolean foo1(Integer i){
  return String.valueOf(i).charAt(0) == '2';
}

我的电脑需要425 毫秒。

2）尝试使用 Integer.toString().startsWith() ：

public static boolean foo2(Integer i){
  return Integer.toString(i).startsWith("2");
}

我的电脑需要410 毫秒。

3)使用 Husman 的解决方案：

public static boolean foo3(Integer i){
  i = Math.abs(i);
  return ((int) Math.floor(i / Math.pow(10, Math.floor(Math.log10(i))))) == 2;
}

需要2020 毫秒。

4）使用乔恩的解决方案：

public static boolean foo4(Integer i){
  return getMostSignificantDigit(i)==2;
}

public static int getMostSignificantDigit(int x)
{
  // TODO: Negative numbers :)
  while (x > 10)
  {
    x = x / 10;
  }
  return x;
}

需要125 毫秒

5）使用 OldCurmudgeon 的解决方案（见她的回答）：

public static boolean foo5(Integer i){
  return OldCurmudgeon.topDigit(i)==2;
}

需要97 毫秒

于 2013-08-05T09:02:35.317 回答
4

还有一种可能性——因为分裂显然是一个瓶颈（或者是吗？）：

// 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;
}
于 2013-08-05T22:48:58.440 回答
3

我在这里回答只是为了发布测试代码和结果：

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()方法是迄今为止最快的方法。

于 2013-08-05T10:02:03.077 回答
0 
    int intValue=213;
    if(String.valueOf(intValue).startsWith("2"))
    {
        System.out.println("Yes");
    }
    else
    {
        System.out.println("No");
    }
于 2013-08-05T08:57:14.373 回答
0

((int) number / 10^(numberlength-1)) 将给出第一个数字。

于 2013-08-05T11:04:32.213 回答