Auf Wert prüfen

Chuqa

Hallo,

ich möchte in meinem Programm einen Wert darauf prüfen, ob er in einer Liste von vordefinierten Werten vorhanden ist, d.h ich z.B. ein Array welches konstante Werte enthält, und nun soll geprüft werden, ob ein z.B. errechneter oder eingebener Wert in diesem Array vorhanden ist. Wie mache ich das bzw. gibt es eine elegantere Lösung, als das Array Element für Element zu durchlaufen? Gibt es eventuell bessere Datenstrukturen um das zu realisieren, oder ist dort ein Array schon das Komfortabelste?

mfg chuqa

Dommel

Ich denke es kommt darauf an, wie diese Werte im Array stehen... Sollten sie zufällig drin stehen, wird es wohl keine bessere Lösung geben, als das Array zu durchlaufen.
Sollten sie aber sortiert drin stehen, könnte man zB binäre Suche verwenden.
Falls die Werte nicht sortiert sind und du öfters überprüfst, ob ein Wert vorkommt, lohnt es sich vielleicht auch, das Array zu sorieren

ser1al

du kannst auch einen vector aus der stl und seine methoden verwenden!

Ansonsten dürfte dich bei relativ kleinen arrays das durchiterieren kein problem sein
Dennoch meine empfehlung: vector, da er auch sicherer ist als von hand angelegte arrays!

Achja, und das Array vorher sortieren wäre viell noch sinnvoll!

LordJaxom

Ich würde dafür ehrlichgesagt ein std::set nehmen, da es zum einen dafür sorgt dass jede Zahl nur einmal vorhanden ist, und zum anderen den Lookup in O(log n) statt O(n) schafft, wie es beim Vector (oder C-Array) der Fall wäre.

EDIT: Und zum dritten eine native find-Methode bietet

camper

LordJaxom schrieb:

Ich würde dafür ehrlichgesagt ein std::set nehmen, da es zum einen dafür sorgt dass jede Zahl nur einmal vorhanden ist, und zum anderen den Lookup in O(log n) statt O(n) schafft, wie es beim Vector (oder C-Array) der Fall wäre.

EDIT: Und zum dritten eine native find-Methode bietet

die beste empfehlung hängt von verschiedenen faktoren, die z.T. noch nicht genannt wurden, ab. ein std::set hat keine vorteile gegenüber einem sortierten vector, wenn dessen daten nur einmalig initialisiert (oder ggf. selten modifiziert werden). im gegenteil, finden sehr viele suchoperationen (im vergleich zu modifikationen) statt, so gibt es zwei probleme:
für kleine objekte T ist der overhead der sets - 2 pointer je element + padding + allocatorverwaltung (wenn der allocator nichts taugt - erheblich
es wird eine menge platz verschwendet (wenn ich ints speichere, brauche ich also auf 32bit systemen mindestens 3mal soviel platz wie ein vector mit minimal allockiertem speicher - d.h. selbst wenn der vector beim reallokieren verdoppelt, bleibt er immer noch sparsamer)
dieser größere speicherverbrauch erhöht nat. das problem von cache misses, und bedingt auch eine relativ schlechte lokalität von referenzen.
ist nun T ein sehr großes objekt, so relativiert sich der mehrverbrauch eines sets, zudem wird das kopieren ja proportional teuerer
zudem spielt die gesamtgröße des containers eine rolle - für sehr kleine container kann eine lineare suche durchaus performanter als eine binäre suche sein

prinzipiell kann also ein vektor oder ein array durchaus die günstiste lösung sein. sofern möglich, dürfte ein statisches array dabei die nase vorn haben.

faustregel: std::set ist besser als sortierte vektoren - wenn
- T sehr groß und teuer zu kopieren ist, oder
- der container oft modifiziert werden muss

dass set eine eigene find-methode hat, bedeutet keinerlei vor- oder nachteil (eigentlich ist es eher ein nachteil, weil so die trennung zwischen algorithmus und datenstruktur aufgegeben wird)

ssm

camper schrieb:

eigentlich ist es eher ein nachteil, weil so die trennung zwischen algorithmus und datenstruktur aufgegeben wird)

Complexity:

std::binary_search : at most log(last - first) + 2 comparisons
std::equal_range : at most 2 * log(last - first) + 1 comparisons
std::upper_bound : at most log(last - first) + 1 comparisons
std::lower_bound : at most log(last - first) + 1 comparisons

ac = associative container
std::ac::find : logarithmic
std::ac::equal_range : logarithmic
std::ac::upper_bound : logarithmic
std::ac::lower_bound : logarithmic

Fragen?

LordJaxom

"At most" bedeutet aber doch nicht "always". Ich gehe doch einfach mal davon aus dass die Standardalgorithmen für assoziative Container hinreichend effizient spezialisiert sind.

Chuqa

Da die Werte statisch sind und es eh nur 3 Werte sind, wird das Array wohl überflüssig sein und es reicht eine einfache if-Prüfung aus.

Ich danke euch für eure Hilfe.

mfg chuqa

LordJaxom

Und für drei Zahlen treiben wir hier so'n Aufwand?

ssm

LordJaxom schrieb:

"At most" bedeutet aber doch nicht "always". Ich gehe doch einfach mal davon aus dass die Standardalgorithmen für assoziative Container hinreichend effizient spezialisiert sind.

Leider ist es einhach unmöglich, die Standardalgorithmen so effizient zu spezialisieren. Scott Meyers hat darauf hingewiesen.

Chuqa schrieb:

nur 3 Werte

camper

ssm schrieb:

LordJaxom schrieb:

"At most" bedeutet aber doch nicht "always". Ich gehe doch einfach mal davon aus dass die Standardalgorithmen für assoziative Container hinreichend effizient spezialisiert sind.

Leider ist es einhach unmöglich, die Standardalgorithmen so effizient zu spezialisieren. Scott Meyers hat darauf hingewiesen.

das scheitert schon daran, dass die assoziativen container alle nur bi-direktionale iteratoren haben, und diese standard-algorithmen folglich gar nicht anwendbar sind.