如何优化Karatsuba算法(使用arraylist和java)

Question

我使用Karatsuba算法乘法两个多项式并返回系数，我使用java，这里要求我们使用数组，但是，我的代码太复杂了，运行时间比我预期的要长得多，有人能帮我减少运行时间并简化代码吗？非常感谢!

public static List<Long> smellCosmos(List<Long> a, List<Long> b) {
    int n = a.size();
    int n1 = a.size() / 2;

    List<Long>c = new ArrayList<Long>();

    if (n == 1) {
        c.add(0, a.get(0) * b.get(0));
        return c;
    };

    List<Long>ahigh = new ArrayList<Long>(n1);

    List<Long>alow = new ArrayList<Long>(n1);

    List<Long>amed = new ArrayList<Long>(n1);

    List<Long>bhigh = new ArrayList<Long>(n1);

    List<Long>blow = new ArrayList<Long>(n1);

    List<Long>bmed = new ArrayList<Long>(n1);

    for (int i = 0; i < n1; i++) {
        ahigh.add(a.get(i));
        alow.add(a.get(i + n1));
        amed.add(alow.get(i) + ahigh.get(i));
        bhigh.add(b.get(i));
        blow.add(b.get(i + n1));
        bmed.add(blow.get(i) + bhigh.get(i));
    }

    List<Long>chigh = smellCosmos(ahigh, bhigh);
    List<Long>clow = smellCosmos(alow, blow);
    List<Long>cmed = smellCosmos(amed, bmed);

    for (int j = 0; j < n1; j++)
        c.add(chigh.get(j));

    for (int m = 0; m < cmed.size(); m++)
        c.add(cmed.get(m) - chigh.get(m) - clow.get(m));

    for (int g = cmed.size() - n1; g < clow.size(); g++)
        c.add(clow.get(g));

    for (int i = n1; i < chigh.size(); i++)
        c.set(i, c.get(i) + chigh.get(i));

    for (int i = 0; i < cmed.size() - n1; i++)
        c.set(n1 * 2 + i, c.get(n1 * 2 + i) + clow.get(i));


    return c;

}
```

Answer 1

减少运行时间

• 也许您可以使用subList来防止新的列表基本上是输入的一部分的副本？这节省了大量的自动装箱(如果算法实现正确的话，我假设这是瓶颈)。您可以对您的应用程序进行概要分析，以查看大部分时间花费在何处。

例如：ahigh = a.subList(0,n1);

• 您可以使用大小初始化List c，因为您知道它的长度。
• 尽可能使用addAll，如果可能的话，它将在内部使用更快的System.arrayCopy。