Um"quadraht"suche...

[Markus**]

Hallo Forum...

In einem Raster von 10000x10000 habe ich zufällig 4791 Punkte verteilt.
Nun möchte ich wissen, welche Punkte Nachbarpunkte in einem gewissen Umkreis, bzw. umquadraht aufweisen. Zur Zeit hab ich das Ganze in einer Datenbanktabelle mit den Spalten id, x, y abgelegt und die Prüfung mache ich wie folgt:

SELECT r1.id, r2.id  
FROM positions r1  
JOIN positions r2 ON r1.id < r2.id  
WHERE ABS( r1.x - r2.x ) <5  
AND ABS( r1.y - r2.y ) <5

Der Join enthält also wie folgt: (4791*4790)/2 = 11.474.445 Datensätze; über Elfmillionen Mal die Vergleiche in der WHERE-Klausel berechnen, dauert natürlich so seine Zeit.

Hat hier irgendjemand 'ne Idee, wie man das optimieren kann? Nicht zwingend mit Hilfe einer Datenbank, denke eher an eine effizientere mathematische Lösung, die nicht den Gauß bedarf um die 11.474.445 Vergleiche zu vermeiden.

Gruß, Markus**

[Vinzenz Mai]

Hallo,

In einem Raster von 10000x10000 habe ich zufällig 4791 Punkte verteilt.
Nun möchte ich wissen, welche Punkte Nachbarpunkte in einem gewissen Umkreis, bzw. umquadraht aufweisen. Zur Zeit hab ich das Ganze in einer Datenbanktabelle mit den Spalten id, x, y abgelegt und die Prüfung mache ich wie folgt:

SELECT  
    r1.id,  
    r2.id  
FROM  
    positions r1  
JOIN  
    positions r2  
ON  
    r1.id < r2.id  
WHERE  
    ABS( r1.x - r2.x ) < 5  
AND  
    ABS( r1.y - r2.y ) < 5

https://forum.selfhtml.org/?t=182509&m=1207661 behandelt das gleiche Problem.
Schon mal probiert, Deine WHERE-Klausel in die Join-Bedingung einzubringen.

Ach ja:
Im Mittel hast Du übrigens die Hälfte vergessen: die Punkte, deren id kleiner ist als die des Referenzpunktes. Betrachte zum Beispiel als Ausgangspunkt den Punkt mit der größten id: Deine Ergebnismenge wird leer sein.

Freundliche Grüße

Vinzenz

[Markus**]

SELECT

r1.id,
    r2.id
FROM
    positions r1
JOIN
    positions r2
ON
    r1.id < r2.id
WHERE
    ABS( r1.x - r2.x ) < 5
AND
    ABS( r1.y - r2.y ) < 5

>   
> <https://forum.selfhtml.org/?t=182509&m=1207661> behandelt das gleiche Problem.  

 Tut es das?!  
  

> Schon mal probiert, Deine WHERE-Klausel in die Join-Bedingung einzubringen.  

klar, dann ändert sich nichts!  

>   
> Ach ja:  
> Im Mittel hast Du übrigens die Hälfte vergessen: die Punkte, deren id kleiner ist als die des Referenzpunktes. Betrachte zum Beispiel als Ausgangspunkt den Punkt mit der größten id: Deine Ergebnismenge wird leer sein.  

Ich glaube hier hast Du nicht richtig aufgepasst, oder ich hab nicht verstanden, was Du willst. Ich vergleiche jedes Koordinatenpaar mit jedem anderen, aber nicht (weil es uninteressant in der Ergebnismenge ist) 1 <=> 2 UND 2<=>1 weil es das Selbe ist. Vergessen tu ich nicht's soweit ich das überschaue!  
  
Gruß, Markus\*\*

[Vinzenz Mai]

Hallo,

Ich glaube hier hast Du nicht richtig aufgepasst, oder ich hab nicht verstanden, was Du willst.

nein, ich hab' nicht verstanden, was Du willst.

Vermeide den unperformanten Selfjoin. Nutze stattdessen Subselects. Sorge dafür, dass die Menge der zusätzlich zu betrachtenden Punkte möglichst schnell klein wird.

Trotz allem: der von mir angesprochene Thread betrachtet die gleiche Problematik :-)

Wie Du sinnvoll vorgehst, ist durchaus davon abhängig, wie diese Daten später genutzt werden sollen.

- Ist es eine einmalige Bestimmung?
 - Wenn nein
     - Kommen Punkte dazu (werden welche entfernt)?

...

Freundliche Grüße

Vinzenz

[Markus**]

Vermeide den unperformanten Selfjoin. Nutze stattdessen Subselects. Sorge dafür, dass die Menge der zusätzlich zu betrachtenden Punkte möglichst schnell klein wird.

Wenn ich wissen möchte, welche von den knapp 5000 koordinaten nah beieinander liegen, muß ich ja jeden mit jeden vergleichen, oder? Genau das tut erstmal der Join; stellt jeden datensatz gegenüber jeden anderen unter der Beachtung, dass 2 nicht mehr mit 1 verglichen werden muß, weil ja 1 schon mit 2 verglichen wurde. Der gleiche Ansatz wird auch in dem anderen Thread verfolgt mit dem Unterschied, dass hier eine einmalige Berechnung ausreicht.

Trotz allem: der von mir angesprochene Thread betrachtet die gleiche Problematik :-)

jop, den hab ich auch schon gelesen, hilft aber nicht deutlich weiter.

Wie Du sinnvoll vorgehst, ist durchaus davon abhängig, wie diese Daten später genutzt werden sollen.

• Ist es eine einmalige Bestimmung?

nein

• Wenn nein
       - Kommen Punkte dazu (werden welche entfernt)?

ja!

Gruß, Markus**

[Vinzenz Mai]

Hallo,

Vermeide den unperformanten Selfjoin. Nutze stattdessen Subselects. Sorge dafür, dass die Menge der zusätzlich zu betrachtenden Punkte möglichst schnell klein wird.
Wenn ich wissen möchte, welche von den knapp 5000 koordinaten nah beieinander liegen, muß ich ja jeden mit jeden vergleichen, oder?

Nein. Auch dann nicht. Wenn Du einen geeigneten Datensatz gefunden hast, reicht es. Wenn Du ausschließen kannst, dass es einen gibt, reicht es auch. Suche gezielt (datenbanktechnisch gesprochen: Nutze Indexe! Funktionale Indexe wären hier von Vorteil :-))

Wie Du sinnvoll vorgehst, ist durchaus davon abhängig, wie diese Daten später genutzt werden sollen.

• Ist es eine einmalige Bestimmung?
  nein
• Wenn nein
       - Kommen Punkte dazu (werden welche entfernt)?
  ja!

Wie oft sind Änderungen im Vergleich zu den Bestimmungen zu erwarten?
Viele Änderungen je neuem Lauf oder viele Bestimmungen je Änderung?

Freundliche Grüße

Vinzenz

[Markus**]

OK, dann mal eine weitere Beschreibung des Vorhabens:
Die Punkte sind in Wirklichkeit Vektoren und haben Eigenschaften wie Richtung, Geschwindigkeit, Typ und weitere. Punkte vom TypA und TypB die sich treffen, löschen sich aus, TypB und TypC weichen einander aus, usw., usw.
heißt also, ich muss ständig prüfen ob irgendwo Treffer vorkommen um sie auszuwerten.
Im großen und ganzen geht es hier also um eine Simulation.

datenbanktechnisch gesprochen: Nutze Indexe! Funktionale Indexe wären hier von Vorteil :-)

jop, aber wie ich im ersten Posting auch schon sagte, muß ich das ja nichtmal zwingend mit Hilfe einer Datenbank machen...

[Vinzenz Mai]

Hallo,

OK, dann mal eine weitere Beschreibung des Vorhabens:
Die Punkte sind in Wirklichkeit Vektoren und haben Eigenschaften wie Richtung, Geschwindigkeit, Typ und weitere. Punkte vom TypA und TypB die sich treffen, löschen sich aus, TypB und TypC weichen einander aus, usw., usw.
heißt also, ich muss ständig prüfen ob irgendwo Treffer vorkommen um sie auszuwerten.

ständig alle Kombinationen durchzutesten, um die wenigen relevanten zu finden, wäre da wirklich keine gute Strategie.

Im großen und ganzen geht es hier also um eine Simulation.

mit vermutlich mehreren Berechnungsläufen je Sekunde :-)

jop, aber wie ich im ersten Posting auch schon sagte, muß ich das ja nichtmal zwingend mit Hilfe einer Datenbank machen...

Ich mag Datenbanken, ich weiß auch, was ein Selfjoin ist :-). Ich rate Dir dringendst von der Verwendung ab.

Freundliche Grüße

Vinzenz

[Klawischnigg]

Hi there,

Wenn ich wissen möchte, welche von den knapp 5000 koordinaten nah beieinander liegen, muß ich ja jeden mit jeden vergleichen, oder?

Naja, Du kannst als erste Vereinfachung (wäre quasi Halbierung) wenn Du einfach nur einmal eine Dimension vergleichst - nur die, die in einer Dimension nahe liegen, können auch als Punkt naheliegen und die untersuchst Du dann, ob Sie auch in der anderen Dimension nahe sind...

[Mega]

Hat hier irgendjemand 'ne Idee, wie man das optimieren kann? Nicht zwingend mit Hilfe einer Datenbank, denke eher an eine effizientere mathematische Lösung, die nicht den Gauß bedarf um die 11.474.445 Vergleiche zu vermeiden.

Ja allerdings.
Ich vermute mal, das diese ~11 Mio. Datensätze alle legal und laut § 6 Absatz 1Satz 1 des AtG. ordungsgemäß abgesichert werden.
Naja, nun sei es so.

Bei Vektor c handelt es sich um Konstante x, y und t (y,x, id).
Die Konstante bleibt immer stabil und konstant, bis die ID (t) die Größe ~3,333 erreicht.  In dem Fall muss man auf folgendes Zugreifen:

Ich hoffe ich konnte dir Helfen, laut meinen Berechnung dauert das Vergleichen der Datensätze (~11 Mio.) etwa 9,543221 sek.

Wenn dir ein BlueGene/L zur Verfügung steht, dann steigert sich die Performance der Berechnung um >10000%.

Viel Spaß!

Gruss

[Klawischnigg]

Hi there,

Ich vermute mal, das diese ~11 Mio. Datensätze alle legal und laut § 6 Absatz 1Satz 1 des AtG. ordungsgemäß abgesichert werden.

??? Wieder zuviel gearbeitet?

[Markus**]

Hi there,

Ich vermute mal, das diese ~11 Mio. Datensätze alle legal und laut § 6 Absatz 1Satz 1 des AtG. ordungsgemäß abgesichert werden.

??? Wieder zuviel gearbeitet?

Hahaha... ja, scheint mir auch so! ;)

[Markus**]

Ja allerdings.
Ich vermute mal, das diese ~11 Mio. Datensätze alle legal und laut § 6 Absatz 1Satz 1 des AtG. ordungsgemäß abgesichert werden.

Selbstverständlich!

Naja, nun sei es so.

Bei Vektor c handelt es sich um Konstante x, y und t (y,x, id).
Die Konstante bleibt immer stabil und konstant, bis die ID (t) die Größe ~3,333 erreicht.  In dem Fall muss man auf folgendes Zugreifen:

Danke für die tollen Formeln!

Ich hoffe ich konnte dir Helfen, laut meinen Berechnung dauert das Vergleichen der Datensätze (~11 Mio.) etwa 9,543221 sek.

Stimmt!

Wenn dir ein BlueGene/L zur Verfügung steht, dann steigert sich die Performance der Berechnung um >10000%.

Viel Spaß!

Immer!

Gruss

:-)

[Patrick Andrieu]

Hallo Markus**!

QUADRAT, STANDARD, SUCHMASCHINE

Und nicht standart, quadraht, quahdrat, der Draht der QUAs glüht, genauso wie das Eiserne Pferd auf den Suchma-SCHIENEN galoppiert....

Aaargh.....

QUADRAHT-TISCH, PRAKT-TISCH, GUHT!

Viehle Grühße aus Frankfurt/Main,
Pahtrick

[Markus**]

Hallo Markus**!

Hallo Pahtrick ;)
Sorry, aber ich bin kein perfekter Rechtschreiber und ich werde nie wieder Quadrat mit H schreiben!

QUADRAT, STANDARD, SUCHMASCHINE

SPONTANEITÄT hast hier noch vergessen, wobei ich glaube, dass es nach der Rechtschreibreform auch SPONTANITÄT geschrieben werden darf.

Und nicht standart...

Standarten aber! ;) Und Standards auch!

Ich reg' mich auch immer über blöde Fehler auf, die andere machen. Die "Kids" lernen offenbar nicht mehr lesen und schreiben heut' zu Tage, da stellen sich mir hin und wieder die Nackenhaare hoch, wenn ich Texte im www lese.
Aber wie ich immer wieder feststelle, mach ich selbst auch mal was falsch.

[Patrick Andrieu]

Hallo Markus**!

Sorry, aber ich bin kein perfekter Rechtschreiber und ich werde nie wieder Quadrat mit H schreiben!

Auch sorry für meinen Ausbruch... aber am meisten aufgeregt hat mich nicht, dass Du einen Fehler gemacht (ich vertippe mich oft oder formuliere beim Tippen um und vergesse dann, zu korrigeren), sondern dass niemand von den vielen Antwortern es im Titel geändert hat ;)

QUADRAT, STANDARD, SUCHMASCHINE
SPONTANEITÄT hast hier noch vergessen, wobei ich glaube, dass es nach der Rechtschreibreform auch SPONTANITÄT geschrieben werden darf.

Da müsste ich nachschlagen, aber ärgern tu ich mich auch über:

Adaption (statt Adaptation)
  Spezifität (statt Spezifizität)

und einige mehr... auch wenn diese Schreibweisen (mittlerweile?) richtig sind ;)

Ich reg' mich auch immer über blöde Fehler auf, die andere machen. Die "Kids" lernen offenbar nicht mehr lesen und schreiben

Mein Patenkind ist schon seit August in der Ersten und, ich weiß nicht, ich meine, mich zu erinnern, dass wir damals im »Cours préparatoire« (in der Ersten) bereits nach drei, vier Monaten schon komplett lesen konnten und uns ans Schreiben machten...

heut' zu Tage,

hm, heutzutage? ;)

da stellen sich mir hin und wieder die Nackenhaare hoch, wenn ich Texte im www lese.

Geht mir genauso ;)

Aber wie ich immer wieder feststelle, mach ich selbst auch mal was falsch.

Bei mir sind es seltener Orthographiefehler sondern eher kleinere Artikel- und Grammatikfehler. Häufiges Beispiel: Ich habe ein Wort im Neutrum als Subjekt, baue dann einen Nebensatz mit »der« als Pronomen (Das Boot, der ich ..., ... .). Wer sowas findet, kann es behalten, denn solche Fehler werde ich hier immer wieder machen ;)

Viele Grüße aus Frankfurt/Main,
Patrick

[Swen]

Moin,

(... und vergesse dann, zu korrigeren)

Echt? Wäre ich jetzt nicht drauf gekommen. SCNR ;-))

heut' zu Tage,
hm, heutzutage? ;)

zur Not reicht sogar ein sparsames "heute"?

Mein Lieblingsschreibfehler: Analge (statt Anlage).
Ich hab wohlmeine anale Phase nicht gut durchlebt :-)

Grüße

Swen

[Patrick Andrieu]

Hallo Swen!

Mein Lieblingsschreibfehler: Analge (statt Anlage).
Ich hab wohlmeine anale Phase nicht gut durchlebt :-)

:)

Ich veruntippe oft »ie« in »ei«, aber anhand des Eicons für meine Corporate Eidentity ist es nicht verwunderlich ;)

Viele Grüße aus Frankfurt/Main,
Patrick

[Markus**]

Ist auch egal, die Umquadrat-Suche dauert bei 4791 Koordinaten jetzt nur noch 0,3sek auf 'nem alten 700er Celeron.
Verfahren:

Ich stecke die Daten (x,y,id) in ein mehrdimensionales Array, sortiere das zunächst nach der Spalte mit den x-werten.
Danach prüfe ich ob abs(x[n-1] - x[n]) und (y[n-1] - y[n]) innerhalb der Quadrat-größe liegt, gebe id[n-1] und id[n] als naheliegendes Pärchen aus.

Fertig! ;) 0,3sek sind VIEEEEL angenehmer als 11,5sek!

Werde jetzt noch kurz checken wie es sich verhält, wenn ich den Pytagoras noch einbaue und ne Umkreissuche daraus mache.

Gruß, Markus

[Klawischnigg]

Hi there,

[...] aber am meisten aufgeregt hat mich nicht, dass Du einen Fehler gemacht (ich vertippe mich oft oder formuliere beim Tippen um und vergesse dann, zu korrigeren), sondern dass niemand von den vielen Antwortern es im Titel geändert hat ;)

Das verrät aber viel mehr über Dich als über den orthographischen Bösewicht...

[Der Martin]

Hallo,

SPONTANEITÄT hast hier noch vergessen, wobei ich glaube, dass es nach der Rechtschreibreform auch SPONTANITÄT geschrieben werden darf.

Spontanität mit Ei? Kurz nachgeschlagen ... scheint nicht falsch zu sein, sieht aber irgendwie kaputt aus. Ich hab's schon immer "Spontanität" geschrieben. Auch vor der Rechtschreibdeform.

Da müsste ich nachschlagen, aber ärgern tu ich mich auch über:
  Adaption (statt Adaptation)

wobei "Adaption" allerdings richtig ist - und "Adaptation" sieht geschrieben genauso merkwürdig aus, wie es gesprochen klingt. Im Englischen und im Französischen klingt "adaptation" wegen der anderen Betonung bzw. Sprachmelodie besser (und ist AFAIK auch richtig).

Spezifität (statt Spezifizität)

Da sind beide Begriffe richtig, aber es gibt einen Bedeutungsunterschied. Während "Spezifität" nur die Tatsache bezeichnet, *dass* etwas spezifisch ist, drückt "Spezifizität" aus, in welchem Ausmaß etwas spezifisch (im Sinn von "genau") ist. Also keine bloße Tatsache, sondern eine quantitative Aussage.

da stellen sich mir hin und wieder die Nackenhaare hoch, wenn ich Texte im www lese.
Geht mir genauso ;)

Mir auch. Und nicht nur im Web. Auch in Print-Publikationen findet man oft tolle Interpretationen der Rechtschreibung, und Zeichensetzung scheint bei vielen auch Glückssache zu sein.

Bei mir sind es seltener Orthographiefehler sondern eher kleinere Artikel- und Grammatikfehler. Häufiges Beispiel: Ich habe ein Wort im Neutrum als Subjekt, baue dann einen Nebensatz mit »der« als Pronomen (Das Boot, der ich ..., ... .). Wer sowas findet, kann es behalten, denn solche Fehler werde ich hier immer wieder machen ;)

Das sei einem Franzosen, dessen Muttersprache kein grammatisches Neutrum kennt, voll und ganz nachgesehen.

So long,
 Martin

[Patrick Andrieu]

Hallo Martin!

Spontanität mit Ei? Kurz nachgeschlagen ... scheint nicht falsch zu sein

Frz.: spontanéité

sieht aber irgendwie kaputt aus. Ich hab's schon immer "Spontanität" geschrieben. Auch vor der Rechtschreibdeform.

Da müsste ich nachschlagen, aber ärgern tu ich mich auch über:
  Adaption (statt Adaptation)

wobei "Adaption" allerdings richtig ist - und "Adaptation" sieht geschrieben genauso merkwürdig aus,

ist aber auch richtig: http://www.duden-suche.de/suche/trefferliste.php?suchbegriff[AND]=adaptation&suche=homepage&treffer_pro_seite=10&modus=title&level=125&x=0&y=0
Frz: adaptation

Das sei einem Franzosen, dessen Muttersprache kein grammatisches Neutrum kennt, voll und ganz nachgesehen.

Danke ;) ´

Viele Grüße aus Frankfurt/Main,
Patrick

[cygnus]

Hallo :)

Und nicht standart, quadraht, quahdrat, der Draht der QUAs glüht, genauso wie das Eiserne Pferd auf den Suchma-SCHIENEN galoppiert....

Aaargh.....

Aber aber -
es ging doch um Umquadraht. Das ist was ganz anderes.

Den Umqua Draht braucht man zum Fliegenfischen dort,
wo der Umqua River in Oregon etwas ruhiger wird

mfg
cygnus

[Patrick Andrieu]

Hallo cygnus!

Den Umqua Draht braucht man zum Fliegenfischen dort,

;)

wo der Umqua River in Oregon etwas ruhiger wird

^^^^^^

Bist Du Uwes Frau? Das wär' echt oregonal!

Viele Grüße aus Frankfurt/Main,
Patrick

[cygnus]

Hallo :)

Bist Du Uwes Frau? Das wär' echt oregonal!

Darüber habe ich jetzt lange nachgedacht, aber ich glaube,
mein Mann heißt nicht Uwe.
Ich möchte ihn aber auch nicht so direkt fragen.

mfg
cygnus