CODEWITHSUNDEEP
javastringperformancelong-integermodulo
user13977876
user13977876

Reputation:

Would finding 0 in a number be faster if I convert the number to a string?

I need to find if a number contains 0 in it. So far, I have tried to take the modulo of the number with 10 and then divide the quotient by 10, and then repeat this process until the number is 0. Is converting this number to a string and searching through this string using the .contains() method more efficient?

my code:

boolean zero(int n) {
    if(n == 0)
        return true;

    while(n > 0) {
        if(n % 10 == 0)
            return true;
        n = n/10;
    }
    return false;
}

Any help would be appreciated.

Upvotes: 0

Views: 99

Answers (1)

JayC667
JayC667

Reputation: 2588

Well, actually, think about how the String, each digit, is 'created': by divisions and modulos of 10. So the int-to-String conversion will actually do the same task you're doing.

Here's the source code of Integer.getChars(), which is what gets called via Integer.toString(), along with some other buffer management:

static void getChars(int i, int index, char[] buf) {
    int q, r;
    int charPos = index;
    char sign = 0;

    if (i < 0) {
        sign = '-';
        i = -i;
    }

    // Generate two digits per iteration
    while (i >= 65536) {
        q = i / 100;
    // really: r = i - (q * 100);
        r = i - ((q << 6) + (q << 5) + (q << 2));
        i = q;
        buf [--charPos] = DigitOnes[r];
        buf [--charPos] = DigitTens[r];
    }

    // Fall thru to fast mode for smaller numbers
    // assert(i <= 65536, i);
    for (;;) {
        q = (i * 52429) >>> (16+3);
        r = i - ((q << 3) + (q << 1));  // r = i-(q*10) ...
        buf [--charPos] = digits [r];
        i = q;
        if (i == 0) break;
    }
    if (sign != 0) {
        buf [--charPos] = sign;
    }
}

As you see, with bigger numbers than 65536, it uses and improved divide-convert loop. And for the lower numbers (or once the original number was cut down) there's some heavy optimization (bit-shifting and bytemasks) and going on. Divisions are usually a lot more costly, about 20 to 60 times slower than bit shifts. So the last part is really fast. But it's only for 5 digits, so how much of an impact will that have?

Also consider memory management. The JVM might run into speed bumps if you system keeps running on 100% across all cores, and when (if) a garbage collection might have to occur, the GC-induced 'forced' pause might annihilate all speed advantages. (Testing this should be a long-term test in the minutes).

You might also consider splitting up the problem/tasks across multiple threads. Easiest would be to use the java 1.8-new streams. Or you have your own parallelizer/splitter and your own task arrays/queues. Might almost n-fold the speed of the task, with n being the number of CPU cores you can use.

As others have stated, it's actually best to test the speeds yourself. Best write a test that runs about 10 seconds. That's long enough to give you a stable estimate and the JIT optimization to kick in, and short enough to not get bored to hell.

On the other hand, it's usually better to solve a problem in an obvious, non-cryptic, easy-to-maintain way. So if I had to implement it, I would test, and if the difference is less than a factor of 5, I would stick to numbers only. No Strings attached :-D

Upvotes: 3

Related Questions