Комментарии 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) {}
:) Угадали, ловите плюсик
Будет в 8 раз больше XOR'ов и, соответственно, на предфильтрации больше шагов сравнения.
Не обязательно больше — может быть и меньше.
Да и в 8 раз больше XOR — это ещё не в 8 раз медленнее. На накиданном в лоб тесте (for(..) a xor b) разница 12%, если вычесть п.1 может ничего не остаться.
Но если нет — может в сторону SSE смотреть? Там можно не только XOR, но и биты считать.
Хороший повод, чтобы потестить, займусь на досуге и отпишусь по результатам. :)
По SSE — тут двояко. Да, может дать хороший прирост, но это прибитие гвоздями к конкретной архитектуре. Если x64 VS x86 — еще более-менее прогнозируемо, то вот SSE… Поправьте, если не прав — не сильно углублялся в тему.
Меньше.
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]. В какой то момент дистанция перейдет за лимит и следующее умножение можно не проводить.
Можно сумму квадратов разности посчитать без циклов и ветвлений. Скорее всего будет быстрее, чем в приведенном примере.
В данном случае для значений [-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 последних решения на Ваших данных и Вашем железе. Даже если по скорости он окажется таким же, то по памяти будет выигрыш. И мне тоже хотелось бы узнать результат :)
Эта статья про константу, а продолжение, случаем, не о поиске быстрее O(N) планируется? Поиск соседей в многомерном пространстве с евклидовой метрикой вроде сравнительно хорошо проработанная тема: locality-sensitive hashing и т.д.
@NotNull
public static ActualClass constructor-impl(@NotNull ActualClass s) {
Intrinsics.checkParameterIsNotNull(s, "s");
return s;
}
Почему его не инлайнят непонятно. Для примитивных типов метод выглядит еще проще (и бесполезней).
public static long constructor-impl(long data) {
return data;
}
Может быть при выводе из экспериментальной версии исправят эту проблему.
Про подсчёт битов, беззнаковые типы в Kotlin и про ситуации, когда экономия на спичках оправдана