Archiv verlassen und diese Seite im Standarddesign anzeigen : Element im Array finden - ein schneller Weg?
nalye
2012-02-27, 15:59:12
Momentan gehe ich mein Array von vorne nach hinten einmal durch:
x=${#ARRAY[@]}
for ((n=0; n<$x; n++)); do
if [[ "$1" == ${ARRAY[$n]} ]]; then
echo $n;
return
fi
done
Kennt jemand eine flottere Möglichkeit? Die jetzt ist quasi der lange Weg, das gefällt mir aber nicht wirklich...
THEaaron
2012-02-27, 16:20:50
Wenn du ein normales unsortiertes Array vor dir liegen hast gibt es nach meiner Denkweise gerade keine Kriterien eine Suche nach bestimmten Eigenschaften zu reduzieren. Ich nehme da einfach mal an die Daten werden sequentiell ins Array gepflastert und haben keinen Bezug zum vorder bzw. hinterem Element.
Ansonsten gäbe es noch die Möglichkeit die Daten in einem Baum zu speichern und dort auszulesen, da gibt es anständige Such-Algorithmen für.
€: oder mal hier vorbeischauen..
http://de.wikipedia.org/wiki/Interpolationssuche
Sind die Daten sortiert oder nicht? :ugly:
Gast_samm
2012-02-27, 16:24:21
Ist das Array in irgendeiner Weise geordnet? Wenn nicht, bleibt dir wohl nichts anderes übrig.
Eine andere Datenstruktur, die beispielsweise davon profitiert dass die möglichen Werte eindeutig sind (was die Frage suggeriert) bleibt dir in Bash auch nicht übrig.
nalye
2012-02-27, 16:26:25
Nein, das Array ist nicht sortiert...
THEaaron
2012-02-27, 16:29:10
Dann bleiben dir nur wenige Möglichkeiten. ;)
Kannst natürlich auch selbst das Array teilen und die entstehenden Teillisten durchsuchen, worauf der Algo bei einem Treffer dann endet. Das ist dann zwar Glückssache aber in 50% der Fälle hast du dann einige Vergleiche gespart.
dann hast du keine andere möglichkeit, etwas im array zu finden...
du könntest aber das array sortieren bzw. die elemente immer an die richtige position einfügen, um anschließend elemente mittels der binären suche zu finden.
musst also abwägen, ob es die schnellere suche das wert ist...
nalye
2012-02-27, 16:40:49
Dann bleiben dir nur wenige Möglichkeiten. ;)
Kannst natürlich auch selbst das Array teilen und die entstehenden Teillisten durchsuchen, worauf der Algo bei einem Treffer dann endet. Das ist dann zwar Glückssache aber in 50% der Fälle hast du dann einige Vergleiche gespart.
Das klingt gar nicht mal schlecht...Bei einer 50:50-Chance hätte ich effektiv 25% Zeitersparnis auf Dauer :)
Gast vom Dienst
2012-02-27, 17:06:27
Das klingt gar nicht mal schlecht...Bei einer 50:50-Chance hätte ich effektiv 25% Zeitersparnis auf Dauer :)Mit Teillisten gewinnst du nichts im Vergleich zu einer sequentiellen Suche über das ganze Array, sofern du abbrichst nachdem das Element gefunden wurde.
Die Chance das Element in der ersten Hälfte zu finden ist 50%. Ob du das Array erst teilst oder aber von vorn nach hinten durchsuchst ändert nichts daran wie schnell du das Element im Schnitt findest. Das was THEaaron da vermutlich im Kopf herumgeschwirrt ist, ist das sortieren. Dort hilft so ein divide and conquer Ansatz weiter. Bei der Suche dagegen, würde es nur helfen wenn du mit Multithreading arbeiten würdest. Da ja scheinbar die Elemente bei dir unabhängig voneinander sind könntest du dann jeden Core bei einem Mehrkernsystem einen Anteil der Elemente durchsuchen lassen. So könntest du die Wartezeit drücken.
Sonst würde dir nur eine Heuristik (das gesuchte Element ist an bestimmten Stellen im Array häufiger zu finden) oder eine geignetere Datenstruktur helfen. Beispielsweise kann man wenn die Elemente nicht sortierbar, aber wenigstens eindeutig sind, mit Hashing arbeiten. Man leitet also aus dem Element selbst die Stelle im Array ab an der es sich befindet.
Allerdings die Kernfrage ist wohl eine andere. Hast du überhaupt so große Datenmengen, dass eine solche Optimierung sich rentieren würde?
nalye
2012-02-27, 17:12:05
Na ja, in dem Array können zu Spitzenzeiten > 10K Werte sein ;)
Was meinst Du mit Hashing? Bin in der Materie nicht so firm...
Senior Sanchez
2012-02-27, 19:10:23
Na ja, in dem Array können zu Spitzenzeiten > 10K Werte sein ;)
Was meinst Du mit Hashing? Bin in der Materie nicht so firm...
Bei 10.000 Elementen, dazu noch so einfachen Schleifendurchläufen, würde ich mir nicht die Mühe machen, irgendetwas zu optimieren.
Ohne eine Sortierung kannst du eh nichts machen. Hashing ( http://de.wikipedia.org/wiki/Hashtabelle ) könnte was bringen, aber bei der geringen Anzahl an Elementen ist das unnötiger Overhead.
THEaaron
2012-02-27, 19:15:20
Mea Culpa, der Gast hat Recht.
Habe es kurz von der Arbeit aus geschrieben und es durcheinander geworfen.
Die Hashtabelle wurde ja schon genannt. :)
Kennt jemand eine flottere Möglichkeit?
Wenn du keine Position als Fundort ausschließen kannst, gibt es keine schnellere Möglichkeit.
Nur wenn du die Positionen irgendwie einschränkst, sei es durch Sortieren, Heap erzeugen oder Hashtabelle bilden, kann man schneller Suchen.
RattuS
2012-02-27, 19:30:00
Wenn dein Array sogar über 10.000 Element haben kann, solltest du unbedingt eine Hash-Table aufbauen. Wenn dein verfügbarer Speicher knapp ist, fällt das allerdings weg.
sind die Elemente begrenzt (praktisch: 0..2^24) eignet sich direkte Adressierung, also perfektes Hashing. Laufzeit O(1)
Spirou
2012-02-27, 19:36:26
Ich nehme an, es geht um häufigeres Suchen in einem Array mit wechselnden Inhalten, bei denen Umsortieren per Bubblesort zu aufwendig wäre.
Eine Lösung wäre, schnelles Sortieren zu implementieren, indem man verkettete Pointer mitführt. So sähe das schematisch aus:
0= 3,2,""
1= 2,5,"Jonas"
2= 0,1,"Berta"
3= 4,0,"Zacharias"
4= 5,3,"Wilhelm"
5= 1,4,"Peter"
Alle Sätze bilden einen geordneten Ring, der von der Reihenfolge unabhängig ist. Der erste Eintrag enhält Pointer auf den ersten und letzten logischen Satz, aber keinen Inhalt. Beim Einfügen eines neuen Eintrags am Ende werden die Pointer des logischen Vorgängers und Nachfolgers geändert, beim Entfernen ebenfalls. Sortieren wird damit enorm beschleunigt.
Eine andere Möglichkeit besteht darin, die Pointer ihrerseits in einem assoziativen Array zu speichern, sodaß man mit wenigen Schritten den richtigen Eintrag findet. Ein assoziatives Array enthält Indizes in sortierter Reihenfolge. Es wird leer angelegt, und zu jedem Eintrag wird der Index an eine Position geschrieben, die der Sortierung entspricht. Wie man die ermittelt kommt auf die Sortierkriterien an. Geht aber auch nicht in fünf Minuten zu kodieren.
del_4901
2012-02-27, 20:08:46
Ich nehme an, es geht um häufigeres Suchen in einem Array mit wechselnden Inhalten, bei denen Umsortieren per Bubblesort zu aufwendig wäre.
Eine Lösung wäre, schnelles Sortieren zu implementieren, indem man verkettete Pointer mitführt. So sähe das schematisch aus:
0= 3,2,""
1= 2,5,"Jonas"
2= 0,1,"Berta"
3= 4,0,"Zacharias"
4= 5,3,"Wilhelm"
5= 1,4,"Peter"
Alle Sätze bilden einen geordneten Ring, der von der Reihenfolge unabhängig ist. Der erste Eintrag enhält Pointer auf den ersten und letzten logischen Satz, aber keinen Inhalt. Beim Einfügen eines neuen Eintrags am Ende werden die Pointer des logischen Vorgängers und Nachfolgers geändert, beim Entfernen ebenfalls. Sortieren wird damit enorm beschleunigt.
Eine andere Möglichkeit besteht darin, die Pointer ihrerseits in einem assoziativen Array zu speichern, sodaß man mit wenigen Schritten den richtigen Eintrag findet. Ein assoziatives Array enthält Indizes in sortierter Reihenfolge. Es wird leer angelegt, und zu jedem Eintrag wird der Index an eine Position geschrieben, die der Sortierung entspricht. Wie man die ermittelt kommt auf die Sortierkriterien an. Geht aber auch nicht in fünf Minuten zu kodieren.
Dadurch verschiebst man die Kosten auch nur vom auslesen zum einsetzen. Das lohnt sich also nur unter der Bedingung das haeufiger gelesen als geschrieben wird. In dem Fall kann man auch ueberlegen ob man nicht gleich das ganze in einen AVL-Baum einsortiert denn man in ein Array ausgebreitet hat. Das sollte nochmal um ein Vielfaches kostenguenstiger und cachefreundlicher sein.
Monger
2012-02-27, 20:13:44
Das einzige was ich zu dem Thema beitragen kann:
We follow two rules in the matter of optimization:
Rule 1. Don’t do it.
Rule 2 (for experts only). Don’t do it yet – that is, not until you have a perfectly clear and unoptimized solution.
Link (http://zcox.wordpress.com/2009/06/12/dont-optimize-your-code-yet/)
Rein vom Gefühl her (Fakten würden schließlich Messergebnisse erfordern, und die haben wir hier nicht) vermute ich, dass es sich nicht lohnt, ein Laufzeitverhalten von O(n) für 10000 Elemente noch weiter zu verbessern. Man kann durch klevere Wahl der verwendeten Daten (also z.B. durch Sortierung) verbessern, und man kann versuchen mit deutlich mehr Speicherverbrauch die CPU ein wenig zu entlasten. Beides hat Nachteile, denn im ersten Fall stell man Annahmen über die zu testenden Daten an, die eventuell auch furchtbar falsch sein können. Und bei zweiterem macht man schnell falsche Grundannahmen über die zugrundeliegende Plattform.
Im Endeffekt hilft nur wieder: Profilen, Flaschenhals erkennen, beheben, wieder profilen, und gucken ob sich WIRKLICH was verbessert hat. Wie beim Arzt: immer die schwerste Wunde zuerst behandeln, und erst das Röntgengerät auspacken wenn man Indizien für einen Bruch hat.
nalye
2012-02-27, 22:24:43
Ich seh schon, das wird komplizierter :ugly: Danke euch :)
Exxtreme
2012-02-27, 22:39:27
Sobald es ans Optimieren geht ... da kann man sich reinsteigern ohne Ende. :freak:
Bei größeren Systemen und Software hocken da wirklich hochbezahlte Softwareingenieure und optimieren rum.
Thunderhit
2012-02-28, 10:59:00
Wie AlphaTier schon sagte würde sich hier unter Umständen ein AVL- oder Rot-Schwarz-Baum lohnen. Dann sind die Daten immer sortiert und einfügen ist auch günstig, kommt eben darauf an, welche Operationen du am meisten auf der Datenstruktur ausführen willst.
Matrix316
2012-02-28, 13:01:52
Wenns wirklich wirklich wirklich viele Daten sind, könnte man sich überlegen diese in eine Datenbank zu schreiben und dann darauf zu suchen.
Ich kann mir auch 'n Nagel ins Knie bohren und daran meine Jacke aufhängen. Macht nur keiner.
Genausowenig wie man wegen lächerlichen (sorry) 10k Elementen hier irgendwelchen fetten Overhead in Form von Datenbanken oder ähnlichem aufzieht.
O(n) ist doch nett.
Wenns ne weitgehend statische Struktur ist, dann kann man tatsächlich über ein Vorsortieren nachdenken, macht damit halt das einfügen langsamer. Oder bei einer dynamischen Struktur mit Hashing nachhelfen, braucht halt mehr Speicher.
Oder es eben einfach so lassen und mit O(n) glücklich sein.
Solange der OP hier keine weiteren Spezifikationen seiner Daten preisgibt, könnt ihr alle tage- und wochenlang um des Kaisers Bart diskutieren, ohne irgendwohin zu kommen.
Und solange wir nichtmal wissen, ob denn überhaupt ein tatsächliches und nicht nur ein gefühltes ("das _muß_!!! doch besser gehen!!!") Performance-Problem vorliegt, sind diese Diskussionen hier sowieso komplett obsolet.
Thunderhit
2012-02-28, 15:39:15
Also Datenbank ist ja wohl totaler Overkill :D
Senior Sanchez
2012-02-28, 19:51:00
Ich kann mir auch 'n Nagel ins Knie bohren und daran meine Jacke aufhängen. Macht nur keiner.
Genausowenig wie man wegen lächerlichen (sorry) 10k Elementen hier irgendwelchen fetten Overhead in Form von Datenbanken oder ähnlichem aufzieht.
O(n) ist doch nett.
Wenns ne weitgehend statische Struktur ist, dann kann man tatsächlich über ein Vorsortieren nachdenken, macht damit halt das einfügen langsamer. Oder bei einer dynamischen Struktur mit Hashing nachhelfen, braucht halt mehr Speicher.
Oder es eben einfach so lassen und mit O(n) glücklich sein.
Solange der OP hier keine weiteren Spezifikationen seiner Daten preisgibt, könnt ihr alle tage- und wochenlang um des Kaisers Bart diskutieren, ohne irgendwohin zu kommen.
Und solange wir nichtmal wissen, ob denn überhaupt ein tatsächliches und nicht nur ein gefühltes ("das _muß_!!! doch besser gehen!!!") Performance-Problem vorliegt, sind diese Diskussionen hier sowieso komplett obsolet.
Mein Reden.
Eine Datenbank dürfte bei der Problembeschreibung in 99,999% aller Fälle totaler Quatsch sein.
Watson007
2012-02-28, 19:54:01
Also Datenbank ist ja wohl totaler Overkill :D
hmm kommt darauf an. "Embedded" Datenbanken gibt es ja nicht ohne Grund, z. B. Firebird embedded. Firebird embedded ist auch klein.
es gibt auch leichtgewichtige Datenbanken wie SQLite: http://de.wikipedia.org/wiki/SQLite
Matrix316
2012-02-28, 20:24:43
Vielleicht gibts ja schon eine Datenbank im Hintergrund. Keine Ahnung. ;)
robobimbo
2012-02-28, 21:34:08
ich glaub auch, das jedweder aufwand für 10k elemente übertrieben ist.
array, baumstruktur (avl, red-black), hashmap - teste einfach, was am besten für deine daten geeignet ist, jedwede db lösung wäre ausser overhead nur overhead :)
Sobald es ans Optimieren geht ... da kann man sich reinsteigern ohne Ende. :freak:
Bei größeren Systemen und Software hocken da wirklich hochbezahlte Softwareingenieure und optimieren rum.Aber mit Sicherheit nicht wahllos und nach Bauchgefühl. Insbesondere in großen Systemen beschränken sich die wirklichen "Hotspots" mit Relevanz auf die Systemperformance doch in den allermeisten Fällen auf sehr kleine Bereiche des Codes. Bevor du da nicht analysiert hast, wo genau sich diese Bereiche befinden und was da überhaupt rauszuholen ist, sind großartige Optimierungsversuche im besten Fall verschwendete Zeit.
Also erstma profilen, dann weitersehen...
x=${#ARRAY[@]}
for ((n=0; n<$x; n++)); do
if [[ "$1" == ${ARRAY[$n]} ]]; then
echo $n;
return
fi
done
was is'n das für ne Programmiersprache? PHP? Perl?
Baalzamon
2012-05-03, 13:35:32
was is'n das für ne Programmiersprache? PHP? Perl?
Bash. ;)
vBulletin®, Copyright ©2000-2024, Jelsoft Enterprises Ltd.