В модуле фасетов Lucene мы недавно добавили поддержку огранки динамического диапазона , чтобы показать, сколько совпадений соответствует каждому из динамического набора диапазонов. Например, Updatedдетализация в приложении поиска проблем Lucene / Solr использует грани диапазона.
Другим примером являются грани расстояния (<1 км, <2 км и т. Д.), Где расстояние динамически вычисляется на основе текущего местоположения пользователя. В грани цены можно также использовать грани диапазона, если диапазоны не могут быть установлены во время индексации.
Чтобы реализовать огранку диапазона, для каждого попадания мы сначала вычисляем значение (расстояние, возраст, цена), которое будет агрегировано, а затем ищем, какие диапазоны соответствуют этому значению, и увеличиваем его количество. Сегодня мы используем простой линейный поиск по всем диапазонам, который имеет O(N)стоимость, где Nнаходится количество диапазонов.
Но это неэффективно!
Сегмент деревьев
Есть забавные структуры данных как сегмент дерева и интервальных дерева с O(log(N) + M)стоимостью за поиск, где Mесть число диапазонов , которые соответствуют данному значению. Я решил исследовать деревья сегментов, поскольку Lucene требует поиска только по одному значению (деревья интервалов также могут эффективно искать все диапазоны, перекрывающие заданный диапазон ), а также потому, что все диапазоны известны заранее (деревья интервалов также поддерживают динамическое добавление или удаление диапазонов).
Если диапазоны никогда не будут перекрываться, вы можете использовать простой двоичный поиск; ГуаваImmutableRangeSet использует этот подход. Однако огранка диапазона Lucene позволяет перекрывать диапазоны, поэтому мы не можем этого сделать.
Деревья сегментов просты для визуализации: вы «проецируете» все диапазоны друг на друга, создавая одномерную диаграмму Венна , чтобы определить элементарные интервалы . Это классифицирует весь диапазон чисел на минимальное количество отдельных диапазонов, каждый элементарный интервал, так что все точки в каждом элементарном интервале всегда соответствуют одному и тому же набору входных диапазонов. Затем процесс поиска представляет собой двоичный поиск, чтобы определить, к какому элементарному интервалу принадлежит точка, и записать соответствующие диапазоны по мере того, как вы просматриваете дерево.
Рассмотрим эти диапазоны; нижнее число включительно, а верхнее число исключительно:
0: 0 – 10 1: 0 – 20 2: 10 – 30 3: 15 – 50 4: 40 – 70
Элементарные интервалы (представьте диаграмму Венна!):
-∞ – 0 0 – 10 10 – 15 15 – 20 20 – 30 30 – 40 40 – 50 50 – 70 70 – ∞
Наконец, вы строите двоичное дерево поверх элементарных диапазонов, а затем добавляете индексы выходного диапазона как к внутренним узлам, так и к листьям этого дерева, что необходимо для предотвращения состязательных случаев, которые требуют слишком много ( O(N^2)) пространства. Во время поиска, когда вы спускаетесь по дереву, вы собираете выходные диапазоны (индексы), с которыми вы сталкиваетесь; для нашего примера каждому элементарному диапазону присваиваются следующие индексы диапазона в качестве выходных данных:
-∞ – 0 → 0 – 10 → 0 10 – 15 → 1, 2 15 – 20 → 1, 2, 3 20 – 30 → 2, 3 30 – 40 → 3 40 – 50 → 3, 4 50 – 70 → 4 70 – ∞ →
Некоторые диапазоны соответствуют 1 элементарному интервалу, в то время как другие диапазоны в целом соответствуют 2 или 3 или более. Некоторые, 2 в этом примере, могут не иметь соответствующих диапазонов ввода.
Поиск подходящих диапазонов
Я перенес все источники, описанные ниже, в новый проект кода Google ; код все еще несколько грубый и исследовательский, поэтому, вероятно, скрываются интересные ошибки, но, похоже, он работает: он включает в себя (прохождение!) тесты и простые микро-тесты.
Я начал с реализации базового дерева сегментов, как описано на странице Википедии , для длинных значений, называемых SimpleLongRangeMultiSet; вот рекурсивный lookupметод:
private int lookup(Node node, long v, int[] answers, int upto) {
if (node.outputs != null) {
for(int range : node.outputs) {
answers[upto++] = range;
}
}
if (node.left != null) {
if (v <= node.left.end) {
upto = lookup(node.left, v, answers, upto);
} else {
upto = lookup(node.right, v, answers, upto);
}
}
return upto;
}
Это работало правильно, но я понял, что должны быть нетривиальные издержки для рекурсии, проверки на нулевые значения, цикла for для выходных значений и т. Д. Затем я попытался переключиться на параллельные массивы для хранения двоичного дерева ( ArrayLongRangeMultiSet ), где левый потомок узла N равен 2 * N, а правый потомок — 2 * N + 1, но это оказалось медленнее.
После этого я протестировал специализированную реализацию кода, сначала создав динамический исходный код Java из двоичного дерева. Это исключает рекурсию и создает единственный простой метод, который использует серию ifоператоров, специализированных для определенных диапазонов, для выполнения двоичного поиска и записи индексов диапазона. Вот результирующий специализированный код, скомпилированный из вышеуказанных диапазонов:
void lookup(long v, int[] answers) {
int upto = 0;
if (v <= 19) {
if (v <= 9) {
if (v >= 0) {
answers[upto++] = 0;
answers[upto++] = 1;
}
} else {
answers[upto++] = 1;
answers[upto++] = 2;
if (v >= 15) {
answers[upto++] = 3;
}
}
} else {
if (v <= 39) {
answers[upto++] = 3;
if (v <= 29) {
answers[upto++] = 2;
}
} else {
if (v <= 49) {
answers[upto++] = 3;
answers[upto++] = 4;
} else {
if (v <= 69) {
answers[upto++] = 4;
}
}
}
}
}
Наконец, используя библиотеку ASM , я скомпилировал дерево непосредственно в специализированный байт-код Java , и это оказалось самым быстрым (до 2,5 раз быстрее в некоторых случаях).
В качестве основы я также добавил простой метод линейного поиска LinearLongRangeMultiSet; если у вас не слишком много диапазонов (скажем, 10 или меньше), его производительность часто лучше, чем у дерева сегментов Java.
Реализация также позволяет вам указать допустимый диапазон входных значений (например, может быть, все значения> = 0 в вашем использовании), что может сохранить один или два оператора if в методе поиска.
Подсчет всех подходящих диапазонов
В то время как дерево сегментов позволяет вам быстро искать все подходящие диапазоны для заданного значения, после приятного совета от коллеги из комитета Lucene Роберта Мьюра мы поняли, что граням диапазона Lucene не нужно знать диапазоны для каждого значения; вместо этого требуется только агрегированные значения для каждого диапазона в конце, после просмотра многих значений.
Это приводит к оптимизации: вычислить значения для каждого элементарного интервала, а затем, в конце, свернуть эти значения, чтобы получить значения для каждого диапазона. Это будет работать только для однозначных полей, так как для многозначных полей вам никогда не придется осторожно увеличивать один и тот же диапазон более одного раза за удар.
Основываясь на этом подходе, я создал новый абстрактный базовый класс LongRangeCounter и реализацию Java SimpleLongRangeCounter , а также специализированную версию ASM, и результаты действительно быстрее (~ 20-50%), чем использование метода поиска для подсчета; Я буду использовать этот подход с Lucene.
Деревья сегментов, как правило, всегда «идеально» сбалансированы, но один последний поворот, который я исследовал, заключался в использовании обучающего набора значений для смещения порядка операторов if. Например, если ваши диапазоны покрывают крошечную часть пространства поиска, как в случае Updatedдетализации , то следует быстрее использовать слегка несбалансированное дерево, сначала проверив, меньше ли значение максимального диапазона. Однако в тестировании, хотя в некоторых случаях это «обучение» происходит немного быстрее, часто оно медленнее; Я не уверен почему.
Lucene
Я еще не свернул это в Lucene, но я планирую; весь исследовательский код пока что находится в проекте Google Code для деревьев сегментов .
Результаты на микро-бенчмарках могут быть совершенно разными, если реализации свернуты в «настоящее» поисковое приложение. Хотя ASM является мощным способом генерации специализированного кода и обеспечивает значительный выигрыш в производительности, по крайней мере, в микро-бенчмарках, это дополнительная зависимость и сложность для непрерывной разработки, и гораздо больше разработчиков знают Java, чем ASM . Это также может запутать горячую точку, вызывая деоптимизацию, когда есть несколько реализаций для абстрактного базового класса. Кроме того, если имеется много диапазонов, результирующий специализированный байт-код может стать довольно большим (но все же O(N*log(N))по размеру), что может вызвать другие проблемы. В целом, я не уверен, что значительное увеличение производительности (на микро-эталоне) оправдывает использование ASM в грани диапазона Lucene.