Pull to refresh

Comments 35

Может быть я не правильно понял, но, считайте не d, а d в квадрате. Нормы и квадраты норм x и y можно предвычислить и хранить рядом с ними. И того, после преобразований, из тяжёлого останется только (x,y).

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


class Signature(val signature: Array<Byte>, val norma: Double)

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

Хм… Стоит попробовать, спасибо.

Ещё раз посмотрел текст статьи и повторюсь. Не считайте d считайте d^2. Тогда в числителе будет сумма квадратов норм минус удвоенное скалярное произведение, а в знаменателе — сумма квадратов норм плюс удвоенное произведение норм. Если вы протягиваете элемент по коллекции, то можно умножения на 2 сделать один раз за прогон. Корень извлекать не надо, сравнивайте с квадратом порогового значения.

Могу лишь повторить


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

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

Кстати, если кто-то предложит, как можно упростить вычисления при такой упаковке — получит большое спасибо и плюс в карму. Хоть и один, но зато от всей души :)

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


fun getSimilar(signature: Signature) = collection
        .filter { estimate(it, signature) } // Полный проход по коллекции
        .filter { calculateDistance(it, signature) < d } // Еще один полный проход

Мне кажется, если оставить только один фильтр, то вы избавитесь от лишнего прохода по коллекции


Вообще реализация фильтра основывается на ArrayList'е


public inline fun <T> Iterable<T>.filter(predicate: (T) -> Boolean): List<T> {
    return filterTo(ArrayList<T>(), predicate)
}

Не забывайте, что ArrayList основывается на массиве и будет расширяться (т.е. выделяться новая память и производится копирование), что в вашем случае с 10 миллионами записей скорее всего приводит к сильному оверхеду. Как вариант — убрать все эти фильтры и оставить обычный for (i in collection) {} который будет складывать результаты в заранее инициализированный ArrayList с примерно прикинутым размером

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

Ход мыслей верный, но в данном конкретном случае это не даст сколько-нибудь значимого прироста производительности, поскольку, как я отмечал, выходная коллекция первого фильтра крайне мала, а под капотом все эти красивые map'ы и filter'ы все одно преобразуются в for.


Как вариант — убрать все эти фильтры и оставить обычный for (i in collection) {}

:) Угадали, ловите плюсик

так в итоге переход от byte к long что-то дал? Кажется, что упаковать по 4 бита можно и так и эдак, но код с byte будет проще.

Будет в 8 раз больше XOR'ов и, соответственно, на предфильтрации больше шагов сравнения.

> Кроме того, совершенно необязательно просчитывать все 27 Long'ов — достаточно на очередном из них превысить порог и можно прерывать проверку и возвращать false.

Не обязательно больше — может быть и меньше.

Да и в 8 раз больше XOR — это ещё не в 8 раз медленнее. На накиданном в лоб тесте (for(..) a xor b) разница 12%, если вычесть п.1 может ничего не остаться.

Но если нет — может в сторону SSE смотреть? Там можно не только XOR, но и биты считать.

Хороший повод, чтобы потестить, займусь на досуге и отпишусь по результатам. :)


По SSE — тут двояко. Да, может дать хороший прирост, но это прибитие гвоздями к конкретной архитектуре. Если x64 VS x86 — еще более-менее прогнозируемо, то вот SSE… Поправьте, если не прав — не сильно углублялся в тему.

А что, у вас есть планы переезда с x64?

ИМХО «переносимый код» бывает в библиотеках, а в вашей конкретной задаче вы же, наверное, знаете на чем это запускать будете ближайшие 5 лет.
А значения (x-y)^2 предвычисляете? всего-то 25 вариантов.

Меньше.


val precomputed = arrayOf(0, 1, 1, 4, 1, -1, 4, 9, 1, -1, -1, -1, 4, -1, 9, 16)
А частоты выпадений для этих квадратов считать пробовали?
У вас ведь есть верхний предел — d^2 * (Nx + Ny)^2.
Можно посчитать частоты для (x-y) — массив счетчиков всего из 4 элементов (с отбросом знака и 0). А потом считать дистанцию, начиная с больших: 16 * Q[4] + 9 * Q[3] + 4 * Q[2] + 5 * Q[1]. В какой то момент дистанция перейдет за лимит и следующее умножение можно не проводить.

Не совсем понял, что вы предлагаете.
Идея с предфильтрацией именно в том и состоит, чтобы максимально быстро/просто (с минимумом операций) отфильтровать гарантируя отсутствие ложно-негативных срабатываний.

Возможно, не буду спорить. Для 11 версии Java он помечен как кандидат в интрисики.
По факту собственная реализация оказалась быстрее, чем использование java.lang.Long.bitCount. Буду благодарен, если расскажете, почему так получается.

Можно сумму квадратов разности посчитать без циклов и ветвлений. Скорее всего будет быстрее, чем в приведенном примере.
В данном случае для значений [-2..2] я использовал по 4 бита на число: [0b0110, 0b0111, 0b0000, 0b0001, 0b0010].
Идея использовать побитовую магию для паралельного подсчета всех полубайтов лонга одновременно.
Код на джаве:


    public static long sumSqDiff(long l1, long l2) {
         // l1 = l1 - l2
        l1 |= 0x8888888888888888L;
        l1 -= l2;

        // l2 = negatives
        l2 = (l1 & 0x4444444444444444L) >>> 2;
        // l1 = abs(l1)
        l1 = (l1 ^ (l2 | (l2 << 1) | (l2 << 2))) + l2;

        // Calculate separate bits, prepare for multiplication
        long b0 = l1 & 0x1111111111111111L; // Bit 0b0001
        b0 = b0 | (b0 << 1); // Bit 0b0001 -> 0b0011
        long b1 = l1 & 0x2222222222222222L; // Bit 0b0010
        b1 = b1 | (b1 >>> 1); // Bit 0b0010 -> 0b0011
        long b2 = (l1 & 0x4444444444444444L) >>> 2; // Bit 0b0100 -> 0b0001

        // l1 = l1 * l1 (low 2 bits only)
        l1 = ((l1 & b1) << 1) + (l1 & b0);

        // Calculate special case for value 4 0b0100
        b2 = (b2 + (b2 >>> 4)) & 0x0F0F0F0F0F0F0F0FL;

        // Combine alltogether
        l1 = (l1 & 0x0F0F0F0F0F0F0F0FL) + ((l1 >>> 4) & 0x0F0F0F0F0F0F0F0FL) ;
        l1 += b2 << 4;
        l1 = (l1 + (l1 >>> 8)) & 0x00FF00FF00FF00FFL;
        l1 = (l1 + (l1 >>> 16));
        l1 = (l1 + (l1 >>> 32));

        return l1 & 0xFFFF;
    }

Надеюсь, у автора будет возможность проверить и написать результат.

Не скрою — была у меня тайная цель увидеть комментарии такого рода ;)

Не сомневаюсь, что ради этого и писалась статья :)
И, раз уж Вы так хотели уложить данные в 3 бита, то это тоже можно сделать. Правда, только 20 штук в long, а не 21, если без костылей просаживающих производительность.
Значения такие же как и в предыдущем примере, [0b110, 0b111, 0b000, 0b001, 0b010]. И все так же без веток и циклов:


    public static final long BITS_001 = 0b001001001001001001001001001001001001001001001001001001001001001L;
    public static final long BITS_010 = BITS_001 << 1;
    public static final long BITS_100 = BITS_001 << 2;
    public static final long BITS_011 = BITS_010 | BITS_001;

    public static final long BITS_GROUP_0N =0b000111000111000111000111000111000111000111000111000111000111000L;
    public static final long BITS_GROUP_0 = 0b111000111000111000111000111000111000111000111000111000111000111L;
    public static final long BITS_GROUP_1 = 0b111000000111111000000111111000000111111000000111111000000111111L;
    public static final long BITS_GROUP_2 = 0b000111111111111000000000000111111111111000000000000111111111111L;

    public static long sumSqDiff(long l1, long l2) {

        // l2 = -l2, inverse L2 to use sum instead of substraction
        long l2Neg001 = (l2 | (l2 >>> 1) | (l2 >>> 2)) & BITS_001;
        long l2Neg111 = (l2Neg001 << 2) | (l2Neg001 << 1) | l2Neg001;
        l2 = (l2 ^ l2Neg111) + l2Neg001;

        // Calculate where substraction is needed (flip highest bit)
        long oneNeg100 = (l1 ^ l2) & BITS_100;

        // sum = l1 + l2
        long sum = ((l1 & BITS_011) + (l2 & BITS_011)) ^ oneNeg100;

        // sum = abs(sum)
        long sumNeg001 = (sum & BITS_100) >>> 2;
        long sumNeg111 = (sumNeg001 << 2) | (sumNeg001 << 1) | sumNeg001;
        sum = (sum ^ sumNeg111) + sumNeg001;

        // Calculate separate bits, prepare for multiplication
        long b0 = sum & BITS_001; // Bit 0b001
        b0 = b0 | (b0 << 1); // Bit 0b001 -> 0b011
        long b1 = sum & BITS_010; // Bit 0b010
        b1 = b1 | (b1 >>> 1); // Bit 0b010 -> 0b011
        long b2 = (sum & BITS_100) >>> 2; // Bit 0b100 -> 0b001

        // mul011 = l1 * l1 (low 2 bits only)
        long sumPart1 = sum & BITS_GROUP_0;
        long sumPart2 = sum & BITS_GROUP_0N;

        long res = ((sumPart1 & b1) << 1) + (sumPart1 & b0) +
                ((((sumPart2 & b1) << 1) + (sumPart2 & b0)) >>> 3);

        // Calculate special case for value 4 = 0b100
        b2 = (b2 + (b2 >>> 3)) & BITS_GROUP_0;
        b2 = (b2 + (b2 >>> 6)) & BITS_GROUP_1;

        // Combine alltogether
        res = (res + (res >>> 6)) & BITS_GROUP_1;
        res += b2 << 4;
        res = (res + (res >>> 12)) & BITS_GROUP_2;
        res = (res + (res >>> 24));
        res = (res + (res >>> 48));

        return res & 0xFFF;
    }

Не знаю как будет по скорости. Наверно можно еще что-то соптимизировать, но я пока пас. Скорее всего примерно так же, как и в предыдущем примере. Но памяти меньше.
Буду ждать от Вас результатов тестов.

То на то вышло: 1.5-1.7, но надо посмотреть, возможно получится где-нибудь еще сэкономить. Ну и пару нюансов еще проверить.
Но вообще зачет — сам люблю битики посмещать, но до вас еще очень далеко. Супер! :)

Странно, что нет повышения производительности. Возможно, что узкое место где-то не здесь. Попробуйте сравнить два (или три) решения без применения предварительного фильтра.
Я еще немного подчистил код для трехбитной реализации. Улучшение производительности в рамках погрешности, хотя вроде и есть.


    public static long sumSqDiff(long l1, long l2) {
        // l2 = -l2, inverse L2 to use sum instead of substraction
        long l2NotZero001 = (l2 | (l2 >>> 1)) & BITS_001;
        long l2Neg111 = (l2NotZero001 << 2) | (l2NotZero001 << 1) | l2NotZero001;
        l2 = (l2 ^ l2Neg111) + l2NotZero001;

        // Calculate where only one negative value is present (flip highest bit)
        long oneNeg100 = (l1 ^ l2) & BITS_100;

        // sum = l1 + l2
        long sum = ((l1 & BITS_011) + (l2 & BITS_011)) ^ oneNeg100;

        // sum = abs(sum)
        long sumNeg100 = sum & BITS_100;
        long sumNeg001 = sumNeg100 >>> 2;
        long sumNeg111 = sumNeg100 | (sumNeg001 << 1) | sumNeg001;
        sum = (sum ^ sumNeg111) + sumNeg001;

        // Calculate separate bits, prepare for multiplication
        long b0 = sum & BITS_001; // Bit 0b001
        b0 = b0 | (b0 << 1); // Bit 0b001 -> 0b011
        long b1 = sum & BITS_010; // Bit 0b010
        b1 = b1 | (b1 >>> 1); // Bit 0b010 -> 0b011
        long b2 = (sum & BITS_100) >>> 2; // Bit 0b100 -> 0b001

        // mul011 = l1 * l1 (low 2 bits only)
        long sumPart1 = sum & BITS_GROUP_0;
        long sumPart2 = sum & BITS_GROUP_0N;

        long res = ((sumPart1 & b1) << 1) + (sumPart1 & b0) +
                ((((sumPart2 & b1) << 1) + (sumPart2 & b0)) >>> 3);

        // Calculate special case for value 4 = 0b100
        b2 = (b2 + (b2 >>> 3)) & BITS_GROUP_0;

        // Combine alltogether
        res += b2 << 4;
        res = (res & BITS_GROUP_1) + ((res >>> 6) & BITS_GROUP_1);
        res = (res + (res >>> 12));
        res = (res + (res >>> 24));
        res = (res + (res >>> 48));

        return res & 0xFFF;
    }
Странно, что нет повышения производительности. Возможно, что узкое место где-то не здесь. Попробуйте сравнить два (или три) решения без применения предварительного фильтра.

На всякий случай поясню, чтобы не оказалось, что о разном говорим. Фильтр по количеству бит крайне эффективен и, из-за этого, является узким местом. Грубо говоря, 99% времени тратится именно на него. Соответственно, отдельно улучшать окончательный расчет смысла мало — надо что-то делать с фильтром. И вот тут ваш вариант оказывается эдакой "серебряной пулей", которая может заменить фильтр и, как приятный бонус, сразу рассчитать результат.


Почему производительность осталась той же? (с равными шансами она могла как вырости, так и снизиться кстати)
Моя реализация фильтра хоть и режет исходя из самого негативного сценария (обрабатывается больше Long'ов из каждой сигнатуры), но крайне легковесна. Ваша реализация работает с реальными данными, cutoff происходит на более ранних стадиях, но вес каждой итерации больше.


Как-то так. :)


PS А не написать ли вам статью про битовую магию? Разные подходы, приемы, занятные алгоритмы. Я бы с удовольствием почитал.

Я понял.
Переписал Ваш код на джаву и проверил производительность с помощью JMH.
Реализация с циклом примерно в 2 раза медленнее моей 4хбитной реализации. Трехбитная реализация была медленнее, но у меня уже есть решение с оптимизацией. Новое решение даже чуть обгоняет четырехбитное (правда, не понимаю почему), но в нем на 25% больше данных, так что в итоге должно быть быстрее и с меньшим потреблением памяти. Грубый фильтр примерно в 6 раз быстрее моей самой быстрой реализации (но это в пересчете на один long а не на количество реальных данных в нем).
Вот результаты тестов:


Benchmark            Mode  Cnt        Score       Error  Units
Jmh.bits3new        thrpt    5   171994.412 ±   925.414  ops/s
Jmh.bits3old        thrpt    5   117730.344 ± 10353.670  ops/s
Jmh.bits4           thrpt    5   163883.382 ±  2206.193  ops/s
Jmh.ref             thrpt    5    77606.405 ±   968.108  ops/s
Jmh.refEstimate     thrpt    5  1027086.177 ± 23775.351  ops/s

Ну и оптимизированый код:


    public static final long BITS_001 = 0b001001001001001001001001001001001001001001001001001001001001001L;
    public static final long BITS_010 = BITS_001 << 1;
    public static final long BITS_100 = BITS_001 << 2;
    public static final long BITS_011 = BITS_010 | BITS_001;

    public static final long BITS_GROUP_0N =0b000111000111000111000111000111000111000111000111000111000111000L;
    public static final long BITS_GROUP_0 = 0b111000111000111000111000111000111000111000111000111000111000111L;
    public static final long BITS_GROUP_1 = 0b111000000111111000000111111000000111111000000111111000000111111L;
    public static final long BITS_MUL     = 0b000000000000001000000000001000000000001000000000001000000000001L;

    public static long sumSqDiff(long l1, long l2) {
        // Calculate same sign places
        long sameSign100 = (~(l1 ^ l2)) & BITS_100;

        // sum = l1 - l2
        long sum = ((l1 | BITS_100) - (l2 & BITS_011)) ^ sameSign100;

        // sum = abs(sum)
        long sumNeg001 = (sum & BITS_100) >>> 2;
        sum = (sum ^ (sumNeg001 * 7)) + sumNeg001;

        // Calculate separate bits, prepare for multiplication
        long b0 = (sum & BITS_001) * 3; // Bit 0b001 -> 0b011
        long b1 = (sum & BITS_010) * 3; // Bit 0b010 -> 0b110

        // mul011 = l1 * l1 (low 2 bits only)
        long sumPart1 = sum & BITS_GROUP_0;
        long sumPart2 = sum & BITS_GROUP_0N;

        long res = ((sumPart1 << 1) & b1) + (sumPart1 & b0) +
                ((((sumPart2 << 1) & b1) + (sumPart2 & b0)) >>> 3);

        // Calculate special case for value 4 = 0b100
        long b2 = (sum & BITS_100) << 2;
        res += (b2 + (b2 >>> 3)) & BITS_GROUP_0N;

        // Combine alltogether
        res = (res & BITS_GROUP_1) + ((res >>> 6) & BITS_GROUP_1);
        res = (res * BITS_MUL) >>> 48;

        return res & 0xFFF;
    }

Статью писать я вряд ли буду, я не так много могу рассказать по этому поводу. Но могу порекомендовать отличную книгу по теме, называется Hacker's Delight или в русском переводе Алгоритмические трюки для программистов.

Ваша задача не отпускает :)
Обнаружил, что джава считает Long.bitCount очень быстро, по крайней мере на моей системе. Скорее всего задействует SSE инструкции или типа того.
А в связи с этим открываются новые возможности по оптимизации:


    public static long sumSqDiff(long l1, long l2) {
        long sameSign100 = (~(l1 ^ l2)) & BITS_100;

        // sum = l1 - l2
        long sum = ((l1 | BITS_100) - (l2 & BITS_011)) ^ sameSign100;

        // correct estimate: add cases for values +/-3
        return Long.bitCount(((sum ^ (sum << 1)) & BITS_100) & (sum << 2)) * 8 + estimate(l1, l2);
    }

    public static long estimate(long l1, long l2) {
        long xor = l1 ^ l2;
        long ones = xor & BITS_001;
        long res = Long.bitCount(ones);
        xor &= ~(ones * 7);
        long twos = xor & BITS_010;
        res += Long.bitCount(twos) * 4;
        xor &= ~(twos * 3);
        res += Long.bitCount(xor) * 16;
        return res;
    }

Это пока самый быстрый код, который я смог получить на своей системе. Не факт что на Вашей системе будет так же.
Метод estimate медленнее, чем у Вас, но более точный. Из плюсов, можно грубо посчитать грубую оценку, а потом при необходимости досчитать. Хотя в Вашем случае выигрыш от такого подхода будет совсем небольшой.

Тут все упирается в баланс "количество операций"*"вес операции" и, на самом, деле, оптимальность того или иного кода будет сильно зависит от входных данных. Если, допустим разница на каждом лонге (с моим методом кодирования, для простоты) будет 0001 0001 0001 0001, то быстрее работать будет мой способ оценки, а если 0000 0000 0000 1111, то ваш. Промежуточные варианты — тут надо оценивать, скорее всего можно высчитать порог 1,1,1,1->0,1,1,2->0,0,1,3->0,0,0,4, на котором перадается первенство.

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

Идея интересная. У меня получился результат примерно на уровне моего последнего решения. Но в тут таки можно использовать память по полной и поместить 21 значения в long.
Из минусов такого подхода — надо подбирать размер массива для конкретного железа. У меня получился лучший результат при 2^12 интов, по 4 трехбитных слова. При использовании 2^9 или 2^15 производительность становится хуже. Так же она становится хуже при использовании массива байтов вместо инта. На Вашем железе может быть по-другому.
Алгоритм простой, сначала посчитать разность (см. предыдуйие код, 2 первые строчки), а потом посуммировать из массива. Если захотите проверить, то разберетесь как это сделать :)
Ну и я бы рекомендовал все-таки проверить мои 2 последних решения на Ваших данных и Вашем железе. Даже если по скорости он окажется таким же, то по памяти будет выигрыш. И мне тоже хотелось бы узнать результат :)

Ну и я бы рекомендовал все-таки проверить мои 2 последних решения на Ваших данных и Вашем железе.

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

Эта статья про константу, а продолжение, случаем, не о поиске быстрее O(N) планируется? Поиск соседей в многомерном пространстве с евклидовой метрикой вроде сравнительно хорошо проработанная тема: locality-sensitive hashing и т.д.

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

Я кстати так и не понял зачем происходит вызов constructor-impl для inline классов. Так как этот конструктор для всех inline классов компилируется в статический метод примерно такого вида, а из-за запрета на блок init в inline классе мы при всём желании не сможем его расширить (ниже декомпилированный метод)
@NotNull
public static ActualClass constructor-impl(@NotNull ActualClass s) {
   Intrinsics.checkParameterIsNotNull(s, "s");
   return s;
}
Почему его не инлайнят непонятно.
Для примитивных типов метод выглядит еще проще (и бесполезней).
public static long constructor-impl(long data) {
   return data;
}
Может быть при выводе из экспериментальной версии исправят эту проблему.
Sign up to leave a comment.