Java BigInteger, обрезать последнюю цифру

StackOverflow https://stackoverflow.com/questions/1144735

Вопрос

Довольно просто: если число BigInteger равно 543, я хочу, чтобы оно обрезало последнюю цифру и стало 54.

Два простых способа сделать это могут быть:

  1. Используйте строки, получите подстроку и создайте новое целое число с новым значением.
  2. Используйте метод деления BigIntegers с номером 10.(543/10 = 54,3 => 54)

Дело в том, что я буду это исполнять много раз с большими целыми числами, конечно.

Я предполагаю, что играть со строками будет медленнее, но опять же, я не так часто использовал Bigintegers и понятия не имею, насколько дорогой является операция «разделения».

Здесь важна скорость. Как это реализовать быстрее всего (с памятью нет проблем, только скорость)?

Другие решения также приветствуются.

Это было полезно?

Решение

Деление на 10 происходит намного быстрее, чем использование операции подстроки.Используя следующий тест, я получаю примерно 161 раз (соотношение пропорционально количеству битов)

    long divTime = 0;
    long substrTime = 0;
    final int bitsCount = 1000;

    for (int i = 0; i < 1000; ++i) {
        long t1, t2;
        BigInteger random = new BigInteger(bitsCount, new Random());

        t1 = System.currentTimeMillis();
        random.divide(BigInteger.TEN);
        t2 = System.currentTimeMillis();
        divTime += (t2 - t1);

        t1 = System.currentTimeMillis();
        String str = random.toString();
        new BigInteger(str.substring(0, str.length() - 1));
        t2 = System.currentTimeMillis();
        substrTime += (t2 - t1);
    }

    System.out.println("Divide: " + divTime);
    System.out.println("Substr: " + substrTime);
    System.out.println("Ratio:  " + (substrTime / divTime));

Другие советы

Разделить на 10, скорее всего, будет быстрее.

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

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

Самый быстрый способ — разделить число на 10 с помощью эффективной реализации внутреннего деления.Внутреннее устройство этой операции скрыто, но, безусловно, нетривиально, поскольку число хранится в системе счисления с основанием 2.

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

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

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

Один только toString(), вероятно, медленнее, чем подстрока.

Различные люди говорили, что деление на 10 будет быстрее, чем преобразование в строку и взятие подстроки.Чтобы понять почему, просто подумайте о вычислениях, связанных с преобразованием BigInteger в String и наоборот.Например: 

/* simplified pseudo code for converting +ve numbers to strings */
StringBuffer sb = new StringBuffer(...);
while (number != 0) {
   digit = number % 10;
   sb.append((char)(digit + '0'));
   number = number / 10;
}
return sb.toString();

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

если производительность имеет решающее значение...не используйте Java

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

Я уверен, что в Java деление int тоже будет быстрее.В противном случае их реализация виртуальной машины действительно странная.

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top