Suche im Array

[Dekan]

Hallo zusammen,

bin hier neu im Forum. Ich suche nach einer schnellstmöglichen Lösung des folgenden Problem. es sind zwei Arrays (eigentlich Hash-Maps)gegeben, aufsteigend sortiert, beide haben über 1. Mio Interger-Werte. Es soll das zweite Array auf Übereinstimmung geprüft werden und zwar so:

z.B der erste Wert im ersten Array ist 53500, es wird im zweiten Array nach diesem Wert(Key) und nach den Werten die "daneben" liegen gesucht. Daneben kann auch ziemlich weit sein. Also bei 53500 sollen Werte des zweiten Array gefunden werden, die im Bereich vom 20000 bis 20050 (beispeilsweise, kann auch 0 bis 50 oder 70 bis 90 oder 758350 bis 758355 sein, maximale Diffirenz ist jedoch 50) relativ zu 53500 liegen => (53500-20050) bis (53500-20000) UND (53500+20000) bis (53500+20050): (33450 bis 33500) UND (73500 bis 73550).

Bis jetzt habe ich das Problem folgendermaßen gelöst. Das erste Array wird komplett durchgegangen (z.B eine for-Schleife). Danach mithilfe zwei anderen inneren for-Schleifen werden die Werte in einem Array gespeichert, die im zweiten Array zu suchen wären (Also in diesem Bespiel => (33450 bis 33500) UND (73500 bis 73550) - insgesamt 100 Werte maximal). Im zweiten Array(oder besser gesagt Hash-Map) wird nach diesen Schlüsseln gesucht, und wenn sie gefunden werden, werden zum Key gehörenden Values in einem result-Array gespeichert. Somit sind 1.000.000 (1.Array) x 100(maximale # von Werten) = 100.000.000 Durchläufe mindestens notwendig, selbst wenn das zweite Array nicht durchsucht wird. (Dafür sind 32 Sekunden auf einem Xeon CPU)

Das Ganze dauert 110 Sekunden bei maximalen Einstellungen (also wenn Streuung 100 ist). Kennt jemand einen Algorithmus, der das schnelle erledigen könnte? Vielen Dank im Voraus

Bearbeitet 8. Dezember 2010 von Dekan

[Astasor]

wenn dein array aufsteigend sortiert ist, kannst du doch "binär suchen". das ist effizienter als durchgehen.

[Dekan]

wenn dein array aufsteigend sortiert ist, kannst du doch "binär suchen". das ist effizienter als durchgehen.

Vielen Dank für deine Antwort

einfach binär zu suchen ergibt immer noch 1.Mio * log(1.Mio) ~ 19,93 Mio Vergleiche, was leider zu viel ist. Aber ich werde es mit meinem Algo vergleichen, vlt. bringt das doch was.

[Klotzkopp]

Ist für das Resultat relevant, zu welchen Keys aus Array 1 die Werte passten? Was ist mit Duplikaten?

[Dekan]

Duplikaten gibt es nicht, weil sie nicht in der Datenbank vorhanden sind.

Für das Resultat ist die Zuordnung sehr wichtig, weil sie das Ergebnis ist!

[Klotzkopp]

Duplikaten gibt es nicht, weil sie nicht in der Datenbank vorhanden sind.

Aber es kann doch passieren, dass ein Key aus dem zweiten Array zu mehr als einem Key aus dem ersten Array passt? Dann wäre der Wert mehrfach im Ergebnis.

Für das Resultat ist die Zuordnung sehr wichtig, weil sie das Ergebnis ist!

Im ersten Beitrag hattest du geschrieben, dass die Values gespeichert werden. Die Keys also auch? Aus beiden Arrays?

[Guybrush Threepwood]

Wenn du die ganzen Werte in einer Datenbank stehen hast warum machst du das dann nicht da statt soviel in ein Array einzulesen? :eek

[Dekan]

Wenn du die ganzen Werte in einer Datenbank stehen hast warum machst du das dann nicht da statt soviel in ein Array einzulesen? :eek

Weil es länger dauert. Selbst das was ich programmiert habe ist dreimal so schnell als auf dem Datenbankserver:)

[Guybrush Threepwood]

Das wage ich zu bezweifeln. Es kann gar nicht schneller sein erst die komplette Tabelle einzulesen und dann zu suchen als direkt von der Datenbank das gewünschte Ergebnis zu bekommen.

Wenn doch was das SQL Statement sehr...ungünstig

Ich würde das Problem mit entsprechendem Tabellenlayout mal im Datenbank Forum posten, da findet sich bestimmt jemand der dir bei dem SQL Statement helfen kann.