Forum: Mikrocontroller und Digitale Elektronik C: "rollierender Index" in Array möglichst elegant realisieren?


von Alexander I. (daedalus)


Lesenswert?

Hallo,

folgendes Code-Beispiel:
1
int MyArray[100] = {1,2, ..., 100};
2
3
for(int i=-200; i<=200; i++)
4
{
5
  int var = MyArray[i%(sizeof(MyArray)/sizeof(int))];
6
}

MyArray sei ein abgeschlossener Wertebereich ... d.h MyArray[99+1] wird 
wieder zu MyArray[0] vergleichbar z.B. mit Sinus von 0 bis 2PI.

Durch die modulo-Operation erreiche ich ja, dass alle Werte >99 wieder 
heruntergebrochen werden und so in den Wertebereich von MyArray passen.

Jetzt die Frage: Gibt es auch ein hübsches kleines Konstrukt OHNE 
if/else mit dem ich dasselbe für Werte <0 erreiche? Also quasi 
MyArray[-1] wird zu MyArray[99]. D.h. am Schluss sollte sowas stehen 
wie:
1
  int var = MyArray[i<this_is_where_the_magic_happens>];

welches den Wertebereich nach oben und unten automatisch "klammert". 
Gibt's da was?

Vielen Dank im Voraus.

von Matthias L. (Gast)


Lesenswert?

(peda)
1
#define ROLLOVER( x, max )  x = ++x >= max ? 0 : x


WIrd aber vom Compiler sicher in ein if-konstrukt umgewandelt

von icke (Gast)


Lesenswert?

1
myArry[nextpos++] = xyz;
2
nextpos &= SIZE - 1;

Wenn SIZE damit klar kommt, eine Zweierpotenz zu sein, sonst kann man 
auch natürlich nextpos = nextpos % SIZE schreiben.

von Stefan (Gast)


Lesenswert?

Einfache, spontane Idee :
Was wäre denn, wenn du vor der modulo Operation einfach 100 ( die Größe 
deines Array) addierst ?
Dann würde aus deiner -1 eine 99 werden und somit hättest du den 
gleichen Effekt für Zahlen, die <0 sind.

Gruß
Stefan

von tuppes (Gast)


Lesenswert?

@lippy und icke:

Ich glaube, eure Vorschläge funktionieren nicht für die geforderten 
negativen Zahlen.

@Alex Wurst:

Mir fällt nix ein, was ohne Fallunterscheidung (if/else oder ?-Operator) 
auskommt. Je nach Zielplattform könnte aber die Unterscheidung 
performanter sein als die Division.

Gruß,
Tuppes

von I_ H. (i_h)


Lesenswert?

Wenn du dich auf einen bestimmten Wertebereich festlegst (du brauchst ja 
wahrscheinlich keine 2^32 Arrayeinträge) kannst du zB. die Untergrenze 
(die dem Element 0 entsprechen sollte) draufaddieren.

Also Arraygröße 10, Untergrenze -100 -> vor der Rechnung 100 
draufaddieren, dann Modulo.

So richtig schön sauber ist das aber auch nicht, wegen der Einschränkung 
im Wertebereich. Aber 30 oder gar 31 Bits sollten sich damit noch 
realisieren lassen.

von Matthias L. (Gast)


Lesenswert?

>Ich glaube, eure Vorschläge funktionieren nicht für die geforderten
>negativen Zahlen.

Negative Array-Indizes haben ja auch keinen Sinn!

von icke (Gast)


Lesenswert?

Ich glaube bei erneutem durchlesen verstehe ich gar nciht mehr so ganz 
genau worum es geht.
Dachte bei rollierend an einen klassischen Ringpuffer, aber scheint ja 
so zu sein, daß man nicht inkrementiert in das Array geht. Das verändert 
des Offsets sich also schenken kann.

Da bleibt einem dann außer einem modulo vor dem Zugriff und wegen mir 
verschieben des index zu Null eigentlich nichts übrig oder sehe ich das 
falsch?

von Random .. (thorstendb) Benutzerseite


Lesenswert?

array[index & MASK]

von ●● pit ●. (Gast)


Lesenswert?

Hello,

ohne deinen restlichen 'Geheimalgorithmus' kann man ohnehin
nix bzw. nur kontextfrei optimieren.

Aber man kann eventuell einfach den Nummernbereich des Array-Index
verschieben, so das es keine negativen mehr gibt und den Also
entspr. anpassen. (i.e. 0 > 400 statt -200 > +200)

Möglicherweise klappt auch ein mehrdimensionales Array, i.e.:
1
int arr[2][100] = {
2
     { 1,2,   ..., 100},
3
     { -1,-2, ..., -100}
4
};
5
6
for(...)
7
{
8
  int pos = arr[0][i%size)];
9
  int neg = arr[1][i%size)];
10
}

Ist deine Anforderung eigentlich rein ästhetischer Natur, oder gibt
es auch einen praktischen Grund wie z.B. Code Size oder Performance?
(Man soll ja nur optimieren, wenn es wirklich nötig ist oder was bringt 
und nicht die Lesbarkeit verschlechtert.)

hth,
 - Karl

von Peter D. (peda)


Lesenswert?

Alex Wurst wrote:

>
1
> int MyArray[100] = {1,2, ..., 100};
2
> 
3
> for(int i=-200; i<=200; i++)
4
> {
5
>   int var = MyArray[i%(sizeof(MyArray)/sizeof(int))];
6
> }
7
>

Was soll das bringen, in einer Schleife immer wieder die gleiche 
Rechnung zu machen, soll das ne Delay-Schleife werden?

Insbesondere die (Modulo-)Division schlägt auf MCs ohne Division so 
richtig ein.

Nimm einfach ne 2. Variable und setze sie auf 0, wenn >=99 und gut is.

Oder nimm nen Pointer und setze ihn auf Array-Start, wenn >Array-End.


Peter

von Gast (Gast)


Lesenswert?

>  ... möglichst elegant realisieren?

Was ist das und warum?

von Alexander I. (daedalus)


Lesenswert?

Es geht nach wie vor um einen Ringpuffer, bei dem z.B. MyArray[-10] 
interpretiert wird als MyArray[Max-10].

Ich habe hier gerade ein ziemliches Gewurschtel an if/else-Konstrukten, 
bei dem ich Werte in einem Array nachbearbeite... Kritisch sind hierbei 
die Randbereiche des Arrays: Angenommen ich habe einen Filter, der die 
Werte n-2 bis n+2 benötigt, wobei n = zu berechnende Position im Array 
von 0 ... 99 ist, dann würde ich z.B. für Position MyArray[0] die 
folgenden Indexe benötigen:

 [98],  [99], [0],  [1],    [2]
(n-2), (n-1), (n), (n+1), (n+2)

und da Wäre ein kleines (evtl auch Makro)-Konstrukt schön, weil ich mir 
2-3 verschachtelte Wertebereich-IFs sparen könnte.

Alles klar?

von Roland P. (pram)


Lesenswert?

Wenn sizeof(Myarray) eine Zweierpotenz ist, sollte doch eine Maskierung 
auf die entsprechenden Bits reichen?

Mit ein paar Casts sollte das auch für negative Zahlen machbar sein
(da normal (int16)(-1) = (uint16)65535 )

@Alex Wurst
Was spricht dagegen eine 2er -Potenz zu verwenden. Dann kannst du's 
machen wie von Random... vorgeschlagen.

ansonsten würde ich es evtl so machen:
1
array[ ((idx % size) + size) % size]
kommt mit negativen Zahlen klar und es kommt kein Vergleich drin vor.
(auf einen µC der absolute Performance-Killer, auf nen x86 aber ggf. 
schneller als mit IF-Abfrage, da die Pipeline nicht unterbrochen wird)

Gruß
Roland

von Alexander I. (daedalus)


Lesenswert?

Der Code läuft auf nem x86 und kann wenn's sein muß auch 3 Tage 
laufen... der µC wird später nur mit dem Ergebnis zu Simulationszwecken 
gefüttert.

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.