Самый быстрый способ дополнить число в Java до определенного количества цифр

Я пытаюсь создать хорошо оптимизированный бит кода для создания количества X-цифр в длину (где X читается из файла свойств среды выполнения) на основе сгенерированного БД порядкового номера (Y), который затем используется папка -имя при сохранении файла.

На данный момент я придумал три идеи, самая быстрая из которых - последняя, ​​но я был бы признателен за любые советы, которые люди могут дать по этому поводу...

1) Создайте экземпляр StringBuilder с начальной емкостью X. Добавьте Y. Пока длина ‹ X, вставьте ноль в нулевой позиции.

2) Создайте экземпляр StringBuilder с начальной емкостью X. Пока длина ‹ X, добавьте ноль. Создайте DecimalFormat на основе значения StringBuilder, а затем отформатируйте число, когда это необходимо.

3) Создайте новый int Math.pow( 10, X ) и добавьте Y. Используйте String.valueOf() для нового числа, а затем подстроку (1) его.

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

Итак, какие-нибудь советы? Используя цикл for из 10 000 итераций, я получаю аналогичные тайминги первых двух, а третий метод примерно в десять раз быстрее. Это кажется правильным?

Полный код тестового метода ниже...

    // Setup test variables
    int numDigits = 9;
    int testNumber = 724;
    int numIterations = 10000;
    String folderHolder = null;
    DecimalFormat outputFormat = new DecimalFormat( "#,##0" );

    // StringBuilder test
    long before = System.nanoTime();
    for ( int i = 0; i < numIterations; i++ )
    {
        StringBuilder sb = new StringBuilder( numDigits );
        sb.append( testNumber );
        while ( sb.length() < numDigits )
        {
            sb.insert( 0, 0 );
        }

        folderHolder = sb.toString();
    }
    long after = System.nanoTime();
    System.out.println( "01: " + outputFormat.format( after - before ) + " nanoseconds" );
    System.out.println( "Sanity check: Folder = \"" + folderHolder + "\"" );

    // DecimalFormat test
    before = System.nanoTime();
    StringBuilder sb = new StringBuilder( numDigits );
    while ( sb.length() < numDigits )
    {
        sb.append( 0 );
    }
    DecimalFormat formatter = new DecimalFormat( sb.toString() );
    for ( int i = 0; i < numIterations; i++ )
    {
        folderHolder = formatter.format( testNumber );
    }
    after = System.nanoTime();
    System.out.println( "02: " + outputFormat.format( after - before ) + " nanoseconds" );
    System.out.println( "Sanity check: Folder = \"" + folderHolder + "\"" );

    // Substring test
    before = System.nanoTime();
    int baseNum = (int)Math.pow( 10, numDigits );
    for ( int i = 0; i < numIterations; i++ )
    {
        int newNum = baseNum + testNumber;
        folderHolder = String.valueOf( newNum ).substring( 1 );
    }
    after = System.nanoTime();
    System.out.println( "03: " + outputFormat.format( after - before ) + " nanoseconds" );
    System.out.println( "Sanity check: Folder = \"" + folderHolder + "\"" );

person Martin    schedule 07.06.2010    source источник
comment
Будьте осторожны с микробенчмаркингом JVM: java.sun.com/docs/hotspot/HotSpotFAQ .html#benchmarking_simple   -  person BalusC    schedule 07.06.2010
comment
Ваш код обращается к жесткому диску, и вы беспокоитесь о производительности форматирования строк для создания имен файлов? Шутки в сторону?   -  person Michael Borgwardt    schedule 07.06.2010
comment
На самом деле, это будет использование GPFS через WebDAV и/или Amazon S3. Я просто пытаюсь оптимизировать все, что могу, пока строю вещь. Кроме того, теперь это стало академическим упражнением и для меня!   -  person Martin    schedule 07.06.2010
comment
Академическое упражнение на то, сколько времени вы можете потратить на зло преждевременной оптимизации? Серьезно, это действительно, действительно, бессмысленно. ЕСЛИ вы идете по сети, это вероятно, даже *больше не имеет значения, чем если вы пишете на HD.   -  person Michael Borgwardt    schedule 07.06.2010
comment
Преждевременная оптимизация обычно наносит вред вашей архитектуре... вы можете создавать быстрое программное обеспечение, но оно может быть непригодным для сопровождения и непонятным... Начните строить архитектурно разумную вещь, а затем оптимизируйте, если вы видите в этом необходимость.   -  person Erk    schedule 26.02.2014


Ответы (5)


Я бы перестал делать оптимизации на основе микротестов и выбрал бы что-то, что выглядит элегантно с точки зрения кода, например String.format("%0"+numDigits+"d", testNumber)

person aioobe    schedule 07.06.2010
comment
Все это имеет смысл, но, согласно микротестированию, это НАМНОГО медленнее. Действительно ли этот материал бесполезен, потому что я получаю результаты, которые предполагают, что String.format в 100 раз медленнее, чем подстрока int. Неужели в нем нет никакой полезности? - person Martin; 07.06.2010
comment
Вы должны быть осторожны при интерпретации цифр из микротестов. В некоторых ситуациях компилятор/JIT-компилятор оптимизирует большие фрагменты кода, если он понимает, что это не нужно. Например, совершенно очевидно, что (в третьем случае) newNum останется неизменным во всех итерациях. Это, в свою очередь, потенциально может привести к тому, что String.valueOf(newNum).substring(1); будет помещено за пределы цикла, что разрушит весь тест. - person aioobe; 07.06.2010
comment
Я создал int[] длиной 10 000, а затем вставил случайное число от 0 до 10 000 в каждую позицию и повторно запустил тесты, и тайминги были почти идентичными. Я очарован и предпочитаю удобочитаемость средств String.format для создания числа, но трудно игнорировать тайминги: StringBuilder: 31 317 244 наносекунды DecimalFormat: 36 368 634 наносекунды Substring: 2 623 557 наносекунд String.format: 184 692 956 наносекунд - person Martin; 07.06.2010
comment
Попробуйте добавить фактическое создание папки (с именем folderHolder) к каждой итерации. Получаете ли вы такую ​​же процентную разницу между тестами? Или вычисление имени папки незначительно? - person aioobe; 07.06.2010
comment
Никакой разницы, от включения объявления объекта String внутри цикла. - person Martin; 07.06.2010
comment
Я имел в виду часть mkdir. (Я предполагаю, что это тоже необходимо, возможно, я ошибаюсь?) - person aioobe; 07.06.2010
comment
@Martin: Вы говорите, что используете эту процедуру для создания имени файла или каталога. Если учесть время, необходимое для доступа к диску, насколько важно, по вашему мнению, оптимизировать эту часть вашего кода? - person jarnbjo; 07.06.2010
comment
На самом деле, это будет использование GPFS через WebDAV и/или Amazon S3. Я просто пытаюсь оптимизировать все, что могу, пока строю вещь. Кроме того, теперь это стало академическим упражнением и для меня! - person Martin; 07.06.2010
comment
Я считаю, что время, необходимое для выполнения вызова String.format, незначительно по сравнению с ним. Мое предложение: используйте самый чистый и читаемый код. - person aioobe; 07.06.2010

Используйте String.format("%0[длина]d", я)

Для длины 8 это будет

String out = String.format("%08d", i);

Это медленнее, но время, затрачиваемое на ввод и отладку более сложного кода, вероятно, превысит общее дополнительное время, которое когда-либо использовалось во время выполнения.

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

person Skip Head    schedule 07.06.2010

Вставка символов заполнения один за другим явно медленная. Если производительность действительно так важна, вы можете вместо этого использовать предопределенные строковые константы длины 1..n-1 (где n — наибольшая ожидаемая длина), хранящиеся в ArrayList по соответствующим индексам.

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

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

person Péter Török    schedule 07.06.2010

Вот решение, которое в основном то же самое, что и ваш StringBuilder, с двумя оптимизациями:

  1. Он напрямую записывает в массив, минуя накладные расходы StringBuilder.
  2. Он выполняет операции в обратном порядке вместо вставки (0), которая каждый раз требует копирования массива.

Он также делает предположения, что numDigits будет >= фактическим требуемым символам, но будет правильно обрабатывать отрицательные числа:

before = System.nanoTime();
String arrString=null;
for ( int j = 0; j < numIterations; j++ ){
  char[] arrNum = new char[numDigits];
  int i = numDigits-1;
  boolean neg = testNumber<0;
  for(int tmp = neg?-testNumber:testNumber;tmp>0;tmp/=10){
    arrNum[i--] = (char)((tmp%10)+48);
  }
  while(i>=0){
    arrNum[i--]='0';
  }
  if(neg)arrNum[0]='-';
  arrString = new String(arrNum);
}
after = System.nanoTime();
System.out.println( "04: " + outputFormat.format( after - before ) + " nanoseconds" );
System.out.println( "Sanity check: Folder = \"" + arrString + "\"" );

Этот метод значительно превзошел ваши образцы на моей машине для негативов и был сопоставим для позитивов:

01: 18,090,933 nanoseconds
Sanity check: Folder = "000000742"
02: 22,659,205 nanoseconds
Sanity check: Folder = "000000742"
03: 2,309,949 nanoseconds
Sanity check: Folder = "000000742"
04: 6,380,892 nanoseconds
Sanity check: Folder = "000000742"

01: 14,933,369 nanoseconds
Sanity check: Folder = "0000-2745"
02: 21,685,158 nanoseconds
Sanity check: Folder = "-000002745"
03: 3,213,270 nanoseconds
Sanity check: Folder = "99997255"
04: 1,255,660 nanoseconds
Sanity check: Folder = "-00002745"

Редактировать: я заметил, что ваши тесты возобновили некоторые объекты в цикле итерации, чего я не делал в своем (например, не пересчитывал baseNum в версии подстроки). Когда я изменил тесты, чтобы они были согласованными (без повторения каких-либо объектов/расчетов, моя версия работала лучше, чем ваша:

01: 18,377,935 nanoseconds
Sanity check: Folder = "000000742"
02: 69,443,911 nanoseconds
Sanity check: Folder = "000000742"
03: 6,410,263 nanoseconds
Sanity check: Folder = "000000742"
04: 996,622 nanoseconds
Sanity check: Folder = "000000742"

Конечно, как уже упоминали другие, микротестирование невероятно сложно / «нечетко» со всей оптимизацией, выполняемой виртуальной машиной, и невозможностью их контролировать.

person M. Jessup    schedule 07.06.2010

В этой, вероятно, связанной ссылке обсуждаются многие способы сделать это. Я бы порекомендовал вариант Apache, StringUtils, он может быть или не быть самым быстрым, но обычно он один из самых простых для понимания, и из него выбито )&##@, поэтому он, вероятно, не сломается. в каком-то непредвиденном пограничном случае. ;)

person mezmo    schedule 07.06.2010