Spieler im Koordinatenbereich erfassen (variablen-filterung)

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Antworten
Jan.O
User
Beiträge: 61
Registriert: Samstag 26. April 2008, 00:32

Dienstag 29. April 2008, 20:11

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?
Jan.O
User
Beiträge: 61
Registriert: Samstag 26. April 2008, 00:32

Dienstag 29. April 2008, 20:44

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

Dienstag 29. April 2008, 21:09

1000 Spieler in Abständen von wenigen Sekunden ist da echt kein Grund keine als "list comprehension" verkleidete Schleife zu verwenden.
audax
User
Beiträge: 830
Registriert: Mittwoch 19. Dezember 2007, 10:38

Dienstag 29. April 2008, 21:32

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.
Benutzeravatar
birkenfeld
Python-Forum Veteran
Beiträge: 1603
Registriert: Montag 20. März 2006, 15:29
Wohnort: Die aufstrebende Universitätsstadt bei München

Dienstag 29. April 2008, 21:39

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
Dann lieber noch Vim 7 als Windows 7.

http://pythonic.pocoo.org/
audax
User
Beiträge: 830
Registriert: Mittwoch 19. Dezember 2007, 10:38

Dienstag 29. April 2008, 21:47

Aber meins kann steps ;)

Aber ja, hast recht...
Jan.O
User
Beiträge: 61
Registriert: Samstag 26. April 2008, 00:32

Dienstag 29. April 2008, 22:14

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?
audax
User
Beiträge: 830
Registriert: Mittwoch 19. Dezember 2007, 10:38

Mittwoch 30. April 2008, 06:45

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.
Benutzeravatar
veers
User
Beiträge: 1219
Registriert: Mittwoch 28. Februar 2007, 20:01
Wohnort: Zürich (CH)
Kontaktdaten:

Mittwoch 30. April 2008, 07:52

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 ;)
[url=http://29a.ch/]My Website - 29a.ch[/url]
"If privacy is outlawed, only outlaws will have privacy." - Phil Zimmermann
sma
User
Beiträge: 3018
Registriert: Montag 19. November 2007, 19:57
Wohnort: Kiel

Mittwoch 30. April 2008, 09:58

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
User
Beiträge: 61
Registriert: Samstag 26. April 2008, 00:32

Mittwoch 30. April 2008, 19:30

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?
Jan-Peer
User
Beiträge: 166
Registriert: Dienstag 2. Oktober 2007, 10:55

Mittwoch 30. April 2008, 19:49

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
Antworten