Циркулярный прирост: что лучше?

Question

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

return (++i == buffer.length) ? 0: i;

или

return ++i % buffer.length;

Есть ли у оператора modulo какие-либо недостатки? Это менее читабельно, чем первое решение?

EDIT:

Конечно, это должен быть ++ i, а не i ++, это изменилось.

РЕДАКТИРОВАТЬ 2:

Одно интересное примечание: я нашел первую строку кода в реализации ArrayBlockingQueue Дуга Ли.

Answer 1

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

Наиболее читаемая версия выглядит следующим образом:

return (i == buffer.length-1) ? 0 : i+1;

Использование ++ добавляет ненужный побочный эффект к проверке (не говоря уже о том, что я твердо считаю, что вы должны были использовать предварительное увеличение вместо этого)

В чем проблема с оригинальным кодом? Давайте посмотрим, не так ли?

return (i++ == N) ? 0 : i; // OP's original, slightly rewritten

Итак, мы знаем, что:

• i - post -инкремментированный, поэтому, когда i == N-1 перед оператором return, это вернет N вместо переноса в 0 немедленно
  • Это предназначено? В большинстве случаев намерением является использование N в качестве эксклюзива верхней границы
• Имя переменной i предполагает использование локальной переменной в соответствии с соглашением об именах, но так ли это на самом деле?
  • Необходимо дважды проверить, если это поле, из-за побочного эффекта

Для сравнения:

return (i == N-1) ? 0 : i+1; // proposed alternative

Здесь мы знаем, что:

• i не изменяется, не имеет значения, является ли это локальной переменной или полем
• Когда i == N-1, возвращается значение 0, что является более типичным сценарием

---

% подход

В качестве альтернативы вы также можете использовать версию % следующим образом:

return (i+1) % N;

В чем проблема с %? Ну, проблема в том, что хотя большинство людей думает, что это оператор по модулю , это НЕ! Это оператор Остаток ( JLS 15.17.3 ). Многие люди часто путают это. Вот классический пример:

boolean isOdd(int n) {
   return (n % 2) == 1; // does this work???
}

Этот код не работает !!! Возвращает false для всех отрицательных значений! Проблема в том, что -1 % 2 == -1, хотя математически -1 = 1 (mod 2).

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

Смотри также

• Википедия: операция по модулю

Answer 2

Не просите меня выбирать между двумя вариантами, которые содержат постинкремент (*), смешанный с оценкой выражения. Я скажу "нет".

(*) Обновление: Позднее оно было зафиксировано в прекременте.

Answer 3

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

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

Так что я бы сказал, что второй вариант «более правильный», но я бы использовал что-то вроде:

i = (i+1) % buffer.length;
return i;

Что, я думаю, не имеет ни одной из двух проблем.

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

public class asdf {

    static int i=0;
    static int[] buffer = {0,1,2};

    public static final void main(String args[]){
        for(int j=0; j<5; j++){
            System.out.println(buffer[getIndex()]);
        }
    }

    public static int getIndex(){
//      return (++i == buffer.length) ? 0: i;
//      return ++i % buffer.length;

//      i = (i++ == buffer.length) ? 0 : i;
//      return i;

//      i++;
//      if (i >= buffer.length) 
//      {
//        i = 0;
//      }
//      return i;

//      return (i+1 == buffer.length) ? 0 : i+1;

        i = (i+1) % buffer.length;
        return i;
    }

}

Ожидаемый результат: 1 2 0 1 2

Заранее извиняюсь, если есть ошибка кодирования с моей стороны, и я случайно кого-то оскорбляю! x.x

PS: +1 за предыдущий комментарий о неиспользовании постинкремента с проверками равенства (на самом деле я пока не могу изменить сообщения = /)

Answer 4

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

Пример:

255 % 7 == 3

Таким образом, если вы используете, например, байт (символ без знака), когда число катится после 255 (то есть ноль), это не приведет к 4. Должно привести к 4 (при 256% 7), поэтому он вращается правильно. Так что просто используйте тестирующие (if и ternary operator) конструкции на правильность

---

Если для достижения производительности, и , если число кратно 2 (то есть 2, 4, 8, 16, 32, 64, ...), используйте оператор &.

Так, если длина буфера равна 16, используйте:

n & 15

Если длина буфера равна 64, используйте 63:

n & 63

Они вращаются правильно, даже если число возвращается к нулю. Кстати, если число кратно 2, даже подход по модулю / остатку также будет соответствовать требованиям, т. Е. Он будет правильно вращаться. Но я могу рискнуть предположить, что & операция быстрее, чем % операция.

Answer 5

Разве версия i++ % buffer.length не будет иметь недостаток, заключающийся в том, что она продолжает увеличивать i, что может привести к тому, что она достигнет своего рода max_int / max_long / max_whwh лимит?

Кроме того, я бы разделил это на

i = (i++ == buffer.length) ? 0 : i;
return i;

, так как иначе у вас, скорее всего, будет ошибка.

Answer 6

Конечно, было бы удобнее использовать if:

i++;
if (i >= buffer.length) 
{
  i = 0;
}
return i;

Зависит от битов при изменении значения buffer.length.

Answer 7

Я думаю, что второе решение имеет явное преимущество в том, что оно работает, а первое - нет. Первое решение всегда возвращает ноль, когда i становится больше buffer.length, потому что i никогда не сбрасывается.

Оператор по модулю не имеет недостатков.

Answer 8

Стоит также отметить, что, если длина нашего буфера равна 2, тогда будет работать очень эффективная битовая манипуляция:

idx = (idx + 1) & (length - 1)

Answer 9

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

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

Мой совет: напишите, какой из них вы считаете наиболее подходящим (если это работает!), И попросите коллегу (если он у вас есть) оценить его. Если они не согласны, спросите другого коллегу - тогда иди с большинством голосов. # Codingbydemocracy

Answer 10

Это очень субъективно и зависит от того, что привыкли видеть ваши коллеги. Я лично предпочел бы первый вариант, поскольку он явно выражает то, что делает код, то есть, если длина буфера достигнута, сбрасывается до 0. Вам не нужно выполнять какое-либо математическое мышление или даже знать, что делает модуль (конечно, вы должен! :))