При необходимости переключитесь на BigInteger - PullRequest
6 голосов
/ 06 апреля 2010

Я читаю текстовый файл, который содержит числа в диапазоне [1, 10 ^ 100]. Затем я выполняю последовательность арифметических операций над каждым числом. Я хотел бы использовать BigInteger, только если число находится вне диапазона int / long. Один из подходов заключается в подсчете количества цифр в строке и переключении на BigInteger, если их слишком много. В противном случае я бы просто использовал примитивную арифметику, поскольку она быстрее. Есть ли лучший способ?

Есть ли причина, по которой Java не может сделать это автоматически, то есть переключиться на BigInteger, если int слишком мал? Таким образом, нам не придется беспокоиться о переполнении.

Ответы [ 7 ]

6 голосов
/ 06 апреля 2010

Я подозреваю, что решение использовать примитивные значения для целых и действительных чисел (сделано по соображениям производительности) сделало эту опцию невозможной. Обратите внимание, что Python и Ruby оба делают то, что вы просите.

В этом случае может потребоваться больше усилий для обработки меньшего специального случая, чем оно того стоит (вам нужен некоторый пользовательский класс для обработки двух случаев), и вы должны просто использовать BigInteger.

4 голосов
/ 06 апреля 2010

Есть ли причина, по которой Java не может сделать это автоматически, то есть переключиться на BigInteger, если int слишком мал?

Потому что это поведение программирования более высокого уровня, чем в настоящее время в Java. Язык даже не знает о классе BigInteger и о том, что он делает (т. Е. Его нет в JLS). Он знает только о Integer (среди прочего) для целей упаковки и распаковки.

Говоря о боксе / распаковке, int - это примитивный тип; BigInteger является ссылочным типом. Вы не можете иметь переменную, которая может содержать значения обоих типов.

1 голос
/ 22 июня 2011

Ява быстрая - действительно очень быстрая. Это только в 2-4 раза медленнее, чем c, а иногда так же быстро или чуть быстрее, когда большинство других языков в 10 раз (python) до 100x (ruby) медленнее, чем C / Java. (Кстати, Фортран тоже очень быстрый)

Частично это связано с тем, что он не выполняет такие функции, как переключение типов номеров. Возможно, но в настоящее время он может встроить такую ​​операцию, как "a * 5", всего за несколько байтов, представить, какие циклы он должен был бы пройти, если бы a был объектом. По крайней мере, это будет динамический вызов метода умножения, который будет в несколько сотен / тысяч раз медленнее, чем когда a просто целочисленное значение.

В наши дни, вероятно, в действительности Java может использовать JIT-компиляцию, чтобы лучше оптимизировать вызов и встроить его во время выполнения, но даже тогда очень немногие вызовы библиотек поддерживают BigInteger / BigDecimal, поэтому было бы МНОГО собственной поддержки совершенно новый язык.

Также представьте, как переключение с int на BigInteger вместо long сделает отладку видеоигр безумно сложной! (Да, каждый раз, когда мы перемещаемся в правую часть экрана, игра замедляется в 50 раз, код все тот же! Как это возможно?! ??)

1 голос
/ 06 апреля 2010

Результат использования 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");
}

в моей системе выдает:

длинный: 375 мс, bigd: 6296 мс, x16,79 больше, mylong: 516 мс, x 1,38 больше

Класс MyLong предназначен только для того, чтобы взглянуть на эффекты бокса, чтобы сравнить с тем, что вы получите с пользовательским классом BigOrLong.

1 голос
/ 06 апреля 2010

Вы можете прочитать значения в BigInteger с, а затем преобразовать их в long с, если они достаточно малы.

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
}

(Вы могли бы сделать возвращаемое значение List<Number> и иметь смешанный набор объектов BigInteger и Long, но это не выглядело бы очень хорошо и не улучшило бы производительность намного.)

Производительность может быть лучше , если большое количество чисел в файле достаточно мало, чтобы поместиться в long (в зависимости от сложности вычислений). Существует риск переполнения в зависимости от того, что вы делаете в primitiveCalculation, и вы теперь повторили код, (по крайней мере) удвоив потенциал ошибки, поэтому вам придется решить, действительно ли выигрыш в производительности того стоит.

Если ваш код чем-то похож на мой пример, вы, вероятно, получите больше выгоды от распараллеливания кода, чтобы вычисления и операции ввода-вывода не выполнялись в одном потоке - вам придется выполнить некоторые действия. довольно тяжелые расчеты для такой архитектуры с привязкой к процессору.

0 голосов
/ 07 апреля 2010

Было бы это возможно?Да.Но с ним много проблем.

Например, рассмотрим, что Java хранит ссылки на BigInteger, который фактически размещен в куче, но хранит int литералы ,Разницу можно прояснить в C:

int i;
BigInt* bi;

Теперь, чтобы автоматически переходить от литерала к ссылке, нужно обязательно как-то аннотировать литерал.Например, если был установлен самый старший бит типа int, то другие биты можно было бы использовать в качестве некоторого вида поиска в таблице для получения правильной ссылки.Это также означает, что вы получите BigInt** bi всякий раз, когда он переполнится.

Конечно, этот бит обычно используется для знака, и аппаратные инструкции в значительной степени зависят от него.Что еще хуже, если мы это сделаем, то аппаратное обеспечение не сможет обнаружить переполнение и установить флаги для его указания.В результате каждая операция должна сопровождаться каким-либо тестом, чтобы увидеть, произошло ли переполнение или произойдет (в зависимости от того, когда оно может быть обнаружено).

Все это добавит много накладных расходов к базовымцелочисленная арифметика, которая на практике сводила бы на нет все преимущества, которые вам приходилось начинать.Другими словами, предполагать, что BigInt быстрее, чем пытаться использовать int и обнаруживать условия переполнения, одновременно совмещая проблему со ссылкой / литералом.

Итак, чтобы получить какое-либо реальное преимущество, нужнопришлось бы использовать больше пробел для представления целых.Таким образом, вместо того, чтобы хранить 32 бита в стеке, в объектах или в любом другом месте, где мы их используем, мы храним, например, 64 бита и используем дополнительные 32 бита, чтобы контролировать, хотим ли мы ссылку или литерал.Это может сработать, но есть очевидная проблема - использование пространства.:-) Мы могли бы видеть больше этого с 64-битным оборудованием, однако.

Теперь вы можете спросить, почему бы не просто 40 бит (32 бита + 1 байт) вместо 64?В основном, на современном оборудовании предпочтительно хранить данные с шагом 32 бита из соображений производительности, поэтому мы все равно добавим от 40 до 64 бит.

EDIT

* 1026Давайте рассмотрим, как можно это сделать в 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, и класс позаботится об использовании того, что подходит лучше.

Обратите внимание, однако, что этот вид оптимизации вполне может быть частью BigInteger C #, учитывая его реализацию в виде структуры.

Если бы в Java было что-то вроде структуры C #, мы могли бы сделать что-то подобное и в Java.

0 голосов
/ 06 апреля 2010

Есть ли причина, по которой Java не смогла сделать это автоматически, т.е. переключиться на BigInteger, если int был слишком маленьким?

Это одно из преимуществ динамической типизации , но Java имеет статическую типизацию и предотвращает это.

В языке динамического типа, когда два Integer, которые суммируются вместе, вызовут переполнение, система может вернуть, скажем, Long. Поскольку язык с динамической типизацией полагается на типизацию с утиным типом, это нормально. То же самое не может произойти в статически типизированном языке; это сломало бы систему типов.

EDIT

Учитывая, что мой ответ и комментарий не были ясны, здесь я попытаюсь предоставить более подробную информацию, почему я считаю, что статическая типизация является основной проблемой:

1) тот факт, что мы говорим о примитивном типе , является проблемой статической типизации; нас не волнует язык динамического ввода.

2) с примитивными типами результат переполнения не может быть преобразован в другой тип, чем int, потому что это не будет корректно при статической типизации * w.r.t

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

3) со ссылочными типами, то же самое, за исключением того, что у нас есть автобокс. Тем не менее, дополнение не может вернуть, скажем, BigInteger, потому что оно не соответствует статической системе типов (A BigInteger не может быть приведено к 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, что нормально.

...