Seite 1 von 1

Spieler im Koordinatenbereich erfassen (variablen-filterung)

Verfasst: Dienstag 29. April 2008, 20:11
von 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?

Verfasst: Dienstag 29. April 2008, 20:41
von BlackJack
Warum keine Schleife?

Verfasst: Dienstag 29. April 2008, 20:44
von Jan.O
Bei zB 1000 spielern zu performance-fressend, wenn es in abständen weniger sekunden ausgeführt wird.

Verfasst: Dienstag 29. April 2008, 21:09
von BlackJack
1000 Spieler in Abständen von wenigen Sekunden ist da echt kein Grund keine als "list comprehension" verkleidete Schleife zu verwenden.

Verfasst: Dienstag 29. April 2008, 21:32
von 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.

Verfasst: Dienstag 29. April 2008, 21:39
von 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

Verfasst: Dienstag 29. April 2008, 21:47
von audax
Aber meins kann steps ;)

Aber ja, hast recht...

Verfasst: Dienstag 29. April 2008, 22:14
von Jan.O
BlackJack hat geschrieben: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?

Verfasst: Mittwoch 30. April 2008, 06:45
von 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.

Verfasst: Mittwoch 30. April 2008, 07:52
von 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." :wink:

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 ;)

Verfasst: Mittwoch 30. April 2008, 09:58
von 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

Verfasst: Mittwoch 30. April 2008, 19:30
von Jan.O
veers hat geschrieben: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?

Verfasst: Mittwoch 30. April 2008, 19:49
von 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