рефакторинг Java-массивов и примитивов (double [] []) в Collections and Generics (список <список <Double>>)

Question

Я занимаюсь рефакторингом одноразового кода, который я написал несколько лет назад в стиле фортрана. Большая часть кода теперь намного более организована и удобочитаема. Однако ядро ​​алгоритма (которое критично к производительности) использует одномерные и двухмерные массивы Java и характеризуется:

    for (int j = 1; j < len[1]+1; j++) {
        int jj = (cont == BY_TYPE) ? seq[1][j-1] : j-1;
        for (int i = 1; i < len[0]+1; i++) {
            matrix[i][j] = matrix[i-1][j] + gap;
            double m = matrix[i][j-1] + gap;
            if (m > matrix[i][j]) {
                matrix[i][j] = m;
                pointers[i][j] = UP;
            }
            //...
        }
    }

Для ясности, удобства сопровождения и взаимодействия с остальным кодом, я бы хотел его реорганизовать. Однако при чтении Синтаксис Java Generics для массивов и Generics Java и число s У меня есть следующие проблемы:

• Производительность. Планируется, что код будет использовать около 10 ^ 8 - 10 ^ 9 секунд в год, и это почти управляемо. Мое чтение предполагает, что изменение double на Double иногда может увеличить производительность в 3 раза. Я хотел бы другой опыт по этому вопросу. Я также ожидал бы, что переход от foo [] к List также станет хитом. У меня нет знаний из первых рук, и снова опыт будет полезен.

• Проверка массива. По-разному ли это трактуется в double [] и List и имеет ли это значение? Я ожидаю, что некоторые проблемы нарушат границы, поскольку алгоритм довольно прост и применяется только к нескольким наборам данных.

• Если я не осуществлю рефакторинг, тогда в коде будет ужасная и, возможно, хрупкая смесь двух подходов. Я уже пытаюсь написать такие вещи, как:

  Список и Список []

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

• устаревание. Один из авторов предложил, чтобы массивы Java были устаревшими. Я предполагаю, что этого не произойдет, но я хотел бы отойти от устаревших подходов.

РЕЗЮМЕ Консенсус на данный момент:

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

• Для строгих числовых (научных) алгоритмов запись массива [] [] на самом деле проще для чтения, но переменные должны быть названы как можно более полезными

• Обобщения и массивы не очень хорошо сочетаются. Может быть полезно обернуть массивы в классы, чтобы транспортировать их в / из строгого алгоритма.

Существует небольшая объективная причина для внесения изменений

ВОПРОС @SeanOwen предположил, что было бы полезно извлечь постоянные значения из циклов. Предполагая, что я не дурак, это будет выглядеть так:

 int len1 = len[1];
 int len0 = len[0];
 int seq1 = seq[1];
 int[] pointersi;
 double[] matrixi;
 for (int i = 1; i < len0+1; i++) {
     matrixi = matrix[i];
     pointersi = pointers[i];
 }
 for (int j = 1; j < len1+1; j++) {
    int jj = (cont == BY_TYPE) ? seq1[j-1] : j-1;
    for (int i = 1; i < len0+1; i++) {
        matrixi[j] = matrixi[j] + gap;
        double m = matrixi[j-1] + gap;
        if (m > matrixi[j]) {
            matrixi[j] = m;
            pointersi[j] = UP;
        }
        //...
    }
}

Я думал, что компиляторы предназначены для умения делать подобные вещи. Нужно ли еще это делать?

Answer 1

Я прочитал отличную книгу Кента Бека о лучших методах кодирования (http://www.amazon.com/Implementation-Patterns/dp/B000XPRRVM). Есть также интересные показатели производительности. В частности, существует сравнение между массивами и различными коллекциями. И массивы действительно намного быстрее (возможно, в 3 раза по сравнению с ArrayList).

Кроме того, если вы используете Double вместо double, вам нужно придерживаться его и не использовать double, так как автоматический (не) бокс убьет вашу производительность.

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

---

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

Однако, если вам не нравится, что переменная верхней границы, используемая только в цикле, доступна вне цикла, вы можете воспользоваться фазой инициализации цикла for следующим образом:

    for (int i=0, max=list.size(); i<max; i++) {
      // do something
    }

---

Я не верю в устаревание массивов в Java. Для цикла, критичного к производительности, я не вижу, чтобы какой-либо конструктор языков убрал самый быстрый вариант (особенно, если разница равна x3).

---

Я понимаю ваше беспокойство по поводу ремонтопригодности и согласованности с остальной частью приложения. Но я считаю, что критический цикл имеет право на некоторые специальные практики.

Я бы постарался сделать код максимально понятным, не меняя его:

• путем осторожного опроса каждого имени переменной , в идеале с 10-минутным сеансом мозгового штурма с моими коллегами
• , написав кодирование комментариев (я против их использования в целом, поскольку неясный код следует разъяснять, а не комментировать; но критический цикл оправдывает это).
• используя приватные методы по мере необходимости (как указал Andreas_D в своем ответе). Если сделать private final, очень велики шансы (так как они будут короткими), что они будут встроены во время работы, поэтому не будет никакого влияния на производительность во время выполнения.

Answer 2

Я полностью согласен с ответом KLE. Поскольку код критичен к производительности, я бы также сохранил структуры данных на основе массива. И я полагаю, что просто введение коллекций, оболочек для примитивных типов и обобщений не улучшит удобство обслуживания и ясность.

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

Для ясности, ремонтопригодности и взаимодействие с остальной частью кода Я хотел бы провести рефакторинг.

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

Просто пример: один 2-мерный массив называется просто «матрица». Но очевидно, что это матрица, поэтому называть ее «матрицей» довольно избыточно. Было бы более полезно переименовать его, чтобы было понятно, для чего эта матрица действительно используется, какие данные находятся внутри.

Другой кандидат - ваша вторая строка. С помощью двух рефакторингов я переименовал бы jj во что-то более значимое и переместил бы выражение в закрытый метод с «говорящим» именем.

Answer 3

Общее правило - предпочитать обобщенные коллекции массивам в Java, но это всего лишь руководство. Моей первой мыслью было бы НЕ менять этот рабочий код. Если вы действительно хотите внести это изменение, сравните оба подхода.

Как вы говорите, производительность имеет решающее значение, и в этом случае код, который соответствует необходимой производительности, лучше, чем код, который этого не делает.

Вы также можете столкнуться с проблемами автобоксирования при упаковке / распаковке двойников - потенциально более тонкая проблема.

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

Answer 4

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

double[][] matrix = new double[10][10];
double t = matrix[0][0];

List<List<Double>> matrix = new ArrayList<List<Double>>(10);
Collections.fill(matrix, new ArrayList<Double>(10));
double t = matrix.get(0).get(0); // autoboxing => performance

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

Answer 5

Я думал, что компиляторы должны быть умно делать такие вещи. Делать нам все еще нужно это сделать?

Вы, вероятно, правы, что JIT позаботится об этом, но если этот раздел настолько критичен по производительности, попытка и сравнение не повредят.

Answer 6

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

• Действительно, не вычисляйте границы цикла каждый раз, сохраняйте их
• Вы неоднократно ссылаетесь на матрицу [i]. Просто сохраните ссылку на этот подмассив вместо разыменования двумерного массива каждый раз
• Этот трюк становится еще более полезным, если вы можете зацикливаться на i во внешнем цикле вместо внутреннего цикла
• Это становится экстремально, но сохранение значения j-1 в локальной системе может даже оказаться лучше, чем пересчет
• Наконец, если вы действительно беспокоитесь о производительности, запустите оптимизатор ProGuard над полученным байтовым кодом, чтобы он выполнил некоторые оптимизации компилятора, такие как развертывание или оптимизация глазка

Answer 7

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