Javascript/lodash binäre Suche nach Funktion

Question

Für die meisten solcher Operationen verwenden wir die Bibliothek lodash. Ich bin offen für andere Vorschläge, würde aber wahrscheinlich die Funktion selbst schreiben, bevor ich eine neue Bibliothek importiere.

lodash hat sortedIndexOf, die eine binäre Suche in einem sortierten Array durchführt (gibt den Index der Übereinstimmung zurück oder -1, falls nicht gefunden). Es hat auch sortedIndexBy, die mithilfe einer binären Suche den Index findet, um ein neues Element einzufügen, wo Sie eine Funktion angeben können, um den Sortiervergleich zu verwenden (gibt einen gültigen Index zurück, wenn nicht gefunden)

Ich kann nicht finden Funktion, um eine Suche durchzuführen (Index wird nur zurückgegeben, wenn sie gefunden wurde), indem eine effiziente sortierte Suche verwendet wird, mit der Sie die Sortierwertfunktion angeben können. Es könnte wie folgt aussehen:

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

Ich glaube, ich

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

verwenden könnte, aber es scheint nur seltsam für mich nicht die syntaktisch kompakte und intuitive Form eines bereits reichen Feature-Set haben von sortierten Suchfunktionen.

Fehle ich etwas aus den Lodash-Dokumenten? Gibt es eine eingebaute Möglichkeit, dies idiomatisch zu tun? Oder sollte ich mit meiner Extra-Check-Methode gehen?

Answer 1

Durchlesen von lodash-Code, sieht aus, als ob es ein Paar Funktionen hat, um nach einem minimalen Index zu suchen, um ein Element einzufügen, während das Array sortiert bleibt - sortedIndex und sortedIndexBy. Former nimmt ein Array und einen Wert, letzteres akzeptiert auch iteratee - eine Funktion, die für jedes Element aufgerufen wird. Hinweis, es gibt auch sortedLastIndex und sortedLastIndexBy. Diese suchen nach dem letzten Index, an dem ein Wert eingefügt werden soll.

Wenn es darum geht zu überprüfen, ob Element im Array ist und seinen Index zurückgibt, wenn es ist, gibt es keine Funktion, die ein iteratee akzeptiert, nur ein einsamer sortedIndexOf. Es wäre nur logisch, sortedIndexOfBy zu haben (die Benennung wird hier knifflig), um einen iteratee zu akzeptieren, sowie sortedLastIndexOfBy.

Ich mag Ihre Idee der Nennung sortedFindBy und wird versuchen, es zusammen mit sortedLastFindBy zu implementieren und fügen Sie eine Pull-Anforderung zu lodash hinzu.

Ihre Extra-Check-Lösung ist vorerst vollkommen in Ordnung und nutzt die Vorteile der binären Suchoptimierung, ohne zu viel zusätzlichen Code hinzuzufügen.

In Zukunft, wenn sortedFindBy in lodash enthalten ist, können Sie Ihren Code für den neuen Funktionsaufruf immer austauschen.

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

Sie werden jedoch keinen Unterschied in der Leistung Ihres Codes sehen.

Answer 2

Ich habe darüber nachgedacht. Ich verwende weder lodash noch Unterstreichung, aber der folgende reine JS-Code könnte Ihren Zwecken dienen. Es führt eine binäre Suche nach sortierten Elementen von Primitiven oder Objekten durch. Ein bereitgestellter Rückruf wird verwendet, um den Wert der Objekteigenschaft abzurufen, auf der die Sortierung des Arrays basiert. Wenn der Callback nicht bereitgestellt wird, wird standardmäßig x => x (function(x) {return x}) verwendet und es wird angenommen, dass die Array-Elemente vom primitiven Typ sind. Momentan werden nur numerische Vergleiche durchgeführt, aber es kann auch ein Vergleichs-Callback hinzugefügt werden.

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);

können Sie spielen mit und ändern Sie es here