Array durchsuchen

[Udo (Gast)]

Hi,

ich möchte ein Array mit Größe SIZE nach einem bestimmten SUCHWERT 
durchsuchen, und falls es nicht gefunden wird eine Funktion aufrufen.

So dachte ich:

 for (i=SIZE ; i-- ;)
 {
  if(SUCHWERT == Array[i])
    break;
  if (i == 0)
    ErrorFkt();
 }
}

Kann man das noch vielleicht optimaler machen? :)

[Karl H. (kbuchegg)]

Udo schrieb:

> Kann man das noch vielleicht optimaler machen? :)

Aber sicher doch.
Frage:
Wenn du in einem Buch nach einem bestimmten Wort suchst, wann kannst du 
frühestens feststellen, dass das Wort nicht im Buch vorkommt?
Doch wohl erst dann, wenn du das Buch komplett durchsucht hast und nicht 
während des Durchsuchens!

  for( i = 0; i < SIZE; ++i ) {
    if( Array[i] == Suchwert )
      break;
  }

  if( i == SIZE )
    // nicht gefunden
  else
    // gefunden

[Philip (Gast)]

Nur wenn das array sortiert ist.

[Peter (Gast)]

mit strchr. Wenn die lib gut ist, dann kann sie es komplett die CPU 
machen lasse dafür gibt es ja extra upcodes.

Aber viel schneller wird es dadurch auch nicht.

[Klaus (Gast)]

Peter schrieb:
> Wenn die lib gut ist, dann kann sie es komplett die CPU
> machen lasse dafür gibt es ja extra upcodes.

1) Das macht sowieso komplett die CPU. Wer denn auch sonst.

2) Das Ding heißt Opcode.

[Rolf Magnus (Gast)]

Udo schrieb:

> ich möchte ein Array mit Größe SIZE nach einem bestimmten SUCHWERT
> durchsuchen, und falls es nicht gefunden wird eine Funktion aufrufen.
>
> So dachte ich:
>
>  for (i=SIZE ; i-- ;)
>  {
>   if(SUCHWERT == Array[i])

Du fängst hier bei Array[SIZE] an, also ein Element nach Ende des 
Arrays.

>     break;
>   if (i == 0)
>     ErrorFkt();
>  }
> }
>
> Kann man das noch vielleicht optimaler machen? :)

Klar. Statt bei jedem Schleifendurchlauf zu prüfen, ob die 
Error-Funktion aufgerufen werden soll, könntest du das auch ein einziges 
mal nach der Schleife tun:

i = SIZE;
while (i-- && SUCHWERT != Array[i])
    ;

if (i < 0)
    ErrorFkt();

[Rolf Magnus (Gast)]

> Du fängst hier bei Array[SIZE] an, also ein Element nach Ende des
> Arrays.

Ok, stimmt natürlich nicht. ignoriere das einfach.

[Peter (Gast)]

Klaus schrieb:
> 1) Das macht sowieso komplett die CPU. Wer denn auch sonst.

wer die schleife macht ist die Frage, schreibt man die Schleife als 
mehre asm Befehle oder nutzt die die String funktioenen der CPU.

Das geht geht aber eh nur wenn man keine 0 in der array hat. Dafür muss 
am ende eine 0 vorhanden sein.

[Rolf Magnus (Gast)]

Peter schrieb:
> wer die schleife macht ist die Frage, schreibt man die Schleife als
> mehre asm Befehle oder nutzt die die String funktioenen der CPU.
>
> Das geht geht aber eh nur wenn man keine 0 in der array hat. Dafür muss
> am ende eine 0 vorhanden sein.

Ich wüßte gerade keinen Prozessor, der einen asm-Befehl hat, der das 
macht. Der Befehl "repne scas" auf x86 kommt dem am nächsten, aber der 
interessiert sich nicht dafür, ob im Array eine 0 vorkommt.

[Udo (Gast)]

Rolf Magnus schrieb:
>> Du fängst hier bei Array[SIZE] an, also ein Element nach Ende des
>> Arrays.
>
> Ok, stimmt natürlich nicht. ignoriere das einfach.

hmm, du hast schon recht. Ich greife ausserhalb des Arrays zu. Das geht 
ja nicht.

Beispiel:

SIZE = 2;
uint Array[SIZE] =
{
  0xAB,
  0xCD
};

Also ich finde auch dass das while eleganter ist:
while (i-- && SUCHWERT != Array[i])

Nur wird es glaube ich nicht funzen, wenn mein i unsigned ist und ich 
mit SIZE die Arraygröße definiere.

[Rolf Magnus (Gast)]

> hmm, du hast schon recht. Ich greife ausserhalb des Arrays zu. Das geht
> ja nicht.

Nein, denn bei:

> for (i=SIZE ; i-- ;)

findet die erste Dekrementierung von i am Beginn des ersten 
Schleifendurchlaufs statt, also bevor du auf Array[i] zugreifst. Mit 
anderen Worten: Innerhalb des Schleifenkörpers ist beim ersten Durchlauf 
i == SIZE-1. Ich hab mich anfangs dadurch verwirren lassen, daß das 
Weitzerzählen des Schleifenzählers bei der for-Schleife im zweiten 
Ausdruck statt im dritten gemacht wird.

[Harald (Gast)]

>wer die schleife macht ist die Frage, schreibt man die Schleife als
>mehre asm Befehle oder nutzt die die String funktioenen der CPU.
>
>Das geht geht aber eh nur wenn man keine 0 in der array hat. Dafür muss
>am ende eine 0 vorhanden sein.

Alter ! Was für ein Quatsch!