Caution. There are some gotchas involved here.
In fact, there are two questions mixed:
- How to transfer data from one list to another, in reverse order?
- How to create a list of digits from a
BigInteger?
I agree with the comment by Roman C: "Moving from one list to another is useless". At least, it seems to be useless in this case. But if there is something happening to the tempList, and the general approach of removing elements from one list and adding them to another list (one by one) is justified in any way, then the question of how to improve the performance for this particular case may still be feasible.
Regarding the core question of how to transfer data from one list to another, in reverse order:
Surprisingly, in the form that it is written now,
...the second snippet is far slower than the first one!
(Explanation follows)
A simple test like this one compares both approaches. (Of course, "micorbenchmarks" like this one should be taken with a grain of salt, but as the performance here is related to asymptotic running times, this is reasonable here)
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Locale;
import java.util.Random;
public class BigIntegerDigitsPerformanceLists
{
public static void main(String[] args)
{
testListConversion();
}
private static void testListConversion()
{
long before = 0;
long after = 0;
for (int size = 10; size <= 1000000; size *= 10)
{
List<Integer> inputA = createRandomList(size);
List<Integer> inputB = createRandomList(size);
before = System.nanoTime();
List<Integer> resultA = convertA(inputA);
after = System.nanoTime();
System.out.printf(Locale.ENGLISH,
"A: size %8d time %8.2fms result %d\n",
size, (after-before)/1e6, resultA.get(0));
before = System.nanoTime();
List<Integer> resultB = convertB(inputB);
after = System.nanoTime();
System.out.printf(Locale.ENGLISH,
"B: size %8d time %8.2fms result %d\n",
size, (after-before)/1e6, resultB.get(0));
}
}
private static List<Integer> createRandomList(int size)
{
List<Integer> result = new ArrayList<Integer>();
Random random = new Random(0);
for (int i=0; i<size; i++)
{
result.add(random.nextInt(10));
}
return result;
}
private static List<Integer> convertA(List<Integer> list)
{
List<Integer> result = new ArrayList<Integer>();
Collections.reverse(list);
while (!list.isEmpty())
{
result.add(list.get(0));
list.remove(0);
}
return result;
}
private static List<Integer> convertB(List<Integer> list)
{
List<Integer> result = new ArrayList<Integer>();
while (!list.isEmpty())
{
result.add(list.get(list.size() - 1));
list.remove(list.get(list.size() - 1));
}
return result;
}
}
The output on my machine is
A: size 10 time 0.08ms result 4
B: size 10 time 0.05ms result 4
A: size 100 time 0.13ms result 1
B: size 100 time 0.39ms result 1
A: size 1000 time 1.27ms result 6
B: size 1000 time 2.96ms result 6
A: size 10000 time 39.72ms result 1
B: size 10000 time 220.82ms result 1
A: size 100000 time 3766.45ms result 7
B: size 100000 time 21734.66ms result 7
...
But....
This is due to a wrong method call. The second approach contains the line
list.remove(list.get(list.size() - 1));
and this is the culprit in this case: You have a list of Integer objects. And you are calling remove, passing in an Integer object. This method will search through the whole list, and remove the first occurrence of the argument. This is not only slow, it also causes the result to be plainly wrong!
What you actually want to do is to remove the last element, using the index of the last element. So changing this line to
list.remove((int)list.size() - 1);
gives an entirely different timing result:
A: size 10 time 0.08ms result 4
B: size 10 time 0.03ms result 4
A: size 100 time 0.13ms result 1
B: size 100 time 0.10ms result 1
A: size 1000 time 1.28ms result 6
B: size 1000 time 0.46ms result 6
A: size 10000 time 39.09ms result 1
B: size 10000 time 2.63ms result 1
A: size 100000 time 3763.97ms result 7
B: size 100000 time 9.83ms result 7
...
So, when implemented properly, then
...the first snippet is far slower than the second one!
For the reasons that Eran mentioned in his answer.
Regarding the question of how to create a list of digits from a BigInteger: There are several possible performance improvements.
Extracting the digits manually, with a sequence of %= 10 and /= 10 calls is very slow. Avoiding the modulo operation already brings a small speedup. So instead of
digit = number % 10;
number = number / 10;
you could do
nextNumber = number / 10;
digit = number - (nextNumber * 10);
number = nextNumber;
But due to the immutability of BigInteger and the expensive division, this is still orders of magnitude slower than simply converting the BigInteger into a string, and extracting the digits from there, as dasblinkenlight suggested in his answer.
A simple comparison:
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;
import java.util.Locale;
import java.util.Random;
public class BigIntegerDigitsPerformance
{
public static void main(String[] args)
{
testListCreation();
}
private static void testListCreation()
{
long before = 0;
long after = 0;
for (int size = 10; size <= 100000; size *= 10)
{
BigInteger number = createRandomBigInteger(size);
before = System.nanoTime();
List<Integer> resultA = createA(number);
after = System.nanoTime();
System.out.printf(Locale.ENGLISH,
"A: size %8d time %8.2fms result %d\n",
size, (after-before)/1e6, resultA.get(0));
before = System.nanoTime();
List<Integer> resultB = createB(number);
after = System.nanoTime();
System.out.printf(Locale.ENGLISH,
"B: size %8d time %8.2fms result %d\n",
size, (after-before)/1e6, resultB.get(0));
before = System.nanoTime();
List<Integer> resultC = createC(number);
after = System.nanoTime();
System.out.printf(Locale.ENGLISH,
"B: size %8d time %8.2fms result %d\n",
size, (after-before)/1e6, resultC.get(0));
}
}
private static BigInteger createRandomBigInteger(int size)
{
StringBuilder sb = new StringBuilder();
Random random = new Random(0);
for (int i=0; i<size; i++)
{
sb.append(String.valueOf(random.nextInt(10)));
}
return new BigInteger(sb.toString());
}
private static List<Integer> createA(BigInteger number)
{
ArrayList<Integer> list = new ArrayList<Integer>();
while (number.compareTo(BigInteger.ZERO) == 1)
{
list.add((number.mod(BigInteger.TEN)).intValue());
number = number.divide(BigInteger.TEN);
}
return list;
}
private static List<Integer> createB(BigInteger number)
{
ArrayList<Integer> list = new ArrayList<Integer>();
while (number.compareTo(BigInteger.ZERO) == 1)
{
BigInteger next = number.divide(BigInteger.TEN);
BigInteger diff = number.subtract(next.multiply(BigInteger.TEN));
list.add(diff.intValue());
number = next;
}
return list;
}
private static List<Integer> createC(BigInteger number)
{
String s = number.toString();
ArrayList<Integer> list = new ArrayList<Integer>(s.length());
for (int i=s.length()-1; i>=0; i--)
{
list.add(s.charAt(i) - '0');
}
return list;
}
}
The output will be along the lines of this:
...
A: size 1000 time 9.20ms result 6
B: size 1000 time 6.44ms result 6
C: size 1000 time 1.96ms result 6
A: size 10000 time 452.44ms result 1
B: size 10000 time 334.82ms result 1
C: size 10000 time 16.29ms result 1
A: size 100000 time 43876.93ms result 7
B: size 100000 time 32334.84ms result 7
C: size 100000 time 297.92ms result 7
showing that the toString approach is more than a hundred times faster than the manual ones.
