Folgendes Problem oder auch keins ein paar Ideen. Wir haben eine Liste dessen Daten sich ändern. Wir benötigen nicht nur Daten einer Node sondern von vielen über die gesamte Liste Lösungen: A: Wir kopieren die Daten in ein Array B: Wir schreiben das Json über eine Callback Funktion , direkt beim zugriff in der Liste C: Wir bauen eine Funktion die sich über einem Token merkt bei welchen Pointer sie war und beim nächsten Aufruf die Daten des nächsten Eintrags zurück gibt. A: Blöd wenn es sehr viele Daten sind und dann sind sie doppelt im Speicher, allerdings ist die Kopie das sicherste... B: Blöd da es die Zeit in dem die Liste blockiert(mutex) wird verlängert. Außerdem ist was in der Funktion faul ist die ganze Liste blockiert. C: Elegant aber beim Vergleich von Pointern können die Daten auf dem er zeigt verändert worden sein. z.Bsp Node entfernt , zugefügt -> gleicher Pointer andere Daten. D: ? Ich will nicht zu viel Speicher anfordern und alles kopieren um dann zu filtern. Ich tendiere zu C:
Marco H. schrieb: > linkedList ... Json ... Callback ... Token ... Pointer ... mutex ... Das alles klingt ziemlich wirr und zusammenhangslos. Versetze dich mal in die Lage eines Außenstehenden, der überhaupt keine Ahnung davon hat, was du da vorhast, und lies deinen eigenen Text aus dieser Perspektive noch einmal durch.
Daten aus einer Liste in ein Json zu schreiben ohne beim zugriff der Liste dies direkt zu tun und damit die Liste zu blockieren. Normalerweise kopiert man die Ergebnisse in ein Array A:, ist sicher und funktioniert. Oder B: man schreibt das Dokument etc. während man in der Liste sucht. C: man merkt sich wo man in der Liste war und setzt die suche dort fort. Man liefert die Daten einzeln zurück und muss sich nicht zwischenspeichern. Ziel ist es die Daten nicht zwischen zu speichern und die Liste so wenig so möglich zeitlich zu blockieren. Gesucht ist das beste Prinzip, nicht fertiger Code ;).
:
Bearbeitet durch User
Wenn man eine gute Strecke auf dem Weg zur Erledigung einer Aufgabe zurück gelegt hat, aber kurz vor dem Ende nicht weiter kommt, dann kann es sein, dass die Inspiration dazu von aussen kommen kann. Darauf hoffst du hier. Es kann allerdings auch sein, dass man irgendwann falsch abgebogen ist, und sich längst in eine Sackgasse manövriert hat. Dann nützt auch die Frage nach den letzten Metern nichts. Dann beschreibt man besser auch das Gesamtproblem, nicht nur das, was man für die letzten Meter erhofft.
PS: Wenn Performance eine Rolle spielt, und daraus folgende Parallelisierung, kommen noch ganz andere Betrachtungen mit hinzu. Auch deshalb kann es nützlich sein, das Szenario insgesamt zu betrachten. Beispiele: globale oder feiner aufgedröselte Mutexe, NUMA - Aspekte, die man in den ganz alten Algorithmenbüchern nicht findet.
:
Bearbeitet durch User
Naja ich erhoffe mir Ideen von Außen ;) Sackgasse kann man nicht sagten, es gibt kein Spezielles Problem damit. Ich finde die das kopieren und das direkte schreiben von Daten beim Zugriff auf einer List nicht sehr elegant. Beim kleinen Datenmengen ist kopieren die beste Lösung, sei es beim Return der Suchfunktion. Wenn es sagen wir mal 5000 Einträge gäbe, wird ein großer Schluck Speicher notwendig und dann haben wir eine weitere Kopie die sich dann im Json wiederfindet.
Marco H. schrieb: > Wenn es sagen wir mal 5000 Einträge gäbe, wird > ein großer Schluck Speicher notwendig 5000 Einträge sind nur dann ein grosser Schluck, wenn bereits ein einzelner Eintrag verdammt gross ist. Auch hier: Niemand ausser dir weiss, ob es um Einträge zu 100 Bytes oder 100 Megabytes geht. 5000 mal 100 Bytes ist heute Kleckerkram, im Kontext von PC-Programmierung.
:
Bearbeitet durch User
D: Die Liste ist immutable. Ändert sich die Liste, erstellt man eine neue.
Vincent H. schrieb: > D: Die Liste ist immutable. Ändert sich die Liste, erstellt man eine > neue. Dann brauchst du nicht das, was man gemeinhin unter einer Liste verstehst, sondern kannst gleich ein Array verwenden. Und wenn das Zeug wirklich gross ist, bist du nur noch am umschaufeln im DRAM, dem langsamsten Teil der Hauptspeicher-Hierarchie.
:
Bearbeitet durch User
Ich wuerde eine zur Liste gehoerige Funktion schreiben, welche das macht. zB ein Copy der Pointer in der richtigen Reihenfolge. Nachher kann man in Ruhe auslesen.
Marco H. schrieb: > Wenn es sagen wir mal 5000 Einträge gäbe, wird ein großer Schluck > Speicher notwendig und dann haben wir eine weitere Kopie die sich dann > im Json wiederfindet. Ohne wirklich kapiert zu haben, worum es geht: Die JSON-Darstellung braucht doch typischerweise ein Vielfaches des Speichers, den die native Darstellung braucht. Sollte man, um Speicherplatz zu sparten, deswegen nicht erst einmal beim JSON ansetzen? Muss das JSON denn unbedingt als Ganzes im Speicher stehen?
(prx) A. K. schrieb: > Vincent H. schrieb: >> D: Die Liste ist immutable. Ändert sich die Liste, erstellt man eine >> neue. > > Dann brauchst du nicht das, was man gemeinhin unter einer Liste > verstehst, sondern kannst gleich ein Array verwenden. Und wenn das Zeug > wirklich gross ist, bist du nur noch am umschaufeln im DRAM, dem > langsamsten Teil der Hauptspeicher-Hierarchie. Eine "neue" Liste ist natürlich keine 1:1 Kopie, sondern die alte plus Änderungen.
Vincent H. schrieb: > Eine "neue" Liste ist natürlich keine 1:1 Kopie, sondern die alte plus > Änderungen. Klar, aber das ändert ja nichts. Wenn du beispielsweise 30 GB in zwei Schüben umkopierst, um zwischendrin 1 kB einzufügen, dann geht das etwas ins Geld. Mach das oft genug... Speicherst du sowas in dieser Dimension nicht als Array, sondern als klassische verpointerte Liste kleiner einzelner Objekte, erzwingst du die ineffizienteste Form des Speicherzugriffs, die diesseits von Paging möglich ist. Andererseits kommt man bei solchen Grössenordnungen vielleicht auf die Idee, die Liste in etliche verkettete Arrays zu zerlegen, die man einzeln auf deine Art manipuliert. Da kriegt man dann überwiegend sequentielle Zugriffe, und kann kleinräumig verteilte Mutexe nutzen statt alles zu blockieren.
:
Bearbeitet durch User
Hmm also erst mal reden wir um kbytes. Die aber pro Request anfallen... Das Json muss ja nicht so groß werden, man sendet dann chunks oder verwendet pagination. Zu der ja genau das Problem auftritt. Wenn man die Daten als Array speichert weiß man ja nicht ob der Client alle Pages auch anfordert und sie bleiben im speicher stehen. Wie man das Problem löst das die Daten aus der Zeit x und y beim Zugriff auf die Liste vermischen weiß ich nicht. Man kann ja die Liste nicht blockieren bis der Client alle Pages gelesen hat. Also muss man damit leben oder den Client mitteilen sie nochmals von vorne zu lesen, da sie sich geändert haben...
:
Bearbeitet durch User
Um welche fucking scheiß Sprache geht es überhaupt? Wie kann man ernsthaft über das Problem diskutieren, wenn völlig offen ist, um was es eigentlich geht? *Kopf schüttel!*
Auch *Kopf schüttel!*, aber über dich. Über Algorithmen kann man diskutieren, ohne die Sprache der Implementierung zu betrachten. Zumindest soweit man im üblichen Paradigma von Sprachen wie den C- und Pascal-Familien oder Java bleibt.
:
Bearbeitet durch User
(prx) A. K. schrieb: > Auch Kopf schüttel!, aber über dich. Über Algorithmen kann man > diskutieren, ohne die Sprache der Implementierung zu betrachten. > Zumindest soweit man im üblichen Paradigma von Sprachen wie den C- und > Pascal-Familien oder Java bleibt. Alles Vermutungen, die Posts vom TO sind völlig aus dem Kontext gerissene Informationshappen Es fehlt die Sprache und Platform: wenn es um Python, Windows und fette Server geht ist das was völlig anderes als wenn es um ein embedded System geht Json könnte eine Projektanforderung sein, oder nur eine Idee vom TO Alles völlig unklar, besonders weil Performant und Json so gar nicht zusammenpasst Das Wir alle hier Algorithmen kennen ist klar, aber warum Vermutungen anstellen wenn der TO sich nicht die Mühe mach einen Kontext zu vermitteln
cppbert3 schrieb: > Alles Vermutungen, die Posts vom TO sind völlig aus dem Kontext > gerissene Informationshappen Korrekt. Es fehlt viel notwendige Information. Die Sprache ist jedoch nicht die wichtigste. > als wenn es um ein embedded System geht Ich nahm einfach an, dass mit "PC-Programmierung" nicht die Programmierung eines ATtinys mittels eines PCs gemeint ist. ;-)
:
Bearbeitet durch User
(prx) A. K. schrieb: > cppbert3 schrieb: > >> Alles Vermutungen, die Posts vom TO sind völlig aus dem Kontext >> gerissene Informationshappen > > Korrekt. Es fehlt viel notwendige Information. > Die Sprache ist jedoch nicht die wichtigste. würde das Puzzle weiter vervollständigen
(prx) A. K. schrieb: > cppbert3 schrieb: >> Alles Vermutungen, die Posts vom TO sind völlig aus dem Kontext >> gerissene Informationshappen > > Korrekt. Es fehlt viel notwendige Information. > Die Sprache ist jedoch nicht die wichtigste. Also ich halte die Sprache durchaus für sehr wichtig. Wenn es sich um Java handelt, kopiert er nicht alle Objekte (die "paar kB") wenn er alles in ein neues Array stopft, sondern lediglich die Referenzen darauf - und ab da würde sich in den allermeisten Fällen die Frage nach der Performance in Wohlgefallen auflösen. Ansonsten ist das Ganze zu nebulös, um sich das Problem überhaupt ansehen zu wollen.
Beitrag #6644462 wurde vom Autor gelöscht.
Beitrag #6644511 wurde von einem Moderator gelöscht.
Oder man erinnert sich daran, was Stroustrup schon vor zig Jahren gesagt hat: nimm vector, keine linked lists. vector ist einfacher und schneller. Ja, auch das Einfügen und Löschen. Siehe hier: https://www.youtube.com/watch?v=YQs6IC-vgmo
Verallgemeinerungen sind immer falsch. Auch Stroustrups. ;-)
:
Bearbeitet durch User
(prx) A. K. schrieb: > Verallgemeinerungen sind immer falsch. Auch Stroustrups. ;-) Nope. Die Verallgemeinerung, daß verlinkte Listen wegen Cache-Trashing bei heutigen CPUs schlecht sind, gilt für jede Programmiersprache. Ebenso, daß der geringe Aufwand beim Einsetzen/Löschen wertlos ist, weil der Hauptaufwand der Lookup ist - der nicht nur linear geht, sondern immer noch mit Cache-Trashing.
Es gibt mehr als ein "entweder oder". Ich hatte oben eine Mischform skizziert, wie du sie ähnlich auch in Baumstrukturen finden kannst. Wenn die Knoten nicht aus kleinen Einzelobjekten bestehen, mit der damit verbundenen Ineffizienz in der Speicherhierarchie. Sondern aus Arrays aus Objekten. Insgesamt balanciert man dabei die Flexibilität von verpointerten Objekten mit der Effizienz von Arrays im Speicher.
So pauschal zu sagen, Listen sind kacke, ist kacke. Das Problem mit dem Cache beim Traversieren bei Listen ist, wenn das eigentliche Traversieren der limitierende Faktor ist, und nicht die Operation auf die einzelnen Elemente selbst. Es ist doch logisch, dass eine Linked-List für Integerzahlen einem Array immer unterlegen sein wird. Alleine schon wegen der größeren, benötigten Speicherbandbreite.
Nop schrieb: > (prx) A. K. schrieb: >> Verallgemeinerungen sind immer falsch. Auch Stroustrups. ;-) > > Nope. Die Verallgemeinerung, daß verlinkte Listen wegen Cache-Trashing > bei heutigen CPUs schlecht sind, gilt für jede Programmiersprache. Das gilt aber nicht für jeden beliebigen Fall. Wenn ich ein 10 GB großes Array habe, an dessen Anfang ich immer wieder neue Werte anfügen muss, wird das ziemlich lahm werden, weil dann für jede dieser Aktionen die kompletten 10 GB umkopiert werden müssen. Übrigens: Es heißt Thrashing, nicht Trashing. > Ebenso, daß der geringe Aufwand beim Einsetzen/Löschen wertlos ist, weil > der Hauptaufwand der Lookup ist - der nicht nur linear geht, sondern > immer noch mit Cache-Trashing. Es sei denn, ich habe das Element schon, weil ich sowie darüber iteriere und dabei nebenher entscheide, ob das aktuelle Element entfernt werden muss. Also stimme ich A. K. zu: Verallgemeinerungen sind immer falsch.
Rolf M. schrieb: > Wenn ich ein 10 GB großes > Array habe, an dessen Anfang ich immer wieder neue Werte anfügen muss, > wird das ziemlich lahm werden Man allokiere ein Array welches 20GB groß ist, setzte den pos Pointer auf 10GB und mache dann folgendes: *(--pos) = value; Schneller geht es nicht. Wenn die 20GB voll sind, allokiert man 40GB und kopiert die 20 GB um. Dieses Umkopieren ist in etwa doppelt so aufwändig wie das einfache Einfügen, aber im Vergleich zum einer Liste immer noch ziemlich günstig, selbst für dieses Spezialfall wo die Suche entfällt. Übrigens ist dieses Beispiel künstlich, da nicht alle Randbedingungen bekannt sind. Wahrscheinlich wächst die Länge nicht in die Unendlichkeit sondern es ist entweder ein Ringpuffer oder wenn ein gewisse Größe erreicht ist wird sowieso ein neuer Puffer allokiert. Dann entfällt sogar das Umkopieren. Michael
Einige Kommentare waren schon hilfreich... Nun die Aufgabe ist schwer kurz zu umschreiben. Zumal sie sich in einigen Teilen des Projektes wiederfinden würde. Im Grunde geht es immer um Listen mit Geräten und dessen Daten nennen wir sie Eigenschaften. Geräte werden gefunden oder auch wieder entfernt. Somit ja auch dessen Daten. Reines kopieren der Listen, genügt nicht da man auch die Daten kopieren muss. Noch ist alles sehr übersichtlich und das verfahren "kopieren" ist wie oben schon gelesen die bessere Lösung. Da auch nur die Eigenschaften kopiert werden die benötigt werden. Aber es durchaus möglich das die Datenmengen zunehmen. Zumal wie oben erwähnt bei jedem Request eine Kopie entstehen würde. Es geht um vor und Nachteile des Ansatzes oder vielleicht auch ein völlig anderen Ansatz. Feinheiten der Programmiersprache wollte ich erst mal nicht zur Diskussion stellen. Wenn es von Interesse ist wir reden von C...
Michael D. schrieb: > Rolf M. schrieb: >> Wenn ich ein 10 GB großes >> Array habe, an dessen Anfang ich immer wieder neue Werte anfügen muss, >> wird das ziemlich lahm werden > > Man allokiere ein Array welches 20GB groß ist, setzte den pos Pointer > auf 10GB und mache dann folgendes: *(--pos) = value; Klar, wenn man genug Platz hat und es wirklich immer das erste Element ist, geht das. Lass es mal ein Element an einer "random"-Position sein, und schon klappt das nicht mehr so einfach. Ein klassisches Beispiel wäre ein Texteditor. Ich muss an beliebigen Stellen Zeichen entfernen oder hinzufügen können. Mit einem reinen Array wird das ziemlich träge, wenn die Datei mal etwas größer ist. Man wird natürlich auch keine reine verkettete Liste nutzen, sondern eher wie von A. K. beschrieben eine Mischform. > Übrigens ist dieses Beispiel künstlich, da nicht alle Randbedingungen > bekannt sind. Das haben Beispiele so an sich. Ich habe auch nicht behauptet, Arrays seien schlechter als verkettete Listen, sondern nur, dass das Gegenteil nicht pauschal für jeden beliebigen Fall gilt.
Hallo Marco, es wurde schon einige Male darauf hingewiesen, sich in die Lage der Anderen zu versetzen. Damit ist gemeint, dass du besser die Aufgabe eschreibst und zweitens eventuell auch deine Lösungs-Vorstellung ein wenig hinterfragst. Ich versuche dir an Beispielen aus deinem Text das zu verdeutlichen. Marco H. schrieb: > Einige Kommentare waren schon hilfreich... Nun die Aufgabe ist schwer > kurz zu umschreiben. Zumal sie sich in einigen Teilen des Projektes > wiederfinden würde. Jede Aufgabe kann abstrakt beschrieben werden. Besonders, wenn sie wieder und wieder verwendet wird. > Im Grunde geht es immer um Listen mit Geräten und dessen Daten nennen > wir sie Eigenschaften. An sich Liste mit Items zu haben, die wiederum weitere Eigenschaften besitzen ist nichts neues. Wo werden sie verwalten und gehalten? Nur im Speicher? Oder doch in einer Datenbank/Datei usw.? Wie werden sie initial ausgelesen? Werden die Eigenschaften und selbst die Items (Geräte) nur im Speicher geändert? Nur zentral? Oder von versch. Orten? > Geräte werden gefunden oder auch wieder entfernt. Was bedeutet gefunden? Wenn du dazu schreibst "..oder wieder entfern"? Ich kenne z.B. so ein Verhalten - sie werden entfernt, wenn sie Anhang eines Keys gefunden wurden. Was bedeutet "Gefunden"? Was bedeutet "..Oder Entfernt" als Gegenaktion zu "Gefunden"? Aus der Liste entnommen, jedoch das Gerät kann weiter "existieren" kann, so dass es wieder aufgenommen werden kann (Validierung von/bis z.B.)? > Somit ja auch dessen Daten. Reines kopieren der Listen, genügt nicht > da auch die Daten kopieren muss. Was bedeutet, dass du Daten kopieren möchtest, nachdem ein Gerät entfernt werden soll? Wozu überhaupt diese Fähigkeit - "Kopieren"? Beim Entfernen meint man immer "Löschen". Hier wird Kopieren vorgesehen. Daher die Frage - wozu? > Noch ist alles sehr übersichtlich und das verfahren "kopieren" ist > wie schon gelesen die bessere Lösung. Da auch nur die Eigenschaften > kopiert werden die benötigt werden. Aber es durchaus möglich das die > Datenmengen zunehmen. Zumal wie oben erwähnt bei jedem Request eine > Kopie entstehen würde. Wie kann man sich das vorstellen, dass bei jedem Request eine Kopie erstellt werden soll? Wie kann man verstehen, dass die Daten zunehmen? Welche Daten? Wo kommen sie her? Erstellt Request eine Dateneinheit (z.B. Gerät) oder mit Zunahme waren die Kopien gemeint? Was ist ein Request überhaupt? > Es geht um vor und Nachteile des Ansatzes oder vielleicht auch ein > völlig anderen Ansatz. Feinheiten der Programmiersprache wollte ich > erst mal nicht zur Diskussion stellen. Wenn es von Interesse ist wir > reden von C... Die Sprache ist zwar relevant, aber wenn die oberen Fragen nicht geklärt sind, ist nicht klar, woran gearbeitet wird. Du hantierst mit Begriffen, die alles Mögliche sein können und ohne Kontext ergeben sie zusammen keinen Sinn. Man kann sehen, dass die Bereitschaft, dir zu helfen ist da, du muss jedoch mitmachen.
:
Bearbeitet durch User
Rolf M. schrieb: > Das gilt aber nicht für jeden beliebigen Fall. Wenn ich ein 10 GB großes > Array habe, an dessen Anfang ich immer wieder neue Werte anfügen muss, ... dann fügt man natürlich am Ende an und invertiert den Lookup. Dann wird gar nichts mehr umkopiert. > Übrigens: Es heißt Thrashing, nicht Trashing. Oh, ja danke. > Es sei denn, ich habe das Element schon, weil ich sowie darüber iteriere > und dabei nebenher entscheide, ob das aktuelle Element entfernt werden > muss. Auch dann bringt Dir die Liste keinen Vorteil, weil das Iterieren dominiert. Siehe Stroustrups Video, einfach mal anschauen.
Marco H. schrieb: > Lösungen: > > A: Wir kopieren die Daten in ein Array > > B: Wir schreiben das Json über eine Callback Funktion , direkt beim > zugriff in der Liste > > C: Wir bauen eine Funktion die sich über einem Token merkt bei welchen > Pointer sie war und beim nächsten Aufruf die Daten des nächsten Eintrags > zurück gibt. > > A: Blöd wenn es sehr viele Daten sind und dann sind sie doppelt im > Speicher, allerdings ist die Kopie das sicherste... > > B: Blöd da es die Zeit in dem die Liste blockiert(mutex) wird > verlängert. Außerdem ist was in der Funktion faul ist die ganze Liste > blockiert. > > C: Elegant aber beim Vergleich von Pointern können die Daten auf dem er > zeigt verändert worden sein. z.Bsp Node entfernt , zugefügt -> gleicher > Pointer andere Daten. Marco H. schrieb: > Im Grunde geht es immer um Listen mit Geräten und dessen Daten nennen > wir sie Eigenschaften. Geräte werden gefunden oder auch wieder entfernt. Ich gehe mal davon aus dass die SW auf einem PC laufen soll, also einer Machine mit mehreren GiB Ram und mehreren Kernen die mit mehr als 3GHz getaktet sind. In diesem Kontext klingt A nach der besten Loesung, was den Aufwand und "Zuverlaessigkeit" betrifft, es klingt so als ob da mehrere Threads laufen, da ist kopieren oft auch die performantere/skalierbare Variante, sonst drehen die anderen Kerne nur Daumen anstatt zeitgleich zu arbeiten. Immutable/CopyOnWrite etc. Datenstrukturen sind heute sehr ueblich wenn man nicht gerade auf Mikrokontrollern arbeitet. Ansonsten mal einen Profiler drueberlaufen lassen, gibt es denn ein konkretes Problem (Laufzeit/Speicher) das geloest werden muss? Oder ist das nur "premature optimisation" die keine messbare Performance Vorteile bringt dafuer die Dinge aber sehr kompliziert macht?
:
Bearbeitet durch User
(prx) A. K. schrieb: > Wenn man eine gute Strecke auf dem Weg zur Erledigung einer Aufgabe > zurück gelegt hat, aber kurz vor dem Ende nicht weiter kommt, dann kann > es sein, dass die Inspiration dazu von aussen kommen kann. Darauf hoffst > du hier. > > Es kann allerdings auch sein, dass man irgendwann falsch abgebogen ist, > und sich längst in eine Sackgasse manövriert hat. Dann nützt auch die > Frage nach den letzten Metern nichts. Dann beschreibt man besser auch > das Gesamtproblem, nicht nur das, was man für die letzten Meter erhofft. Einer der besten Kommentare, die ich gelesen habe. Kurz, aber inhaltlich sehr präzise und hilfreich. Ich notiere ihn für mich persönlich. Danke
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.