mikrocontroller.net

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


Announcement: there is an English version of this forum on EmbDev.net. Posts you create there will be displayed on Mikrocontroller.net and EmbDev.net.
von Daniel (Gast)


Bewertung
0 lesenswert
nicht 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)


Bewertung
0 lesenswert
nicht 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)


Bewertung
0 lesenswert
nicht 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)


Bewertung
0 lesenswert
nicht lesenswert
Dynamischer Speicher mit realloc

oder

auf C++ umsteigen und std::vector benutzen

von Daniel (Gast)


Bewertung
0 lesenswert
nicht 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)


Bewertung
0 lesenswert
nicht 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)


Bewertung
0 lesenswert
nicht 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. (achs)


Bewertung
1 lesenswert
nicht 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.

: Bearbeitet durch User
von Dirk B. (dirkb2)


Bewertung
0 lesenswert
nicht lesenswert
Mit realloc kann man den Speicherbereich auch verkleinern.

von Rolf M. (rmagnus)


Bewertung
0 lesenswert
nicht 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)


Bewertung
0 lesenswert
nicht 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)


Bewertung
0 lesenswert
nicht 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)


Bewertung
0 lesenswert
nicht 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)


Bewertung
1 lesenswert
nicht 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)


Bewertung
0 lesenswert
nicht lesenswert
Wenn der dynamischa allozierbare Speicher ausgeht, einfach den
Controller resetten.

von Oliver S. (oliverso)


Bewertung
0 lesenswert
nicht 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

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.