Der schnellste Weg, Objekte aus einer Sammlung zu finden, die mit der Bedingung eines String-Mitglieds übereinstimmen

StackOverflow https://stackoverflow.com/questions/97329

Frage

Angenommen, ich habe eine Sammlung (sei es ein Array, eine generische Liste oder was auch immer). am schnellsten Lösung dieses Problems) einer bestimmten Klasse, nennen wir es ClassFoo:

class ClassFoo
{
    public string word;
    public float score;
    //... etc ...
}

Gehen wir davon aus, dass die Sammlung etwa 50.000 Objekte umfasst, alle im Speicher.Jetzt möchte ich so schnell wie möglich alle Instanzen in der Sammlung abrufen, die einer Bedingung für ihr Bar-Mitglied gehorchen, zum Beispiel so:

List<ClassFoo> result = new List<ClassFoo>();
foreach (ClassFoo cf in collection)
{
    if (cf.word.StartsWith(query) || cf.word.EndsWith(query))
        result.Add(cf);
}

Wie erhalte ich möglichst schnell Ergebnisse?Sollte ich einige fortgeschrittene Indizierungstechniken und Datenstrukturen in Betracht ziehen?

Die Anwendungsdomäne für dieses Problem ist ein Autovervollständiger, der eine Abfrage erhält und als Ergebnis eine Sammlung von Vorschlägen liefert.Gehen Sie davon aus, dass die Bedingung nicht komplexer wird.Gehen Sie auch davon aus, dass es viele Suchanfragen geben wird.

War es hilfreich?

Lösung

Mit der Einschränkung, dass die Bedingung Klausel kann „alles“ sein, dann sind Sie begrenzt die gesamte Liste zu scannen und Anwenden der Bedingung.

Wenn es Beschränkungen für die Bedingungsklausel sind, dann können Sie sich auf die Daten zu organisieren, um wirkungsvoller die Anfragen zu verarbeiten.

Zum Beispiel kann der Code Probe mit dem „byFirstLetter“ Wörterbuch hilft nicht, überhaupt mit einer „endsWith“ Abfrage.

Also, es kommt wirklich darauf an, was fragt man gegen diese Daten machen will.

In Datenbanken, dieses Problem ist die Belastung des „Abfrageoptimierer“. In einer typischen Datenbank, wenn Sie eine Datenbank ohne Indizes haben, offensichtlich jede Abfrage wird ein Table-Scan sein. Wie Sie Indizes in die Tabelle einfügen, kann der Optimierer diese Daten verwenden komplexere Abfragepläne besser auf die Daten erhalten zu machen. Das ist im Wesentlichen das Problem, das Sie beschreiben.

Wenn Sie eine konkretere Teilmenge der Arten von Abfragen haben, dann können Sie eine bessere Entscheidung treffen, welche Struktur am besten ist. Außerdem müssen Sie die Menge der Daten prüfen. Wenn Sie eine Liste von 10 Elementen, die jeweils weniger als 100 Byte haben, kann auch ein Scan von allem das schnellste, was du tun können, da man so eine kleine Menge von Daten haben. Offensichtlich, dass skaliert nicht auf ein 1M Elemente, sondern auch klug Zugriffstechniken führen einen Kosten in der Erstellung, Wartung (wie Indexwartung) und Speicher.

Bearbeiten , auf der Grundlage der Kommentar

Wenn es ein Auto completer ist, wenn die Daten statisch ist, sortieren sie dann und eine binäre Suche verwenden. Sie sind wirklich nicht in Gang bringen schneller als das.

Wenn die Daten dynamisch ist, dann speichern Sie es in einem ausgewogenen Baum, und suchen Sie das. Das ist effektiv eine binäre Suche, und es können Sie die Daten zufällig halten hinzuzufügen.

Alles andere ist einige Spezialisierung auf diesen Konzepten.

Andere Tipps

var Antworten = myList.Where (item => item.bar.StartsWith (Abfrage) || item.bar.EndsWith (Abfrage));

Das ist die einfachste meiner Meinung nach, sollte ziemlich schnell auszuführen.

Nicht sicher, ob ich verstehen ... Alles, was Sie wirklich tun können, ist die Regel optimieren, das ist der Teil, der schnellste sein muss. Sie können nicht die Schleife beschleunigen, ohne nur mehr Hardware auf sie zu werfen.

Sie könnten parallelisieren, wenn Sie mehrere Kerne oder Maschinen haben.

Ich bin gerade nicht mit Java vertraut, würde aber über die folgenden Dinge nachdenken.

Wie erstellen Sie Ihre Liste?Vielleicht können Sie es bereits bestellt so erstellen, dass die Vergleichszeit verkürzt wird.

Wenn Sie Ihre Sammlung nur in einer Schleife durchlaufen, werden Sie keinen großen Unterschied zwischen der Speicherung als Array oder als verknüpfte Liste feststellen.

Bei der Speicherung der Ergebnisse könnte die Struktur je nachdem, wie Sie sie sammeln, einen Unterschied machen (aber unter der Annahme, dass die generischen Strukturen von Java intelligent sind, ist das nicht der Fall).Wie gesagt, ich bin nicht mit Java vertraut, aber ich gehe davon aus, dass die generische verknüpfte Liste einen Endzeiger behalten würde.In diesem Fall würde es keinen wirklichen Unterschied machen.Jemand mit mehr Wissen über die zugrunde liegende Array- und verknüpfte-Listen-Implementierung und darüber, wie sie letztendlich im Bytecode aussieht, könnte Ihnen wahrscheinlich sagen, ob das Anhängen an eine verknüpfte Liste mit einem Endzeiger oder das Einfügen in ein Array schneller ist (meine Vermutung wäre das Array). ).Andererseits müssten Sie die Größe Ihres Ergebnissatzes kennen oder etwas Speicherplatz opfern und ihn so groß machen wie die gesamte Sammlung, die Sie durchlaufen, wenn Sie ein Array verwenden möchten.

Es könnte auch hilfreich sein, Ihre Vergleichsabfrage zu optimieren, indem Sie herausfinden, welcher Vergleich am wahrscheinlichsten zutrifft, und diesen zuerst durchführen.dh:Wenn im Allgemeinen in 10 % der Fälle ein Mitglied der Sammlung mit Ihrer Abfrage beginnt und in 30 % der Fälle ein Mitglied mit der Abfrage endet, sollten Sie zuerst den Endvergleich durchführen.

Für Ihre speziellen Beispiel die Sammlung Sortierung helfen würde, wie Sie auf das erste Element binarychop könnte, die mit Abfrage beginnt und Anfang beenden, wenn Sie das nächste erreichen, das nicht der Fall ist; Sie können auch eine Tabelle von Zeigern auf Kollektionsteile von der Rückseite jeder Zeichenfolge für die zweite Klausel.

sortiert produzieren

Im Allgemeinen, wenn Sie die Struktur der Abfrage im Voraus kennen, können Sie Ihre Sammlung sortieren (oder mehrere sortierte Indizes für Ihre Sammlung aufbauen, wenn es mehrere Klauseln) sind angemessen; Wenn Sie dies nicht tun, werden Sie als lineare Suche nicht besser in der Lage zu tun.

Wenn es etwas, wo Sie die Liste einmal füllen und dann tun viele Lookups (Tausende oder mehr), dann könnten Sie eine Art Lookup Wörterbuch erstellen, die Karten beginnt mit / endet mit Werten den tatsächlichen Werten. Das wäre ein schnelles Nachschlagen, würde aber viel mehr Speicherplatz. Wenn Sie nicht, dass viele Lookups tun oder wissen, dass Sie die Liste zumindest halb häufig würde ich mit der LINQ-Abfrage gehen zu repopulating, die CQ vorgeschlagen.

Sie können eine Art von Index erstellen und es könnte schneller.

Wir können einen Index wie folgt erstellen: 

Dictionary<char, List<ClassFoo>> indexByFirstLetter;
foreach (var cf in collection) {
  indexByFirstLetter[cf.bar[0]] = indexByFirstLetter[cf.bar[0]] ?? new List<ClassFoo>();
  indexByFirstLetter[cf.bar[0]].Add(cf);
  indexByFirstLetter[cf.bar[cf.bar.length - 1]] = indexByFirstLetter[cf.bar[cf.bar.Length - 1]] ?? new List<ClassFoo>();
  indexByFirstLetter[cf.bar[cf.bar.Length - 1]].Add(cf);
}

Dann die es wie folgt verwendet werden: 

foreach (ClasssFoo cf in indexByFirstLetter[query[0]]) {
  if (cf.bar.StartsWith(query) || cf.bar.EndsWith(query))
    result.Add(cf);
}

Jetzt möglicherweise haben wir eine Schleife nicht durch so viele ClassFoo wie in Ihrem Beispiel, aber dann haben wir wieder den Index auf dem neuesten Stand zu halten. Es gibt keine Garantie dafür, dass es schneller ist, aber es ist auf jeden Fall komplizierter.

Kommt drauf an. Sind alle Ihre Objekte gehen zu ladende im Speicher immer? Haben Sie eine endliche Grenze von Objekten, die geladen werden können? Werden Ihre Fragen haben Objekte zu betrachten, die noch nicht geladen haben?

Wenn die Sammlung groß werden wird, würde ich auf jeden Fall einen Index verwenden.

In der Tat, wenn die Sammlung auf eine beliebige Größe wachsen kann und Sie nicht sicher sind, dass Sie in der Lage sein wird, sie alle in den Speicher zu passen, würde ich in ein ORM suchen, eine In-Memory-Datenbank oder eine andere eingebettet Datenbank. XPO von DevExpress für ORM oder SQLite.Net für In-Memory-Datenbank in den Sinn kommt.

Wenn Sie dies nicht weit gehen wollen, einen einfachen Index der „bar“ Mitglied Referenzen Mapping Klassenreferenzen aus machen.

Wenn die Menge der möglichen Kriterien festgelegt ist und klein, können Sie eine Bitmaske für jedes Element in der Liste aus. Die Größe der Bitmaske ist die Größe der Menge der Kriterien. Wenn Sie ein Element erstellen / fügen Sie ihn in der Liste, überprüfen Sie, welche Kriterien erfüllt es und legen Sie dann die entsprechenden Bits in der Bitmaske dieses Elements. Passende die Elemente aus der Liste wird so einfach wie ihre Bitmasken mit dem Ziel Bitmaske entsprechen. Eine allgemeinere Methode ist die Bloom-Filter.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top