javascript/lodash бинарный поиск по функциям

Question

Для большинства таких операций мы используем библиотеку lodash. Я открыт для других предложений, но, скорее всего, просто напишу функцию перед импортом новой библиотеки.

lodash имеет sortedIndexOf, который выполняет двоичный поиск в отсортированном массиве (возвращает индекс соответствия или -1, если не найден). Он также имеет sortedIndexBy, который, используя двоичный поиск, находит индекс для вставки нового элемента, где вы можете указать функцию, используемую для сравнения сортировки (возвращает действительный индекс, если не найден)

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

_.sortedFindBy(array, value, function(x){x.timestamp}) 

Я считаю, что я мог бы использовать

var idx = _.sortedIndexBy(array, value, function(x){x.timestamp}) 
return (array[idx] && array[idx].timestamp === value.timestamp) ? idx : -1 

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

Я что-то упустил из документов lodash? Есть ли встроенный способ сделать это более идиоматично? Или я должен пойти с моим методом проверки?

Answer 1

Чтение кода lodash, похоже, что у него есть пара функций для поиска минимального индекса для вставки элемента при сохранении массива отсортированы - sortedIndex и sortedIndexBy. Бывший принимает массив и значение, последний также принимает iteratee - функцию, которая вызывается для каждого элемента. Обратите внимание, что есть также sortedLastIndex и sortedLastIndexBy. Они ищут последний индекс, в который нужно вставить значение.

Когда дело доходит до проверки того, находится ли элемент в массиве и возвращает его индекс, когда он есть, нет функции, которая принимает итерацию, просто одинокую sortedIndexOf. Было бы логично иметь sortedIndexOfBy (здесь именование начинает запугивать), чтобы принять итерацию, а также sortedLastIndexOfBy.

Мне нравится ваша идея называть его sortedFindBy и попытается реализовать его вместе с sortedLastFindBy и добавить запрос на тягу к lodash.

В настоящее время ваше решение для дополнительной проверки отлично подходит и использует преимущества бинарной оптимизации поиска, не добавляя слишком много дополнительного кода.

В будущем, когда sortedFindBy включен в lodash, вы всегда можете обменять свой код на новый вызов функции.

_.sortedFindBy(array, value, function(x){x.timestamp}) 

Однако вы не увидите никакой разницы в производительности вашего кода.

Answer 2

Я подумал об этом. Я не использую ни lodash, ни underscore, но следующий чистый JS-код может служить вашим целям. Он выполняет двоичный поиск в отсортированных элементах примитивов или объектов. Предоставленный обратный вызов используется для извлечения значения свойства объекта, на котором основана сортировка массива. Если обратный вызов не указан, он будет по умолчанию равен x => x (function(x) {return x}), и предполагается, что элементы массива являются примитивными. На данный момент это будет делать только численные сравнения, но также можно добавить обратный вызов сравнения.

Array.prototype.sortedFindIndex = function(val, cb = x => x) { // default callback for primitive arrays 
 
    var deli = this.length-1,         // delta index 
 
     base = 0;            // base to add the delta index 
 
    while (deli > 0 && cb(this[base + deli]) != val) { 
 
    \t deli = ~~(deli/2); 
 
    \t cb(this[base + deli]) < val && (base += deli); 
 
    } 
 
    return cb(this[base + deli]) === val ? base + deli : -1; 
 
}; 
 
var ara = [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18], 
 
    ina = ara.sortedFindIndex(17), 
 
    arb = [{a:0,b:"foo"},{a:1,b:"bar"},{a:2,b:"baz"},{a:3,b:"qux"},{a:4,b:"fox"},{a:5,b:"pun"},{a:6,b:"alf"}], 
 
    inb = arb.sortedFindIndex(4, o => o.a); 
 
console.log(ina); 
 
console.log(inb);

Вы можете играть и изменить его here