 |
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 |
St_W
Anmeldungsdatum: 22.07.2007
Beiträge: 956
Wohnort: Austria
|
 Verfasst am: 08.01.2010, 00:22 Titel: Linked List No. 2 |
 |
|
Schon wieder eine Liste wird sicher manch einer von euch sagen - und da habt ihr auch nicht ganz unrecht. Im Gegensatz zu jener von Stueber (mit dem ich wie von ihm bereits erwähnt vor kurzem über u.a. dieses Thema diskutiert habe) handelt es sich bei dieser Liste jedoch und eine Liste, die auf Arrays basiert.
Ich hatte den Hintergedanken im Kopf die mir aus C# bekannte Liste möglichst gut nachzubilden. Und das ist mir meiner Ansicht nach auch ganz gut gelungen. Nur beim Indizieren fällt es ein kleines bisschen komplizierter aus, da FreeBasic keine Indexer unterstützt).
Falls wer die Listen in C# nicht kennt hier ein kleines Beispiel:
| Code: | List<int> meineListe = new List<int>();
meineListe.Add(3);
System.Console.WriteLine(meineListe[0].ToString()); |
Ich habe mich bemüht die Syntax so einfach und so gut wie möglich nachzubilden.
Features:
Meine Liste ist für *jeweils einen* bestimmten Datentyp ausgelegt. (Es können nicht mehrere verschiedene Datentypen in einer Liste vorkommen; sehr wohl kann es aber mehrere Listen geben, die jeweils unterschiedliche Datentypen beinhalten)
*Ohne Änderung der Quellcodes* können beliebige Datentypen verwendet werden (einzige Ausnahme: Strings, hier muss derzeit auf einen String ptr oder ein UDT zurückgegriffen werden, welches einen String enthält). Das Problem mit String versuche ich noch zu beseitigen.
Die meisten aus C# bekannten Funktionen:
| Code: | sub Add (value as datatype)
sub Add (values() as datatype)
sub AddRange cdecl (cnt as Integer, ...)
sub Clean()
function Count() as Integer
function Count(value as datatype) as Integer
function Exists(value as datatype) as Integer
function IndexOf(value as datatype) as Integer
function IndexOf(value as datatype, index as Integer) as Integer
function IndexOf(value as datatype, index as Integer, cnt as Integer) as Integer
sub Insert(index as Integer, value as datatype)
sub Insert(index as Integer, values() as datatype)
sub InsertRange cdecl (index as Integer, cnt as Integer, ...)
function LastIndexOf(value as datatype) as Integer
function LastIndexOf(value as datatype, index as Integer) as Integer
function LastIndexOf(value as datatype, index as Integer, cnt as Integer) as Integer
sub Remove(value as datatype)
sub RemoveAll(value as datatype)
sub RemoveAt(index as Integer)
sub RemoveRange(index as Integer, cnt as Integer)
sub Reverse() |
Einziger Unterschied zu C#: das Löschen aller Elemente der Liste heißt nicht Clear, da dieses Schlüsselwort bereits von FB vergeben ist, sondern Clean.
Verwendungsbeispiel:
| Code: | LL(Integer,Integer) 'Listentyp deklarieren mit Datentyp Integer und Namen LLInteger)
dim meineListe as LLInteger
meineListe.Add(3)
meineListe.Add(4)
meineListe.RemoveAt(0)
meineListe.Insert(0, 1)
for q as Integer = 0 to meineListe.Count()-1
print meineListe.Daten[q]
next
|
Download:
http://wurzinger.bplaced.net/files/programmierung/fb/List.bas
_________________
Aktuelle FreeBasic Builds, Projekte, Code-Snippets unter http://users.freebasic-portal.de/stw/
http://www.mv-lacken.at Musikverein Lacken (MV Lacken) |
|
| Nach oben |
|
 |
Stueber
Anmeldungsdatum: 07.07.2008
Beiträge: 202
|
| Verfasst am: 08.01.2010, 15:05 Titel: |
|
|
Hab mir die Implementierung angesehen und muss sagen Respekt. 
Ich hätte echt nicht gedacht das man "eine Liste, viele Datentypen" auch anders machen kann.
Für Leute die mit den Quelltexten nicht zurecht kommen:
Seine Liste benutzt Arrays, meine verkettete Listen, auf seine greift man mit [] zu, auf meine mit value(), seine ist Datentyp übergreifend durch #define's meine durch eine Container Klasse.
Versuch auch mal eine Map auf der Basis, die nimmt einem viel arbeit ab und würde mich interessieren wie du das implementierst. |
|
| Nach oben |
|
|
Stueber
Anmeldungsdatum: 07.07.2008
Beiträge: 202
|
| Verfasst am: 08.01.2010, 15:24 Titel: |
|
|
| Code: | dim a as datatype ptr = new datatype[this.__count+1]
for q as Integer = 0 to this.__count-1
memcpy(@a[q], @this.Daten[q], sizeof(datatype))
Next
this.Daten = a
this.Daten[this.__count] = value
this.__count += 1
|
Das ist deine add Funktion.
Wenn ich das richtig gesehen habe baust du hier ein riesen Speicherleck, vor allem bei UDTs.
Wenn die Liste Integer listet und sie 1000 Einträge hat, werden jedesmal wenn ein Eintrag hinzukommt 4kb Speicher belegt aber der alte wird nicht befreit.
Wenn es sich um eine UDT Liste handelt von einem UDT mit 20 Variablen kann das fatal enden.
Lösung:
| Code: | dim a as datatype ptr = new datatype[this.__count+1]
for q as Integer = 0 to this.__count-1
memcpy(@a[q], @this.Daten[q], sizeof(datatype))
Next
delete this.Daten
this.Daten = a
this.Daten[this.__count] = value
this.__count += 1
|
Wenn die Liste selbst nicht mit new angelegt wurde wird sie ja nach dem beenden der Funktion oder des Subs in dem sie erzeugt wurde gelöscht, aber der Array wird nicht wieder freigegeben.
Lösung: Einen Destruktor schreiben der den Array wieder freigibt.
Solltest du unbedingt beides machen, sofern ich den Quelltext richtig gedeutet habe. |
|
| Nach oben |
|
|
Stueber
Anmeldungsdatum: 07.07.2008
Beiträge: 202
|
| Verfasst am: 08.01.2010, 16:13 Titel: |
|
|
Im IRC hast du gesagt das du keine Speicherlecks bei 2 Milliarden durchläufen gefunden hast.
| Code: | LL(integer, intL)
Dim l as LLintL
dim as integer i = 0
do
i = i + 1
l.add(3)
loop until i = 200000
sleep |
Dieses Beispiel bei dem es nur um Integers geht verbraucht bei mir bei 200000 durchläufen ganze 2.6gb Speicher, danach stürtzt das Programm ab.
Eine Lösung dafür muss her, 2.6gb sind ja ziemlich viel 
Wenn ich delete bei add einfüge passiert garnichts, die Schleife läuft durch und das Programm belegt 3.4mb Speicher.
200000 * 4b = 800000b = 0.8mb
Da stimmt also noch immer was nicht, aber ist trotzdem weit von 2.6 gb entfernt.
Beim durchlauf mit einem "print i" ist mir übrigens noch etwas aufgefallen, was in der Praxis aber warscheinlich nur selten relevant ist:
Die ersten 10000 Einträge sind in ca. 2s hinzugefügt aber die letzten 10000 von 190000 bis 200000 dauern über 16s.
Ich will deine Liste keineswegs schlecht machen, das sind nur Verbesserungsvorschläge 
Übrigens gibt es in Qt eine Klasse die genau so funktioniert wie deine Liste, die heist QVector.
http://doc.trolltech.com/4.6/qvector.html
Schau dir doch da ein paar Memberfunktionen ab, da sind ein paar dabei die Sinn machen und du noch nicht hast. |
|
| Nach oben |
|
|
OneCypher
Anmeldungsdatum: 23.09.2007
Beiträge: 802
|
| Verfasst am: 08.01.2010, 17:27 Titel: |
|
|
Ich vermisse immer noch eine vernünftige schleifen-implementation die es erlaubt element für element durchzulaufen..
For Each ... in ..
...
Next
Gibts ja leider erstmal nich in Freebasic... trotzdem wärs schön eine ähnliche implementation sehen und benutzen zu können!
In meiner Collection.bi hab ich das per makro gelöst .. ist nicht die feinste methode aber immerhin ein bischen komfort.. |
|
| Nach oben |
|
|
Stueber
Anmeldungsdatum: 07.07.2008
Beiträge: 202
|
| Verfasst am: 08.01.2010, 17:39 Titel: |
|
|
Ich weis nicht genau warum, aber wenn du for each brauchst schau in meinen Thread, ich habs verwirklicht.
Es ist ein Makro das unverändert auch mit St_W's Liste funktioniert, da die benötigten Funktionen gleich heisen. |
|
| Nach oben |
|
|
28398
Anmeldungsdatum: 25.04.2008
Beiträge: 1917
|
| Verfasst am: 08.01.2010, 21:32 Titel: |
|
|
Einer der Gründe warum ich inzwischen zu C++ abgewandert bin, ist der, dass es in FB keine Templates gibt. Stattdessen muss man diese recht aufwändig und unkomfortabel mit Makros oder anderen Hacks nachbilden. Das ist besonders deswegen schlecht, weil der Compiler Fehler in einem Makro nicht im Makro aufzeigt, sondern an der Stelle, wo das Makro eingefügt wurde.
Würden Templates implementiert (was in einer vereinfachten Variante ohne Klassentemplates und Klassenmemberfunktionstemplates sowie explizite Templates nicht sehr aufwendig ist), würde das solche Sachen ganz arg vereinfachen und die Fehlerträchtigkeit auf ein Minimum reduzieren.
Ich finde es trotzdem schön, dass einige Leute sich noch mit Freebasic beschäftigen und trotz der Nachteile noch aktiv Software entwickeln.
Daumen hoch! |
|
| Nach oben |
|
|
Jojo
alter Rang
Anmeldungsdatum: 12.02.2005
Beiträge: 9736
Wohnort: Neben der Festplatte
|
| Verfasst am: 08.01.2010, 21:34 Titel: |
|
|
Das kann man aber auch umdrehen! Schön, dass manche Leute sich immer noch hinsetzen und mit C++ "trotz der Nachteile noch aktiv Software entwickeln".
_________________
» Die Mathematik wurde geschaffen, um Probleme zu lösen, die es nicht gäbe, wenn die Mathematik nicht erschaffen worden wäre.
 |
|
| Nach oben |
|
|
St_W
Anmeldungsdatum: 22.07.2007
Beiträge: 956
Wohnort: Austria
|
| Verfasst am: 09.01.2010, 03:28 Titel: |
|
|
In der Tat haben sich ein paar Fehler eingeschlichen, die ich bei meinen Tests durch glückliche Umstände nicht aufgetreten waren. Ich habe mich aber sofort an die Arbeit gemacht um die Fehler zu beheben und nun ist die Überarbeitete Version fertig.
Am Ende der Datei findet ihr unter den anderen Beispielen ein Beispiel zur Verwendung von einfachen Strings. Dabei wird der String in ein UDT eingebettet und mit Operatorüberladungen das Verhalten eines "normalen" Strings (fast) vollständig hergestellt. Ich werde dieses Verfahren bei Gelegenheit direkt in die Liste integrieren, wenn der Datentyp String angegeben wird.
Wichtige Änderung: UDTs werden weiterhin ohne jegliche Änderung an der Liste unterstützt, diese müssen jedoch jetzt zwei Voraussetzungen erfüllen:
1. Überladener = Operator zum Vergleich zweier UDTs dieses Typs
2. Überladener let Operator zum Kopieren der Daten zwischen zwei UDTs dieses Typs
Beispiele dazu finden sich ebenso im Programm (das String Beispiel gehört z.B. auch dazu)
Download
Downloadlink ist der selbe wie oben. Hier zur Sicherheit noch einmal:
>> Download <<
Hinweis: Da die Daten in einem Array verwaltet werden muss derzeit bei jeder Größenänderung der Liste das Array neu angelegt werden, was besonders bei größeren Listen längere Zeit beansprucht. Mir ist dieser Nachteil sehrwohl bekannt und ich bin dabei eine Milderung des Effekts zusammenzubasteln. Als Anwender der Liste ist es daher sinnvoll ein Array an Werten auf einmal hinzuzufügen, anstatt jeden Wert einzeln, da dies fast ums doppelte schneller ist.
@OneCypher: Ich verstehe nicht ganz wieso du foreach vermisst, da es doch mit einer FOR-Schleife so leicht zu implementieren ist:
| Code: | for q as Integer = 0 to Liste.Count()-1
dim Elem as Integer = Liste.Daten[q]
print Elem
next
'entspricht:
foreach Elem in Liste.Daten
print Elem
next |
@Jojo, 28398: Es ist ja nichts Neues, dass ihr euch nicht einig seid, darum hoffe ich die Grundsatzdiskussionen hier zu vermeiden.
Es ist schön, dass sowohl mit FB als auch mit C++ viele Leute (hoffentlich) sinnvolle Programme entwickeln. Jede Sprache ist für manches besser und eben auch für manches weniger gut geeignet, C++ und FB sind da keine Ausnahmen. Jeder soll in der Sprache programmieren, die ihm am Besten zusagt.
_________________
Aktuelle FreeBasic Builds, Projekte, Code-Snippets unter http://users.freebasic-portal.de/stw/
http://www.mv-lacken.at Musikverein Lacken (MV Lacken) |
|
| 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
