java – 将Integer拆分成数字的最快方法是什么?
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了java – 将Integer拆分成数字的最快方法是什么?,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含7832字,纯文字阅读大概需要12分钟。
内容图文
我做了很多操作,将数字拆分成单独的数字,将数字放在ArrayList中并将这些数字逐个传递给其他ArrayList进行进一步操作,直到tempList为空 – 然后转到下一个比之前更大的数字.
我想知道哪种方法更快.
这两种方法共有的部分:
// Split number into digits and put into array
BigInteger number; // the number can be very big => BigInteger
ArrayList<Integer> tempList = new ArrayList<>();
while (number.compareTo(BigInteger.ZERO) == 1) {
tempList.add((number.mod(BigInteger.TEN)).intValue());
number = number.divide(BigInteger.TEN);
}
然后我可以通过2种方式逐个将这些数字传递给其他ArrayList主列表,并在以下后删除它们:
方式1:
// reverse the tempList (as digits are put there backwards) and take the first elements
Collections.reverse(tempList);
while (!tempList.isEmpty()) {
mainList.add(tempList.get(0);
tempList.remove(0);
}
方式2:
// take the last elements
while (!tempList.isEmpty()) {
mainList.add(tempList.get(tempList.size()-1);
tempList.remove(tempList.get(tempList.size()-1);
}
哪种方式更快?考虑到数十亿的操作数十亿的数字被拆分和添加.我认为像Collections.reverse()这样的方法需要更多的时间,但我每次使用下一个数字的新数字更新tempList时都会调用它.但在方式2中,我调用.size() – 对每个操作进行1次操作.
数字越大 – 更新tempList与从中获取数字(显然)之间的差距越大,因此调用的方法越少.reverse().
数字从1开始并进入无穷大.
tempList是有原因的,所以请不要建议绕过它.
附加问题:衡量此类事物的最佳做法是什么?
解决方法:
警告.这里涉及一些问题.
事实上,有两个问题混合在一起:
>如何以相反的顺序将数据从一个列表传输到另一个列表?
>如何从BigInteger创建数字列表?
我同意comment by Roman C:“从一个列表移到另一个列表是没用的”.至少,在这种情况下似乎没用.但是如果tempList发生了某些事情,并且从一个列表中删除元素并将它们添加到另一个列表(逐个)的一般方法以任何方式都是合理的,那么如何提高这个特定情况的性能的问题可能仍然可行.
关于如何以一个相反的顺序将数据从一个列表传输到另一个列表的核心问题:
令人惊讶的是,以现在写的形式,
……第二个片段远比第一个慢!
(以下说明)
像这样的简单测试比较两种方法. (当然,像这样的“micorbenchmarks”应该用一粒盐,但由于这里的性能与渐近运行时间有关,这在这里是合理的)
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
...
但….
这是由于错误的方法调用.第二种方法包含该行
list.remove(list.get(list.size() - 1));
这是这种情况的罪魁祸首:你有一个Integer对象列表.你正在调用remove,传入一个Integer对象.此方法将搜索整个列表,并删除第一次出现的参数.这不仅速度慢,而且还会导致结果明显错误!
你真正想要做的是使用最后一个元素的索引删除最后一个元素.所以改变这一行
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
...
那么,当正确实施时,那么
……第一个片段比第二个片段慢得多!
原因是Eran mentioned in his answer.
关于如何从BigInteger创建数字列表的问题:有几种可能的性能改进.
使用%= 10和/ = 10次调用的序列手动提取数字非常慢.避免模??运算已经带来了一个小的加速.而不是
digit = number % 10;
number = number / 10;
你能做到的
nextNumber = number / 10;
digit = number - (nextNumber * 10);
number = nextNumber;
但由于BigInteger的不变性和昂贵的划分,这仍然比简单地将BigInteger转换为字符串并从那里提取数字要慢几个数量级,如dasblinkenlight suggested in his answer所示.
一个简单的比较:
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方法比手动方法快一百多倍.
内容总结
以上是互联网集市为您收集整理的java – 将Integer拆分成数字的最快方法是什么?全部内容,希望文章能够帮你解决java – 将Integer拆分成数字的最快方法是什么?所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。