Du verwendest einen veralteten Browser. Es ist möglich, dass diese oder andere Websites nicht korrekt angezeigt werden. Du solltest ein Upgrade durchführen oder ein alternativer Browser verwenden.
ich möchte eine Datenstruktur implementieren die folgende Anforderungen erfüllt:
- sie soll Objekte beinhalten die aus Tupeln aus ca. 10 doubles bestehen (falls das überhaupt relevant ist)
- sie soll n oder weniger Objekte aufnehmen können (n wird bei 100 - 500 liegen)
- die Objekte haben eine Ordnung (Reihenfolge der Einfügung)
- wenn sie bereits n Objekte enthält soll ein neues Objekt eingefügt werden indem das älteste entfernt wird (FIFO)
- ich muss auf ein beliebiges (i-tes) Element zugreifen können und dann von diesem ausgehend das vorherige, vor-vorherige, ... , j-vorherige (j = ca. 20) zugreifen können
- das ganze soll threadsicher sein, das Verhältniss von Einfügen eines neuen Elementes zum lesen ist ca. 1 x Einfügen = 100.000 lesen.
- einmal eingefügte Objekte werden nicht mehr geändert, also nur noch gelesen bzw. irgendwann von neuen verdrängt (Diese Vorgabe könnte sich aber später ändern).
Es stellen sich nun folgende Fragen:
Nehme ich einen vector, dann ist es erstmal threadsicher aber deshalb wohl langsamer.
Oder nehme ich eine ArrayList und kümmere mich um die Threadsicherheit zu Fuß (wie?)?
Wie implementiere ich das FIFO Prinzip: schiebe ich beim Einfügen (bei voller Datenstruktur) alle Elemente durch das ganze Ding oder baue ich so eine Art Ringspeicher bei dem nur ein Zeiger (der auf den "aktuellen" Kopf zeigt) verschoben wird? Dann muss ich aber alle Anfragen nach dem n-ten Element entsprechend der "Kopfstellung" umleiten.
Das ganze soll eine Art Simulationsprogramm werden, d.h. durch die Datenstruktur werden sehr viele male sehr viele (Mio.) Objekte "durchgeschoben". Es soll also möglichst performant sein. Ich kann die angedeuteten Varianten bzgl. der zu erwartenden Performanz mangels Erfahrung nicht annährend einschätzen. Könntet Ihr mal Euere Meinung hierzu abgeben?
Wegen der sehr speziellen Kombination von Anforderungen wäre mein Ansatz jetzt, ein Interface (!) zu schreiben, wo genau die benötigten Methoden genau spezifiziert drin stehen, und dann zu überlegen, wie man die zeitkritischen Operationen in O(1) implementieren kann.
Die Datenstruktur generisch zu implementieren, sodass sie unabhängig von den eingespeisten Objekten ist.
Zur internen Verwaltung ein Array benutzen. Das bietet sich hier meiner Meinung nach an, weil
eine obere Schranke für die Anzahl der Elemente existiert.
sehr oft lesend auf Elemente zugegriffen wird (Performanz).
die Datenstruktur in den meisten Fällen bis zur oberen Schranke gefüllt sein wird (soll ja eine Queue werden). Ein Speicheroverhead wird dadurch wahrscheinlich eher selten vorkommen.
auf die Objekte über ihre Indizes zugegriffen werden soll (im Array extrem leicht zu implementieren).
Das FIFO-Prinzip auf jeden Fall mit Ringspeicher und Zeiger implementieren! Das ist wesentlich einfacher und performanter, als die Elemente herumzuschieben. Bei Anfragen nach dem n-ten Element nimmst Du den Modulo-Operator.
Threadsicherheit mit synchronized-Methoden herstellen. Hier muss ich zugeben, dass ich mich da selbst nicht so gut auskenne, aber dieses Kapitel schien mir sehr Reich an verschiedenen Methoden zur absicherung parallelisierter Programme.
Hallo Rol,
Das FIFO-Prinzip auf jeden Fall mit Ringspeicher und Zeiger implementieren! Das ist wesentlich einfacher und performanter, als die Elemente herumzuschieben. Bei Anfragen nach dem n-ten Element nimmst Du den Modulo-Operator.
Bist Du sicher? Einfügen und somit verschieben muss ich nur 1x pro ca. 100.000 Leseoperationen. Bei jeder Leseoperation muss dann per Modulo-Operator der Arrayindex umgerechnet werden. Ich habe da eben kein Gefühl was die größere Performance Bremse wäre...
Sei n die größe des Arrays. Bei n = 500 und 1.000.000 eingespeisten Objekten wird die Queue während ihrer Lebenszeit 2000 Mal neu gefüllt. Ab dem 500. Objekt gilt: Für jedes weitere Objekt, das eingefügt wird, musst Du 499 Objekte verschieben. Das macht dann 498.750.500 Verschiebungsoperationen während der Lebenszeit eines Objekts.
Das Verhältnis von Lesen zu Schreiben ist 100.000:1. Daraus folgt, dass das Verhältnis von Lesen zu Verschiebungsoperation ca. 1:4.987 ist. Pro lesendem Zugriff auf die Datenstruktur machst Du also knapp 5.000 Verschiebungen, wenn ich mich nicht verrechnet habe.
Mit dem Ringspeicher bildest Du pro lesendem Zugriff eine Summe und führst eine Modulooperation über dem Ergebnis dieser Summe aus. Die Summe ist bei n = 500 maximal 998. Das scheint mir insgesamt kostengünstiger als die andere Vorgehensweise.
Und wenn man ein Interface verwendet, kann man schnell ein paar mögliche Implementierungen durchprobieren, und sieht, welche wirklich im konkreten Anwendungsfall die beste ist...
