[Alg]Manier om algoritme te versnellen

[Thijsch]

Hey, ik ben met een programma bezig dat op zich goed werkt.

Het doel is een hottopic kloon voor linux, en op het moment dat je een topic toevoegt wordt gekeken of die niet al in de lijst staat. Wat er dus gebeurd:

Van een url wordt het topic nummer gehaald, dan wordt 1 voor 1 alle topic nummers uit de lijst gehaald en vergeleken. Met een paar topics werkt dat goed, maar met > 15 topics wordt dat verschrikkelijk traag, het duurt meer dan 1 seconde voordat dat allemaal gecontroleerd is.
Nu vroeg ik mij af: hoe ik dat kan versnellen?

Misschien kan ik alle nummers in een textuele lijst zetten en daarmee vergelijken?

Wat is hiervoor de beste oplossing?

[RickN]

Oplossing voor je probleem:
topic nummers gesorteerd bijhouden en met een binary search kijken of een topic al bestaat. (google is je vriend)

Vraag: 15 topics en 1 seconde zoeken?! Je doet iets fout.

[Zoijar]

Je lijst gesorteerd op nummer opslaan. Je kan dan bij elke toevoeging heel snel opzoeken of het nummer al bestaat en waar je het moet toevoegen om de lijst gesorteerd te houden. Wordt een O(log n) operatie ipv O(n). Moet maar eens zoeken op bv "insertion sort", of eventueel "B+ trees"

[Varienaja]

Noh.. dit lijkt me vrij simpel.

Je maakt een gesorteerde lijst van topics. Bij het toevoegen van een nieuw topic zet je deze op de 'goede' plek in de lijst. Mocht er op die plek al precies zo'n topic staan, dan voeg je niets toe.

Zoeken in een alfabetisch gesorteerde lijst duurt O=log(n), eventueel een item toevoegen duurt O=1.

[Zoijar]

Je kan dit trouwens niet sneller doen dan O(log n). Dus als het dan nog steeds een probleem is, heb jij een probleem.

[RickN]

Zoijar schreef op 13 January 2003 @ 16:03:
Je kan dit trouwens niet sneller doen dan O(log n). Dus als het dan nog steeds een probleem is, heb jij een probleem.

Kan wel sneller hoor. D.w.z. in theorie niet, maar in de praktijk wel. In de praktijk kun je namelijk best een max en min topic nummer bedenken en vervolgens in een binair array bijhouden welke topic nummer je al hebt uitgegven.

O(1) toevoegen O(1) opzoeken O(1) verwijderen

[Thijsch]

Mijn excuses trouwens Het gaat om Een C programma, Gtk+ met Glib.

de code ziet er versimpeld nu zo uit:

C:

for( i = 0; i < topic_rows; i++)
{
      gtk_clist_get_text(GTK_CLIST(clist_topics),i,&currentID);  //haalt het topic nummer van rij i
          if(currentID == newID )
           {
                show_popup(NULL,TRUE,"topic already in list");
                 return;
           }
}

//topic isnt in list, add it:

.......

wat ik dus zou moeten doen is de topics op volgorde ordenen ? en dan de middelste ophalen, hoger, degene op 3/4 van de lijst, lager, die daar tussenin etc ?

[ Voor 11% gewijzigd door Thijsch op 13-01-2003 16:19 ]

[RickN]

ParaDot schreef op 13 January 2003 @ 16:17:
wat ik dus zou moeten doen is de topics op volgorde ordenen ? en dan de middelste ophalen, hoger, degene op 3/4 van de lijst, lager, die daar tussenin etc ?

[Thijsch]

das dan duidelijk

/nick Para|Coden

[Zoijar]

RickN schreef op 13 January 2003 @ 16:16:
[...]


Kan wel sneller hoor. D.w.z. in theorie niet, maar in de praktijk wel. In de praktijk kun je namelijk best een max en min topic nummer bedenken en vervolgens in een binair array bijhouden welke topic nummer je al hebt uitgegven.

O(1) toevoegen O(1) opzoeken O(1) verwijderen

Ja klopt natuurlijk. Je zou het ook kunnen hashen met en O(log n) worst-case (alles op 1 hash, sorted list) en een O(1) best case. Misschien wel een idee voor de ts. Dit is zonder maximum (en theoretisch ook nog steeds O(log n)), maar praktisch vaak O(1) voor kleine n en grote tabel.

[Verwijderd]

ParaDot schreef op 13 January 2003 @ 16:17:
Mijn excuses trouwens Het gaat om Een C programma, Gtk+ met Glib.

Als het om een C programma gaat kan ik me niet voorstellen dat een lijstje van iets van 15 tot 100 strings doorzoeken lang kan duren. Als je de strings in een normale C structuur zou opslaan (array, linked list, whatever) moet je binnen een seconde echt wel een lijst van 1000 strings door kunnen zoeken. Of draai je dit op een mobiele telefoon of zo?

Ik ken de gtk toolset niet, maar waarschijnlijk is de gebruikte gtk_clist_get_text constructie gewoon extreem langzaam. (of de vertraging zit geheel ergens anders) Bouwt die GTK_CLIST() misschien een nieuw lijst op op basis van de clist_topic argument?

Het is waarschijnlijk veel simpeler om naast je gtk lijst de lijst in een C structuurtje bij te houden en daar de duplicate check op te doen.

[Glimi]

Mij rest nog te zeggen: waarom geen C++ ( -> std::set ) Welk voordeel denk je te hebben door in puur C te gaan coderen?

[ Voor 5% gewijzigd door Glimi op 13-01-2003 21:40 ]

[Verwijderd]

Glimi: Gtk+/Gnome is in C/glib (gobject) gecode. Ik progsel mijn GUI-flanseltjes ook vnml. in Gnome/Gtk+ en dus C. . Werkt gewoon lekker, en maakt C++ overbodig.