Array durchsuchen und Position des Treffers liefern - javarea.de Forum powered by javarea.de

Archivlink: javarea.de Forum > JavaScript > Array durchsuchen und Position des Treffers liefern

Vollständigen Link anzeigen: javarea.de Forum > JavaScript > Array durchsuchen und Position des Treffers liefern

Pages: [1]

geschrieben von Micha am 23.07.2008 - 11:16

Hallo,

ich möchte in JAVA ein Array durchsuchen und die Position des Treffers zurück bekommen. JAVA bietet bereits eine entsprechende Methode binarySearch für verschiedene Datentypen an. Nachteil ist, dass das Array hierzu sortiert sein muß und damit der eigentliche Index verloren im Originalarray geht.

Eine simple Implementierung ist soweit auch klar:

	HTML-Quelltext
1: 2: 3: 4: 5:	int Menge[] = {3,6,1,7,9,4,25}; int gesuchteZahl = 4; for (int i=0; Menge.length; i++) if (Menge[i] == gesuchteZahl) System.out.println( "Der Treffer ist " + i ); //5

In einer Funktion verpackt und fertig.

Wie man erkennen kann, wird in dem Beispiel fast das ganze Array durchsucht, bevor der Treffer kommt, was hier also viel Zeit kostet. Man könnte nun gleichzeitig von vorn und hinten suchen lassen aber das löst das Problem nicht wirklich. Hat einer eine Idee, wie man das geschickt machen kann?

Micha

geschrieben von Klaush am 23.07.2008 - 12:32

	Zitat
	Wie man erkennen kann, wird in dem Beispiel fast das ganze Array durchsucht, bevor der Treffer kommt, was hier also viel Zeit kostet.

Wenn das Array keine 1 Millionen Datensätze enthält

, sollte das Array relativ schnell durchlaufen sein. Ist die Zeit jedoch auf Millisekunden abhängig, dann ist es vlt. ratsam das Array schon beim Aufbau zu sortieren. Soll bedeuten, das dass Array schon im Aufbau mit der kleinsten beginnen soll.

Besser noch ein zweidimensionales Array aufbauen, wo Wert und Key abgelegt werden, dann kannst du sortieren wie du willst und hast den alten Ursprungskey als Wert hinterlegt.

geschrieben von Micha am 23.07.2008 - 13:22

Hi Klaus,

ich möchte mit dünnbesetzten Matrizen rechnen. Hierzu fange ich an, in JAVA eine Klasse zu implementieren. Dünnbesetzte Matrizen haben viele Null-Elemente, die nicht gespeichert werden müssen. Ich habe hierzu zwei 1D-Arrays.

Im Ersten stehen die Schlüssel drin und im zweiten der eigentliche Wert. Der Schlüssel ergibt sich aus der Zeilen- und Spaltennummer der eigentlichen Matrix. Wenn ich nun Element X aus der Zeile 4 und Spalte 5 habe, dann erzeuge ich den Schlüssel zb 36 und suche diesen im ersten Array. Wenn ich ihn finde, dann ist der Index des 1. Arrays mit dem des 2., wo der eigentliche Wert drin steht, identisch, sodass ich das Element zurück geben kann. Ist der Schlüssel nicht drin, so handelt es sich um ein Null-Element und es wir 0 (Null) zurück gegeben.
Ich hoffe es war soweit verständlich. Ich habe große Matrizen und die Belegen auch mal den gesamten Speicher (1.6GB) und rechnen ca 6 Stunden - da gibts es also Speichertechnisch schon was zu optimieren - Zeit ist unkritisch.
Der Suchlauf selbst ist natürlich auch recht fix. Er kostet aber in der Summe Zeit. Bei jedem Schreib/Lesezugriff benötige ich den Index, den ich Suchen muß.

Vll ist eine MAP hier doch besser geeignet.

Gruß Micha

geschrieben von Klaush am 23.07.2008 - 20:14

Ich schau's mir morgen noch einmal an, bin gerade am neuer Beitrag-BUG. Wie ich dich kenne, hast du morgen sicherlich schon eine Lösung ;)

geschrieben von Micha am 23.07.2008 - 22:07

Hi,

ich habe es in einer HashMap nun gelöst. Damit komme ich um das Sortieren rum.

Danke trotzdem
Micha

P.S. kann ich den Beitrag abhacken?

geschrieben von Klaush am 23.07.2008 - 22:39

	Zitat von: Micha am 23.07.2008 - 22:07
	P.S. kann ich den Beitrag abhacken?

Ja, leider vorerst nur über die Themenansicht. In den nächsten Tagen baue ich eine Option direkt beim Posten ein, dann kann das Thema schon bei der letzten Antwort als erledigt markiert werden.

Das mit der HashMap musst du mir noch einmal auf Deutsch im ICQ bei einer Flasche Bier erzählen....

HTML-Quelltext

Zitat

Zitat von: Micha am 23.07.2008 - 22:07