Shift von Array werten?



  • Hi,

    ich habe ein int Array mit 20 Werten. Nun sollen zur Mittelwertermittlung alle Werte um 1 weiter geschoben werden der letzte Wert somit rausgeschoben und auf den ersten Platz ein neuer Wert geschrieben werden.

    Habe habe es bis jetzt mit einer for-Schleife realisiert. Habe mir jetzt aber überlegt ob ich es auch über ein Shift realisieren kann. Habe leider bis jetzt aber noch keine Lösung gefunden, die funktioniert hat.

    Geht es überhaupt, wenn ja hat einer ein Beispiel?

    Gruß SkySurfer



  • Nein



  • Hi,

    wenn ich es mir recht überlege ...
    ich weiss nicht ob das so geht ...
    also, wenn ich recht informiert bin hat ein array auch einen zeiger auf den adressbereich seiner variablen. wenn man den wert so weit "vorziehen" würde, dass davor wieder eine variable passt, und evtl. noch was macht damit der lezte teil des arrays freigegeben wird, könnte man das in wenigen schritten realisieren. Ein problem das dabei entstehen würde wäre auf jeden fall, dass das programm evtl. abstürzt, weil der teil vom arbeitsspeicher davor schon belegt ist oder das betriebssystem(vielleicht sogar der compiler) so etwas nicht zulassen könnte. Wie gesagt, denke nicht, dass das geht.

    mfg Oermel

    PS: ich würde auch gern rückmeldung über die eigendliche durchführbarkeit dieser möglichkeit haben.
    PPS: ich weiss, so was wäre sehr schlecht programmiert, würde mich aber jetzt trozdem mal interessieren 🙂



  • Umkopieren ist schlecht. Mach lieber einen Ringpuffer.

    int arr[20];
    int i=0;
    
    // hier irgendeine Schleife drum
    arr[i] = foo; // foo ist der neue einzufügende Wert
    i = (i+1) % 20; // Modinkrement, zählt also immer von 0..19
    // Schleife Ende
    

    Es wird somit "automatisch" der älteste Wert rausgeschmissen.



  • TactX schrieb:

    Umkopieren ist schlecht. Mach lieber einen Ringpuffer.

    kommt auf die grösse des ringbuffers an.
    beim ringbuffer hat man zwar kein umkopieren, dafür sind die zugriffe langsamer...
    🙂



  • Hmmm, wo da wohl der break-even liegt? Bei 2 oder 3 Elementen? *scnr*



  • @SkySurfer: wenn du alle Werte im Speicher um sizeof(int) verschieben willst, dann nimm doch memmove

    int array[20];
    
    /* array wird hier mit Daten gefüllt */
    
    memmove(&array[1], array, sizeof(int)*19);
    

    @Oermel: keine Ahnung, was du da versuchst zu erklären, aber das ist 100% falsch, zumal du keinen Speicher freigeben kannst, denn du nicht mittels *alloc-Family angefordert hast.



  • TactX schrieb:

    Hmmm, wo da wohl der break-even liegt? Bei 2 oder 3 Elementen? *scnr*

    die frequenz der zugriffe ist der knackpunkt.



  • musst du ein standard array nehmen? Also wirklich die werte verschieben? Ansonsten schreib dir einen ringbuffer struct. Anstatt die Werte zu shiften schiebst du einen startzeiger nach links. Das spart rechenzeit. Musst halt nur immer prüfen wann du an den grenzen bist und den zeiger halt hinten wieder einordnen. So hat es nach aussen hin den anschein als würdest du die Werte shiften.



  • vista schrieb:

    TactX schrieb:

    Hmmm, wo da wohl der break-even liegt? Bei 2 oder 3 Elementen? *scnr*

    die frequenz der zugriffe ist der knackpunkt.

    Erklär mal.



  • TactX schrieb:

    vista schrieb:

    TactX schrieb:

    Hmmm, wo da wohl der break-even liegt? Bei 2 oder 3 Elementen? *scnr*

    die frequenz der zugriffe ist der knackpunkt.

    Erklär mal.

    bei der buffer-kopier variante ist das schreiben langsam, das lesen schnell.
    je grösser der buffer ist, desto langsamer sind die schreibzugriffe.
    beim ringbuffer sind beide zugriffszeiten ziemlich ausgewogen, die buffer-grösse spielt keine rolle.
    beim ringbuffer verliert man die zeit durch lesezugriffe, die man beim 'kopierbuffer' gespart hat.
    wenn man z.b. selten schreibt und oft liest, dann ist buffer-kopieren besser.
    erst recht, wenn man es etwas beschleunigt, z.b. man nimmt einen 3mal so grossen speicherbereich und muss dann seltener umkopieren...
    🙂



  • ich würde nicht sagen das beim ring puffer die Zeit die man beim kopieren spart anhängen muss.... denn ich kann ausgehend vom aktuellen Zeiger doch genau berechnen auf welches element ich zugreifen muss. Das heißt auch das Lesen klappt in O(1) der Ring puffer braucht halt nur entsprechend implementierungsaufwand. Natürlich sollte ich den wirklichen anfang des arrays kennen und nicht nur den aktuellen welcher zurück geliefert wird. ein Umkopieren der Elemente dauert immer O(n) da ich ja jedes einzelne element umkopieren muss, beim ring muss ich nur den zeiger weiter schieben, und wenn ich auch auf ein element wahlfrei im puffer zugreifen will kann ich mir solange ich die größe des Arrays kenne und den anfang immer noch mit nur einen schritt berechnen wo ich hin zu greifen habe. Oder sehe ich da jetzt was falsch?



  • @ Fedaykin: Wie könnte so eine Ringpuffer Struktur aussehen? Kann mir da grade nichts darunter vorstellen. Hast du zufällig ein Beispiel parat?

    Gruß SkySurfer



  • prinzip eines ringbuffers:

    #define BUFFSIZE 100
    char memory[BUFFSIZE];
    int idx = 0;
    
    void write (char byte)
    {
      memory[idx++] = byte;  // ein byte speichern
      if (idx == BUFFSIZE)   // am ende des arrays angekommen?
         idx = 0;            // ja, dann vorne wieder anfangen
    }
    

Log in to reply