Java BigInteger 替代方案

Question

有没有一种方法可以通过缓存来提高BigInteger的性能？

当你对BigInteger进行操作时，它总是创建一个新的BigInteger。例如，当您乘以两个大整数时，会创建一个新的BigInteger来保存结果。我想使用某种可变版本的BigInteger，它将使用结果更新其中一个字段。

- Ilya Gazman

---

你做错了。如果你想提高性能，一开始就不要使用 BigInteger。你想要解决的性能瓶颈是什么？ - Tunaki

一个技术上的答案是编写你自己的实现，但可能更好的是@Tunaki说的。如果你正在以这样密集的方式使用BigInteger，以至于它实际上影响了性能，那么你应该使用其他东西。如果你必须使用BigInteger，那么就要接受它所带来的性能损失。 - Gorbles

换句话说，您正在寻找某种可修改的大整数（ModifyableBigInteger）？ - tobias_k

@tobias_k 是的，有些类似这样的东西。 - Ilya Gazman

@Tunaki 我正在实现整数因子分解，我正在使用gcm（），乘法，模，除法，以及BigInteger提供的所有功能。决定不使用BigInteger并不是一件那么简单的事情... - Ilya Gazman

Answer 1

我怀疑如果你以某种方式这样做，你的算法性能不会有所提高，但主要原则是BigInteger是不可变的。你无法在不生成新实例的情况下对其执行操作，这是有好的理由希望它有这种行为 - 即，如果您有多个线程操作单个BigInteger，您可以放心这些线程不会直接覆盖该BigInteger。

如果您不想要此行为，则唯一的选择是创建一个新类，但请记住，您仍然将在某个层面上处理BigInteger的不可变性。

^{*：就像长时间不重新分配变量一样...}

- Makoto

---

你仍然需要在某个层面上处理BigIntegers的不可变性。或者，你可以从头开始重新实现大整数（呸）。 - John Dvorak

@JanDvorak：为什么要重复造轮子呢？:P - Makoto

@Makoto：车轮每时每刻都在被重新发明。在这种情况下，很可能会这样做是为了获得所需的可变BigInt类。;-) 事实是，可以在不涉及BigInteger的不可变性的情况下完成它。 - Rudy Velthuis

拥有可变的替代方案将极大地改善内存重新分配。关于多线程的论点，为不同目的拥有专用的可变和不可变版本有何不妥之处？就像我们拥有普通和并发集合一样。 - ruX

Answer 2

有可变的 BigInteger 版本存在（例如：https://github.com/bwakell/Huldra），或者你可以自己编写。使用可变对象可能会减少垃圾回收器的压力。你真的应该对你的应用程序进行基准测试，以确定是否值得这样做。

- David Soroko

---

实际上，Java也有一个MutableBigInteger类，但它仅在内部使用。 - Rudy Velthuis

有趣 - 也被 BigInteger 使用 - David Soroko

Answer 3

您所要求的操作，除了加法之外，不太可能在性能上有任何提升。原因是几乎所有数学运算（除了上述的加法）得到的结果位数都不同于原始数字。您几乎总是需要为结果分配一个新数字并将其复制回原始数字，实际上只会使它变得更慢。

然而，如果您只需要进行加/减操作，则可以做到，并且实际上可能会更快，因为不需要为加法分配新数组。

几乎所有其他函数最好委托给BigInteger类。

class MutableBigInteger {
    BigInteger n;

    public MutableBigInteger add (MutableBigInteger n) {
        this.n = this.n.add(n.n);
        return this;
    }
}

- OldCurmudgeon

---

这只有在您执行一个操作时才是正确的，但考虑下一个例子：ab/cd，它变得更加复杂。此外，这使我可以在未来的操作中重用我的BigInteger。 - Ilya Gazman

如果最高位相加有进位，则数组必须比原始数组多1个位。此外，两个不同值通常大小不同，因此即使进行加法或减法运算，也经常需要重新分配空间。 - Rudy Velthuis

Huldra的基准测试似乎与您的观点不符。我想知道这些基准测试在Java 8 BigInteger面前会表现如何。 - President James K. Polk