 |
Das deutsche QBasic- und FreeBASIC-Forum
Für euch erreichbar unter qb-forum.de, fb-forum.de und freebasic-forum.de!
|
| Vorheriges Thema anzeigen :: Nächstes Thema anzeigen |
| Autor |
Nachricht |
ALWIM
Anmeldungsdatum: 08.08.2006
Beiträge: 1048
Wohnort: Niederbayern
|
 Verfasst am: 08.07.2017, 01:15 Titel: Strings sortieren - geeigneter Sortieralgorithmus? |
 |
|
Wie sortiere ich Strings am schnellsten? Ich habe 12 Strings die gleichzeitig sortiert werden sollen. Jeder der 12 Strings hat ca. 3000 Werte. Die 12 Strings werden 3-4 mal sortiert. Welcher Algorithmus eignet sich da am besten fürs sortieren?
String sieht wie folgt aus:
Die gefundenen Sortieralgorithmen brauchen entweder zu lang, oder sind nicht für Strings geeignet.
Mein Gedankengang:
| Code: | FOR i = 1 TO 3000
FOR j = 1 TO 30
SWAP Namen(j,1),Namen(j+1,1)
SWAP Namen(j,2),Namen(j+1,2)
SWAP Namen(j,3),Namen(j+1,3)
...
NEXT
NEXT |
obiger Code braucht zu lange! Wenn ich jetzt 10 Minuten zum sortieren brauche, ist das auch nicht grad Sinn und Zweck der Sache!
Hat jemand eine Idee?
Gruß
ALWIM
_________________
SHELL SHUTDOWN -s -t 05 |
|
| Nach oben |
|
 |
Sebastian
Administrator
Anmeldungsdatum: 10.09.2004
Beiträge: 5969
Wohnort: Deutschland
|
| Verfasst am: 08.07.2017, 01:38 Titel: |
|
|
Hi ALWIM!
Für so eine geringe Datenmenge sollte bei einigermaßen aktueller Hardware selbst ein BubbleSort allenfalls Sekunden brauchen. 
Was du beschreibst, ist ein zweidimensionales Array, also quasi eine Tabelle mit Zeilen und Spalten. Vermutlich möchtest du, dass Zeilen als Ganzes sortiert werden nach einer bestimmten Spalte, richtig?
Dein vorgeschlagener Algorithmus wird dazu nicht funktionieren: Der betrachtet den Inhalt der Spalten gar nicht, d.h. ob "Zitrone" vor "Apfel" steht oder umgekehrt. Sondern du vertauscht immer nur ein Element mit dem jeweils nächsten, egal, ob die Reihenfolge passt oder nicht. Und das 3000x hintereinander immer wieder von vorne.
Viele Grüße!
Sebastian
_________________
Die gefährlichsten Familienclans | Opas Leistung muss sich wieder lohnen - für 6 bis 10 Generationen! |
|
| Nach oben |
|
|
Sebastian
Administrator
Anmeldungsdatum: 10.09.2004
Beiträge: 5969
Wohnort: Deutschland
|
| Verfasst am: 08.07.2017, 02:10 Titel: 2-dimensionales Array mit BubbleSort sortieren |
|
|
Hi ALWIM,
hier mal ein einfaches Beispiel zum Nachverfolgen. Das 2-dimensionale Array wird nach der ersten Spalte (Name) sortiert.
| Code: | Dim Tabelle(1 To 5, 1 To 4) As String
Tabelle(1,1) = "Thorben"
Tabelle(1,2) = "Ufologe"
Tabelle(1,3) = "Bonn"
Tabelle(1,4) = "35"
Tabelle(2,1) = "Mandy"
Tabelle(2,2) = "Spiritistin"
Tabelle(2,3) = "Erfurt"
Tabelle(2,4) = "42"
Tabelle(3,1) = "Siggi"
Tabelle(3,2) = "Guru"
Tabelle(3,3) = "Rosenheim"
Tabelle(3,4) = "72"
Tabelle(4,1) = "Walburga"
Tabelle(4,2) = "Schlagersaengerin"
Tabelle(4,3) = "Duisburg"
Tabelle(4,4) = "58"
Tabelle(5,1) = "Aalfred"
Tabelle(5,2) = "Krabbenpuler"
Tabelle(5,3) = "Kiel"
Tabelle(5,4) = "29"
Print "Name | Beruf | Wohnort | Alter"
Print "--------------------------------------------------------------------------"
For i As Integer = LBound(Tabelle,1) To UBound(Tabelle,1)
Print Using "\ \ | \ \ | \ \ | \ \"; _
Tabelle(i,1); Tabelle(i,2); Tabelle(i,3); Tabelle(i,4)
Next i
Print
Print "Jetzt wird sortiert!"
Print
' BubbleSort
For j As Integer = UBound(Tabelle,1) To LBound(Tabelle,1)+1 Step -1
For i As Integer = LBound(Tabelle,1) To j-1
If( Tabelle(i,1) > Tabelle(i+1,1) ) Then
For spalte As Integer = LBound(Tabelle,2) To UBound(Tabelle,2)
Swap Tabelle(i,spalte), Tabelle(i+1, spalte)
Next spalte
End If
Next i
Next j
Print "Name | Beruf | Wohnort | Alter"
Print "--------------------------------------------------------------------------"
For i As Integer = LBound(Tabelle,1) To UBound(Tabelle,1)
Print Using "\ \ | \ \ | \ \ | \ \"; _
Tabelle(i,1); Tabelle(i,2); Tabelle(i,3); Tabelle(i,4)
Next i
GetKey
End |
Und so sähe das für 3000 Datensätze aus. Auf meinem mittlerweile über 7 Jahre alten PC dauert das Sortieren mit BubbleSort übrigens 0,27 Sekunden... 
| Code: | Dim Tabelle(1 To 3000, 1 To 4) As String
' Zufallseingaben generieren
Randomize Timer
Dim Zufallsname As String
For i As Integer = LBound(Tabelle,1) To UBound(Tabelle,1)
For j As Integer = 1 To 3
Zufallsname = ""
For zeichen As Integer = 1 To (5 + Int(RND*15))
If( zeichen = 1 ) Then
Zufallsname += Chr(65+Int(RND*26))
Else
Zufallsname += Chr(97+Int(RND*26))
End If
Next zeichen
Tabelle(i,j) = Zufallsname
Next j
Tabelle(i,4) = Ltrim(Str(18+Int(RND*80))) 'Zufaelliges Alter
Next i
' Zufallsdaten anzeigen
Print "Name | Beruf | Wohnort | Alter"
Print "--------------------------------------------------------------------------"
For i As Integer = LBound(Tabelle,1) To UBound(Tabelle,1)
Print Using "\ \ | \ \ | \ \ | \ \"; _
Tabelle(i,1); Tabelle(i,2); Tabelle(i,3); Tabelle(i,4)
Next i
Print
Print Ltrim(Str(UBound(Tabelle,1) - LBound(Tabelle,1) + 1)) + " zufaellige Datensaetze generiert."
Print "Bitte beliebige Taste druecken zum Sortieren und fuer Zeitmessung!"
Print
Print
GetKey
Dim Startzeit As Double
Dim Endzeit As Double
Startzeit = TIMER
' Sortieren mit BubbleSort
For j As Integer = UBound(Tabelle,1) To LBound(Tabelle,1)+1 Step -1
For i As Integer = LBound(Tabelle,1) To j-1
If( Tabelle(i,1) > Tabelle(i+1,1) ) Then
For spalte As Integer = LBound(Tabelle,2) To UBound(Tabelle,2)
Swap Tabelle(i,spalte), Tabelle(i+1, spalte)
Next spalte
End If
Next i
Next j
Endzeit = TIMER
' Wie lange hat's gedauert?
Print
Print "Das Sortieren hat "; Ltrim(Str(Endzeit-Startzeit)); " Sekunden gedauert."
Print
Print "Beliebige Taste druecken, um sortierte Ergebnisse anzeigen zu lassen."
Print
GetKey
Print
' Sortierte Ergebnisse anzeigen
Print "Name | Beruf | Wohnort | Alter"
Print "--------------------------------------------------------------------------"
For i As Integer = LBound(Tabelle,1) To UBound(Tabelle,1)
Print Using "\ \ | \ \ | \ \ | \ \"; _
Tabelle(i,1); Tabelle(i,2); Tabelle(i,3); Tabelle(i,4)
Next i
GetKey
End |
Das Langsamste ist übrigens die Ausgabe der 3000 Zeilen auf dem Bildschirm. Das Sortieren ist Sekundenbruchteilen erledigt.
Viele Grüße!
Sebastian
_________________
Die gefährlichsten Familienclans | Opas Leistung muss sich wieder lohnen - für 6 bis 10 Generationen! |
|
| Nach oben |
|
|
ALWIM
Anmeldungsdatum: 08.08.2006
Beiträge: 1048
Wohnort: Niederbayern
|
| Verfasst am: 09.07.2017, 21:03 Titel: |
|
|
| Sebastian hat Folgendes geschrieben: | Hi ALWIM!
Für so eine geringe Datenmenge sollte bei einigermaßen aktueller Hardware selbst ein BubbleSort allenfalls Sekunden brauchen.
Was du beschreibst, ist ein zweidimensionales Array, also quasi eine Tabelle mit Zeilen und Spalten. Vermutlich möchtest du, dass Zeilen als Ganzes sortiert werden nach einer bestimmten Spalte, richtig?
Dein vorgeschlagener Algorithmus wird dazu nicht funktionieren: Der betrachtet den Inhalt der Spalten gar nicht, d.h. ob "Zitrone" vor "Apfel" steht oder umgekehrt. Sondern du vertauscht immer nur ein Element mit dem jeweils nächsten, egal, ob die Reihenfolge passt oder nicht. Und das 3000x hintereinander immer wieder von vorne.
Viele Grüße!
Sebastian |
Die Sortierung funktioniert nun! Ich war bei meiner Idee schon am richtigen Weg. Hatte ihn nur nicht optimiert! Das was ich im Quellcode drin hatte, funktionierte auch, nur war das ganze etwas zu langsam! Jetzt ist die Sortierung schneller. Vielen herzlichen Dank für die Aufklärung!
Gruß
ALWIM
_________________
SHELL SHUTDOWN -s -t 05 |
|
| Nach oben |
|
|
dreael
Administrator
Anmeldungsdatum: 10.09.2004
Beiträge: 2530
Wohnort: Hofen SH (Schweiz)
|
| Verfasst am: 10.07.2017, 17:50 Titel: |
|
|
Falls ein schöner Code ein Thema ist: Warum nicht mit TYPE eine Klasse erstellen mit den Tabellenfeldern als Attribute, danach einen eigenen "operator<" fürs Sortieren implementieren? Hier sonst ein Bespiel:
| Code: | Type Person
namen As String * 25
beruf As String * 25
wohnort As String * 20
alter As Integer
Declare Function toString()As String
End Type
Function Person.toString() As String
Return namen + Space(25 - Len(namen + "")) + beruf + Space(25 - Len(beruf + "")) + wohnort + _
Space(26 - Len(wohnort + "") - Len(Str(alter))) + Str(alter)
End Function
Operator>(p1 As Person, p2 As Person)As Integer
' Hier als Beispiel Wohnort als 1. Kriterium, danach der Name as Unterkriterium
If p1.wohnort = p2.wohnort Then
Return p1.namen > p2.namen
Else
Return p1.wohnort > p2.wohnort
EndIf
End Operator
Sub Sortieren(p() As Person)
Dim i As Integer, j As Integer
For i = LBound(p) To UBound(p) - 1
For j = i + 1 To UBound(p)
If p(i) > p(j) Then
Swap p(i), p(j)
EndIf
Next j
Next i
End Sub
Dim p(...) As Person => {("Thorben", "Ufologe", "Bonn", 35), _
("Mandy", "Spiritistin", "Erfurt", 42), ("Siggi", "Guru", "Rosenheim", 72), _
("Walburga", !"Schlagers\132ngerin", "Duisburg", 58), ("Aalfred", "Krabbenpuler", "Kiel", 29), _
("Hannes", "Besenbinder", "Rosenheim", 55), ("Anton", "Billettentwerter", "Erfurt", 28)}
Dim i As Integer
ScreenRes 640, 480, 4
Width 80, 30
Print "Vor der Sortierung"
For i = LBound(p) To UBound(p)
Print p(i).toString
Next i
Sortieren p()
Print
Print "Nach der Sortierung"
For i = LBound(p) To UBound(p)
Print p(i).toString
Next i
Sleep |
_________________
Teste die PC-Sicherheit mit www.sec-check.net |
|
| Nach oben |
|
|
ALWIM
Anmeldungsdatum: 08.08.2006
Beiträge: 1048
Wohnort: Niederbayern
|
| Verfasst am: 11.07.2017, 20:12 Titel: |
|
|
| dreael hat Folgendes geschrieben: | Falls ein schöner Code ein Thema ist: Warum nicht mit TYPE eine Klasse erstellen mit den Tabellenfeldern als Attribute, danach einen eigenen "operator<" fürs Sortieren implementieren? Hier sonst ein Bespiel:
| Code: | Type Person
namen As String * 25
beruf As String * 25
wohnort As String * 20
alter As Integer
Declare Function toString()As String
End Type
Function Person.toString() As String
Return namen + Space(25 - Len(namen + "")) + beruf + Space(25 - Len(beruf + "")) + wohnort + _
Space(26 - Len(wohnort + "") - Len(Str(alter))) + Str(alter)
End Function
Operator>(p1 As Person, p2 As Person)As Integer
' Hier als Beispiel Wohnort als 1. Kriterium, danach der Name as Unterkriterium
If p1.wohnort = p2.wohnort Then
Return p1.namen > p2.namen
Else
Return p1.wohnort > p2.wohnort
EndIf
End Operator
Sub Sortieren(p() As Person)
Dim i As Integer, j As Integer
For i = LBound(p) To UBound(p) - 1
For j = i + 1 To UBound(p)
If p(i) > p(j) Then
Swap p(i), p(j)
EndIf
Next j
Next i
End Sub
Dim p(...) As Person => {("Thorben", "Ufologe", "Bonn", 35), _
("Mandy", "Spiritistin", "Erfurt", 42), ("Siggi", "Guru", "Rosenheim", 72), _
("Walburga", !"Schlagers\132ngerin", "Duisburg", 58), ("Aalfred", "Krabbenpuler", "Kiel", 29), _
("Hannes", "Besenbinder", "Rosenheim", 55), ("Anton", "Billettentwerter", "Erfurt", 28)}
Dim i As Integer
ScreenRes 640, 480, 4
Width 80, 30
Print "Vor der Sortierung"
For i = LBound(p) To UBound(p)
Print p(i).toString
Next i
Sortieren p()
Print
Print "Nach der Sortierung"
For i = LBound(p) To UBound(p)
Print p(i).toString
Next i
Sleep |
|
Schöner Code muss es nicht unbedingt sein. Es muss nur funktionieren! Und das tut es.
Gruß
ALWIM
_________________
SHELL SHUTDOWN -s -t 05 |
|
| Nach oben |
|
|
St_W
Anmeldungsdatum: 22.07.2007
Beiträge: 958
Wohnort: Austria
|
| Verfasst am: 11.07.2017, 21:14 Titel: |
|
|
| ALWIM hat Folgendes geschrieben: | | Schöner Code muss es nicht unbedingt sein. Es muss nur funktionieren! |
Also diese Einstellung würde ich nochmal überdenken 
Es gibt eigentlich so gut wie keinen Grund unsauberen Code sauberem Code vorzuziehen, umgekehrt gibt es aber viele Gründe guten (schönen) Code zu schreiben.
Sünden in der Vergangenheit holen einen meist irgendwann wieder ein. Spätestens dann wirst du dir wünschen es gleich ordentlich gemacht zu haben.
_________________
Aktuelle FreeBasic Builds, Projekte, Code-Snippets unter http://users.freebasic-portal.de/stw/
http://www.mv-lacken.at Musikverein Lacken (MV Lacken) |
|
| Nach oben |
|
|
nemored
Anmeldungsdatum: 22.02.2007
Beiträge: 4710
Wohnort: ~/
|
| Verfasst am: 12.07.2017, 16:40 Titel: |
|
|
Und der große Vorteil an "schönem Code mit TYPE" ist, dass bei einem neuen Anwendungsbereich nur noch der Operator > korrekt angepasst werden muss, und schon funktioniert die Sortier-Routine für einen komplett anderen Datentyp.
(Bei mir ist dann nur das Problem, dass ich immer irgendwelche komischen Extrawünsche habe, wie das parallele Sortieren zweier Listen, wo sich aus Performance-Gründen das Zusammenkopieren zu einem UDT nicht lohnt, weshalb ich mein QuickSort letztendlich doch immer wieder neu anpasse  aber auch da ist das mit "schönen Code" sehr viel einfacher als bei "Code, der einfach nur funktioniert".)
_________________
Deine Chance beträgt 1:1000. Also musst du folgendes tun: Vergiss die 1000 und konzentriere dich auf die 1. |
|
| Nach oben |
|
|
Sebastian
Administrator
Anmeldungsdatum: 10.09.2004
Beiträge: 5969
Wohnort: Deutschland
|
|
| Nach oben |
|
|
ALWIM
Anmeldungsdatum: 08.08.2006
Beiträge: 1048
Wohnort: Niederbayern
|
| Verfasst am: 15.07.2017, 23:24 Titel: Re: TYPE |
|
|
Auch wenn UDTs besser sind, so programmiere ich halt nicht! Es geht ja anders auch, wie man sieht. Mein Programm funktioniert ja! Erfolgreich getestet bei einem Turnier.
| Zitat: | | Sünden in der Vergangenheit holen einen meist irgendwann wieder ein. Spätestens dann wirst du dir wünschen es gleich ordentlich gemacht zu haben. |
Das habe ich bei meinem Programm schon gemerkt! Aber da hätte mir ein UDT auch nicht geholfen.
| Zitat: | | Also diese Einstellung würde ich nochmal überdenken |
Werde ich vielleich mal tun. Aber im Moment, komme ich so damit klar!
Trotzdem vielen herzlichen Dank für die Hilfe!
Gruß
ALWIM
_________________
SHELL SHUTDOWN -s -t 05 |
|
| Nach oben |
|
|
dreael
Administrator
Anmeldungsdatum: 10.09.2004
Beiträge: 2530
Wohnort: Hofen SH (Schweiz)
|
| Verfasst am: 16.07.2017, 19:01 Titel: Re: TYPE |
|
|
| ALWIM hat Folgendes geschrieben: | | Auch wenn UDTs besser sind, so programmiere ich halt nicht! ;) Es geht ja anders auch, wie man sieht. Mein Programm funktioniert ja! Erfolgreich getestet bei einem Turnier. |
Das allesentscheidende Stichwort: Wartbarkeit!
Software Engineering ist nun einmal ein komplexer Prozess (aktuell lese ich auch wieder gerade ein iX-Sonderheft rund ums Thema agile Softwareentwicklung z.B. mit Scrum).
In der professionellen IT-Welt generiert nun einmal ein schlecht geschriebener Code sog. technische Schulden. Heisst ganz praktisch gesprochen: Steht ein Änderungswunsch im Raum, so rächt sich ein schlecht geschriebener Code später entsprechend als erheblicher (zeitlicher und finanzieller) Mehraufwand, weil im Extremfall ein komplettes Neuschreiben (Refactoring) nötig ist.
Fähige Softwarefirmen wenden deshalb beispielsweise den Code Review an, d.h. ein bewusst unvoreingenommener Software-Entwickler versucht den Code seines Kollegen zu verstehen und nachvollziehen. Ist dies nicht (mit vernünftigem Aufwand) möglich, dann sollte sich der ursprüngliche Entwickler ernsthaft einmal mit den Grundprinzipien von Clean Code auseinandersetzen.
Empfehlun von mir: Selbst im Hobbybereich ist es sinnvoll, sich mit der letztgenannten Thematik auch einmal etwas auseinanderzusetzen.
_________________
Teste die PC-Sicherheit mit www.sec-check.net |
|
| Nach oben |
|
|
grindstone
Anmeldungsdatum: 03.10.2010
Beiträge: 1283
Wohnort: Ruhrpott
|
| Verfasst am: 17.07.2017, 10:18 Titel: |
|
|
| dreael hat Folgendes geschrieben: | | Fähige Softwarefirmen wenden deshalb beispielsweise den Code Review an, d.h. ein bewusst unvoreingenommener Software-Entwickler versucht den Code seines Kollegen zu verstehen und nachvollziehen. Ist dies nicht (mit vernünftigem Aufwand) möglich, dann sollte sich der ursprüngliche Entwickler ernsthaft einmal mit den Grundprinzipien von Clean Code auseinandersetzen. |
Das könnten auch einige C - Programmierer gebrauchen, die ihren vollständig unkommentierten Quellcode auf 50 oder 60 undurchschaubar voneinander abhängige Minidateien verteilen.  (Wäre vielleicht mal ein lohnendes Projekt: Ein FB-Programm, das solche Abhängigkeiten übersichtlich in einer Baumstruktur darstellt...)
Und was ALWIM betrifft: Wenn man das Programmieren im Spaghetti - Stil gewohnt ist (und damit bisher ganz gut zurechtkam), erfordert die Einsicht in die Vorteile von UDTs -wie ich aus eigener Erfahrung weiss- einen gewissen Leidensdruck. Wenn man zum ersten Mal in einem selbstgeschriebenen Programm vollkommen den Überblick verloren hat, dann ist es soweit. Haben wir also noch etwas Geduld, das wird schon! 
Gruß
grindstone
_________________
For ein halbes Jahr wuste ich nich mahl wie man Proggramira schreibt. Jetzt bin ich einen! |
|
| Nach oben |
|
|
|
|
Du kannst keine Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum nicht antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.
|
|
FAQ
Suchen
Mitgliederliste
Benutzergruppen
Registrieren
Profil
Einloggen, um private Nachrichten zu lesen
Login
