Forum: PC-Programmierung Indizes unbekannter Länge abspeichern - Datentyp?


von Daniel (Gast)


Lesenswert?

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!

von Oliver S. (oliverso)


Lesenswert?

Je nun, hilfreich wäre eine Info über die von dir bevorzugte 
Programmiersprache. In den allermeisten gibts dafür was passendes.

Oliver

von Daniel (Gast)


Lesenswert?

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.

von Dirk B. (dirkb2)


Lesenswert?

Dynamischer Speicher mit realloc

oder

auf C++ umsteigen und std::vector benutzen

von Daniel (Gast)


Lesenswert?

Dirk B. schrieb:
> Dynamischer Speicher mit realloc
>
> oder
>
> auf C++ umsteigen und std::vector benutzen

Danke, werde ich mal probieren...

von c-hater (Gast)


Lesenswert?

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...

von Oliver S. (oliverso)


Lesenswert?

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

: Bearbeitet durch User
Beitrag #6044827 wurde von einem Moderator gelöscht.
Beitrag #6044927 wurde von einem Moderator gelöscht.
von A. S. (Gast)


Lesenswert?

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.

von Dirk B. (dirkb2)


Lesenswert?

Mit realloc kann man den Speicherbereich auch verkleinern.

von Rolf M. (rmagnus)


Lesenswert?

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)

von imonbln (Gast)


Lesenswert?

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

von Vlad T. (vlad_tepesch)


Lesenswert?

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.

von Rolf M. (rmagnus)


Lesenswert?

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.

von Vlad T. (vlad_tepesch)


Lesenswert?

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.

: Bearbeitet durch User
von Javafrickler (Gast)


Lesenswert?

Wenn der dynamischa allozierbare Speicher ausgeht, einfach den
Controller resetten.

von Oliver S. (oliverso)


Lesenswert?

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

Bitte 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
Noch kein Account? Hier anmelden.