Geordnete Arrays - Implementation

Algorithmen, Sprachunabhängige Diskussionen zu Konzepten, Programmiersprachen-Design
Antworten
Benutzeravatar
Dirty Oerti
Beiträge: 2229
Registriert: Di Jul 08, 2008 5:05 pm
Wohnort: Thurndorf / Würzburg

Geordnete Arrays - Implementation

Beitrag von Dirty Oerti » Do Okt 09, 2008 2:23 pm

Tag! :)
Nachdem Paging nun (zur Zeit befriedigend gut) funktioniert, möchte ich natürlich weitermachen :)
Jetzt geht es dann daran, einen Heap zu schreiben.
Um einen Heap zu implementieren, und auch später, werde ich geordnete Arrays brauchen.
Also schreibe ich mir dafür mal Funktionen.

Problem: Wie implementiere ich das möglichst gut? Will heißen möglichst schnell?
Gibt es irgendwo Code dazu, den ich mir mal anschauen könnte?

Ich habe zwar eine Vorlage (HIER), allerdings möchte ich gerne unterschiedliche Möglichkeiten sehen, bevor ich mich für eine entscheide.
Außerdem:
http://www.jamesmolloy.co.uk/tutorial_html/7.-The%20Heap.html hat geschrieben:There are better implementations of ordered arrays than this (c.f. heap-ordering, binary search trees), but I decided to go with a simple one for teaching purposes.
Diese einfache Implementation habe ich verstanden. Nun will ich mehr ( ;) ). Und zwar bessere, schneller Arten der Implementation.

Kennt sich da jemand aus? :)

*edit an andere Moderatoren* Soll ich das hier drinn lassen, oder kommt das besser in Algorithmen und Konzepte?*/edit*
*edit2* Ich hab's mal verschoben. Das passt hier doch besser */edit2*

EDIT:
Es müssen nicht unbedingt geordnete Arrays sein.

Ich brauche irgendetwas, um eine Suchfunktion möglichst gut zu implementieren.
Ich habe mir auch schon Binäre Bäume angesehen, weiß aber nicht so recht, wie ich das in meinem Fall verwirklichen könnte.
Das Problem dabei ist, dass ich z.B. nach dem Wert 4 suche.
Falls es genau diesen Wert nun nicht gibt, dann möchte ich den nächste größeren Wert bekommen, der am nächsten drann ist.

Ideen?
Bei Fragen einfach an daniel[ät]proggen[Punkt]org
Ich helfe gerne! :)
----------
Wenn du ein Licht am Ende des Tunnels siehst, freu dich nicht zu früh! Es könnte ein Zug sein, der auf dich zukommt!
----
It said: "Install Win95 or better ..." So I installed Linux.

Benutzeravatar
cloidnerux
Moderator
Beiträge: 3083
Registriert: Fr Sep 26, 2008 4:37 pm
Wohnort: Ram (Gibts wirklich)

Re: Geordnete Arrays - Implementation

Beitrag von cloidnerux » Fr Okt 10, 2008 3:45 pm

Sortire doch nach dem AscII code.
Du nimmst ein Zweidimensionalen Array ungefär so

Code: Alles auswählen

long int liste[255][1[hier schreibst du den Link zu ein array eines bestimmten anfangs]

die 255 ssteht natürlich alle ascii zeichen. z.B in

Code: Alles auswählen

liste['a''(97)]
stehen natürlich alle elemente die mit a anfangen. In der zweiten dimension stehen natürlich die Adressen der Array einzelnener gruppen.
Wenn du jezt nach 'abcd' suchst, dann suchst du anch etwas das mit 'a' anfängt also muss du in liste[97/'a'] schauen. Das würde die PErformance Totall erhöhen.
Redundanz macht wiederholen unnötig.
quod erat expectandum

Benutzeravatar
Dirty Oerti
Beiträge: 2229
Registriert: Di Jul 08, 2008 5:05 pm
Wohnort: Thurndorf / Würzburg

Re: Geordnete Arrays - Implementation

Beitrag von Dirty Oerti » Fr Okt 10, 2008 3:48 pm

Ich brauche eine dynamische Liste, die sich in der Größe verändern kann. ;)
Das würde die PErformance Totall erhöhen.
Da bin ich mir nicht unbedingt so sicher.
Bei Fragen einfach an daniel[ät]proggen[Punkt]org
Ich helfe gerne! :)
----------
Wenn du ein Licht am Ende des Tunnels siehst, freu dich nicht zu früh! Es könnte ein Zug sein, der auf dich zukommt!
----
It said: "Install Win95 or better ..." So I installed Linux.

Benutzeravatar
cloidnerux
Moderator
Beiträge: 3083
Registriert: Fr Sep 26, 2008 4:37 pm
Wohnort: Ram (Gibts wirklich)

Re: Geordnete Arrays - Implementation

Beitrag von cloidnerux » Fr Okt 10, 2008 8:15 pm

Hast du mal vectoren unter C++ gesehn. Das wäre villeicht etwas für dich.
Das Problem ist ja, wenn du ein Elemnt hinzufügst, wilst du das nichtr am ende, sondern da mchen wo er hingehört, also müsstetst du alle anderen element um x nach hintenschiebern
Redundanz macht wiederholen unnötig.
quod erat expectandum

Benutzeravatar
Dirty Oerti
Beiträge: 2229
Registriert: Di Jul 08, 2008 5:05 pm
Wohnort: Thurndorf / Würzburg

Re: Geordnete Arrays - Implementation

Beitrag von Dirty Oerti » Sa Okt 11, 2008 9:22 am

Wenn ich alle anderen verschieben muss, ist das nicht gerade schnell.
Aber vectoren?
Kernelprogrammieren?
No way...
Bei Fragen einfach an daniel[ät]proggen[Punkt]org
Ich helfe gerne! :)
----------
Wenn du ein Licht am Ende des Tunnels siehst, freu dich nicht zu früh! Es könnte ein Zug sein, der auf dich zukommt!
----
It said: "Install Win95 or better ..." So I installed Linux.

Benutzeravatar
cloidnerux
Moderator
Beiträge: 3083
Registriert: Fr Sep 26, 2008 4:37 pm
Wohnort: Ram (Gibts wirklich)

Re: Geordnete Arrays - Implementation

Beitrag von cloidnerux » So Okt 12, 2008 11:17 am

Es ist nur ein vorschlag

Wie groß soll denn so eine Liste sein?
Für 20-50 Einträge wäre sowas noch möglich, aber für mehr musst du natürlich was besseres programmieren.
Redundanz macht wiederholen unnötig.
quod erat expectandum

taljeth
Beiträge: 18
Registriert: Di Okt 14, 2008 8:22 pm
Kontaktdaten:

Re: Geordnete Arrays - Implementation

Beitrag von taljeth » Di Okt 14, 2008 9:39 pm

Dirty Oerti hat geschrieben:Ich brauche irgendetwas, um eine Suchfunktion möglichst gut zu implementieren.
Ich habe mir auch schon Binäre Bäume angesehen, weiß aber nicht so recht, wie ich das in meinem Fall verwirklichen könnte.
Das Problem dabei ist, dass ich z.B. nach dem Wert 4 suche.
Falls es genau diesen Wert nun nicht gibt, dann möchte ich den nächste größeren Wert bekommen, der am nächsten drann ist.
Hm, wozu das? Aber auch das ist nicht besonders schwer, wenn du in jedem Knoten noch einen Verweis auf den Vaterknoten drin hast (aber das braucht es genau genommen nichtmal - erst, wenn du von beliebigen Knoten den Vorgänger oder Nachfolger willst). Erstmal bis ganz nach unten durchhangeln ist ja kein Problem. Entweder du hast deine 4 dann, oder du suchst den nächstgrößeren Wert. In letzterem Fall prüfen, ob der Knoten, an dem du rausgekommen bist, größer ist (wenn ja => fertig), ansonsten zum Vaterknoten gehen (=> auch fertig).

Einfach nur binäre Bäume sind leicht zu implementieren. Schwierig wird es erst dann, wenn du irgendwelche Vorkehrungen willst, daß die Bäume nicht entarten. Also Stichwort AVL-Bäume oder Rot-Schwarz-Bäume.

Und wegen der passenden Datenstruktur solltest du dir vielleicht erstmal überlegen, was die Anforderungen wirklich sind. Geordnete Arrays sind beispielsweise toll zum drin suchen, aber nicht mehr ganz so toll, wenn es um einfügen oder löschen geht. In Bäume kann man schnell einfügen, aber sie brauchen mehr Platz. Und so weiter.

Antworten