Spieler im Koordinatenbereich erfassen (variablen-filterung)

[Jan.O]

Hallo,


Bei einer Serveranwendung stehe ich nun vor folgendem Problem: Ich habe auf einem server eine Gewisse anzahl von spielern. Ich muss nun schnell ermitteln können, welche dieser Spieler eine x-koordinate zwischen zB 10 und 20 haben und eine y-koordinate zwischen zB 20 und 30. Dabei möchte ich möglichst keinen loop verwenden.

Das ganze soll vergleichbar sein mit dem mysql-statement
"[...] WHERE x BETWEEN 10 AND 20
AND
y BETWEEN 20 AND 30 [...]"

Gibt es in Python eine bestimme Art, die Variablen so zu speichern, dass man sie schnell nach Eigenschaften filtern kann?

[BlackJack]

Warum keine Schleife?

[Jan.O]

Bei zB 1000 spielern zu performance-fressend, wenn es in abständen weniger sekunden ausgeführt wird.

[BlackJack]

1000 Spieler in Abständen von wenigen Sekunden ist da echt kein Grund keine als "list comprehension" verkleidete Schleife zu verwenden.

[audax]

Code: Alles auswählen

val_x, val_y = (xrange(10,41), xrange(31))
for player in (p for p in players if p.x in val_x and p.y in val_y):
    print "Player %s ist da!" % player.name

So z.B. könnte man das machen. Die Mengen definiere ich vorher, damit das xrange nicht immer wieder aufgerufen wird. Falls der Profiler sagt, das der Teil ein Engpass ist, könnte man mal schaun, obs mit set(xrange(foo)) fixer geht.

[birkenfeld]

Das ist aber ne ziemlich umständliche (und langsame) Art und Weise, das hier zu schreiben:

Code: Alles auswählen

for p in players:
    if 10 <= p.x <= 40 and 0 <= p.y <= 30:
        print "Player %s ist da!" % p.name

[audax]

Aber meins kann steps

Aber ja, hast recht...

[Jan.O]

1000 Spieler in Abständen von wenigen Sekunden ist da echt kein Grund keine als "list comprehension" verkleidete Schleife zu verwenden.

Auch wenn jeder dieser 1000 spieler in kurzen abständen alle anderen spieler loopen müsste?

[audax]

probier es eben aus...lass den profiler laufen und schau, wo der engpass ist. Dann kannst du evtl. anfangen, zu optimieren....entweder den Algo oder die Technik.

[veers]

Die alternative wäre noch 2 Listen sortiert nach der X/Y Koordinate zu erstellen. Dann dürfte das ganze in ~O(lg n) lösbar sein.

Aber wie Hoare schon sagt:
"Premature optimization is the root of all evil."

Ich weis das ist hart. Aber überleg dir mal wieso die Python Programmierst - Vermutlich nicht weil es die schnellste Programmiersprache ist

PS: Falls du wie oben angetönt Kollisionen zwischen Spielern finden willst brauchst du definitiv einen besseren Algorithmus. Dann ist die Laufzeit nämlich O(n^2) was bei 1000 Usern bereits einer Million entspricht. Das Problem ist jedoch bekannt und es gibt einige brauchbare Lösungsansätze. Google ist dein Freund

[sma]

Ich würde darauf tippen, dass der Datenbankserver auch entweder einen Tablescan macht oder aber zwei binäre Indizes anlegt. Das könnte man auch alles selbst in Python machen. Es gibt aber, wenn mich mein Gedächnis nicht im Stich lässt, Partitionierungsalgorithmen, die schneller als mit zwei binären Suchen feststellen können, ob ein Punkt in einem Bereich liegt. Habe aber meine Computergrafik-Bücher nicht griffbereit. Entweder würde ich empfehlen, so einen Algorithmus zu recherchieren oder mal zu gucken, ob eine Datenbank, die GIS-Operationen unterstützt, dass nicht von sich aus kann.

Stefan

[Jan.O]

Die alternative wäre noch 2 Listen sortiert nach der X/Y Koordinate zu erstellen. Dann dürfte das ganze in ~O(lg n) lösbar sein.

Was das?

[Jan-Peer]

Eine Angabe zur Komplexität des Algorithmus. In etwa: Wieviel Zeiteinheiten zur Lösung des Problems bei n Spielern benötigt werden. Google: O-Notation