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

Question

我进行了很多操作，将数字分为单独的数字，将数字放入arraylist中，然后将此数字逐个传递给另一个Arraylist，以进行进一步的操作，直到模板为空，然后将下一个比以前大的数字更大。

我想知道哪种方法更快。

两种方法共有的部分：

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

哪种方式更快？考虑到这是数十亿美元的运营，并分配了数十亿美元的数字。我认为诸如collections.reverse（）之类的方法需要更多的时间，但是每次使用下一个数字的新数字更新时，我只会称其为“它”。但是以2我调用.size（）-1操作在每个操作中。

同样，数字越大 - 更新模板和从中获取数字之间的差距就越大，那么renverse（）方法调用越小。 该数字从1开始，到达无穷大。

模板主义者是有原因的，所以请不要建议绕过它。

其他问题：测量此类事情的最佳实践是什么？

Answer 1

警告。这里有一些陷入困境。

实际上，有两个问题混合在一起：

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

我同意：“从一个列表到另一个列表是没有用的” 。至少在这种情况下，它似乎没有用。但是，如果femplist发生了一些事情，并且以任何方式证明了从一个列表中删除元素并将其添加到另一个列表中的一般方法，那么提高此特定情况的性能仍然可能是可行的。

---

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

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

...第二片片段比 far 慢第一个！

（遵循说明）

这样的简单测试都比较了这两种方法。 （当然，像这样的“ Micorbenchs”应该用一粒盐进行，但是由于此处的性能与渐近运行时间有关，因此这里是

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对象的列表。您正在调用删除，以整数对象传递。此方法将搜索整个列表，并删除参数的第一次出现。这不仅很慢，还导致结果显然是错误的！

您实际想做的是使用最后一个元素的索引删除最后一个元素。 ，更改这条线以

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在他的回答中提到。

---

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

用％= 10和/= 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方法的速度比手动的方法快100倍以上。

Answer 2

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

1. 不必扭转阵列列表，正如您所认识的那样。

2. 删除阵列列表的最后一个元素比删除第一个元素要快，因为删除第一个元素涉及减少所有剩余元素的索引（通过System.ArrayCopy完成）。

Answer 3

两个片段都很慢。如果您想更快地做，请列出适当的尺寸，然后从背面填充。

此答案显示了如何获得所需的arraylist＆lteger＆lteger＆gt; gt;。现在您可以执行此操作：

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());

demo。