| Vorheriges Thema anzeigen :: Nächstes Thema anzeigen |
| Autor |
Nachricht |
Muttonhead
Anmeldungsdatum: 26.08.2008
Beiträge: 564
Wohnort: Jüterbog
|
 Verfasst am: 01.03.2023, 20:35 Titel: Datenarray und Double Linked List |
 |
|
Hallo @all.
Ich habe versucht ein Datenfeld (aus einer .csv) mit verschachtelten Double Linked Lists zu realisieren, anstatt eines Arrays.
Das funktioniert eigentlich auch ganz gut soweit.
Im Speicher sieht das dann ungefähr so aus:
Die Nodes der "Haupliste" sollen die Zeilen darstellen. An diesen "ZeilenNodes" ist jeweils wieder
eine Linked List gekoppelt und deren Nodes stellen dann die eigentlichen Zellen dar.
| Code: | LL
|
|
node1 LL----node1----node2----node3)...
(Zeile) (Zelle) (Zelle) (Zelle)
|
|
node2 LL----node1----node2----node3)...
(Zeile) (Zelle) (Zelle) (Zelle)
|
|
node3 LL----node1----node2----node3)...
(Zeile) (Zelle) (Zelle) (Zelle)
.
.
. |
Der Vorteil für mich hier: in einer Zeile steht der "komplette Datensatz" hintereinander.
Das einzige Problem was ich damit hab: Es gibt praktisch keinen Spaltenbezug.
Habe das auch schon um 90Grad gedreht versucht, logischerweise bekommt man dann den Datensatz einer Zeile nur sehr aufwendig zusammen. Dafür kann man dann eine Spalte gut durchsuchen
Es fehlt also immer eine Verlinkungsichtung.
Gibt es soetwas wie eine 2dimensionale LL? Allerdings möchte ich mir den Aufwand beim Löschen,Verschieben usw
nicht vorstellen.
Würdet ihr sowas überhaupt via LL lösen?
Mutton |
|
| Nach oben |
|
 |
nemored
Anmeldungsdatum: 22.02.2007
Beiträge: 4648
Wohnort: ~/
|
| Verfasst am: 01.03.2023, 21:29 Titel: |
|
|
Zweidimensionale Listen kann ich mir insofern nicht vorstellen, weil es dann nach meiner Definition keine Liste mehr wäre. Andere zwei- oder mehrdimensionale verlinkte Strukturen sind selbstverständlich vorstellbar. Aber wie du schon schreibst - die Verlinkungen zu pflegen ist höchstwahrscheinlich ziemlich grausam. Am ehesten denke ich an einen Baum, aber wenn ich es richtig verstehe, machst du das bereits.
Ich würde wahrscheinlich einen wohl sehr unkonventionellen Weg wählen:
Die Zeilen können untereinander über eine LL verlinkt sein. Der Zeileninhalt ist allerdings in einem String (als Array-Ersatz) gespeichert; je 4 oder 8 Byte (plattformabhängig) für den Speicherplatz eines Eintrags. String deshalb, weil man den ohne Aufwand verlängern oder in der Mitte etwas einfügen oder löschen kann (wenn das nicht nötig ist, tut es auch ein Array). Es existiert dann zwar immer noch keine Spaltenverlinkung, aber die Pointer für die Einträge derselben Spalte stehen an derselben Positon der Strings.
Lässt sich damit was anfangen?
_________________
Deine Chance beträgt 1:1000. Also musst du folgendes tun: Vergiss die 1000 und konzentriere dich auf die 1. |
|
| Nach oben |
|
|
Muttonhead
Anmeldungsdatum: 26.08.2008
Beiträge: 564
Wohnort: Jüterbog
|
| Verfasst am: 01.03.2023, 22:13 Titel: |
|
|
| nemored hat Folgendes geschrieben: | | Zweidimensionale Listen kann ich mir insofern nicht vorstellen, weil es dann nach meiner Definition keine Liste mehr wäre. |
...öhhm, lass mich kurz nachdenken... jahhh, keine Liste, per Definition 
| nemored hat Folgendes geschrieben: |
Lässt sich damit was anfangen? |
Je länger ich drüber nachdenke, doch, die Idee gefällt mir 
Der gleiche Offset im "PointerString" liefert mir dann alle Zeiger der Zellen einer Spalte.
vielen Dank für die Inspiration
Mutton |
|
| Nach oben |
|
|
grindstone
Anmeldungsdatum: 03.10.2010
Beiträge: 1235
Wohnort: Ruhrpott
|
| Verfasst am: 02.03.2023, 15:08 Titel: |
|
|
Und warum dann nicht ein 2-dimensionales Array von Pointern, die jeweils auf den Inhalt der Zelle zeigen? Das wäre doch viel übersichtlicher und auch einfacher zu handhaben.
Oder (wenn es denn unbedingt eine Liste sein soll) eine Mischform, bei der jeder Zeilen-node ein Array mit Pointern auf Spalten-nodes enthält.
Denkbar wäre auch, daß jeder Spalten-node einen Index mitbekommt, der dann als Spaltennummer dient.
Oder habe ich da etwas falsch verstanden?
Gruß
grindstone
_________________
For ein halbes Jahr wuste ich nich mahl wie man Proggramira schreibt. Jetzt bin ich einen! |
|
| Nach oben |
|
|
Muttonhead
Anmeldungsdatum: 26.08.2008
Beiträge: 564
Wohnort: Jüterbog
|
| Verfasst am: 02.03.2023, 20:57 Titel: |
|
|
nein nein, hast du nicht.
Aber wie löst man Zeilen/Spalten- Operationen in einem Array?
Wie gesagt, ich such nur nach ein paar Inspirationen, da ich grad die Erfahrung gemacht hab: mal spontan die Daten-Organisation zu ändern ist, wie neu schreiben.
Fakt ist: eine LL ist eindimensional und funktioniert auch nur in dieser Richtung gut. another case for Captain Obvious 
Mutton |
|
| Nach oben |
|
|
nemored
Anmeldungsdatum: 22.02.2007
Beiträge: 4648
Wohnort: ~/
|
| Verfasst am: 02.03.2023, 23:01 Titel: |
|
|
Die grundsätzliche Frage ist, soll die Datengröße während der Laufzeit erweitert, verkleinert, umstrukturiert ... werden? Dann ist ein Array ziemlich mühselig, vor allem, wenn du eine Zeile oder Spalte mittendrin einfügen oder löschen willst (aber ganz allgemein ist das Redimensionieren eines zweidimensionalen Arrays nicht problemlos). Ist die Anzahl der Zeilen und Spalten nach der Initialisierung fix, ist ein Array deutlich einfacher zu gestalten. Hängt halt davon ab, was die Datenstruktur leisten können soll.
_________________
Deine Chance beträgt 1:1000. Also musst du folgendes tun: Vergiss die 1000 und konzentriere dich auf die 1. |
|
| Nach oben |
|
|
Muttonhead
Anmeldungsdatum: 26.08.2008
Beiträge: 564
Wohnort: Jüterbog
|
| Verfasst am: 02.03.2023, 23:41 Titel: |
|
|
Richtig nemored, Lastenheft:
primär:
*Daten Raster, natürlich ist dann mindestens 1 Spalte erforderlich
*Datensatz entspricht einer Zeile
*zur Laufzeit Zeile(Datensatz) anhängen
sekundär:
*zur Laufzeit Spalte anhängen
tertiär: ... sorry abitur und lateinfrei
*Spaltenverschiebung?
(und ausserhalb jeder Zeitrechnung)sci-fi:
*bestehende Zeilen sortierten auf Grundlage einer Spalte
... ich würde mich auf primär und sekundär beschränken wollen
Mutton |
|
| Nach oben |
|
|
grindstone
Anmeldungsdatum: 03.10.2010
Beiträge: 1235
Wohnort: Ruhrpott
|
| Verfasst am: 03.03.2023, 12:20 Titel: |
|
|
Meine erste spontane Idee:
Einen Type "Zeile" erstellen, der ein eindimensionales dynamisches Array enthält, dessen Größe der Anzahl der Spalten entspricht. Jede Instanz dieses Types stellt eine Zeile dar.
Dann einen weiteren Type "Tabelle" mit einem eindimensionalen dynamischen Array des Types "Zeile" erstellen. Die Größe dieses Arrays entspricht der Anzahl der Zeilen.
Alle Tabellenoperationen können dann mithilfe von Subs, Fuctions und Properties erledigt werden.
Zum Beispiel braucht für das Anhängen einer Zeile nur das Array im Type "Tabelle" um ein Element vergrößert werden, beim Anhängen einer Spalte muß diese Operation bei allen Elementen vom Type "Zeile" durchgeführt werden, was dann eine entsprechende Sub erledigen kann. Ähnliches gilt für alle anderen Operationen.
Gruß
grindstone
EDIT:
Dieser Programmschnippsel sollte eigentlich zur Erläuterung dienen, aber offensichtlich lassen sich Types mit dynamischen Arrays nicht verschachteln. | Code: | Type tZeile
As Byte dummy
Static As Integer spalte()
End Type
ReDim As Integer tZeile.spalte(0)
Type tTabelle
As Byte dummy
Static As tZeile zeile()
End Type
ReDim As tZeile tTabelle.zeile(0)
Dim test As tTabelle
'5 x 6 - tabelle erstellen
ReDim test.zeile(5) '5 zeilen
For x As Integer = 1 To UBound(test.zeile) 'für jede zeile
With test.zeile(x)
ReDim .spalte(6) '6 spalten
End With
Next
'einige werte in die Tabelle schreiben
test.zeile(1).spalte(1) = 1
test.zeile(2).spalte(2) = 2
test.zeile(3).spalte(3) = 3
test.zeile(4).spalte(4) = 4
'tabelle ausdrucken
For z As Integer = 1 To UBound(test.zeile)
With test.zeile(z)
For s As Integer = 1 To UBound(test.zeile(z).spalte)
Print .spalte(s); " ";
Next
End With
Print
Next
Sleep
|
Mit einem statischen Array in "tZeile" funktioniert es, aber das ist ja nicht Sinn der Sache. 
Damit wird nemoreds Idee mit dem String als Zeile wieder interessant.
Auf solch einen String kannst du sehr bequem mit gecasteten Pointern zugreifen. Dieser Programmausschnitt zeigt, wie ich meine Audiodateien normalisiere:
| Code: | Dim As String g 'enthält die audiodaten
Dim As Single verst 'verstärkungsfaktor
Dim As Single Ptr gpf
Dim As Short Ptr gpp
...
Select Case audioformat 'audiodaten umrechnen
Case 1 'pcm
For gpp = Cast(Short Ptr,StrPtr(g)) To Cast(Short Ptr,StrPtr(g) + Len(g) - 1)
*gpp *= verst
Next
Print #2, g;
Case 3 '32bit float
For gpf = Cast(Single Ptr,StrPtr(g)) To Cast(Single Ptr,StrPtr(g) + Len(g) - 1)
*gpf *= verst
Next
Print #2, g;
End Select
... |
_________________
For ein halbes Jahr wuste ich nich mahl wie man Proggramira schreibt. Jetzt bin ich einen! |
|
| Nach oben |
|
|
Muttonhead
Anmeldungsdatum: 26.08.2008
Beiträge: 564
Wohnort: Jüterbog
|
| Verfasst am: 04.03.2023, 08:04 Titel: |
|
|
Nur nochmal zur Erklärung warum LL:
In meinem Dauerprojekt wird jeder allozierter Speicher in nem Dutzend zentraler Listen verwaltet, sozusagen mein "RAM-Management". Zum Programmende wird, hoffentl., der gesamte Speicher durch einen allg. Destruktor wieder freigegeben.
Darum meine Obsession auf die LL. Zumindest in diesem speziellen Fall wirkt das dann doch etwas, naja aufgeblasen...
| Code: | 'Haupttype für LL
type node extends object
prev_node as node ptr'double linked List
next_node as node ptr'double linked List
ntype as integer
Index as integer
Owner as _sGUIList ptr
'Data:
'für den einfachsten Fall einer Liste kann man in einem node einen Zeiger hinterlegen
anypointer as any ptr
end type
type Cell extends node
Text as string
end type |
Wie man sieht, erbt dann auch noch jedes UDT den node Type und ist damit
"listenfähig".
Ein gewaltiger Überbau für nen String, und wahrlich nicht schön... aber vllcht kommen ja noch mehr Daten in die Zelle.
Will damit eigentl auch nur sagen, selbst jede erzeugte Zelle ist definitiv schon Bestandteil einer Liste.
Nun gut, vielen Dank nochmal Euch
Die Sache mit dem String als "Pointer-Look-Up" werd ich benutzen, vielleicht sogar zusätzlich.
Mutton |
|
| Nach oben |
|
|
grindstone
Anmeldungsdatum: 03.10.2010
Beiträge: 1235
Wohnort: Ruhrpott
|
| Verfasst am: 04.03.2023, 13:31 Titel: |
|
|
Ah, langsam wird die Sache klarer. Ich habe mir noch einmal deinen ersten Post angesehen. Ein Spaltenbezug liesse sich doch ganz einfach (na ja...) durch zusätzliches vertikales Verlinken herstellen. Dann kannst du dich sowohl hoizontal als auch vertikal durch die Tabelle hangeln. Und auch Operationen wie Einfügen, Löschen oder Vertauschen von Spalten oder Zeilen sind dann kein Hexenwerk mehr: | Code: | 'Haupttype für LL
Type node extends object
prev_node As node Ptr'double linked List
next_node As node Ptr'double linked List
upper_node As node Ptr'vom node der oberen liste
lower_node As node Ptr'zum node der unteren liste
ntype As Integer
Index As Integer
Owner As _sGUIList Ptr
'Data:
'für den einfachsten Fall einer Liste kann man in einem node einen Zeiger hinterlegen
anypointer As Any Ptr
End Type
Type Cell extends node
Text As String
End Type
LL
|
|
node1 LL----node1----node2----node3)...
(Zeile) (Zelle) (Zelle) (Zelle)
| | | |
| | | |
node2 LL----node1----node2----node3)...
(Zeile) (Zelle) (Zelle) (Zelle)
| | | |
| | | |
node3 LL----node1----node2----node3)...
(Zeile) (Zelle) (Zelle) (Zelle)
|
Gruß
grindstone
_________________
For ein halbes Jahr wuste ich nich mahl wie man Proggramira schreibt. Jetzt bin ich einen! |
|
| Nach oben |
|
|
Muttonhead
Anmeldungsdatum: 26.08.2008
Beiträge: 564
Wohnort: Jüterbog
|
| Verfasst am: 04.03.2023, 19:01 Titel: |
|
|
@grindstone:
sieht erstmal logisch aus, aber willst du upper/lower_node wirklich pflegen?
wenn du ein Zeile verschieben würdest, was müsstest du alles neu verlinken?
Mal abgesehen von den Spezialfällen Listenanfang und Ende:
(wandernde Zeile selbst + 2*neue Nachbarn + 2*alte Nachbarn) * Anzahl Spalten
nee, willste nicht 
mein Idee wäre jetzt eine spezielles Zeilen UDT, das sowohl die zwangsläufige Zellen-LL enthält als auch einen String, der diese Liste als "Pointer-Map" abbildet. Auch diese muss natürlich bei entsprechenden Spaltenoperationen aktualisiert/gepflegt werden müssen
Mutton |
|
| Nach oben |
|
|
nemored
Anmeldungsdatum: 22.02.2007
Beiträge: 4648
Wohnort: ~/
|
| Verfasst am: 04.03.2023, 21:02 Titel: |
|
|
Ich habe nochmal überlegt, in welcher zweidimensionale Datenstruktur man leicht ganze Blöcke verschieben, einfügen und löschen kann. Tut mir leid, dass meine Antwort jetzt ziemlich abstrus ist - aber ich bin bei FB.Image gelandet.  Jedes Pixel repräsentiert einen 32-Bit-Pointer (bei 64 Bit braucht man dann immer zwei Pixel pro Eintrag, was zwar nicht mehr so schön, aber zumindest möglich ist); Einfügen/Löschen einer Zeile oder Spalte funktioniert sehr einfach durch Verschieben des rechten oder unteren Blocks mittels GET und PUT. Möglicherweise braucht die Datenstruktur dann aber zwingend SCREENRES.
Wie gesagt, tut mir leid, dass ich mit so verrückten Sachen komme ... 
_________________
Deine Chance beträgt 1:1000. Also musst du folgendes tun: Vergiss die 1000 und konzentriere dich auf die 1. |
|
| Nach oben |
|
|
Muttonhead
Anmeldungsdatum: 26.08.2008
Beiträge: 564
Wohnort: Jüterbog
|
| Verfasst am: 04.03.2023, 21:52 Titel: |
|
|
und | Code: | | cast( any ptr,Point(x,y,map) |
liefert mir dann die Zelle?
cool
Trotzdem darf man nicht vergessen, das Image ist "nur" ein Abbild der Verlinkung, der Organisationsstruktur, trotzdem musst du nach wie vor sämtliche Pointer extern speichern.
Ein | Code: | | pset map,(x,y),[ptr] |
schreibt zwar die Adresse ins Image, wäre aber bei irgendwelchen get() put() shifts lost, aber defintiv noch alloziert
Mutton |
|
| Nach oben |
|
|
ThePuppetMaster
Anmeldungsdatum: 18.02.2007
Beiträge: 1837
Wohnort: [JN58JR]
|
| Verfasst am: 04.03.2023, 22:02 Titel: |
|
|
Hallöle ... jetz klinke ich mich auch mal in das Thema ein ...
@Mutton ... prinzipiel gibt es in deinem Fall ja nur 2 Möglichkeiten. Entweder machst du es mit einem sehr schnell arbeitendem Array oder mit einer vergleichsweise sehr langsam arbeitenden Linked-List.
Wieso schnell und langsam? .. Nun .. Das beruht prinzipiel auf der Mechanik hinter beiden Verfahren.
Array: Ein Array-Element anzusprechen funktioniert prinzipiel mit einer einfachen Rechenoperation, welche ein PC sehr flott ausführen kann. Nachteil: Es MUSS ein zusammenhängender Speicherbereich assoziiert werden.
LL: Der Vorteil hier ist die flexibilität des Speicherbereichs. Es muss eben nicht zusammenhängend sein. Dafür allerdings kann man den Speicher nicht direkt ansprechen, sondern muss sich immer duchhangeln.
Schlussfolgernd kann man das ganze damit zusammenfassen, das ein Array sicher sinvoller ist, wenn man: 1. eine unbegrenzt große Anzahl an Speicher zur Verfügung hat und 2. man auch sehr schnell lesende Operationen darauf ausführen möchte.
Ist der Speicherplatz begrenzt, dann sollte man eine Linked-List nutzen, da dies nicht zusammenhängend sein muss. Allerdings sind lesende Operationen dafür sehr langsam.
Auch muss hier unterschieden werden, ob Primär gelesen oder geschrieben wird.
Lesen aus einem Array ist deutlich schneller als aus einer LL. Schreiben hingegen ist mit einer LL schneller als mit einem Array.
Der Grund liegt auch hier wieder in der systematik. Linked Lists sind Speicherbläcke, welche unabhäängig Ihrer Umgebung existieren können, und nur durch das "Zeigen" auf Ihre Umgebung verweisen. Ein Array hingegen ist ein Block der "umgebaut" werden muss.
Einige Vorschläge in diesem Topic sind schon sehr Interessant. So z.B. von nemored, welcher die möglichkeit von Grafikoerationen vorgeschlagen hat. Dies ist in der tat eine sehr gute Möglichkeit Array's schreibend zu manipulieren. Als Tip kann ich dir noch anführen, das man bei 64bit nicht mit 2 Bytes in einer Map arbeitet, sondern lieber 2 map's macht. Eine für das High und eine für das Low-Byte. Das ändert zum einen das verfahren der Manipulation auf 2x <Aktion> und zum anderen halbiert dies den Speicherverbrauch in 2 seperate blöcke.
Ein weiterer Vorteil ist die nutzbarkeit der Grafikeinheit (GPU). Die ist auf solche operationen spezialisiert. Kann also sehr viel schneller Speicherverschiebungen ausführen. Leider ist auch auch dies bei größeren Datenmengen der LL deutlich unterlegen.
Du solltest dir also zuerst einmal Gedanken darüber machen, was dein Primäres Ziel sein wird, bevor du dich für eine Basistechnik entscheiden kannst.
Für beides gibt es sehr gute Optimierungsmöglichkeiten, sofern eben entsprechend auch das richtige Verhalten bestimmt wurde.
MfG
TPM
_________________
[ WebFBC ][ OPS ][ ToOFlo ][ Wiemann.TV ] |
|
| Nach oben |
|
|
grindstone
Anmeldungsdatum: 03.10.2010
Beiträge: 1235
Wohnort: Ruhrpott
|
| Verfasst am: 04.03.2023, 22:19 Titel: |
|
|
Zumindest die Notwendigkeit von Screenres dürfte kein Problem sein. Wenn das Ganze für sGUI ist, ist Screenres ja sowieso aktiv.
Gruß
grindstone
_________________
For ein halbes Jahr wuste ich nich mahl wie man Proggramira schreibt. Jetzt bin ich einen! |
|
| Nach oben |
|
|
nemored
Anmeldungsdatum: 22.02.2007
Beiträge: 4648
Wohnort: ~/
|
| Verfasst am: 04.03.2023, 22:51 Titel: |
|
|
| ThePuppetMaster hat Folgendes geschrieben: | | Als Tip kann ich dir noch anführen, das man bei 64bit nicht mit 2 Bytes in einer Map arbeitet, sondern lieber 2 map's macht. Eine für das High und eine für das Low-Byte. Das ändert zum einen das verfahren der Manipulation auf 2x <Aktion> und zum anderen halbiert dies den Speicherverbrauch in 2 seperate blöcke. |
Stimmt, da fallen dann die (aus meiner Sicht eher unangenehmen) Rechenoperationen weg. Sollte sich auch mit Preprozessoren leicht plattformunabhängig gestalten lassen - mit dem 32-Bit-Compiler wird die High-Byte-Map nicht angelegt und die Adressen direkt aus der Low-Byte-Map gelesen bzw. gespeichert.
_________________
Deine Chance beträgt 1:1000. Also musst du folgendes tun: Vergiss die 1000 und konzentriere dich auf die 1. |
|
| Nach oben |
|
|
ThePuppetMaster
Anmeldungsdatum: 18.02.2007
Beiträge: 1837
Wohnort: [JN58JR]
|
|
| Nach oben |
|
|
|
FAQ
Suchen
Mitgliederliste
Benutzergruppen
Registrieren
Profil
Einloggen, um private Nachrichten zu lesen
Login
