Was ist günstiger? Array oder verkettete Liste??



  • Welche Datenstruktur ist für das Einfügeverfahren (Insertion Sort) günstiger? Eine einfach verkettete Liste oder ein Array?

    Geht man hier von der Implementierung oder vom Logischen aus? Wenn man von der Implementierung ausgeht, wie stellt man eine verkettete Liste in einer Sprache dar (z.B. in C oder in Java)? Wird eine verkettete Liste in Java allgemein nur als Array dargestellt oder als struct + Array?

    struct
    {
      int zahl;
      int *zgr_next;
    }
    

    Weiterhin wäre es interessant, wie man die beiden anhand der Vertauschungs- und Vergleichoperationen vergleichen kann.



  • Ich würde mal vermuten, für Insert-Sort ist die (doppelt verkettete) Liste günstiger, weil du das gerade eingefügte Element nur an der richtigen Stelle einhängen mußt (beim Array mußt du alle Elemente hinter der Zielposition umkopieren, um Platz zu schaffen).



  • 1. ist die Formulierung ein bisschen schwammig
    2. machen wir hier keine Hausaufgaben fuer dich (weil deine Frage klingt ein bisschen nach einer typischen Hausaufgabenstellung)
    3. die asymptotische Komplexitaet ist bei Array und Listen identisch, es gibt sicher Eingabedaten, bei denen eine Liste effizienter ist (z. B. Eingabedaten sind in umgekehrter Reihenfolge, dann muss immer das ganze bereits sortiere Array im Einsortieren-Schritt umkopiert werden). Situationen, wo ein Array guenstiger ist, fallen mir grad nicht ein, aber ich bin zu faul drueber nachzudenken.
    4. hab ich absolut k.A. was du mit "geht man von der Implementierung oder vom Logischen" meinst.
    5. eine verkettete Liste wird in Java natuerlich nicht als Array dargestellt, sondern ganz normal wie in anderen Sprachen auch:

    class Node
    {
        private Node* next;
        private Data myData;
    }
    


  • Insertionsort besteht ja im Wesentlichen aus 2 Schritten:

    1. Einfügeposition für nächstes Element bestimmen

    2. Element an dieser Stelle einfügen

    3. benötigt bei der liste lineare Zeit, dafür geht dort Schritt 2) in O(1).

    Beim Array geht das suchen schnell: O(log n) mit binärer suche, dafür benötigt Schritt 2) lineare Zeit.

    Dazu kommt noch, dass der Verwaltungsaufwand bei der Liste meist größer ist.



  • Danke für die bisherigen Antworten.

    @BlueTiger: Es steht mir fern, hier sinnlos nur meine Aufgabe zu posten und dies von euch beantworten zu lassen. Mir geht es nur um Lösungsansätze oder auch mal einen Link.

    beim Array mußt du alle Elemente hinter der Zielposition umkopieren, um Platz zu schaffen

    Beim Array vertausche ich doch auch bloß 2 Werte oder? Also ich möchte den Wert mit dem Index X an die Stelle mit dem Index Y kopieren:

    int tmp = A [X];
    A[X] = A[Y];
    A[Y] = tmp;
    
    1. benötigt bei der liste lineare Zeit, dafür geht dort Schritt 2) in O(1).

    Beim Array geht das suchen schnell: O(log n) mit binärer suche, dafür benötigt Schritt 2) lineare Zeit.

    Bedeutet ja, dass sie im Endeffekt den gleichen Aufwand benötigen. (gleiche Komplexität haben und somit auch gleiche Kosten)

    4. hab ich absolut k.A. was du mit "geht man von der Implementierung oder vom Logischen" meinst.

    Unser Ansatz war dabei, dass wir nicht genau wussten, ob wir uns das erst mal "programmieren" und das dann vergleichen. Oder ob wir das einfach nur formell durchsprechen. Deshalb "Logisch" und "Implementierung".

    Grüße



  • e86 schrieb:

    Beim Array vertausche ich doch auch bloß 2 Werte oder? Also ich möchte den Wert mit dem Index X an die Stelle mit dem Index Y kopieren:

    Nein. Stell dir folgendes Szenarion vor:

    3 4 5 6 7 8 [b]1[/b] 9
    

    Jetzt willst du das fettgedruckte Element einsortieren, also an Stelle [0]. Damit muss du die Elemente 0...5 um eins nach hinten verschieben, um überhaupt erst Platz an [0] zu bekommen.



  • e86 schrieb:

    beim Array mußt du alle Elemente hinter der Zielposition umkopieren, um Platz zu schaffen

    Beim Array vertausche ich doch auch bloß 2 Werte oder? Also ich möchte den Wert mit dem Index X an die Stelle mit dem Index Y kopieren:

    int tmp = A [X];
    A[X] = A[Y];
    A[Y] = tmp;
    

    Ja, du vertauschst zwei Werte, aber das entsprechend oft - im Extremfall tauschst du das neu einzufügende Element stückweise durch das gesamte Array bis zum Anfang. Bei der Liste mußt du gar nicht mehr tauschen (wäre auch unökonomisch, es zu machen) - du hängst das untersuchte Element aus der Liste aus, suchst die gewünschte Einfügeposition und hängst es dort wieder dazwischen.

    1. benötigt bei der liste lineare Zeit, dafür geht dort Schritt 2) in O(1).

    Beim Array geht das suchen schnell: O(log n) mit binärer suche, dafür benötigt Schritt 2) lineare Zeit.

    Bedeutet ja, dass sie im Endeffekt den gleichen Aufwand benötigen. (gleiche Komplexität haben und somit auch gleiche Kosten)

    Aus Sicht der Komplexitätstheorie ja, aber langfristig gibt es schon einen Unterschied zwischen O(n)+O(1) (Liste) und O(log n)+O(n) (Array) - außerdem kommt noch dazu, daß du beim Array echt kopieren mußt (ist mitunter teurer als das Zeiger-Jonglieren in der list<>).
    (im Gegenzug hat die Liste einen Overhead beim Speicherbedarf - die braucht O(n) Byte, um die Verkettungen (Pointer) unterzubringen)



  • inplace insertsort ist bei beiden gleich komplex

    das array kann man jedoch auch per effizienteren algo sortiern, während die liste da keine chance hat besser zuwerden



  • ronny schrieb:

    das array kann man jedoch auch per effizienteren algo sortiern, während die liste da keine chance hat besser zuwerden

    ist ja garnicht wahr. quicksort funktioniert auch prima mit listen.



  • hmm - stimmt - ich war voreilig - das resultat war mist 😕



  • CStoll schrieb:

    Aus Sicht der Komplexitätstheorie ja, aber langfristig gibt es schon einen Unterschied zwischen O(n)+O(1) (Liste) und O(log n)+O(n) (Array) - außerdem kommt noch dazu, daß du beim Array echt kopieren mußt (ist mitunter teurer als das Zeiger-Jonglieren in der list<>).
    (im Gegenzug hat die Liste einen Overhead beim Speicherbedarf - die braucht O(n) Byte, um die Verkettungen (Pointer) unterzubringen)

    Wobei sich auch die größere Cache-Effizienz von Arrays stark bemerkbar machen dürfte. Ich denke langfristig gewinnt vermutlich trotzdem das Array, wenn die Elemente nicht gerade sehr groß sind. Ansonsten kann man ja auch immer noch zunächst die pointer sortieren.

    Interessant ist, dass Insertionsort nur linear viele Branch-Misses hat, während Quicksort O(n log n) hat. Allerdings dürfte sich das für große Eingabegrößen kaum bemerkbar machen, bei kleinen dafür schon eher.



  • Jester schrieb:

    ronny schrieb:

    das array kann man jedoch auch per effizienteren algo sortiern, während die liste da keine chance hat besser zuwerden

    ist ja garnicht wahr. quicksort funktioniert auch prima mit listen.

    Und MergeSort dürfte mit Listen sogar besser funktionieren als mit Arrays (da kannst du dir das Zweitarray als Zwischenspeicher sparen).



  • CStoll schrieb:

    Jester schrieb:

    ronny schrieb:

    das array kann man jedoch auch per effizienteren algo sortiern, während die liste da keine chance hat besser zuwerden

    ist ja garnicht wahr. quicksort funktioniert auch prima mit listen.

    Und MergeSort dürfte mit Listen sogar besser funktionieren als mit Arrays (da kannst du dir das Zweitarray als Zwischenspeicher sparen).

    Die Verkettung fuer die list duerfte mehr Speicheraufwand bedeuten als ein AoP.

    Ich denke es duerfte sehr Implementierungsabhaengig sein was von beiden besser ist.

    Jester schrieb:

    Interessant ist, dass Insertionsort nur linear viele Branch-Misses hat, während Quicksort O(n log n) hat. Allerdings dürfte sich das für große Eingabegrößen kaum bemerkbar machen, bei kleinen dafür schon eher.

    Wuerde man bei Insertsort im Array nicht Binaer suchen? Was Branchmisses angeht wuerde man dann nicht besser als Quicksort sein, oder?
    Notfalls einfach branchfree machen, yay. 🕶



  • rapso schrieb:

    CStoll schrieb:

    Jester schrieb:

    ronny schrieb:

    das array kann man jedoch auch per effizienteren algo sortiern, während die liste da keine chance hat besser zuwerden

    ist ja garnicht wahr. quicksort funktioniert auch prima mit listen.

    Und MergeSort dürfte mit Listen sogar besser funktionieren als mit Arrays (da kannst du dir das Zweitarray als Zwischenspeicher sparen).

    Die Verkettung fuer die list duerfte mehr Speicheraufwand bedeuten als ein AoP.

    Das kommt auf die Größe der Nutz-Daten an - wenn du int's sortieren willst, ist das Zweitarray kleiner, bei std::string nehmen die prev/next-Zeiger weniger Platz in Anspruch (vom Kopieraufwand ganz zu schweigen).

    (Detail am Rande: std::sort() ist typischerweise als QuickSort implementiert, std::list<>::sort() auf Basis von MergeSort (auch wenn das nicht vom Standard vorgegeben ist)



  • CStoll schrieb:

    rapso schrieb:

    CStoll schrieb:

    Jester schrieb:

    ronny schrieb:

    das array kann man jedoch auch per effizienteren algo sortiern, während die liste da keine chance hat besser zuwerden

    ist ja garnicht wahr. quicksort funktioniert auch prima mit listen.

    Und MergeSort dürfte mit Listen sogar besser funktionieren als mit Arrays (da kannst du dir das Zweitarray als Zwischenspeicher sparen).

    Die Verkettung fuer die list duerfte mehr Speicheraufwand bedeuten als ein AoP.

    Das kommt auf die Größe der Nutz-Daten an - wenn du int's sortieren willst, ist das Zweitarray kleiner, bei std::string nehmen die prev/next-Zeiger weniger Platz in Anspruch (vom Kopieraufwand ganz zu schweigen).

    ich glaube ein ArrayOfPointers is grundsaetzlich nie groesser als "die prev/next-Zeiger" einer gleich langen liste.



  • Hallo
    Bin neu hier und fand die Diskussion über google

    Habe so ziemlich die selbe Aufgabe gehabt nun stören mich ein paar Sachen und ich würde gerne das für mich klären

    1.Ob array oder liste bei insertion Sort wird doch immer linear gesucht
    2.Die liste wäre doch schneller da das einfügen schneller geht, weil weniger verschoben bzw. kopiert werden muss

    Ist mir schon klar das komplexitätsmäßig beides in n² anzuordnen ist doch die list sollte besser sein oder nicht?

    Ach was mich noch interessieren würde wie sieht der Algorithmus für listen bei dem sort aus ohne eine zweite liste anzufangen?



  • minimax schrieb:

    1.Ob array oder liste bei insertion Sort wird doch immer linear gesucht

    Warum? Nur weil die Standardimplementierung auf Wikipedia linear sucht? Was hindert dich daran, eine optimierte Verison zu schreiben, die binaer im Array sucht?

    2.Die liste wäre doch schneller da das einfügen schneller geht, weil weniger verschoben bzw. kopiert werden muss.
    Ist mir schon klar das komplexitätsmäßig beides in n² anzuordnen ist doch die list sollte besser sein oder nicht?.

    Ja, das einfuegen geht schneller, aber das suchen langsamer. Wenn du eine Maschine hast, die sehr, sehr schnell ist im Array-kopieren, kann es sein dass das Array schneller ist (wobei ich persoenlich mir auch vorstellen kann das die Liste schneller ist, aber genau wissen kannst du es nicht).
    Letzten Endes muesstest du's also selber implementieren und testen, um zu wissen was auf deiner CPU-Architektur besser ist.



  • Blue-Tiger schrieb:

    minimax schrieb:

    1.Ob array oder liste bei insertion Sort wird doch immer linear gesucht

    Warum? Nur weil die Standardimplementierung auf Wikipedia linear sucht? Was hindert dich daran, eine optimierte Verison zu schreiben, die binaer im Array sucht?

    Hm, Binärsuche in einem Sortieralgorithmus? Warum klingelt da irgendwas bei mir?



  • nman schrieb:

    Hm, Binärsuche in einem Sortieralgorithmus? Warum klingelt da irgendwas bei mir?

    Naja, vielleicht meint er eine randomisierte statt lineare Suche 🤡



  • nman schrieb:

    Blue-Tiger schrieb:

    minimax schrieb:

    1.Ob array oder liste bei insertion Sort wird doch immer linear gesucht

    Warum? Nur weil die Standardimplementierung auf Wikipedia linear sucht? Was hindert dich daran, eine optimierte Verison zu schreiben, die binaer im Array sucht?

    Hm, Binärsuche in einem Sortieralgorithmus? Warum klingelt da irgendwas bei mir?

    Keine Ahnung. Warum denn?


Log in to reply