警告。这里涉及一些问题。
事实上，有两个问题混合在一起：
- 如何以相反的顺序将数据从一个列表传输到另一个列表？
- 如何从 a 创建数字列表
BigInteger?
我同意罗曼·C 的评论: “从一个列表移动到另一个列表是没有用的”。至少，在这种情况下，似乎没有什么用处。但如果有什么事情发生tempList，并且从一个列表中删除元素并将它们添加到另一个列表（一个接一个）的一般方法在任何方面都是合理的，那么如何提高这种特定情况下的性能的问题可能仍然是可行的。
关于如何将数据从一个列表传输到另一个列表的核心问题，以相反的顺序：
令人惊讶的是，按照现在写的形式，
...第二个片段是far比第一个慢！
（解释如下）
像这样的简单测试可以比较这两种方法。 （当然，像这样的“微基准测试”应该持保留态度，但由于这里的性能与渐近运行时间相关，所以这是合理的）
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;
}
}
我的机器上的输出是
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....
这是由于方法调用错误造成的。第二种方法包含行
list.remove(list.get(list.size() - 1));
这就是本例中的罪魁祸首：你有一个列表Integer对象。而你正在呼唤remove，传入一个Integer目的。此方法将搜索整个列表，并删除第一次出现的参数。这不仅很慢，而且还会导致结果明显错误！
你真正想要做的是删除最后一个元素，使用index最后一个元素的。所以将这一行更改为
list.remove((int)list.size() - 1);
给出了完全不同的计时结果：
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
...
因此，如果实施得当，那么
...第一个片段是far比第二个慢！
由于以下原因Eran在他的回答中提到.
关于如何从a创建数字列表的问题BigInteger：有几个可能的性能改进。
手动提取数字，使用一系列%= 10 and /= 10通话速度很慢。避免模运算已经带来了小幅加速。所以而不是
digit = number % 10;
number = number / 10;
你可以做
nextNumber = number / 10;
digit = number - (nextNumber * 10);
number = nextNumber;
但由于其不变性BigInteger和昂贵的除法，这仍然比简单地转换要慢几个数量级BigInteger到一个字符串中，并从那里提取数字，如dasblinkenlight 在他的回答中建议.
一个简单的比较：
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;
}
}
输出将类似于：
...
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
表明toString方法比手动方法快一百倍以上。
