Diskussion:In-Place-Algorithmus

Allgemeines

Die Grundlage zur Benutzung eines in-place Algorithmus in einer Programmiersprache ist die, dass die verwendete Programmiersprache die Möglichkeit bietet, Variablen vom Typ Referenz zu benutzen. Daher ist der Satz

Funktionale Programmiersprachen nutzen oft keine in-place Algorithmen

meines Erachtens fehl am Platz, da sich diejenigen Programmiersprachen, die (verzeihung) so "schlecht" sind, sich eher in der Minderheit befinden, oder etwa nicht?

Die bekanntesten Vertreter dieser funktionalen Sprachen wären afaik Scriptsprachen wie PHP, Perl, Python. Alle drei ermöglichen die Benutzung von Referenzen (wenn auch zum Teil in einem anderen Stil als in C).

Da ich nicht weiß, ob ich mit meiner Theorie recht habe, erhoffe ich mir Antwort :)
viele Grüße, --Benji 20:28, 25. Nov 2005 (CET)

Wiki-Prinzip missverstanden

Dies ist kein Artikel einer allgemeinen Enzykopädie. Sondern er ist in klassischem Fachchinesisch abgefasst. Sätze wie

Die Platzkomplexität von in-place arbeitenden Algorithmen ist, in der Landau-Notation ausgedrückt, O(1)

sind nur für Experten verständlich, die brauchen den Artikel aber nicht, weil Sie den Grundbegriff ja eh schon kennen werden. Wikipedia ist eine Enzyklopädie. Ihr Zweck ist, Dinge allgemeinverständlich dartzstellen. Dazu sind Enzyklopädien da. Gibt es denn keinen Fachautoren, der sich von dem Blabla seines Wissenschaftszweiges lösen und die Sache allgemeinverständlich erklären kann? -- Tim, 29.10.2006.

Man braucht doch nicht in einem weiterführenden Artikel die Landau-Notation erklären. Dafür gibts schließlich den Hauptartikel Landau-Notation. Allerdings sind die Artikel in-place und out-of-place eigentlich Worterklärungen, die vielleicht im Hauptartikel Sortierverfahren besser aufgehoben wären. --Amogorkon 16:29, 10. Aug. 2007 (CEST)

'in-place' und 'out-of-place' sind Eigenschaften beliebiger Algorithmen und mitnichten auf Sortierverfahren beschränkt - das ist nicht der 'Hauptartikel' für diese Eigenschaften.

Wenn schon, dann könnte wohl eher "Platzkomplexität" als 'Hauptartikel' herhalten.

--arilou (Diskussion) 12:05, 2. Dez. 2020 (CET)

Konstante Platzkomplexität

Hallo,

im Artikel wird behauptet, ein in-place-Algorithmus würde nur eine konstante Menge an Speicher, also ${\mathcal {O}}(1)$ benötigen. Je nach Berechnungsmodell müsste aber logarithmischer Speicher für Programmzeiger zugelassen werden. Gerade habe ich nur en:In-place algorithm zu Hand, daher habe ich jetzt Bausteine platziert, bis die korrekte Platzkomplexität aus der Fachliteratur nachgetragen wird.

Viele Grüße --Bejahend (Diskussion) 23:27, 1. Dez. 2020 (CET)

Ich denke, da liegt (vor allem bzgl. der Behauptung, Quicksort sei 'in-place') ein Verständnisfehler vor.

Was der engl. Artikel in seiner Einleitung verdeutlichen will, möchte ich an einem Beispiel erläutern:

Bubblesort gilt (in weniger-strenger Auslegung von 'in-place') als 'in-place' -Algorithmus. Seine Inputs sind

• array a mit zu sortierenden Elementen
• Zahlenwert n := Länge von a

Dieser Zahlenwert n braucht ja selbst etwas Platz - um ihn zu speichern, braucht man zumindest ₂log(n) bits (aufgerundet). Außerdem muss Bubblesort ja intern mehrere Schleifenzähler bis n laufen lassen, die brauchen ebenfalls soviele Bits. Die 'strictest form' (ich nenn's mal "Pfennigfuchser-Auslegung") von 'in-place' beschert Bubblesort damit eine O(log(n)) -Platzkomplexität, da für große n ja der Speicherplatz für den Zahlenwert n mit 2_log(n) wächst.

Die (laut englischem Artikel) "More broadly" -Bedeutung von 'in-place' ist, dass man (nur!) diesen Aspekt unter den Tisch fallen lässt, also die „Eigenlänge“ von (Array-)Längenangaben und Indizes/Pointern ignoriert ("to [not] count the index lengths as part of the space used").

Dadurch wird Bubblesort dann zu einer Platzkomplexität von O(1).

---

Der zusätzliche Platzverbrauch Quicksorts dadurch, dass man (rekursiv) eine Menge Pointer/Indexwerte auf dem Stack benötigt, hat mit obiger Problemstellung nichts zu tun - folgerichtig ordnet der Artikel die Platzkomplexität gemäß 'strictest' als O(log^2(n)) ein, in 'more broadly' als immernoch O(log(n)) ein.

--arilou (Diskussion) 12:37, 2. Dez. 2020 (CET)

Das ist nicht nur Fachchinesisch vom Feinsten, sondern auch noch falsch. Es gibt sicherlich Algorithmen die (teilweise) in-situ arbeiten, aber trotzdem nicht die Speicherkomplexität O(1) haben. --CyDeFect (Diskussion) 20:31, 12. Sep. 2023 (CEST)