Эффективная проверка, если число делится на 3

Я ищу обзор кода, лучшие практики и оптимизации.

public final class DivThreeEfficiently {

    private DivThreeEfficiently() {}

    /**
     * Returns true if the input number is divisible by three. 
     * Else returns false.
     * 
     * @param n     the input number
     * @return      true if input number is divisible by three
     */
    public static boolean isMultipleOfThree(int n) {
        if(n < 0) n = -n;

        int evenCtr = 0;
        int oddCtr = 0;

        while (n != 0) {
            if ((n & 1) == 1) { 
                oddCtr++;
            } 
            n = n>>1;
            if ((n & 1) == 1) {
                evenCtr++;
            } 
            n = n>>1;
        }

        return evenCtr == oddCtr;
    }   
}

public class DivThreeEfficientlyTest {

    @Test
    public void testEvenNegative() {
        assertTrue(DivThreeEfficiently.isMultipleOfThree(-3));
        assertTrue(DivThreeEfficiently.isMultipleOfThree(-6));
        assertTrue(DivThreeEfficiently.isMultipleOfThree(-12));
    }

    @Test
    public void testEvenPositive() {
        assertTrue(DivThreeEfficiently.isMultipleOfThree(0));
        assertTrue(DivThreeEfficiently.isMultipleOfThree(3));
        assertTrue(DivThreeEfficiently.isMultipleOfThree(6));
    }


    @Test
    public void testOddNegative() {
        assertFalse(DivThreeEfficiently.isMultipleOfThree(-1));
        assertFalse(DivThreeEfficiently.isMultipleOfThree(-4));
        assertFalse(DivThreeEfficiently.isMultipleOfThree(-11));
    }

    @Test
    public void testOddPositive() {
        assertFalse(DivThreeEfficiently.isMultipleOfThree(1));
        assertFalse(DivThreeEfficiently.isMultipleOfThree(4));
        assertFalse(DivThreeEfficiently.isMultipleOfThree(11));
    }
}
46 голосов | спросил JavaDeveloper 3 J0000006Europe/Moscow 2014, 01:48:46

8 ответов


109

Компьютеры - это не люди. Человеку может быть проще всего применить правило делимости. Однако на компьютере все равно.

Простейшим кодом будет проверка n % 3 == 0. Оператор modulo использует код операции JVM irem , который примерно так же эффективен, как вы можете получить.

На процессоре Intel, irem, вероятно, реализован с использованием IDIV ( подписанное разделение) . На большинстве современных x86-совместимых процессоров IDIV с 32-разрядным операндом использует от 10 до 30 микро- и имеет латентность от 20 до 61 тактов. Что еще более важно, тенденция к более новому и более мощному оборудованию для IDIV занимает меньше тактовых циклов. Другими словами, запись программы, как если бы это был RISC-процессор, является контрпродуктивной «оптимизацией» - было бы лучше, если бы аппаратное обеспечение полностью выполнило операцию деления.

Для сравнения € |

javap -c DivThreeEfficiently

 public final class DivThreeEfficiently {
  public static boolean isMultipleOfThree(int);
    Code:
       0: iload_0       
       1: ifge          7
       4: iload_0       
       5: ineg          
       6: istore_0      
       7: iconst_0      
       8: istore_1      
       9: iconst_0      
      10: istore_2      
      11: iload_0       
      12: ifeq          46
      15: iload_0       
      16: iconst_1      
      17: iand          
      18: iconst_1      
      19: if_icmpne     25
      22: iinc          2, 1
      25: iload_0       
      26: iconst_1      
      27: ishr          
      28: istore_0      
      29: iload_0       
      30: iconst_1      
      31: iand          
      32: iconst_1      
      33: if_icmpne     39
      36: iinc          1, 1
      39: iload_0       
      40: iconst_1      
      41: ishr          
      42: istore_0      
      43: goto          11
      46: iload_1       
      47: iload_2       
      48: if_icmpne     55
      51: iconst_1      
      52: goto          56
      55: iconst_0      
      56: ireturn       
}

Div3MoreEfficiently.java

public class Div3MoreEfficiently {
    private Div3MoreEfficiently() {}

    public static boolean isMultipleOfThree(int n) {
        return n % 3 == 0;
    }
}

javap -c Div3MoreEfficiently

 public class Div3MoreEfficiently {
  public static boolean isMultipleOfThree(int);
    Code:
       0: iload_0       
       1: iconst_3      
       2: irem          
       3: ifne          10
       6: iconst_1      
       7: goto          11
      10: iconst_0      
      11: ireturn       
}
ответил 200_success 3 J0000006Europe/Moscow 2014, 02:01:20
38

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

Я бы предположил, что если число положительное, вы можете начать с добавления верхних 11 бит к середине 10 и ниже 10. Это даст 12-битное значение, которое будет кратно 3 тогда и только тогда, когда Первоначальное значение было (назовите это значение Q). Умножьте Q на 0x5556 и сдвиньте вправо на 16, умножьте на 3 и вычтите из Q. Этот результат будет равен нулю тогда и только тогда, когда исходное число было кратно трем. Для процессоров с однократным умножением, но с 32-тактным делением, этот подход может оказаться заметно быстрее, чем использование инструкции деления. Что-то вроде

int Q = (n >> 20) + ((n >> 10) & 0x3FF) + (n & 0x3FF);
Q -= ((Q*0x5556) >> 16)*3; // Divide Q by three and then multiply by 3 to get remainder
// Q will be zero if and only if the original number was a multiple of three

Альтернативный подход, который может быть быстрее на некоторых процессорах, будет следующим:

if (n<0) n=-n;
int q = (int)((n*0x55555556L) >> 32);
n=n-q-q-q;    
return n==0;

Хорошо ли это будет работать, зависит от того, признает ли JITter, что оба аргумента для умножения long на самом деле являются int.

ответил supercat 3 J0000006Europe/Moscow 2014, 03:54:46
32

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

int mask = 0x2AAAAAAA; // special handling for the sign bit
int diff = 2 * Integer.bitCount(x & mask) + Integer.bitCount(x & ~mask);

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

Теперь у нас есть число от 0 до 48, которое делится на 3, если if x делится на 3. Самый быстрый способ - это, вероятно, таблица, упакованная в один long.

 return (TABLE << diff) < 0;

ИЗМЕНИТЬ

Я немного изменил приведенный выше код, чтобы упростить объяснение.

Остальная по модулю 3 такая же для 1 и 10, что и 10% 3 = 1, а это означает, что в десятичной позиции позиция цифры не имеет значения для этого остатка. Это приводит к известному правилу суммы цифр .

В двоичном выражении это работает не так, как 2% 3! = 1. Но 4% 3 = 1, поэтому мы можем переписать (8 * a + 4 * b + 2 * c + d)% 3 = (2 * (a + c) + (b + d))% 3. Так как каждая цифра равна нулю или одной, все, что нам нужно, - это подсчет единиц в соответствующих позициях. Поскольку вес самого старшего бита равен -2 ** 31, ему нужна специальная обработка (см. Маску).

ИЗМЕНИТЬ

Я вижу, что я пропустил тривиальную оптимизацию. Это весь код после этого:

private static final long TABLE = 0x9249249249240000L;

int diff = Integer.bitCount(x & 0x2AAAAAAA) + Integer.bitCount(x);
return (TABLE << diff) < 0;

ИЗМЕНИТЬ

Исправлено (long ТАБЛИЦА необходимо) и полностью тестировалось для всех int s.

ЭТАЛОН

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

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

ВЕРОЯТНЫЙ ПОБЕДИТЕЛЬ

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

ответил maaartinus 3 J0000006Europe/Moscow 2014, 08:34:04
18

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

for (int i=-100000; i<100000; i++)
    assertEquals(DivThreeEfficiently.isMultipleOfThree(i), i%3==0);

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

ответил Jerry Coffin 3 J0000006Europe/Moscow 2014, 01:59:26
17

Поскольку ваша первоначальная реализация не дает правильных результатов для 21, 42, 69, 81, 84, 87 и 93 (это всего лишь от 0 до 100!), я хотел бы предоставить более «общий» способ рассмотрим вопрос делимости на три. Это то, что делают многие люди, когда они сталкиваются с числом с большим количеством цифр и хотят определить, делится ли он на три или нет:

  

Число делится на 3, если сумма всех его цифр делится на три

Основное преимущество этого подхода состоит в том, что его легче понять для человеческого разума. Это можно превратить в хороший малорекурсивный метод:

public static boolean isDivisibleByThree(int n) {
    int sum = 0;
    int abs = Math.abs(n);
    if (abs < 10) {
        return abs == 3 || abs == 6 || abs == 9 || abs == 0;
    }
    while (n != 0) {
        sum += n % 10;
        n = n / 10;
    }
    return isDivisibleByThree(sum);
}

По общему признанию, это не так быстро, как ваш текущий подход (по моему бенчмаркингу, он примерно в два раза медленнее), но он дает правильные результаты. (Даже для экстремального значения Integer.MIN_VALUE).

Хотя в конце ничего не читается для программиста как i % 3 == 0

ответил Simon Forsberg 3 J0000006Europe/Moscow 2014, 03:45:05
15

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

import java.util.Arrays;

public class DivisibilityBenchmark {
    static abstract class DivPredicate {
        private final String name;

        public DivPredicate(String name) {
            this.name = name;
        }

        public abstract boolean isMultiple(int n);
    }

    private static final long MAAARTINUS_TABLE = 0x9249249249240000L;
    // = 0b1001001001001001001001001001001001001001001001000000000000000000L;

    private static final DivPredicate[] SOLUTIONS = new DivPredicate[] {
        new DivPredicate("canonical") {
            public boolean isMultiple(int n) {
                return n % 3 == 0;
            }
        },

        new DivPredicate("200_success") {
            public boolean isMultiple(int n) {
                return n % 3 == 0;
            }
        },

        new DivPredicate("JavaDeveloper") {
            public boolean isMultiple(int n) {
                if(n < 0) n = -n;

                int evenCtr = 0;
                int oddCtr = 0;

                while (n != 0) {
                    if ((n & 1) == 1) { 
                        oddCtr++;
                    } 
                    n = n>>1;
                    if ((n & 1) == 1) {
                        evenCtr++;
                    } 
                    n = n>>1;
                }

                return evenCtr == oddCtr;
            }
        },

        new DivPredicate("Simon André Forsberg") {
            public boolean isMultiple(int n) {
                int sum = 0;
                int abs = Math.abs(n);
                if (abs < 10) {
                    return abs == 3 || abs == 6 || abs == 9 || abs == 0;
                }
                while (n != 0) {
                    sum += n % 10;
                    n = n / 10;
                }
                return isMultiple(sum);
            }
        },

        new DivPredicate("supercat Rev 2") {
            public boolean isMultiple(int n) {
                int q = (n >> 20) + ((n >> 10) & 0x3ff) + (n & 0x3ff);
                return q == ((q * 0x5556) >> 16) * 3;
            }
        },

        new DivPredicate("supercat Rev 4") {
            public boolean isMultiple(int n) {
                if (n < 0) n = -n;
                int q = (int)((n * 0x55555556L) >> 32);
                n = n - q - q - q;
                return n == 0;
            }
        },

        new DivPredicate("maartinus Rev 4") {
            public boolean isMultiple(int x) {
                int diff = Integer.bitCount(x & 0x2AAAAAAA) + Integer.bitCount(x);
                return (MAAARTINUS_TABLE << diff) < 0;
            }
        },

        new DivPredicate("200_success (bis)") {
            public boolean isMultiple(int n) {
                return n % 3 == 0;
            }
        }
    };

    public static boolean[] run(DivPredicate pred, int lower, int upper) {
        boolean[] results = new boolean[upper - lower];
        for (int i = lower; i < upper; i++) {
            results[i - lower] = pred.isMultiple(i);
        }
        return results;
    }

    public static int perf(DivPredicate pred, int lower, int upper) {
        int count = 0;
        for (int i = lower; i < upper; i++) {
            if (pred.isMultiple(i)) {   // Count results to ensure that the
                count++;                // work is not optimized away
            }
        }
        return count;
    }

    public static void main(String[] args) {
        // Warm-up and correctness tests
        boolean[] expected = null;
        for (DivPredicate pred : SOLUTIONS) {
            boolean[] actual = run(pred, -5000, 5000);
            if (expected == null) {
                expected = actual;
            } else if (!Arrays.equals(expected, actual)) {
                System.out.println("Mismatch " + pred.name);
            }
        }

        // Performance measurement
        final int LOWER = -0x00FFFFFF, UPPER = 0x00FFFFFF;
        for (DivPredicate pred : SOLUTIONS) {
            long start = System.currentTimeMillis();
            perf(pred, LOWER, UPPER);
            long finish = System.currentTimeMillis();
            System.out.printf("Time %s: %d ms\n", pred.name, finish - start);
        }
        for (int i = SOLUTIONS.length - 1; i >= 0; i--) {
            DivPredicate pred = SOLUTIONS[i];
            long start = System.currentTimeMillis();
            perf(pred, LOWER, UPPER);
            long finish = System.currentTimeMillis();
            System.out.printf("Time %s: %d ms\n", pred.name, finish - start);
        }
    }
}

Результаты

Java (TM) SE Runtime Environment (сборка 1.7.0_45-b18) на OS X 10.9, Intel Core i7-2600 Sandy Bridge 3,4 ГГц:

  • Несоответствие JavaDeveloper
  • Время каноническое: 62 мс ( â †Грубо несправедливое преимущество! )
  • Время 200_success: 79 мс ( По-прежнему ненадежно! )
  • Время JavaDeveloper: 995 мс
  • Время Саймон Андре Форсберг: 1146 мс
  • Время supercat Rev 2: 151 мс
  • Время supercat Rev 4: 146 мс
  • Время maartinus Rev 4: 142 мс
  • Время 200_success (бис): 146 мс ( â † Вероятно, справедливое сравнение )
  • Время 200_success (бис): 146 мс
  • Время maartinus Rev 4: 140 мс
  • Время supercat Rev 4: 146 мс
  • Время supercat Rev 2: 153 мс
  • Время Саймон Андре Форсберг: 1168 мс
  • Время JavaDeveloper: 1029 мс
  • Время 200_success: 143 мс
  • Время каноническое: 144 мс

Обсуждение

Как отмечает @maaartinus, первые три решения в этом тесте получают несправедливое преимущество из-за мономорфного встроенного кэширования или других оптимизаций JIT. . Чтобы проиллюстрировать, как этот показатель был ошибочным, я включил одно и то же решение три раза (как «канонический», «200_success» и «200_success (бис)»), а затем выполнили тесты в обратном порядке для хорошей меры. Я возьму это в качестве урока для использования надлежащего инструмента сравнения, например суппорт .

Основываясь на пересмотренных измерениях, я бы сделал вывод, что решения @ 200_success, @supercat и @maaartinus почти идентичны по производительности.

ответил Simon Forsberg 3 J0000006Europe/Moscow 2014, 03:45:05
9

В духе преждевременной оптимизации, это быстрый метод, основанный на модульной арифметике:

import java.math.BigInteger;

private static final int MULTIPLIER =
  BigInteger.valueOf(3).modInverse(BigInteger.valueOf(2).pow(32)).intValue();
private static final int LOWER_LIMIT = Integer.MIN_VALUE / 3;
private static final int UPPER_LIMIT = Integer.MAX_VALUE / 3;

public static boolean divideFast(int i) {
  int j = i * MULTIPLIER;
  return LOWER_LIMIT <= j && j <= UPPER_LIMIT;
}

Идея состоит в том, что в Java умножение по модулю 2 32 (поскольку оно обертывается при переполнении), а в модульной арифметике вы можете разделить на умножение - что обычно быстрее, чем деление. Каждое нечетное число имеет «обратный» - число, которое вы можете умножить на 1, поскольку нечетные числа взаимно просты до 2 32 . Обратное значение 3 равно MULTIPLIER.

Если i делится на 3 в регулярной целочисленной арифметике, то i * MULTIPLIER будет i / 3. Если i не делится на 3, то все еще верно, что 3 * (i * MULTIPLIER) === i по модулю 2 32 , но только потому, что умножение обертывается при переполнении.

Таким образом, числа, которые делятся на 3, являются точками, в которых мы можем умножить i * MULTIPLIER на 3 без переполнения. I.e, числа, в которых i * MULTIPLIER находится между Integer.MIN_VALUE / 3 и INTEGER.MAX_VALUE / 3.

В моем тесте этот метод работает на 0.72ns за проверку, против 0.93ns на op для ближайшего ближайшего, @maaartinus.

ответил James_pic 5 J0000006Europe/Moscow 2014, 18:05:13
2

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

В случае, если вы действительно замедляете свою программу, вы можете использовать решение здесь . Он использует тот факт, что если сумма всех цифр числа в базе N делит делитель M из N-1, то это число делится на M. Исходная версия имеет дело с неподписанными числами, поэтому нам нужно небольшое изменение

private static int reduce(int i) {
    if (i >= 6)
        return reduce((i >> 2) + (i & 0x03));
    else
        return i; // Done.
}

public static boolean isMultipleOfThree(int i) {
    if (i < 0) i = -i;
    // Sum of digits in base 4
    i = (i >> 16) + (i & 0xFFFF);
    i = (i >> 8) + (i & 0xFF);
    i = (i >> 4) + (i & 0xF);
    i = reduce(i);
    return i == 0 || i == 3;
}

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

ответил phuclv 5 J0000006Europe/Moscow 2014, 15:21:20

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132