Inhalt eines arrays auf einmal überprüfen,

[Black_Panter]

hi,

ich hab einen Array, wo zahlen drin sind. jetzt soll eine weiter zahl hinzugefügt werden, aber nur wenn diese zahl noch nicht im Array zweimal vorhanden ist. kann man dies nur mit einer schleife überprüfen, indem man jede zahl im Array einzeln überprüft, oder geht das auch schneller?

gruß
Sören

 

[Mr. Snoot]

PHP?

Prüfen ob etwas in einem Array steht kannst du z.B. hiermit:

http://de3.php.net/manual/de/function.in-array.php
http://de3.php.net/manual/de/function.array-key-exists.php

 

[Fruchtnektar]

Suchalgorithmen sind ziemlich umfangreich.
Kommt auf die Programmiersprache/Skriptsprache an, wie das Array implementiert ist. Meistens sind es imo einfach verkettete Listen.

Such mal nach verketteten Listen, da erfährst du ziemlich viel zu Suchalgorithmen

 

[Pelesit]

Aber ob sich der Aufwand lohnt, so ein Array durzugehen ist was anderes.
Ich denk einfach ne Schleife machen, ist schnell und effizient genug.

 

[7H3 N4C3R]

Wenn das Array sortiert ist, kannst du mit einer Komplexität log(n) eine binäre Suche machen. Allerdings ist das Einfügen in ein sortiertes Array aufwändiger, je nach verwendeter Datenstruktur.

 

[hArdLuck]

jepp... pelesit hat sowas von recht... denn ansonsten musst du das ding sortieren... (was natürlich auch wieder dauert... und das ganze nicht unbedingt einfacher macht) und wenn du nicht gerade mehrer hunderttausend werte oder eine extrem zeitkritische anwendung hast lohnt sich das eh nich
einfach eine normale for-schleife in pseudo-code:

for i=0 bis ArrayLänge mache
wenn (zahl == Array(an der stelle i)) dann zähler + 1
ende for schleife
wenn (zähler < 2) dann füge zahl dem array hinzu

 

[muckelzwerg]

Ja es geht schneller. Du landest aber fast immer bei einem Tradeoff zwischen Geschwindigkeit und Speicherplatz.
Du kannst z.B. für jede Zahl einen Platz in Deinem Array reservieren.
Wenn die Zahl eingefügt wird, erhöhst Du den Wert am entsprechenden Index.
Du speicherst also nichtmehr die Zahlen selbst, sondern zählst, wie oft sie im Array vorhanden sind.
Für Deinen Test brauchst Du nur den Wert am entsprechenden Index prüfen.
Dadurch kann der Speicherplatzverbrauch natürlich enorm steigen, unrealistisch sind solche Verfahren aber nicht.
Wenn man z.B. bloß Informationen über 52 Spielkarten speichern möchte, kann das passen.
Und wenn das Programm auf einem Microcontroller läuft (Handy, Gameboy, etc...) ist der Geschwindigkeitsvorteil evtl. sogar relevant.
Falls der Zahlenraum zu groß ist, kannst Du es immernoch mit einer Partition versuchen.
Du kannst z.B. die Zahlen von eins bis hundert in einer Liste hinter dem ersten Index halten,
die von 101 bis 200 am zweiten index etc.
Wenn die Zahlen ungleichmäßig verteilt sind, musst Du die Bereiche entsprechend anpassen.

Es stellt sich aber wirklich die Frage, was Du genau machst. Sonst kann man da nicht so viel zu sagen.

@ hArdLuck: es sollte (zähler < 2) sein?

-- -- muckelzwerg

 

[hArdLuck]

@ muckelzwerg ... ups stimmt hab oben wohl ein "nicht" überlesen -_-

habs geändert...