6

我正在阅读一个文本文件，其中包含 [1, 10^100] 范围内的数字。然后我对每个数字执行一系列算术运算。仅当数字超出 int/long 范围时，我才想使用 BigInteger。一种方法是计算字符串中有多少位，如果太多则切换到 BigInteger。否则我只会使用原始算术，因为它更快。有没有更好的办法？

如果 int 太小，Java 是否有任何理由不能自动执行此操作，即切换到 BigInteger？这样我们就不用担心溢出了。

4

7 回答 7

6

我怀疑将原始值用于整数和实数的决定（出于性能原因这样做）使该选项成为不可能。请注意，Python 和 Ruby 都按照您的要求执行。

在这种情况下，处理较小的特殊情况可能比它值得做的工作更多（你需要一些自定义类来处理这两种情况），你应该只使用BigInteger.

于 2010-04-06T17:56:56.773 回答
4

如果 int 太小，Java 是否有任何理由不能自动执行此操作，即切换到 BigInteger？

因为这是比 Java 当前更高级别的编程行为。该语言甚至不知道BigInteger类和它的作用（即它不在 JLS 中）。它只知道Integer（除其他外）装箱和拆箱目的。

说到装箱/拆箱，anint是原始类型；BigInteger是引用类型。你不能有一个变量可以同时保存这两种类型的值。

于 2010-04-06T18:22:42.383 回答
1

您可以将这些值读入BigIntegers，然后long如果它们足够小，则将它们转换为 s。

private final BigInteger LONG_MAX = BigInteger.valueOf(Long.MAX_VALUE);
private static List<BigInteger> readAndProcess(BufferedReader rd) throws IOException {
    List<BigInteger> result = new ArrayList<BigInteger>();
    for (String line; (line = rd.readLine()) != null; ) {
        BigInteger bignum = new BigInteger(line);
        if (bignum.compareTo(LONG_MAX) > 0) // doesn't fit in a long
            result.add(bignumCalculation(bignum));
        else result.add(BigInteger.valueOf(primitiveCalculation(bignum.longValue())));
    }
    return result;
}
private BigInteger bignumCalculation(BigInteger value) { 
    // perform the calculation 
}
private long primitiveCalculation(long value) {
    // perform the calculation
}

（您可以将返回值设为 a并将其作为对象和对象List<Number>的混合集合，但这看起来不太好，并且不会大大提高性能。）BigIntegerLong

如果文件中的大量数字足够小以适合 a （取决于计算的复杂性），则性能可能会更好。仍然存在溢出的风险，具体取决于您在 中所做的事情，并且您现在已经重复了代码，（至少）使错误可能性增加了一倍，因此您必须确定性能提升是否真的值得。longprimitiveCalculation

但是，如果您的代码与我的示例类似，您可能会通过并行化代码获得更多收益，这样计算和 I/O 就不会在同一个线程上执行 - 您必须进行一些非常繁重的计算像这样的架构受 CPU 限制。

于 2010-04-06T18:56:50.617 回答
1

当较小的东西就足够时使用 BigDecimals 的影响令人惊讶，错误，大：运行以下代码

public static class MyLong {
    private long l;
    public MyLong(long l) { this.l = l; }
    public void add(MyLong l2) { l += l2.l; }
}

public static void main(String[] args) throws Exception {
    // generate lots of random numbers
    long ls[] = new long[100000];
    BigDecimal bds[] = new BigDecimal[100000];
    MyLong mls[] = new MyLong[100000];
    Random r = new Random();
    for (int i=0; i<ls.length; i++) {
        long n = r.nextLong();
        ls[i] = n;
        bds[i] = new BigDecimal(n);
        mls[i] = new MyLong(n);
    }
    // time with longs & Bigints
    long t0 = System.currentTimeMillis();
    for (int j=0; j<1000; j++) for (int i=0; i<ls.length-1; i++) {
        ls[i] += ls[i+1];
    }
    long t1 = Math.max(t0 + 1, System.currentTimeMillis());
    for (int j=0; j<1000; j++) for (int i=0; i<ls.length-1; i++) {
        bds[i].add(bds[i+1]);
    }
    long t2 = System.currentTimeMillis();
    for (int j=0; j<1000; j++) for (int i=0; i<ls.length-1; i++) {
        mls[i].add(mls[i+1]);
    }
    long t3 = System.currentTimeMillis();
    // compare times
    t3 -= t2;
    t2 -= t1;
    t1 -= t0;
    DecimalFormat df = new DecimalFormat("0.00");
    System.err.println("long: " + t1 + "ms, bigd: " + t2 + "ms, x"
            + df.format(t2*1.0/t1) + " more, mylong: " + t3 + "ms, x"
            + df.format(t3*1.0/t1) + " more");
}

在我的系统上产生以下输出：

long：375ms，bigd：6296ms，x16.79 更多，mylong：516ms，x1.38 更多

该MyLong课程仅用于查看拳击的效果，与您使用自定义BigOrLong课程获得的效果进行比较。

于 2010-04-06T19:49:56.953 回答
1

Java 很快——真的很快。它只比 c 慢 2-4 倍，有时与大多数其他语言比 C/Java 慢 10 倍（python）到 100 倍（ruby）一样快或快一点。（顺便说一句，Fortran 也很快）

部分原因是它不会为您执行切换号码类型之类的操作。它可以，但目前它可以在几个字节内内联像“a * 5”这样的操作，想象一下如果 a 是一个对象，它必须经历的圈子。这至少是对 a 的乘法方法的动态调用，这将比 a 只是一个整数值时慢几百/千倍。

如今，Java 可能实际上可以使用 JIT 编译来更好地优化调用并在运行时内联它，但即便如此，也很少有库调用支持 BigInteger/BigDecimal，因此会有很多本机支持，这将是一种全新的语言.

还可以想象从 int 切换到 BigInteger 而不是 long 会使调试视频游戏变得非常困难！（是的，每次我们移动到屏幕右侧，游戏速度都会减慢 50 倍，代码都是一样的！这怎么可能？！？？）

于 2011-06-21T22:34:44.113 回答
0

有可能吗？是的。但它有很多问题。

例如，考虑 Java 存储对 BigInteger 的引用，BigInteger 实际上是在堆上分配的，但存储的是 int literals。在 C 中可以清楚地看出区别：

int i;
BigInt* bi;

现在，要自动从文字转为引用，必须以某种方式对文字进行注释。例如，如果设置了 int 的最高位，那么其他位可以用作某种类型的表查找以检索正确的引用。BigInt** bi这也意味着当它溢出时你会得到一个。

当然，这是通常用于符号的位，硬件指令几乎都依赖于它。更糟糕的是，如果我们这样做，那么硬件将无法检测溢出并设置标志来指示它。结果，每个操作都必须伴随一些测试，以查看是否发生溢出或将发生溢出（取决于何时可以检测到）。

所有这些都会给基本的整数算术增加很多开销，这实际上会抵消你必须开始的任何好处。换句话说，假设 BigInt 比尝试使用 int 并检测溢出条件同时处理引用/文字问题要快。

因此，要获得任何真正的优势，就必须使用更多的空间来表示整数。因此，我们不是在堆栈、对象或我们使用它们的任何其他地方存储 32 位，而是存储 64 位，并使用额外的 32 位来控制我们是否需要引用或文字。这可能行得通，但它有一个明显的问题——空间使用。:-) 不过，我们可能会在 64 位硬件上看到更多。

现在，您可能会问为什么不只是 40 位（32 位 + 1 字节）而不是 64 位？基本上，在现代硬件上，出于性能原因，最好以 32 位增量存储内容，因此无论如何我们都会将 40 位填充到 64 位。

编辑

让我们考虑如何在 C# 中执行此操作。现在，我没有使用 C# 的编程经验，所以我无法编写代码来完成它，但我希望我能给出一个概述。

这个想法是为它创建一个结构。它应该大致如下所示：

public struct MixedInt
{
   private int i;
   private System.Numeric.BigInteger bi;

   public MixedInt(string s) 
   {
      bi = BigInteger.Parse(s);
      if (parsed <= int.MaxValue && parsed => int.MinValue)
      {
          i = (int32) parsed;
          bi = 0;
      }   
   }

   // Define all required operations
}

因此，如果数字在整数范围内，我们使用 int，否则我们使用 BigInteger。操作必须确保根据需要/可能从一个过渡到另一个。从客户的角度来看，这是透明的。它只是一种 MixedInt 类型，该类负责使用更适合的类型。

但是请注意，这种优化很可能已经是 C# 的 BigInteger 的一部分，因为它是作为结构实现的。

如果 Java 有类似 C# 的结构，我们也可以在 Java 中做类似的事情。

于 2010-04-06T20:06:16.073 回答
-2

如果 int 太小，Java 是否有任何理由不能自动执行此操作，即切换到 BigInteger？

这是动态类型的优点之一，但 Java 是静态类型的，因此可以防止这种情况。

在动态类型语言中，当两个Integer相加会产生溢出时，系统可以自由返回，例如 a Long。因为动态类型语言依赖于鸭子类型，所以没问题。在静态类型语言中不会发生同样的情况。它会破坏类型系统。

编辑

鉴于我的回答和评论不清楚，在这里我尝试提供更多详细信息，为什么我认为静态类型是主要问题：

1）我们所说的原始类型是一个静态类型问题；我们不会关心动态类型语言。

2) 对于原始类型，溢出的结果不能转换为除 an 之外的其他类型，int因为它不是正确的静态类型

   int i = Integer.MAX_VALUE + 1; // -2147483648

3）对于引用类型，除了我们有自动装箱外，它是相同的。尽管如此，加法还是不能返回，比如说，a，BigInteger因为它与静态类型系统不匹配（ABigInteger不能被强制转换为Integer）。

  Integer j = new Integer( Integer.MAX_VALUE ) + 1; // -2147483648

4）可以做的是子类化，说，Number并实现在UnboundedNumeric内部优化表示的类型（表示独立性）。

 UnboundedNum k = new UnboundedNum( Integer.MAX_VALUE ).add( 1 ); // 2147483648

不过，这并不是原始问题的真正答案。

5）使用动态类型，例如

var d = new Integer( Integer.MAX_VALUE ) + 1; // 2147483648

会返回一个Long没问题的。

于 2010-04-06T19:05:05.307 回答