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?
Spieler im Koordinatenbereich erfassen (variablen-filterung)
1000 Spieler in Abständen von wenigen Sekunden ist da echt kein Grund keine als "list comprehension" verkleidete Schleife zu verwenden.
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
- birkenfeld
- Python-Forum Veteran
- Beiträge: 1603
- Registriert: Montag 20. März 2006, 15:29
- Wohnort: Die aufstrebende Universitätsstadt bei München
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
Auch wenn jeder dieser 1000 spieler in kurzen abständen alle anderen spieler loopen müsste?BlackJack hat geschrieben:1000 Spieler in Abständen von wenigen Sekunden ist da echt kein Grund keine als "list comprehension" verkleidete Schleife zu verwenden.
- veers
- User
- Beiträge: 1219
- Registriert: Mittwoch 28. Februar 2007, 20:01
- Wohnort: Zürich (CH)
- Kontaktdaten:
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
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
[url=http://29a.ch/]My Website - 29a.ch[/url]
"If privacy is outlawed, only outlaws will have privacy." - Phil Zimmermann
"If privacy is outlawed, only outlaws will have privacy." - Phil Zimmermann
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
Stefan