在Java中，如果不将数字转换为字符串，有什么更快的方法来查找给定整数是否以数字2开头？
String.valueOf(number).charAt(0) == '2'
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方法更快。
- Jon Skeet
6
不确定是否更快，但肯定更容易理解 :D 无论如何，两者都加1。 - Mena
2你可以在开始之前获取整数的绝对值，以确保它是正数。 - Husman
@Husman：我考虑过这个问题，但你需要考虑到
Integer.MIN_VALUE。基本上它变得足够棘手，以至于我不想深入研究它 ;) - Jon Skeet请注意，JDK对
Integer.toString的实现已经高度优化。 - Marko Topolnik2应该将 while (x > 10) 改为 while (x >= 10)，以避免在 x=10 时返回 10。 （由于我的编辑不足6个字符，因此堆栈溢出不允许我编辑代码） - Husman
我测试了不同的解决方案（请参见我的答案），这个是最快的 :) - Arnaud Denoyelle
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比divide更快4.6倍，并且只比bitTwiddling稍慢0.2倍。
请注意，我使用的数值非常大；相对速度随着数量级的变化而变化。
- Marko Topolnik
8
1也许可以使用位移运算符代替 pow 函数，这样会稍微快一些。 :) - Sajal Dutta
1@SajalDutta - 你打算如何使用移位运算来计算10的N次方？ - Stephen C
@StephenC 哎呀，我没看到整数限制，我的错。 - Sajal Dutta
1@OldCurmudgeon 有一件事：你组合数组的方式偏向于大数，而我正在测试大数。如果反过来，对于相同的数字范围，它可能会变得稍微慢一点。 - Marko Topolnik
显示剩余3条评论
8
我会考虑做这样的事情：
我会考虑做这样的事情：
x = Math.abs(x);
if ( ((int) Math.floor(x / Math.pow(10, Math.floor(Math.log10(x))))) == 2 )
{
... // x equals 2
}
- Husman
7
该内容源于 Sean Eron Anderson 的位操作技巧
(相关IT技术)
/*
* 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)];
}
我已经测试过了，似乎可以工作 - 它的基准测试结果如何？
- OldCurmudgeon
24
它实际上比Jon Skeet的解决方案快了大约5倍。虽然它看起来更加复杂，但很容易忘记现代CPU上分支（例如while循环）的速度有多慢。 - jarnbjo
@jarnbjo - 确实应该更快，但它是否更快取决于基准测试。我期待Arnauld的反馈。 - OldCurmudgeon
你应该在
log10() 方法的结果上加上 +1。 - Arnaud Denoyelle@ArnaudDenoyelle - 你确定吗？我已经尽可能地匹配原始数据。虽然我的测试不够严格，但似乎产生了正确的顶部数字。 - OldCurmudgeon
@Husman - 谢谢，但这不是我的作品（除了从C翻译成Java），请看我在开头发布的参考资料。 - OldCurmudgeon
显示剩余19条评论
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;
}
- OldCurmudgeon
1
Marko的基准测试表明，这个函数是所有函数中最快的，甚至比我预期的还要快得多。 - OldCurmudgeon
4
更新：我现在在每个迭代中测试不同的数字，并添加了OldCurmudgeon的解决方案（从Sean Eron Anderson的位扭曲技巧中推导出来的）。
我对不同的解决方案进行了基准测试，包括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) 使用Jon的解决方案：
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毫秒
- Arnaud Denoyelle
15
2你的基准测试存在一些缺陷（没有预热，方法结果被丢弃...），因此很难确定结果是否可靠。 - assylias
如果您不仅测试单个数字的算法，那么基准测试将更加有用！ - Gyro Gearless
1我更感兴趣的是看到使用不同参数调用该方法，例如999999并递减1等，以查看它们在负载下的表现如何。虽然除法（又名Jon Skeet）方法看起来像一个确定的赢家。 - Husman
1@assylias 嗯，他的结果使Jon的解决方案与我的结果相比显得太过突出：快了7倍，而我只是快了60%。他使用了
startsWith 而不是 charAt，不知道这有多大影响。 - Marko Topolnik1
return t - (v < PowersOf10[t] ? 1 : 0); => return 1 + t - (v < PowersOf10[t] ? 1 : 0); - Arnaud Denoyelle显示剩余10条评论
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() 方法是目前最快的方法。
- user2652406
0
int intValue=213;
if(String.valueOf(intValue).startsWith("2"))
{
System.out.println("Yes");
}
else
{
System.out.println("No");
}
- Shahdat
2
3你读到这个问题了吗：不需要将数字转换为字符串？ - anubhava
2嗯，问题已经编辑了，我考虑不使用子字符串。 - Shahdat
0
((int) number / 10^(numberlength-1)) 将会给出第一个数字。
- Ali
1
1为了获取数字长度，你需要将数字转换为字符串（等同于 OP 的解决方案），或者使用 log10 函数（等同于 Husman 的解决方案）。 - Arnaud Denoyelle
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
substring，你的意思是要避免转换为字符串吗？ - Marko Topolnik