К написанию статьи подтолкнул вот этот комментарий. А точнее, одна фраза из него.
… расходовать память или такты процессора на элементы в миллиардных объёмах — это нехорошо…Так сложилось, что в последнее время мне именно этим и пришлось заниматься. И, хотя, случай, который я рассмотрю в статье, довольно частный — выводы и применённые решения могут быть кому-нибудь полезны.
// Порог
const val d = 0.3
// 10.000.000 объектов.
// Будем держать эту цифру в уме,
// чтобы не упоминать в каждом втором предложении
val collection: MutableList<Signature> = mutableListOf()
// signature — массив из 420 значений типа Byte
class Signature(val signature: Array<Byte>, val norma: Double)
fun getSimilar(signature: Signature) = collection
.filter { calculateDistance(it, signature) < d }
fun calculateDistance(first: Signature, second: Signature): Double =
Math.sqrt(first.signature.mapIndexed { index, value ->
Math.pow((value - second.signature[index]).toDouble(), 2.0)
}.sum()) / (first.norma + second.norma)
10M
квадратных корней Math.sqrt
10M
сложений и делений / (first.norma + second.norma)
4.200M
вычитаний и возведений в квадрат Math.pow((value - second.signature[index]).toDouble(), 2.0)
4.200M
сложений .sum()
Byte
(или, не дай бог, кто-то догадался бы использовать Int
) на хранение трёх значащих бит — это непростительное расточительство.Long
— это 64 бита, что, в нашем случае, позволит хранить в нём 21 значение (и 1 бит останется неприкаянным).// массив из 20 значений типа Long
class Signature(val signature: Array<Long>, val norma: Double)
fun calculateDistance(first: Signature, second: Signature): Double =
Math.sqrt(first.signature.mapIndexed { index, value ->
calculatePartial(value, second.signature[index])
}.sum()) / (first.norma + second.norma)
fun calculatePartial(first: Long, second: Long): Double {
var sum = 0L
(0..60 step 3).onEach {
val current = (first.ushr(it) and 0x7) - (second.ushr(it) and 0x7)
sum += current * current
}
return sum.toDouble()
}
4.200M
против 1.600M
байт, если грубо), но что там с вычислениями?8.400M
сдвигов и 8.400M
логических И. Может и можно оптимизировать, но тенденция всё равно не радует — это не то, чего мы хотели.-2 | 0b1100 |
-1 | 0b0100 |
0 | 0b0000 |
1 | 0b0010 |
2 | 0b0011 |
XOR
'ом получать Long
с разностями (не совсем) сразу 16-ти элементов. Кроме того, будет всего 11 вариантов распределения бит в каждом конечном полубайте, что позволит использовать заранее рассчитанные значения квадратов разностей.// массив из 27 значений типа Long
class Signature(val signature: Array<Long>, val norma: Double)
// -1 для невозможных вариантов
val precomputed = arrayOf(0, 1, 1, 4, 1, -1, 4, 9, 1, -1, -1, -1, 4, -1, 9, 16)
fun calculatePartial(first: Long, second: Long): Double {
var sum = 0L
val difference = first xor second
(0..60 step 4).onEach {
sum += precomputed[(difference.ushr(it) and 0xF).toInt()]
}
return sum.toDouble()
}
2.160M
против 1.600M
— неприятно, но всё же лучше, чем начальные 4.200M
.10M
квадратных корней, сложений и делений (никуда не делись)270M
XOR
'ов4.320
сложений, сдвигов, логических И и извлечений из массива.Long
'ах вычислить минимальное возможное значение левой части неравенства. После чего просто отбрасывать все сигнатуры, ему не удовлетворяющие.Long
'е всего 64 бита, читай 64 возможных результата. И они отлично рассчитываются заранее и складываются в массив, по аналогии с предыдущим разделом.Long
'ов — достаточно на очередном из них превысить порог и можно прерывать проверку и возвращать false. Такой же подход, кстати, можно использовать и при основном расчёте.fun getSimilar(signature: Signature) = collection
.asSequence() // Зачем нам лишняя промежуточная коллекция!?
.filter { estimate(it, signature) }
.filter { calculateDistance(it, signature) < d }
val estimateValues = arrayOf(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 19, 22, 25, 28, 31, 34, 37, 40, 43, 46, 49, 52, 55, 58, 61, 64, 69, 74, 79, 84, 89, 94, 99, 104, 109, 114, 119, 124, 129, 134, 139, 144, 151, 158, 165, 172, 179, 186, 193, 200, 207, 214, 221, 228, 235, 242, 249, 256)
fun estimate(first: Signature, second: Signature):Boolean{
var bitThreshold = Math.pow(d * (first.norma + second.norma), 2.0).toLong()
first.signature.forEachIndexed { index, value ->
bitThreshold -= estimateValues[java.lang.Long.bitCount(value xor second.signature[index])]
if (bitThreshold <= 0) return false
}
return true
}
d=0.3
пройти фильтр удаётся довольно малому количеству объектов и вклад их обсчёта в общее время ответа настолько мизерный, что им можно пренебречь. А раз так, то можно ещё немножко сэкономить.sequence
— это хорошая защита от крайне неприятного Out of memory. Однако если мы заведомо знаем, что на первом же фильтре коллекция уменьшится до вменяемых размеров, то гораздо более разумным выбором будет использовать обычный перебор в цикле с созданием промежуточной коллекции, потому как sequence
— это не только модно и молодёжно, но ещё и итератор, у которого hasNext
сотоварищи, которые совсем не бесплатны.fun getSimilar(signature: Signature) = collection
.filter { estimate(it, signature) }
.filter { calculateDistance(it, signature) < d }
java.lang.Long.bitCount
! А ещё недавно в язык подвезли беззнаковые типы. В атаку!Long
заменены на ULong
, из исходников Java с корнем выдрана java.lang.Long.bitCount
и переписана как функция расширения для ULong
fun ULong.bitCount(): Int {
var i = this
i = i - (i.shr(1) and 0x5555555555555555uL)
i = (i and 0x3333333333333333uL) + (i.shr(2) and 0x3333333333333333uL)
i = i + i.shr(4) and 0x0f0f0f0f0f0f0f0fuL
i = i + i.shr(8)
i = i + i.shr(16)
i = i + i.shr(32)
return i.toInt() and 0x7f
}
bitCount()
почти 16 миллионов вызовов Kotlin.ULong.constructor-impl
. WAT!?ULong
public inline class ULong @PublishedApi internal constructor(@PublishedApi internal val data: Long) : Comparable<ULong> {
@kotlin.internal.InlineOnly
public inline operator fun plus(other: ULong): ULong = ULong(this.data.plus(other.data))
@kotlin.internal.InlineOnly
public inline operator fun minus(other: ULong): ULong = ULong(this.data.minus(other.data))
@kotlin.internal.InlineOnly
public inline infix fun shl(bitCount: Int): ULong = ULong(data shl bitCount)
@kotlin.internal.InlineOnly
public inline operator fun inc(): ULong = ULong(data.inc())
и т.д.
}
ULong
сейчас experimental
, но как так-то!?java.lang.Long.bitCount
— не самый оптимальный. Он даёт хороший результат в общем случае, но если мы заранее знаем на каких процессорах будет работать наше приложение, то можно подобрать более оптимальный способ — вот очень хорошая статья об этом на Хабре Обстоятельно о подсчёте единичных битов, крайне рекомендую к прочтению.fun Long.bitCount(): Int {
var n = this
n -= (n.shr(1)) and 0x5555555555555555L
n = ((n.shr(2)) and 0x3333333333333333L) + (n and 0x3333333333333333L)
n = ((((n.shr(4)) + n) and 0x0F0F0F0F0F0F0F0FL) * 0x0101010101010101).shr(56)
return n.toInt() and 0x7F
}
Что делали | попугаи (секунды) |
---|---|
Подход первый, наивный | 25± |
Подход второй, упаковываем | - |
Подход третий, упаковываем заново с подвыподвертом | 11-14 |
Подход четвёртый, крупное сито | 2-3 |
Подход пятый, избавляемся от sequence | 1.8-2.2 |
Подход шестой, хотели как лучше | 3-4 |
«Комбинированный метод» подсчёта установленных битов | 1.5-1.7 |
К сожалению, не доступен сервер mySQL