Heapsort

Code-Stücke können hier veröffentlicht werden.
EnTeQuAk
User
Beiträge: 986
Registriert: Freitag 21. Juli 2006, 15:03
Wohnort: Berlin
Kontaktdaten:

Heapsort

Beitragvon EnTeQuAk » Freitag 24. August 2007, 03:52

Hallo alle zusammen!

Ich war mal auf der Suche nach einem schnellen Sortier-Algorithmus und bin bei Heapsort fündig geworden.


Die tests haben ergeben, das er ansich funktioniert. Nichts desto trotz, würde ich euch bitten ihn gründlichst auszutesten, solltet ihr verwendung für das Snippet haben.


Hier ist der Code:

Code: Alles auswählen

#-*- coding: utf-8 -*-
from random import random

def heap_sort(A):
    j = 0
    item = 0
    temp = 0

    for k in xrange(len(A)-1, -1, -1):
        for i in xrange(k+1):
            item = A[i]
            j = i/2
            while (j > 0) and (A[j] < item):
                A[i] = A[j]
                i = j
                j = j/2

            A[i] = item

        temp = A[1]
        A[1] = A[k]
        A[k] = temp
    return A


if __name__ == '__main__':
    l = [random() for x in xrange(0, 10)]
    sl = heap_sort(l)
    print sl


Mir gefällt zwar das ganze Variablenkopieren noch nicht so wunderbar, aber vorerst reichts. Mal schaun, ob ich das noch irgentwie schicker hinbekomme.

MfG EnTeQuAk
EyDu
User
Beiträge: 4866
Registriert: Donnerstag 20. Juli 2006, 23:06
Wohnort: Berlin

Beitragvon EyDu » Freitag 24. August 2007, 09:32

Also bei mir liefert deine Implementierung falsche Ergebnisse:

Code: Alles auswählen

>>> x = [random.randint(0, 10) for x in range(10)]
>>> x
[3, 4, 1, 3, 7, 2, 4, 5, 4, 7]
>>> heap_sort(x)
[1, 3, 2, 3, 4, 4, 4, 5, 7, 7]


Dann hätte ich aber noch ein paar Anmerkungen zu deinem Quellcode, falls es dir recht ist :-)

Als ersten Schritt würde ich zu Beginn der Funktion "A" in eine Liste umwandeln, da dies von deiner Implementierung eh benötigt wird. Wo kann man auch Generatoren etc. entgegennehmen:

Code: Alles auswählen

def heap_sort(A):
    A = list(A)     #das hier
    j = 0
    ....


Dann würde ich noch die folgenden drei Zeilen einsparen, da die durchgeführte Initialisierung unnötig ist. Viel schlimmer ist eigentlich, dass du damit unter Umständen Fehler verdeckst, welche korrekterweise durch einen nicht vorhandenen Namen ausgelöst werden sollten:

Code: Alles auswählen

    j = 0
    item = 0
    temp = 0


Und wie du selber schon bemerkt hast, nervt dich das Variablenkopieren. Da gibt es in Python doch eine wunderschöne Lösung, welches "temp" überflüssig macht:

Code: Alles auswählen

i = j
j = j/2

#wird zu
i, j = j, j/2

#und
temp = A[1]
A[1] = A[k]
A[k] = temp

#wird zu
A[1], A[k] = A[k], A[1]


Und wie bei Heapsort so üblich, hat man natürlich noch das Problem, dass die Lösung nicht stabil ist. Das ist natürlich immer Ermessenssache, ob man diese Eigenschaft benötigt oder nicht.
EnTeQuAk
User
Beiträge: 986
Registriert: Freitag 21. Juli 2006, 15:03
Wohnort: Berlin
Kontaktdaten:

Beitragvon EnTeQuAk » Freitag 24. August 2007, 11:39

Also Grundsätzlich, erstmal Danke für deine ausführliche Meinung!

EyDu hat geschrieben:Also bei mir liefert deine Implementierung falsche Ergebnisse:

Code: Alles auswählen

>>> x = [random.randint(0, 10) for x in range(10)]
>>> x
[3, 4, 1, 3, 7, 2, 4, 5, 4, 7]
>>> heap_sort(x)
[1, 3, 2, 3, 4, 4, 4, 5, 7, 7]


Das werde ich heute abend, wenn ich Feierabend habe mal genauer unter die Lupe nehmen. Denn die Ergebnisse sehen irgentwie sehr komisch aus (im Gegensatz zu meinen zu Hause).
Mal schaun...
EyDu hat geschrieben:Dann hätte ich aber noch ein paar Anmerkungen zu deinem Quellcode, falls es dir recht ist :-)

Eine der besten Dinge der Welt ist Kritik. Ohne sie kann man nicht dazulernen. Genauso, wie Fehler sehr wichtig sind. Nicht nur sie zu beseitigen.

EyDu hat geschrieben:Als ersten Schritt würde ich zu Beginn der Funktion "A" in eine Liste umwandeln, da dies von deiner Implementierung eh benötigt wird. Wo kann man auch Generatoren etc. entgegennehmen:

Code: Alles auswählen

def heap_sort(A):
    A = list(A)     #das hier
    j = 0
    ....

Sehr gute Idee, daran habe ich noch gar nicht gedacht.

EyDu hat geschrieben:Dann würde ich noch die folgenden drei Zeilen einsparen, da die durchgeführte Initialisierung unnötig ist. Viel schlimmer ist eigentlich, dass du damit unter Umständen Fehler verdeckst, welche korrekterweise durch einen nicht vorhandenen Namen ausgelöst werden sollten:

Code: Alles auswählen

    j = 0
    item = 0
    temp = 0


Und wie du selber schon bemerkt hast, nervt dich das Variablenkopieren. Da gibt es in Python doch eine wunderschöne Lösung, welches "temp" überflüssig macht:

Code: Alles auswählen

i = j
j = j/2

#wird zu
i, j = j, j/2

#und
temp = A[1]
A[1] = A[k]
A[k] = temp

#wird zu
A[1], A[k] = A[k], A[1]

Stimmt, da war doch etwas. Danke, werde ich ändern. (Und Hey, es sieht wirklich schicker aus)

EyDu hat geschrieben:Und wie bei Heapsort so üblich, hat man natürlich noch das Problem, dass die Lösung nicht stabil ist. Das ist natürlich immer Ermessenssache, ob man diese Eigenschaft benötigt oder nicht.

Was bei Zahlen (wofür ich es brauchte) nicht das Problem ist, da ich nur eine einfache Zahlenliste sortiert haben brauchte.
JAAA, ich weiß dazu kann man ''list.sort'' verwenden. Aber man möchte ja lernen und selber machen :=)


Aber grundsätzlich kann ich sagen, das ich irgentwie gefallen an diesem Thema "sortieren & Datenstrukturen" gefunden habe. Mal schaun, was sich da noch so machen lässt. Habe schon viele interessante Dinge gefunden, die keine Python-Implementierung besitzen. (zumindest habe ich nichts gefunden)

Danke erstmal für deine Kritik!

MfG EnTeQuAk
BlackJack

Beitragvon BlackJack » Freitag 24. August 2007, 13:10

Heapsort geht auch deutlich kürzer:

Code: Alles auswählen

import heapq

def heapsort(sequence):
    return heapq.nsmallest(len(sequence), sequence)


;-)
EyDu
User
Beiträge: 4866
Registriert: Donnerstag 20. Juli 2006, 23:06
Wohnort: Berlin

Beitragvon EyDu » Freitag 24. August 2007, 13:23

Da könnte ich auch gleich noch meine eigene Listen-Implementierung in Python beisteuern ;-) :

Code: Alles auswählen

mylist = list


Bei der Gelegenheit fällt mir noch ein schöner Ansatz aus dem Cookbook ein: der hier.
EnTeQuAk
User
Beiträge: 986
Registriert: Freitag 21. Juli 2006, 15:03
Wohnort: Berlin
Kontaktdaten:

Beitragvon EnTeQuAk » Freitag 24. August 2007, 14:14

Och verdammt. Es hat doch etwas schönes, das die Python-Baterien fast nicht erschöpfbar sind.

Das modul hab ich irgentwie immer übersehen :=)

Danke für diese Lösung :D


MFG EnTeQuAk

Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder