Schnelle Teilübereinstimmung mit Mehrkomponenten-Tasten

Question

Ich habe eine große Liste von Mehrkomponenten-Tasten konstruiert aus poi Datentypen mit Vergleichsoperatoren definiert:

typedef boost::tuple<int, char, unsigned long> Key; 

Diese Schlüssel Ich möchte gegen festen Satz Muster entsprechen, , die aus gleichen Komponenten besteht, insbesondere aber Muster könnte eine Komponente verzichtet werden:

typedef boost::tuple< 
    boost::optional<int> 
    , boost::optional<char> 
    , boost::optional<unsigned long> > Pattern; 

boost :: optional mit Wert Sternchen ungesetzt darstellt, "Entsprechen alles":

Key(1, 2, 3) match Pattern(1, 2, *) 
Key(1, 2, 3) match Pattern(*, 2, 3) 

Und ich möchte Matches führen schneller als O (N), wobei N Menge von Mustern ist.

Ich habe mit benutzerdefinierten Vergleich operator1 für Muster gestartet, um sie in sortierten Vektor zu speichern. Operator1 sortiert nur Sternchen nach allem anderen. Führen Sie anschließend die Abfragen mit std :: lower_bound mit dem benutzerdefinierten Vergleichsoperator2 aus. Operator2 lässt während des Vergleichs nicht festgelegte Schlüsselkomponenten aus. Aber ich kann nicht mit einfach sortierten Vektor wegkommen, denn wenn zweite Komponente ist * und ich es weglassen gibt es keine Garantie, dass "Slice" von dritten Komponenten sortiert sind und ich etwas mit std :: lower_bound nützlich.

Answer 1

Sortieren Sie die Schlüssel in einer bestimmten Reihenfolge. Erstellen Sie für jede Komponente einen Index, wobei die Sortierreihenfolge beibehalten wird.

Suchen Sie das nächste Element für jede Komponente mithilfe des Index. Wenn Indizes auf denselben Gegenstand zeigen, haben Sie eine Übereinstimmung. Wenn nicht, wählen Sie die Komponente, die auf das kleinste Element zeigt (in der Sortierreihenfolge) und überspringen Sie, bis Sie mindestens auf dem größten Element sind (std :: lower_bound würde es tun).

Dies ist derselbe Algorithmus zum Schneiden sortierter Listen.

Die Geschwindigkeit hängt davon ab, wie dicht Ihre Daten sind. Wenn Sie nach (*, *, true) suchen und 95% der Daten übereinstimmen, werden Sie O (N) sein. Wenn die Daten ausreichend spärlich sind, kann dies sehr schnell sein.