Leere Einträge aus Array löschen

[Tim H. (hotty)]

Hallo,

ich habe habe ein Array mit 192 Einträgen. Dabei handelt es sich um die 
Daten für eine LED-Matrix. Wie kann ich jetzt die 0x00 auf einmal 
kürzen, wenn es 2 und mehr mal hintereinander kommt:

BSP:

data[0] = 0x30
data[1] = 0x00
data[2] = 0x00
data[3] = 0x00
data[4] = 0x45
data[5] = 0x82
data[6] = 0x00

zu


data[0] = 0x30
data[1] = 0x00
data[2] = 0x45
data[3] = 0x82
data[4] = 0x00
data[5] = 0x00
data[6] = 0x00

Bisher habe ich schon ein wenig rumexperimentiert. Bin aber zu noch 
nichts gekommen. Ich habe nur bisher das Datenarray in ein 2. Array 
gespeichert. Am Ende wird das 2. Array wieder in das erste geschrieben. 
Dazwischen sollte dann aus dem 2. Array die aufeinanderfolgenden 0x00 
gekürzt werden.

Hat jemand eine Ahnung wie das geht? Muss kein Code sein, eine Idee 
reicht auch schon.

Tim

[Bastler (Gast)]

Ich ersehe zwar keine Sprache, in der du das ganze machen willst, aber 
vom Prinzip her könntest du dir das 2. Array fast sparen und statt 
dessen eine Liste von Pointern anlegen. Du schreibst halt nur die 
Pointer auf Daten in die Liste, welche auf Daten ungleich 0 zeigen.

Also Array durchlaufen und immer wenn der Wert der Stelle auf die dein 
Laufpointer grad zeigt ungleich 0 ist, Laufpointer in eine neue Liste 
kopieren....

Danach sollte eine Liste entsanden sein, die quasie ein neues Array nur 
aus Werten ist...

[Bastler (Gast)]

Nachtrag: Vergiss die Frage mit der Sprache, hab grad gesehen, dass das 
im GCC Forum steht... bin sonst mehr bei den µC und deshalb meien 
Frage...

[Mark B. (markbrandis)]

Ist das Array fest vorgegeben und wird erst von Dir bearbeitet, oder 
erzeugst Du es selbst? Im letzteren Fall könnte man einfach eine 
Hilfsvariable einführen und prüfen, ob der letzte in das Array 
geschriebene Wert bereits Null war, und anstatt schon wieder eine Null 
zu schreiben überspringt man dies einfach.

[Klaus W. (mfgkw)]

Vielleicht in der Art (nicht getestet, bitte noch mit
verschiedenen Fällen prüfen!!!):

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>


void moveBackDuplicateZero_ui8( uint8_t arr[], unsigned int nArr )
{
  unsigned int iArr;

  // letztes Element !=0 suchen:
  for( iArr=nArr; iArr>=0; --iArr )
  {
    if( arr[iArr] )
    {
      break;
    }
  }

  for( iArr=1; iArr<nArr; ++iArr )
  {
    if( arr[iArr]==0 && arr[iArr-1]==0 )
    {
      // Beginn einer 0-Folge gefunden!
      // Ab hier alle Nullen nach hinten schieben, alle anderen
      // Elemente vorziehen.
      // Ende der 0-Folge suchen:
      unsigned int nLast0 = iArr;
      while( nLast0<nArr && arr[nLast0]==0 )
      {
        nLast0++;
      }
      // nLast0 ist jetzt der Index NACH dem letzten 0-Element.
      // Um (nLast0-iArr) Positionen müssen jetzt alle restlichen
      // Elemente nach vorne gezogen werden, bzw. die letzten zu 0
      // gesetzt werden:
      {
        unsigned int iArrMove;
        for( iArrMove=iArr; iArrMove<nArr; ++iArrMove )
        {
          if( iArrMove<(nArr-(nLast0-iArr)) )
          {
            arr[iArrMove] = arr[iArrMove+nLast0-iArr];
          }
          else
          {
            arr[iArrMove] = 0;
          }
        }
      }
    }
  }
}

int main( )
{
  uint8_t    arr_test[192];
  uint8_t    arr[192] =
    {
      0x30,
      0x00,
      0x00,
      0x00,
      0x45,
      0x82,
      0x00,
      0x30,
      0x00,
      0x00,
      0x00,
      0x45,
      0x82,
      0x00,
      0x30,
      0x00,
      0x00,
      0x00,
      0x45,
      0x82,
      0x00,
      0x30,
      0x00,
      0x00,
      0x00,
      0x45,
      0x82,
      0x00,
      0x30,
      0x00,
      0x00,
      0x00,
      0x45,
      0x82,
      0x00,
      0x30,
      0x00,
      0x00,
      0x00,
      0x45,
      0x82,
      0x00,
      0x30,
      0x00,
      0x00,
      0x00,
      0x45,
      0x82,
      0x00,
      0x30,
      0x00,
      0x00,
      0x00,
      0x45,
      0x82,
      0x00,
      0x30,
      0x00,
      0x00,
      0x00,
      0x45,
      0x82,
      0x00,
      0x30,
      0x00,
      0x00,
      0x00,
      0x45,
      0x82,
      0x00,
      0x30,
      0x00,
      0x00,
      0x00,
      0x45,
      0x82,
      0x00,
      0x30,
      0x00,
      0x00,
      0x00,
      0x45,
      0x82,
      0x00,
      0x30,
      0x00,
      0x00,
      0x00,
      0x45,
      0x82,
      0x00,
      0x30,
      0x00,
      0x00,
      0x00,
      0x45,
      0x82,
      0x00,
      0x30,
      0x00,
      0x00,
      0x00,
      0x45,
      0x82,
      0x00,
      0x30,
      0x00,
      0x00,
      0x00,
      0x45,
      0x82,
      0x00,
      0x30,
      0x00,
      0x00,
      0x00,
      0x45,
      0x82,
      0x00,
      0x30,
      0x00,
      0x00,
      0x00,
      0x45,
      0x82,
      0x00,
      0x30,
      0x00,
      0x00,
      0x00,
      0x45,
      0x82,
      0x00,
      0x30,
      0x00,
      0x00,
      0x00,
      0x45,
      0x82,
      0x00,
      0x30,
      0x00,
      0x00,
      0x00,
      0x45,
      0x82,
      0x00,
      0x30,
      0x00,
      0x00,
      0x00,
      0x45,
      0x82,
      0x00,
      0x30,
      0x00,
      0x00,
      0x00,
      0x45,
      0x82,
      0x00,
      0x30,
      0x00,
      0x00,
      0x00,
      0x45,
      0x82,
      0x00,
      0x30,
      0x00,
      0x00,
      0x00,
      0x45,
      0x82,
      0x00,
      0x30,
      0x00,
      0x00,
      0x00,
      0x45,
      0x82,
      0x00,
      0x30,
      0x00,
      0x00,
      0x00,
      0x45,
      0x82,
      0x00,
      0x30,
      0x00,
    };


  unsigned int iAusgabe;

  unsigned int i;

  for( i=0; i<sizeof(arr)/sizeof(arr[0]); ++i )
  {
    arr_test[i] = arr[i];
  }

  moveBackDuplicateZero_ui8( arr, sizeof(arr)/sizeof(arr[0]) );

  for( iAusgabe=0; iAusgabe<sizeof(arr)/sizeof(arr[0]); ++iAusgabe )
  {
    printf( "{%3u]: alt=0x%02x neu==0x%02x\n", iAusgabe, arr_test[iAusgabe], arr[iAusgabe] );
  }

  return 0;
}

[Yalu X. (yalu) (Moderator)]

Für den Obfuscated C Contest reicht's noch nicht, aber ich habe mir Mühe
gegeben ;-)

void s(uint8_t d[], uint8_t n, uint8_t z) {
  uint8_t i, j=0, c=0;
  for(i=0; i<n; i++)
    if((c = d[i]?0:c+1) <= z)
      d[j++] = d[i];
  while(j < n)
    d[j++] = 0;
}

d ist das Array mit den Daten, n die Anzahl der Elemente im Array und z
die maximale Anzahl der Nullen, die in Serie stehen bleiben dürfen (in
deinem Fall ist z=1). Nach der Ausführung stehen die zusammengeschobenen
Daten im gleichen Array.

[Klaus W. (mfgkw)]

Nachtrag zu meiner Version:
Die erste Schleife ("letztes Element !=0 suchen") ist sinnlos
und kann weg.
Gedacht war sie mal, um nicht immer die schon am Ende angesammelten
Nullen nach vorne schieben zu müssen; das erfüllt sie aber eh nicht.
Korekt geschrieben wäre es effizienter, macht aber sonst keinen
Unterschied.

Ich schaue es mir morgen nochmal an.

[Klaus W. (mfgkw)]

@Yalu: Hoffentlich machen unsere Versionen etwa das Gleiche...

[Tim H. (hotty)]

Hallo,

vielen Dank für eure Lösungen! Ich hab mich von der von Klaus Wachtler 
inspirieren lassen und meine Geschrieben.
Es war übrigens 0xFF statt 0x00 :)

Meine Lösung (falls jemand sich dafür interessiert)

  //Code auslesen
        for(i = 0; i <= 50; i++){
    zeichen = text[i];
    db_pointer = zeichen * 6 -1;
    for(zei = db_pointer; zei < db_pointer + 6; zei++)
    {
      data[ofs] = 255 - pgm_read_byte(&charsetDE[zei]);
      ofs++;
    }
  }


  for(i = 0; i < 192; i++)
  {
      temp[i] = 0xFF;
  }

  //optimize1
  uint8_t i_over = 0;

  for(i = 0; i < 191; i++)
  {  
    if(data[i] == 0xFF && data[i+1] == 0xFF){
      //2 Leere Spalten
    }
    else{
      i_over++;
        temp[i_over] = data[i];    
    }
   }
 

  for(i = 0; i < 192; i++)
  {
      data[i] = temp[i];
  }

[Karl H. (kbuchegg)]

Tim H. schrieb:
> Hallo,
>
> vielen Dank für eure Lösungen! Ich hab mich von der von Klaus Wachtler
> inspirieren lassen und meine Geschrieben.
> Es war übrigens 0xFF statt 0x00 :)
>
> Meine Lösung (falls jemand sich dafür interessiert)

Zur Übung für dich: Und jetzt das Ganze ohne Zwischenarray.
(Ist nicht wirklich schwer)

Warum diese Übung?
Ganz einfach: Was machst du wenn dein Array im µC den halben Speicher 
belegt und du den Speicher ganz einfach nicht hast um dir temporär eine 
Kopie erlauben zu dürfen.
(Von Laufzeitüberlegungen einmal ganz abgesehen. Array umkopieren kostet 
auch Zeit. Wobei in diesem Fall diese Zeit noch nicht einmal gut 
investiert ist. Das Umkopieren bringt nämlich überhaupt nichts. Keine 
Arbeitserleichterung, keinen Speed. Gar nichts. Es belegt nur Speicher 
:-)

[Tim H. (hotty)]

Stimmt! Da hast du recht.

  uint8_t i_over = 0;

  for(i = 0; i < 191; i++)
  {  
    if(data[i] == 0xFF && data[i+1] == 0xFF){
      //2 Leere Spalte
    }
    else{
      data[i_over] = data[i];  
      i_over++;  
    }
   }

  for(i = i_over; i < 191; i++)
  {
    data[i] = 0xFF; //Rest löschen
  }

Gehts noch besser?

[Karl H. (kbuchegg)]

Tim H. schrieb:
> Stimmt! Da hast du recht.
>
>

>   uint8_t i_over = 0;
> 
>   for(i = 0; i < 191; i++)
>   {
>     if(data[i] == 0xFF && data[i+1] == 0xFF){
>       //2 Leere Spalte
>     }
>     else{
>       data[i_over] = data[i];
>       i_over++;
>     }
>    }
> 
>   for(i = i_over; i < 191; i++)
>   {
>     data[i] = 0xFF; //Rest löschen
>   }
>

>
> Gehts noch besser?

Das würd ich so machen

  uint8_t i_over = 0;
 
  for(i = 0; i < 191; i++)
  {
    data[i_over++] = data[i];

    if(data[i] == 0xFF) {  // einmal 0xFF ist ok. Aber alle die jetzt
                           // noch hinten drann kommen, fliegen raus
      i++;
      while( i < 191 && data[i] == 0xFF )
        i++;
    }
  }

  for(i = i_over; i < 191; i++)
    data[i] = 0xFF; //Rest löschen

[Tim H. (hotty)]

Danke nochmal. Bei deiner Lösung hat er den Abstand zwischen den Zeichen 
auf 0 verkleinert... 1 sollte ja sein. Ich hab einfach nochmal i_over 
weiterzählen lassen :). Aber Danke!
Im Anhang mal was das optimieren gebracht hat.

  //optimize1
  uint8_t i_over = 0;
 
  for(i = 0; i < 191; i++)
  {
    if(data[i] == 0xFF) {  // einmal 0xFF ist ok. Aber alle die jetzt
                           // noch hinten drann kommen, fliegen raus
      i++;i_over++;
      while( i < 191 && data[i] == 0xFF )
        i++;
    }

    data[i_over++] = data[i];


  }

  for(i = i_over; i < 191; i++)
    data[i] = 0xFF; //Rest löschen

[Karl H. (kbuchegg)]

@yalu
schöne Lösung :-)

da kann man dann auch noch das Byte einbauen, welches gefiltert werden 
soll

void s(uint8_t d[], uint8_t p, uint8_t n, uint8_t z) {
  uint8_t i, j=0, c=0;
  for(i=0; i<n; i++)
    if((c = (d[i]==p)?0:c+1) <= z)
      d[j++] = d[i];
  while(j < n)
    d[j++] = p;
}

[Yalu X. (yalu) (Moderator)]

Karl heinz Buchegger schrieb:
> @yalu
> schöne Lösung :-)

Naja, die mit Klaus' und deiner Hilfe entstandene letzte Variante von
Tim unterscheidet sich ja gar nicht mehr so arg von meiner, bis auf die
innere Schleife, die mit Hilfe dieser Abfrage

    if((c = (d[i]==p)?0:c+1) <= z)

als Bestandteil der äußeren läuft. Aber gerade diese Abfrage ist es, die
wohl bei den meisten (zurecht) ein kaltes Grausen auslöst ;-)

[Klaus W. (mfgkw)]

ich erwähne jetzt vielleicht besser nicht, was eine
unkommentierte Funktion s mit so poetischen Variablennamen
wie d, i, p, c und z bei mir auslöst...
Nein, ich tue es nicht.
:-)

[horst (Gast)]

Wenn Du der Reihe nach in das Array schreibst:
Erhöhe den Pointer oder Index erst, wenn der aktuelle Inhalt oder der 
neue Wert ungleich 0 ist.

if( data[i] || neuerWert )
    data[++i] = neuerWert;

Wenn über den Index nicht der Reihe nach auf das Array zugegriffen wird, 
dann hat die Position wohl irgendeine Bedeutung:
Beim Verschieben solltest Du festhalten, wo ein neuer Wert denn jetzt 
hinzukommen hat. Im Prinzip kannst Du das Array dann komprimieren, aber 
nicht einfach angeblich leere Einträge löschen.

[Karl H. (kbuchegg)]

Klaus Wachtler schrieb:
> ich erwähne jetzt vielleicht besser nicht, was eine
> unkommentierte Funktion s mit so poetischen Variablennamen
> wie d, i, p, c und z bei mir auslöst...
> Nein, ich tue es nicht.
> :-)

Der Fairness halber hat Yalu ja auch den OCCC erwähnt.
Für diesen Bewerb ist dieser Code allerdings noch lange nicht kryptisch 
genug :-)

[Klaus W. (mfgkw)]

Bis der zum nächsten Mal stattfindet, kann man den Quelltext wohl
noch einige Zeit optimieren.

[Mark B. (markbrandis)]

Klaus Wachtler schrieb:
> Bis der zum nächsten Mal stattfindet,

wenn überhaupt.