Ich habe eine vielleicht ziemlich einface Frage.
Ich möchte in einem Power-Spektrum einen "Detektor-Algorithmus"
drüberlaufen lassen, der mir Peaks-Indizes im Spektrum ausgibt.
Nun wird das in einer einfachen for-Schleife gemacht, in dem jedes
Element + der umgebende Bereich gewichtet summiert und der Schwellwert
mit einem Komparator verglichen wird.
Zur Frage:
Wie kann ich eine unbekannte Anzahl an Indizes abspeichern, OHNE das ich
zunächst ein Feld anlege (da müssste ich nämlich alle Datenpunkte des
Spektrums als Feld-Größe nehmen), da ich ja die Größe nicht kenne.
Gibt es dafür einen Datentyp?
Vielen Dank!
Oliver S. schrieb:> Je nun, hilfreich wäre eine Info über die von dir bevorzugte> Programmiersprache. In den allermeisten gibts dafür was passendes.>> Oliver
C (für STM32-uC)
und vielleicht etwas äquivalentes für MATLAB - auch wenn es da viele
Funktionen gibt.
Daniel schrieb:> Dirk B. schrieb:>> Dynamischer Speicher mit realloc>>>> oder>>>> auf C++ umsteigen und std::vector benutzen>> Danke, werde ich mal probieren...
Letzteres läuft letztlich auch auf dynamische Speicherallozierung
hinaus. Und wie du richtig erkannt hast, erreicht der Speicherbedarf im
ungünstigsten Fall tatsächlich dieselbe Größe wie das Spektrum.
Bei dynamischer Speicherallozierung ist es nun so, dass es irgendwo
mittendrin knallen kann, obwohl eigentlich mengenmäßig noch genug
Speicher vorhanden ist, dieser aber zu sehr fragmentiert ist. Und es
kann sehr gut passieren, dass die Fragmentierung gerade durch das
dynamische Wachstum erst erzeugt wurde. Alle Implementierungen
dynamischer Speicherverwaltungen bemühen sich natürlich, dieses Problem
zu minimieren, aber sie können gegen die normative Kraft des Faktischen
letztlich nicht wirklich etwas ausrichten.
Du aber kannst es, du bist weit klüger als irgendwelche
(notwendigerweise) allgemein gehaltenen Algorithmen. Denn du kennst die
konkreten Umstände, insbesondere den worst case und die sonstige Nutzung
des Speichers.
Mit diesem Hintergrundwissen, über das generische Implementierungen
nunmal nicht verfügen können, kann man oft etwas weit besseres auf die
Beine stellen. Natürlich benutzt man auch dazu die vorhandene dynamische
Speicherverwaltung. Aber clever. Dazu muss man allerdings wissen, wie
diese im Detail funktioniert, es gibt da durchaus erhebliche
Unterschiede...
Und natürlich muss man sich darüber im Klaren sein, dass auch alle
Cleverness nicht hilft, wenn insgesamt einfach mal nicht genug Speicher
für den worst case da ist...
c-hater schrieb:> Mit diesem Hintergrundwissen, über das generische Implementierungen> nunmal nicht verfügen können, kann man oft etwas weit besseres auf die> Beine stellen. Natürlich benutzt man auch dazu die vorhandene dynamische> Speicherverwaltung. Aber clever.
Ich sag mal vorsichtig, daß es dir schwer fallen wird, cleverer als die
seit Jahrzehnten optimierte STL zu sein (bei gleichem Funktionsumfang).
Da es aber um C geht, müssen halt Pointer und malloc ausreichen. Mehr
braucht’s eigentlich auch nicht. Eigentlich sollte ein Blick in den
Source von malloc ausreichen, denn das löst prinzipiell deine
Aufgabenstellung: Auf Anforderung Speicherblöcke zur Verfügung stellen,
und dazu eine Verwaltungsfunktion, daß man die auch wiederfindet.
Oliver
Daniel schrieb:> Wie kann ich eine unbekannte Anzahl an Indizes abspeichern, OHNE das ich> zunächst ein Feld anlege (da müssste ich nämlich alle Datenpunkte des> Spektrums als Feld-Größe nehmen), da ich ja die Größe nicht kenne.
Wozu möchtest Du das denn?
Rechne Dir den worst Case aus (als obere Grenze), und lege dann ein
Maximum fest. Fertig. Wenn Du mehr brauchst, gibt es halt einen Fehler.
Erst wenn Du mehrere solcher Routinen gleichzeitig hast, zuwenig
Speicher und einen Benutzer, der notfalls eingreift, macht dynamischer
Speicher, der auf Anforderung wächst, Sinn.
Oliver S. schrieb:> c-hater schrieb:>> Mit diesem Hintergrundwissen, über das generische Implementierungen>> nunmal nicht verfügen können, kann man oft etwas weit besseres auf die>> Beine stellen. Natürlich benutzt man auch dazu die vorhandene dynamische>> Speicherverwaltung. Aber clever.>> Ich sag mal vorsichtig, daß es dir schwer fallen wird, cleverer als die> seit Jahrzehnten optimierte STL zu sein (bei gleichem Funktionsumfang).
Er hat allerdings damit recht, dass die Standard-Implementationen
allgemein gehalten sind. Vielleicht ist cleverer nicht ganz das passende
Wort. Man kann die Strategie besser für diesen konkreten Fall
optimieren.
Auf dem PC spielt das meist keine so große Rolle, aber auf dem µC mit
begrenztem Speicher evtl. schon. Denn obwohl das hier in
PC-Programmierung gepostet wurde, geht's offenbar gar nicht um einen PC:
Daniel schrieb:> C (für STM32-uC)
Dirk B. schrieb:> Dynamischer Speicher mit realloc>> oder>> auf C++ umsteigen und std::vector benutzen
Wenn es bei C bleiben soll, verkette liste und Chunk weise allozieren.
Jedes Element speichert dann zum Beispiel 4096 Byte oder so. Also
manuell das machen was std::vector vor dir versteckt und vermutlich
eleganter Implementiert. :P
was ich mich frage, ist warum das Spektrum eine unbekannte Größe hat.
Deine FFT hat doch eine feste Breite, oder nicht? Das Spektrum kann doch
nicht größer werden.
Solange nicht genug Samples zur Verfügung hat, kann man vielleicht
kürzere Transformationen machen um geringer aufgelöste Spektren zu
erhalten, aber irgendwann ist doch der Punkt erreicht, an dem eine
höhere Spektralauflösung keinen Sinn mehr ergibt. Entweder aus
signaltechnischer Sicht (Bandbreite des und Auflösung des Sensors) oder
aus Applikationssicht.
Diesen Maximalwert würde ich als Samplepuffergröße benutzen und irgend
ein sinnvollen Bruchteil davon als Peak-Index-Puffer.
Vlad T. schrieb:> was ich mich frage, ist warum das Spektrum eine unbekannte Größe hat.
[...]
> Diesen Maximalwert würde ich als Samplepuffergröße benutzen und irgend> ein sinnvollen Bruchteil davon als Peak-Index-Puffer.
Ich verstehe die Frage so, dass es ausschließlich um die Größe des
Peak-Index-Buffers geht und darum, dass die sich dynamisch anpassen
soll.
Rolf M. schrieb:> Ich verstehe die Frage so, dass es ausschließlich um die Größe des> Peak-Index-Buffers geht und darum, dass die sich dynamisch anpassen> soll.
wenn es wirklich darum geht, ist die Frage genauso sinnvoll wie:
"wie kann ich die Power-On-LED meines 10W LED-Strahlers deaktivieren um
Akku zu sparen"
Ich würde einfach ein Array fester Länge anlegen und eine
Füllstands-Zählervariable daneben.
Je nach Peakfinder würde ich nicht mehr als ~ 1/5 der
Sample-Puffergröße vorsehen.
Vorteile ist, dass es so keine Probleme mit dynamischer
Speicherverwaltung gibt und alles schön deterministisch bleibt.
Rolf M. schrieb:> Er hat allerdings damit recht, dass die Standard-Implementationen> allgemein gehalten sind. Vielleicht ist cleverer nicht ganz das passende> Wort. Man kann die Strategie besser für diesen konkreten Fall> optimieren.
Indem man dem Vector einen eigenen, der Aufgabenstellung angepassten,
Allocator mitgibt.
Oliver
