Suche in Liste

  • Allgemein

Es gibt 18 Antworten in diesem Thema. Der letzte Beitrag () ist von RodFromGermany.

    Suche in Liste

    Ich habe eine unsortierte Liste von ungefähr 100 Millionen Longs, bei denen ich alle Zahlen zwischen einem kleinem und einem großen Wert haben möchte. Die Werte der Anfrage müssen aber nicht in der Liste sein.

    Beispielliste:
    [1,4,2,3,8]

    Suche(2,5) -> return (2,3,4)

    Mein bisheriger Ansatz war:
    1). Liste sortieren
    2). balancierten Binärbaum aufstellen
    3). Beide Elemente von der Root aus suchen und dann im sortierten Array alles zwischen den Indizes zurückgeben.

    Das funktioniert auch ganz gut, doch weil ich sehr viele Anfragen stellen möchte, würde es mich interessieren, ob jemand einen besseren Ansatz wüsste :)

    Wie oft musst Du denn die

    Telcrome schrieb:

    Liste sortieren
    :?:
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!

    Willst du denn die Werte aus der Liste am Ende auch sortiert rausbekommen? Wenn ja, würde ich die Werte in Quicksort reinschmeißen und den Teiler mal auf das Mittel zwischen dem angegebenen Minimum und Maximum festlegen. Das sollte dann ziemlich schnell gehen.

    Ohne Sortieren geht es schonmal sehr schnell - habe mal ein kleines Testprogramm geschrieben (nur ints statt longs, da Random nichts anderes produzieren kann):

    C#-Quellcode

    1. ​Console.WriteLine("Generating Array with 100.000.000 random entries...");
    2. Random random = new Random();
    3. int[] array = new int[100000000];
    4. for (int i = 0; i < 100000000; i++)
    5. {
    6. array[i] = random.Next(int.MinValue, int.MaxValue);
    7. }
    8. Console.WriteLine("Finished the generation.");
    10. int min = random.Next(int.MinValue, int.MaxValue);
    11. int max = random.Next(min, int.MaxValue);
    12. Console.WriteLine("Searching all values between {0} and {1}...", min, max);
    13. List<int> result = new List<int>(array.Length / 20); //schonmal ne große Länge fürs Array reservieren, damit das Array nicht allzu oft resized werden muss
    14. for (int i = 0; i < array.Length; i++)
    15. {
    16. if (array[i] >= min && array[i] <= max)
    17. {
    18. result.Add(array[i]);
    19. }
    20. }
    21. Console.WriteLine("Found {0} matching values.", result.Count);
    23. Console.ReadKey();

    Für n->Anzahl der Elemente
    Dein Algorithmus braucht dann n*2 Vergleiche

    Bei meinem bisherigen Ansatz brauche ich log(2,n) Vergleiche (Eben nur ein leicht modifizierter BST)

    In einem Beispiel von z.B. 200000 Einträgen würde dein Algorithmus 400000 Vergleiche brauchen und ein BST 18. Das ist wahrscheinlich auch das Kernproblem, die Anzahl der Vergleiche von 18 zu reduzieren. (Das war jetzt eine Rechnung für nur eine Suchanfrage von vielen)

    Mein eigentliches Problem arbeitet nämlich nicht mit Longs, sonderm mit einem Inhaltsobjekt, dass das Interface IComparable implementiert und bei meinem Inhaltsobjekt sind Vergleiche dann eben relativ teuer (Ist aber natürlich eigentlich das gleiche Problem, wie Longs zu vergleichen, deshalb habe ich es auf diese Weise vereinfacht).

    Bei 100000 Suchanfragen braucht mein Algorithmus ungefähr 3 ms Rechenzeit, womit ich noch nicht ganz zufrieden bin.

    Wenn es 2 ms sind braucht mein Server 1/3 weniger Strom :D

    EDIT: Solange man mit Nachdenken die bessere Hardware überflüssig machen kann ist doch schön. Ich arbeite auch schon seit längerem an dem Problem und wollte nur sichergehen, dass ich den richtigen Weg eingeschlagen habe

    Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von „Telcrome“ ()

    es geht auch ohne BinärBaum und Kram.
    eine einfache sortierte Liste kann man mit einer Binären Suche ebensoschnell (glaub sogar schneller) durchsuchen.
    List(Of T) hat sogar eine BinarySearch-Methode - also dein Prob sollte mit 5 Zeilen erledigt sein.
    Naja - evtl. 15 CodeZeilen, weil beim Auftreten mehrerer gleicher Zahlen findet BinarySearch nur irgendeine - nicht unbedingt die erste.

    @ErfinderDesRades
    Binäre Suche hat zwar die gleiche Asymptotische Komplexität, doch nutzt sie Zugriffe auf ein Array statt Pointern und muss jedes Mal aufs neue die Mitte berechnen. In meiner Java-Testimplementation ist der BST ungefähr doppelt so schnell wie direkt im Array mit Binärer Suche zu suchen.

    Aber jetzt reden wir nicht mehr von milli- sondern nur noch von Mikro-Sekunden oder noch kleiner. Und dass sich Optimierungen in dem Bereich überhaupt noch irgendwie auswirken, bezweifel ich stark.
    Ein Pluspunkt der Binärsuche ist ihr geringerer Speicherbedarf - einen BST mit 100Mio Nodes - belegt der nicht über ein GB Speicher?

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „ErfinderDesRades“ ()

    Telcrome schrieb:

    mein Algorithmus
    ist mit welchem Code implementiert?
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!

    @RodFromGermany
    Java erstmal (Teambedingt), ist aber eigentlich egal für den Ansatz

    @ErfinderDesRades
    Speicher ist nicht wichtig, hab 200GB ram zur verfügung. Eine Mikrosekunde pro Suche wäre schon krass viel find ich, es gibt ja viele suchanfragen...
    Tatsächlich ist der Speicherbedarf eines BST nicht soooo schlimm. Also der ist noch völlig im grünen Bereich, so um die 40GB Ram werden belegt :)

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „Telcrome“ ()

    Ich verstehe nicht ganz, wieso das relevant ist ;( Ich selbst hab nichtmal einen Server mit dem irgendwas passieren könnte... Obwohl ich deinen Link vllt. auch falsch verstanden haben könnte, da ich ihn nicht ganz durchgelesen hab^^

    Obwohl die Story schon ganz interessant ist :D

    OT:
    @Telcrome Mich würde mal interessieren, was das -präzise- für ein Projekt ist. Geht es darum, solche Daten in Echtzeit auszuwerten? Oder darfst du nicht sagen, was/für wen das Projekt ist?

    Link :thumbup:
    Hello World

    Telcrome schrieb:

    mein Server

    Telcrome schrieb:

    Ich selbst hab nichtmal einen Server
    Wat?

    Telcrome schrieb:

    Ich verstehe nicht ganz, wieso das relevant
    Weil das u. U. sehr teuer werden kann, siehe (Hyper-)Link.
    Mit freundlichen Grüßen,
    Thunderbolt

    RodFromGermany schrieb:

    mit welchem Code

    Telcrome schrieb:

    Java erstmal
    Kannst Du den Code der betreffenden Prozedur posten?
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!

Facebook
Telefonspende