问题：

将整数拆分为数字的最快方法是什么？

敖硕

2023-03-14

我做了很多操作，将数字拆分为单独的数字，将数字放入ArrayList并将这些数字一个接一个地传递给其他ArrayList以进行进一步的操作，直到temList为空-然后是下一个比前一个大的数字。

我想知道哪种方法更快。

这两种方法的共同点是：

// 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);
}

然后我可以通过两种方式将这些数字逐个传递给其他ArrayList mainList，并在之后删除它们：方式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);
}

哪种方法更快？考虑到这是数十亿次操作，数十亿个数字被拆分和html" target="_blank">添加。我认为像Collections.reverse（）这样的方法需要更多的时间，但是我只在每次用下一个数字的新数字更新temList时调用它。但是在方式2中，我对每个操作都调用. size（）-1操作。

而且数字越大——更新圣堂武士和从中获取数字之间的差距越大（显然），所以越小。reverse（）方法调用。这个数字从1开始到无穷大。

圣殿骑士的存在是有原因的，所以请不要建议绕过它。

另外一个问题：衡量这些东西的最佳实践是什么？

共有3个答案

唐繁

2023-03-14

这两个片段都很慢。如果你想做得更快，就列一个适当大小的清单，从后面填写。

这个答案显示了如何获得所需的ArrayList的长度

BigInteger number; // the number can be very big => BigInteger
ArrayList<Integer> res = new ArrayList<Integer>(
    // getDigitCount comes from the answer linked above
    Collections.nCopies(getDigitCount(number), 0)
);
int pos = res.size()-1;
while (number.compareTo(BigInteger.ZERO) == 1) {
    res.set(pos--, (number.mod(BigInteger.TEN)).intValue());
    number = number.divide(BigInteger.TEN);
}

这会立即以所需的顺序生成ArrayList，因此完全不需要反转例程。

注意：Java-8允许您在一行中转换为整数数组：

BigInteger number = new BigInteger("12345678910111213141516171819");
List<Integer> res = number
    .toString()
    .chars()
    .mapToObj(c -> Character.digit(c, 10))
    .collect(Collectors.toList());

演示。

魏君博

2023-03-14

第二段应该更快，原因有两个：

不必反转数组列表，因为你认识到自己。

删除ArrayList的最后一个元素比删除第一个元素快，因为删除第一个元素会减少所有剩余元素的索引（这是通过System.arraycopy完成的）。

锺离嘉茂

2023-03-14

小心。这里有一些陷阱。

事实上，有两个问题好坏参半：

如何以相反的顺序将数据从一个列表传输到另一个列表
如何从BigInteger创建数字列表

我同意Roman C的评论：“从一个列表移动到另一个列表是无用的”。至少，在这种情况下，它似乎是无用的。但是，如果圣殿骑士发生了什么事情，并且从一个列表中删除元素并将其添加到另一个列表（一个接一个）的一般方法在任何方面都是合理的，那么对于这种特殊情况，如何提高性能的问题可能仍然是可行的。

关于如何以相反的顺序将数据从一个列表传输到另一个列表的核心问题：

令人惊讶的是，以现在的形式，

...第二段比第一段慢得多！

（解释如下）

像这样一个简单的测试比较了这两种方法。（当然，像这样的“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));

这是这种情况下的罪魁祸首：您有一个Intger对象的列表。您正在调用删除，传入一个Intger对象。此方法将搜索整个列表，并删除第一次出现的参数。这不仅速度慢，还会导致结果明显错误！

实际上，您要做的是使用最后一个元素的索引删除最后一个元素。所以把这行改成

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
...

所以，如果实施得当

...第一段比第二段慢得多！

因为埃兰在回答中提到的原因。

关于如何从biginger创建数字列表的问题：有几种可能的性能改进。

手动提取数字，使用一系列%=10和/=10调用非常慢。避免模运算已经带来了一点加速。所以代替

digit = number % 10;
number = number / 10;

你可以做的

nextNumber = number / 10;
digit = number - (nextNumber * 10);
number = nextNumber;

但由于biginger的不变性和昂贵的除法，这仍然比简单地将biginger转换为字符串并从中提取数字慢几个数量级，正如达斯宾莱特在回答中所建议的那样。

一个简单的比较：

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方法比手动方法快100多倍。

将整数拆分为数字的最快方法是什么？

共有3个答案

相关问答

相关文章

相关阅读

相关工具

相关文档