Sortieralgorithmus - Problem

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
BlackJack

Dienstag 30. September 2008, 19:16

@sea-live: Die Zahlen sind IMHO nicht aussagekräftig, da viel zu klein. Bei der kurzen Laufzeit und den wenigen Daten fallen Laufzeitschwankungen viel zu sehr ins Gewicht.
sea-live
User
Beiträge: 440
Registriert: Montag 18. Februar 2008, 12:24
Wohnort: RP

Dienstag 30. September 2008, 19:20

Danke für die info

war sowieso grade beim Basic an dem sortieren deswegen der versuch hier mal in python
mit 4Mhz würde das dann was ausmachen
tauschen bubbel sort oder quicksort
Benutzeravatar
name
User
Beiträge: 254
Registriert: Dienstag 5. September 2006, 16:35
Wohnort: Wien
Kontaktdaten:

Dienstag 30. September 2008, 19:30

sea-live hat geschrieben:das ist bei mir aber langsammer ?
selber testen

Code: Alles auswählen

....
ergebniss
sort
7.29142949732e-005
sorted
4.10666718815e-005
forschleife
0.00497465459996
tauschen
0.00504365778332
FEHLERTEUFEL
die nachfolgenden funktionen bekommen ja ein sortiertes nicht ein unsortiertes array(liste)
Du solltest, wenn du schon timings machst, zumindestens xrange benutzen. Ausserdem koennte man die timings schoen in eine Funktion auslagern, aber das ist hier nicht das Thema.
Ohloh | Mein Blog | Jabber: segfaulthunter@swissjabber.eu | asynchia – asynchrone Netzwerkbibliothek

In the beginning the Universe was created. This has made a lot of people very angry and has been widely regarded as a bad move.
BlackJack

Dienstag 30. September 2008, 19:53

@Sandra: Das `x` aus der äusseren Schleife wird nicht verwendet. Das könnte man auch einfacher mit einer ``while``-Schleife formulieren.

`range()` erzeugt eine Liste mit Zahlen die eigentlich gar nicht gebraucht wird. `xrange()` ist da speicherschonender.

Schau Dir mal die `pop()`-Methode auf Listen an.

Und ``m = float("-inf")`` ist keine so gute Idee, da es erstens so nicht auf jeder Plattform funktioniert, denn die Zeichenkettendarstellung für Unendlich hängt von der C-Bibliothek ab. Unter Windows sieht das z.B. anders aus. Und zweitens muss "Minus Unendlich" nicht für jeden Datentyp der kleinste Wert sein. Man sollte hier vielleicht besser aus den Daten einfach das Minimum bestimmen. Oder das Maximum und dann die Bedingung in Zeile 21 umdrehen. Damit wird das `reverse()` überflüssig.
Sandra
User
Beiträge: 11
Registriert: Dienstag 30. September 2008, 12:44

Mittwoch 1. Oktober 2008, 00:25

Das `x` aus der äusseren Schleife wird nicht verwendet. Das könnte man auch einfacher mit einer ``while``-Schleife formulieren.
Dies vestehe ich nicht ganz, wie lässt sich denn eine while-Schleife dafür einsetzen?
`range()` erzeugt eine Liste mit Zahlen die eigentlich gar nicht gebraucht wird. `xrange()` ist da speicherschonender.
OK werde ich mir merken.
Schau Dir mal die `pop()`-Methode auf Listen an.
Ich nehme an, du meinst etwas wie:

Code: Alles auswählen

a.append(li.pop(n))
Und ``m = float("-inf")`` ist keine so gute Idee, da es erstens so nicht auf jeder Plattform funktioniert, denn die Zeichenkettendarstellung für Unendlich hängt von der C-Bibliothek ab. Unter Windows sieht das z.B. anders aus. Und zweitens muss "Minus Unendlich" nicht für jeden Datentyp der kleinste Wert sein. Man sollte hier vielleicht besser aus den Daten einfach das Minimum bestimmen. Oder das Maximum und dann die Bedingung in Zeile 21 umdrehen. Damit wird das `reverse()` überflüssig.
Wie kann man denn das Minimum ermitteln, dieses verändert sich ja, bei

Code: Alles auswählen

a.append(li.pop(li.index(min(li))))
würde doch sicherlich 2 mal die Liste durchgegangen, oder?

mfg Sandra
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

Mittwoch 1. Oktober 2008, 07:09

Ich glaube, es wäre ganz hilfreich, wenn du deinen letztgültigen Code noch einmal posten könntest - dann kann man konkreter Bezug nehmen.

Zu der Sache mit dem Minimum:
Vor der inneren Schleife hattest du m=0 gesetzt. Wenn du m stattdessen auf das Minimum der Liste setzt, dann klappt es.
BlackJack

Mittwoch 1. Oktober 2008, 08:36

@Sandra: ``while``-Schleifen werden solange durchlaufen wie die angegebene Bedingung wahr ist. Jetzt musst Du Dir nur noch überlegen was gelten muss, damit die Schleife noch einmal ausgeführt werden muss. Du veränderst in der Schleife ja einige Werte, was ist also das Anzeichen dafür, dass die Verarbeitung fertig bzw. noch nicht fertig ist!?

Mit `pop()` meinte ich genau das. :-)

Beim Minimum siehe den Beitrag von numerix. Das würde ich das nur *einmal* vor der Schleife ermitteln und an einen weiteren Namen binden. Das Minimum aller Objekte, die sortiert werden sollen, ändert sich während des Sortierens ja nicht.
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

Mittwoch 1. Oktober 2008, 08:52

BlackJack hat geschrieben:Beim Minimum siehe den Beitrag von numerix. Das würde ich das nur *einmal* vor der Schleife ermitteln und an einen weiteren Namen binden. Das Minimum aller Objekte, die sortiert werden sollen, ändert sich während des Sortierens ja nicht.
Ja, so sollte man es machen.
Sandra
User
Beiträge: 11
Registriert: Dienstag 30. September 2008, 12:44

Mittwoch 1. Oktober 2008, 15:08

Hier mein neuer Code:

Code: Alles auswählen

#! /usr/bin/env python

import random

a = []

for x in range(10):
  a.append(random.random())

a.append(-1)
a.append(-0.5)

print a

def sort1(li):
  li = li[:]
  a = [] 
  mi = min(li)
  ll = len(li)
  while(len(a)<ll):
    n = 0
    m = mi
    for y in xrange(len(li)):
      if li[y] > m:
        n = y
        m = li[y]
    a.append(li.pop(n))
  a.reverse()
  return a
  
b = sort1(a)  

print b
Das mit dem Minimum und Maximum habe ich allerdings noch nicht verstanden. Reverse ändert doch die Reihenfolge einer Liste, wie soll man sich dies ersparen?

Kann mir eigenentlich jemand die Zeile

Code: Alles auswählen

li = li[:]
erklären? Es funktioniert, und Darii hat geschrieben, es kopiert die Liste, doch warum funktioniert es mit li = li nicht?

mfg Sandra
sea-live
User
Beiträge: 440
Registriert: Montag 18. Februar 2008, 12:24
Wohnort: RP

Mittwoch 1. Oktober 2008, 15:21

@sandra du solltst mal ein paar tips auch annehmen

das befüllen der liste geht ganz ohne inizialisierung des ARRAY's
a=[]

einfach reinschiesen !

Code: Alles auswählen

a = [random.random() for i in xrange(10)]
zu listen hier die docu
http://www.python.org/doc/2.4.2/tut/node7.html
Zuletzt geändert von sea-live am Mittwoch 1. Oktober 2008, 15:27, insgesamt 1-mal geändert.
lunar

Mittwoch 1. Oktober 2008, 15:23

Eine Zuweisung der Art "li = li" bindet das dahinter liegende Objekt nur an einen neuen Namen, erzeugt aber keine Kopie des Objekts selbst.

Ein Slice über die gesamte Liste "li[:]" dagegen erzeugt ein neues Listen-Objekt mit allen Elementen der Originalliste. Diese wird dann in der Zuweisung an einen Namen gebunden.
sea-live
User
Beiträge: 440
Registriert: Montag 18. Februar 2008, 12:24
Wohnort: RP

Mittwoch 1. Oktober 2008, 15:38

Zum Doppelpunkt solltest du einige übungen anstellen mit der shell z.B

Code: Alles auswählen

>>> a=[1,2,3,4,5,6,]
>>> a[1:-1]
[2, 3, 4, 5]
>>> a[:]
[1, 2, 3, 4, 5, 6]
>>> a[:2]
[1, 2]
>>> a[2:]
[3, 4, 5, 6]
>>> a[2:4]
[3, 4]
: = alles
1:-1 vom element an index 1 bis element 1 weniger listenlenge
:2 alles vor element 2
2: element 2 bis listenende
2:4 element 2 bis vor element 4
Sandra
User
Beiträge: 11
Registriert: Dienstag 30. September 2008, 12:44

Mittwoch 1. Oktober 2008, 16:02

Ich bin für jede Antwort dankbar, und versuche Tips an zu nehmen, doch frage halt manchmal nach, da ich es wirklich verstehen möchte, und nicht nur irgend welche Zeilen übernehmen :)

Ich denke, den Doppelpunkthabe ich jetzt auch verstanden.

Mit etwas Spielerei habe ich nun folgendes gebastelt:

Code: Alles auswählen

def sort1(li):
  li, a = li[:], []
  while(li):
    m = li[0]
    n = 0
    for x in xrange(1,len(li)):
      if li[x] < m:
        m = li[x]
        n = x
    a.append(li.pop(n))
  return a
mfg Sandra
sea-live
User
Beiträge: 440
Registriert: Montag 18. Februar 2008, 12:24
Wohnort: RP

Mittwoch 1. Oktober 2008, 17:37

@sandra
Ich bitte dich nochmals um aufklärung warumm du das ausdrücklich in dieser weise Realisieren möchtest.

es gab nun doch schon genügend einfacherer Lösungswege als deine Listen kopie und erstellung einer neuen sortierten Liste

du übergibst doch eine liste Diese soll unverändert bleiben und als rückgabe erhälst du eine sortierte liste

Dir sollte klar sein das das li in def nicht das li im hauptpfad ist wenn li=li[:] da steht
und somit kansst du mit der liste in def alles machen ohne die original zu zerstören !
BlackJack

Mittwoch 1. Oktober 2008, 17:42

@sea-live: Sandra hat jetzt eine von ihr selbst geschriebene und komplett verstandene Lösung, warum muss sie sich Dir jetzt unbedingt erklären und eine andere Lösung nehmen?

Dein letzter Satz ist auch ziemlich unangebracht. Genau das hat sie ja verstanden. Das brauchst Du jetzt nicht noch einmal mit Nachdruck erklären.
Antworten