ArrayList für drei verschiedene Typen

@supertux
jeder, wie er s haben will.

@uwerothfeld
mal eine ganz blöde frage: wieso machst du das alles so ultra kompliziert? was du brauchst ist keine liste sondern ein simples array.

wenn man mal annimmt, dass deine zahlen messwerte sind, bekommst du von einem interrupt handler oder durch polling bei jedem durchlauf einen wert.

du allokierst zur compilierzeit derzeit einfach die maximale menge an werten. das ist schon mal ok, wenn du kein malloc hast. die frage ist nur, wieso du das über so einen komischen wrapper machen willst? es wär doch viel einfacher, das mit einem simplen pointer zu machen. das is schneller und braucht so gut wie gar keinen code.

du nimmst einen pointer auf elem, den du mit "content" initialisierst. jeden neuen messwert schreibst du an die stelle, auf die der pointer zeigt und inkrementierst diesen pointer danach.

zum berechnen der nicht-temporären werte machst du genau das gleiche und gehst somit deine "liste", die einfach nur ein array ist, durch.

es ist löblich, dass du dir viele gedanken machst, aber hier denkst du eindeutig viel zu kompliziert.

uwerothfeld

Morgen :),

also

besserwisser schrieb:

@uwerothfeld
mal eine ganz blöde frage: wieso machst du das alles so ultra kompliziert? was du brauchst ist keine liste sondern ein simples array.

Echt? Findest du es kompliziert? Finde ich eigentlich nicht, aber ok. Vielleicht liegt es daran, dass ich eigentlich eher aus der OO Ecke komme. Zugriffe direkt auf Datenstrukturen sind daher für mich etwas böses ;).

besserwisser schrieb:

wenn man mal annimmt, dass deine zahlen messwerte sind, bekommst du von einem interrupt handler oder durch polling bei jedem durchlauf einen wert.
du allokierst zur compilierzeit derzeit einfach die maximale menge an werten. das ist schon mal ok, wenn du kein malloc hast. die frage ist nur, wieso du das über so einen komischen wrapper machen willst?

Diese Annahme ist nicht ganz richtig. Es sind zwar quasi Messwerte, diese werden allerdings in einem Rutsch in die Liste geschrieben. Die Abarbeitung dieser Liste erfolgt dann allerdings durch verschiedene Funktionen und unterschiedliche Zeiten. Daher der Wrapper, da ich mir keine Gedanken machen wollte, wann wie und wo ich Zuzugreifen habe und ob eigentlich noch was da ist. Also Funktion A füllt die Liste und anschließend werden (hier nicht weiter wichtig) die Funktionen B und C aufgerufen, z.B. C-B-C-C-B-B-C. Nun will ich in B und C halt relativ einfach auf die Liste zugreifen können, ohne derren interna zu kennen. Daher soll mir die Liste sagen: Ich bin leer.

besserwisser schrieb:

du nimmst einen pointer auf elem, den du mit "content" initialisierst. jeden neuen messwert schreibst du an die stelle, auf die der pointer zeigt und inkrementierst diesen pointer danach.

Wie meinst das genau? Ich glaub dafür ist es noch zu früh für mich.

Im Moment ist die "Liste" in der Tat nur ein Array, richtig. Ich hätte gerne eher etwas in Richtung echter verketteter Liste gehabt, weiß aber nicht wie und ob überhaupt so etwas statisch geht, ohne Speicher zu verschwenden beim Elemente entfernen.

Gruß

supertux

uwerothfeld schrieb:

besserwisser schrieb:

du nimmst einen pointer auf elem, den du mit "content" initialisierst. jeden neuen messwert schreibst du an die stelle, auf die der pointer zeigt und inkrementierst diesen pointer danach.

Wie meinst das genau? Ich glaub dafür ist es noch zu früh für mich.

Im Moment ist die "Liste" in der Tat nur ein Array, richtig. Ich hätte gerne eher etwas in Richtung echter verketteter Liste gehabt, weiß aber nicht wie und ob überhaupt so etwas statisch geht, ohne Speicher zu verschwenden beim Elemente entfernen.

da du kein malloc hast (und wahrscheinlich keine sonstige Speicherverwaltungsfunktion hast, ist es schwer Speicher zur Laufzeit zu reservieren, deswegen reservierst zu zur Compilezeit den Speicher und benutzt diesen. Am einfachsten ist es dann mit einem Array. Das Problem mit dem obigen Ansatz ist es, wenn du Daten löscht, hinzufügst, wieder löscht, usw, dann fragmentiert sich der Speicher und müsstest defrgmentieren, damit du keinen Buffer Ovreflow erzeugst.

Ich hatte dieses Problem mit einem selbst geschriebenen Mikrokernel, da habe ich es so gelöst:

ich hab mir schnell eine Double-Linked-List Struktur (struct DLList) geschrieben und global ein Array vom Typ struct DLList angelegt. Dann habe ich so initialisiert, dass für 1 <= i <= max-2 gilt

array[i].next = &array[i+1];

und sonst

array[0].prev = &array[max - 1];
array[max - 1].next = NULL;

Dann hab ich 2 Zeiger deklariert, free_space = &array[0]; und list = NULL . Ich denke, jetzt siehst du, wie das funktioniert. Mit einer geeigneter Funktion kannst du immer das erste freie Feld über mem = &free_space[0] bekommen und dann mit list[curr_num_elemnts-1].next = mem; in die aktuelle List bekommen. Dann weißt du, das nächste freie Element ist mem.next und kannst somit free_space wieder anpassen:

free_space = mem.next;
mem.next = NULL; /* weil das letzte Element der 'list'-Liste,
  die Information auf das nächste freie Feld nicht mehr gebraucht,
  weil free_space auf das richtige Feld hat */

Indem du die next und prev Elemete geschickt setzt, kannst du mit 2 Pointern sowohl die freien Felder als auch die verwendeten Felder verwalten, ohne den Speicher defragmentieren zu müssen. Wenn du mal ein Bsp willst oder so, dann schick mir ne PM (persönliche Nachricht) oder Mail übers Board.

TheTester

Die Erklärung von Supertux erinnert mich an eine "Freispeicherliste" für homogene Elemente. Eine knappe und einleuchtende Erklärung findet sich in einer Praktikumsaufgabe unter folgendem Link http://www.cs.hm.edu/~koehler/alg_dat/alg_dat_prakt_2008/p1_ss08.pdf

Weitere Quellen welche die Idee demonstrieren wären "Introduction do Algorithms (Cormen et. al)" dort findet sich etwas unter "free list". Und Knuth spricht in seinem ersten Buch (Fundamental Algorithms) von einer "available space list" um die grundlegende Idee zu verdeutlichen.

Wollte gerade vorschlagen, dass eine ArrayList wie man sie zumindest derzeit im Sprachgebrauch nutzt kein normales Array ist, das einfach nur wächst, sondern tatsächlich einige Listen-Eigenschaften besitzt.
Bzw. diese Sichtweise ist schlecht, es lässt sich besser formulieren als eine Liste mit einigen Array-Eigenschaften.

Denn das meiste was eine Liste kann, kann man mit einem Array auch und das Löschen und Einfügen in der Mitte geht bei einem Array halt nicht in konstanter Zeit.
Daher ist es besser wenn man von einer Liste mit Array-Eigenschaften spricht. Man bekommt dadurch nämlich eine Liste mit O(1) Zugriff auf jedes Element. Dafür wird das Löschen/Einfügen in der Mitte allerdings nicht mehr in O(1) möglich.
Über die genauen Aufwände kann man i.A. nichts genaues sagen, das kommt auf die Implementierung drauf an. Die Java-Leute haben sich da recht viel Mühe gegeben.

uwerothfeld

Hallo zusammen,

also an einem Beispiel wäre ich wirklich interessiert. By the way: Wo ist hier die PM Funktion??? Aber was mich wundert: Wo soll die Fragmentierung und der BufferOverflow in meiner Implementierung herkommen? Ich sehe es nicht. Das PDF ist für mich nicht richtig einsetzbar, da ich O(n) zugunsten von Speicherersparniss gerne akzeptiere. Wie gesagt, Speicher ist bei mir extrem knapp, warten kann ich zu not

Gruß
Uwe

uwerothfeld schrieb:

Zugriffe direkt auf Datenstrukturen sind daher für mich etwas böses.

diesen aberglauben solltest du dir schnell abgewöhnen, wenn du's mit solchen minimalsystemen zu tun hast.

uwerothfeld

hi,

ja ist schon klar aber man kann sich doch zumindest das leben einfacher machen. ich finde addElem() ist besser lesbar statt list->content[list->next++]= ... oder ähnliches.

Softwarequalität durch Design sozusagen

Gruß

supertux

uwerothfeld schrieb:

also an einem Beispiel wäre ich wirklich interessiert. By the way: Wo ist hier die PM Funktion???

Geh mal auf http://www.c-plusplus.net/forum/profile-var-mode-is-viewprofile-and-u-is-13057.html da ist ein "Email senden" link.

uwerothfeld schrieb:

Aber was mich wundert: Wo soll die Fragmentierung und der BufferOverflow in meiner Implementierung herkommen? Ich sehe es nicht.

Fragmentierung und BufferOverflows kommen im Verfahren vom besserwisser vor, wenn man nur ein Array anlegt und ein Zeiger darauf hat, um an die Daten zu kommen. Das hat erstmal nichts mit deinem Code zu tun.

uwerothfeld

hallo und noch ne frage,

wie soll mir eigentlich der verzicht auf addElem, getElem ... Codesize sparen? Ich meine wenn ich auf das Array zugreife muß ich eh jedesmal schauen, ob noch Platz ist, mir merken wieviel Elemente ich schon gespeichert habe, was das letzte Element ist ... . Ich sehe da keinen Vorteil, ob ich nun den Code dafür einmal in eine eigene Funktion kapsele oder es jedesmal vor Ort mache. Kommentare?

Uwe

uwerothfeld

hi,

supertux schrieb:

Fragmentierung und BufferOverflows kommen im Verfahren vom besserwisser vor, wenn man nur ein Array anlegt und ein Zeiger darauf hat, um an die Daten zu kommen. Das hat erstmal nichts mit deinem Code zu tun.

Ja das leuchtet dann ein. Wollte dennoch mal fragen, man lernt ja nie aus

ok, ich geb auf. ich habe versucht, die einfachste methode anzugeben. aber im endeffekt muss doch uwerothfeld entscheiden, wie er es programmiern will.

wieso meine funktion buffer overflows hat und den speicher fragmentiert, weiß ich nicht. vielleicht erklärt mir das jemand?

@uwerothfeld
viel glück noch und schreib es so, wie du es für richtig hälst.

besserwisser schrieb:

wieso meine funktion buffer overflows hat und den speicher fragmentiert, weiß ich nicht. vielleicht erklärt mir das jemand?

das hab' ich auch nicht verstanden. zumal die elemente ja eine feste länge haben und man immer genau weiss, wieviel noch in den buffer passt. auch bei variablen elementlängen ist das ermitteln des noch freien speicherplatzes keine hexerei. deine methode ist simpel und genau das richtige für so'n minimalsystem wie's der OP hat. allerdings würde ich das array als ringbuffer ansprechen, so dass schon mal was rausgeholt werden kann, während daten eintrudeln.

supertux

besserwisser schrieb:

wieso meine funktion buffer overflows hat und den speicher fragmentiert, weiß ich nicht. vielleicht erklärt mir das jemand?

ok, ich wollte nicht sagen, dass deine Funktion welche hat, sondern wenn man nur ein Array legt und ein Pointer drauf kann es halt dazu führen

struct gen_data_type memory[MAX_ELEMS];
struct gen_data_type *list = &memory[0];
...
list->data = ...;
list++;
list->data = ...;
list++; 
...
list++; /* Gefahr über die Array Grenze zu gehen */

Aber ich muss jetzt zugeben, dass beim 2. Durchlesen des ganzen Threads die Sache nicht mehr so erscheint, wie ich es am Anfang interpretiert habe. Ich hatte schon mal eine (wie auf der anderen Seite) beschriebene Liste gehabt und wenn man viele Listenoperationen insert,insert,remove,insert,usw. hat, dann hätte man entweder bei jedem remove alles nach dem gelöschten Element im Array verschieben müssen oder eine Lücke lassen (darum verwalte ich da 2 Zeiger für den freien und den belegten Speicher). Sorry, jetzt merke ich aber, dass dieser Ansatz nicht so ganz mit deinem übereinstimmt.

supertux schrieb:

list++; /* Gefahr über die Array Grenze zu gehen */

nicht wirklich. du kennst ja MAX_ELEMS und die aktuelle zeigerposition.

supertux

-fricky- schrieb:

supertux schrieb:
list++; /* Gefahr über die Array Grenze zu gehen */
nicht wirklich. du kennst ja MAX_ELEMS und die aktuelle zeigerposition.

natürlich kennst du die, aber der nicht aufmerksame Programmierer könnte das vergessen. Ich geb zu, hab vorhin was falsch verstanden, weil ich nur den Thread schnell überflogen bin.

supertux schrieb:

Ich geb zu, hab vorhin was falsch verstanden, weil ich nur den Thread schnell überflogen bin.

halb so schlimm. ich hab' auch nicht verstanden, wieso er einträge mittendrin löschen muss und bestimmt auch unpassende tipps gegeben.

supertux

-fricky- schrieb:

supertux schrieb:

Ich geb zu, hab vorhin was falsch verstanden, weil ich nur den Thread schnell überflogen bin.

halb so schlimm. ich hab' auch nicht verstanden, wieso er einträge mittendrin löschen muss und bestimmt auch unpassende tipps gegeben.

ich ging eher von einem generellen Einsatz einer Liste, da hat man nicht nur Einfüge- sondern auch Löschoperationen, deswegen habe ich das erwähnt. Aber vielleicht war es dann zu viel des Guten

uwerothfeld

Hallo zusammen,

ich möchte nochmal Euch allen Danken für die Hilfe, die ich hier bekommen habe. Ich habe meine Lösung noch an einigen Punkten ändern könen, hoffentllich zum guten

besserwisser schrieb:

ok, ich geb auf. ich habe versucht, die einfachste methode anzugeben. aber im endeffekt muss doch uwerothfeld entscheiden, wie er es programmiern will.
[...]
@uwerothfeld
viel glück noch und schreib es so, wie du es für richtig hälst.

Ich wollte durch die Disskussion keinen vor den Kopf stoßen, sollte dies dennoch passiert sein, entschuldigt dies. Ich habe festgestellt, dass die zusätzlichen Codezeilen für meine addElem ... Funktionen die gleiche Codegröße erzeugen, bei dem verwendeten Compiler, wie die von besserwisser vorgeschlagene Version. Auch ein interessanter Aspekt.

Nun jedoch nocheinmal zurück zu einer Teilfrage meines Problems, welches glaube ich etwas untergegangen ist :). Ich definiere ja die Länge des Arrays über MAXLENGTH. Gibt es hier nen Möglichkeit ala OO, das ich beim definieren der Struktur sage:

List list(10);

wobei 10 für die MAXLENGTH des spezifischen Arrays steht? In jede Struktur ne eigene MAXLENGTH einzupacken fällt mir nur ein, aber macht man soewtas?

Vielen Dank.

Uwe