Liste ab Index X iterieren

[theliquidwave]

Hallo.
Ich habe mal wieder ein Problem.
Es geht dieses mal um Performance sparen, auch wenn es nur ganz wenig ist.

Darstellen:
Es gibt X "Checkpoints" die jeweils eine ID von 0 bis X-1 haben.
Es gibt Y "Spieler" die jeweils die aktuelle ID des zuletzt durchlaufenen Checkpoints gespeichert haben.

Problem: Ich muss mehrmals pro Sekunde alle Spieler durchlaufen und alle Checkpoints durchlaufen (eine Funktion der Klasse aufrufen), jedoch kann ich mir alle Checkpoints sparen, die ich bereits durchlaufen habe.

Beispiel:
Spieler A hat bereits 3 Checkpoints (also ID 0, 1 und 2) durchlaufen, also brauch er nur noch die Checkpoints 4 bis 6 durchlaufen (also ID 3, 4 und 5).

Wie kriege ich es nun hin, dass ich eine for-Schleife bekomme, die folgendem Pseudocode entspricht?

Code: Alles auswählen

for player in players:
    for checkpoint in checkpoints[ab checkpoint mit id größer als player.lastcheckpoint]:
        checkpoint.callAnything()

Gruß,
Chris

[Leonidas]

Wenn die Liste von Checkpoints sortiert ist, kannst du einfach mit der Slicing-Syntax arbeiten und alle elemente ab dem 3 bis zum letzten "herausslicen".

[theliquidwave]

Wow - der Tipp ist gut. Ich hoffe, ich habe das richtig verstanden.
Hier mal 2 Ergebnise von timeit

Code: Alles auswählen

>>> Timer("""for x in a[1:]:
	pass""", """a = ["lol", "rofl", "omg", "penis"]""").timeit()
0.4901405090143553
>>> Timer("""for x in a[1:]:
	pass""", """a = ["lol", "rofl", "omg", "penis"]""").timeit()
0.48246583567396328
>>> Timer("""for x in filter(lambda x: x[0] > 0, enumerate(a)):
	pass""", """a = ["lol", "rofl", "omg", "penis"]""").timeit()
6.6803945704419334
>>> Timer("""for x in filter(lambda x: x[0] > 0, enumerate(a)):
	pass""", """a = ["lol", "rofl", "omg", "penis"]""").timeit()
6.5947354580753199

Ich führe die Tests immer 2x durch, auch wenn ich weiß, dass eh 100.000 Durchläufe / Test vorhanden sind. Die Ergebnisse sind wohl sehr aussagekräftig. Falls noch etwas schnelleres vorhanden ist, würde ich gerne mehr darüber erfahren.

Gruß

[Leonidas]

Also dass die Variante mit ``filter``, ``lambda`` und ``enumerate`` jetzt viel langsamer ist verwundert dich nicht wirklich, oder? Dafür brauchts keinen Benchmark.

[theliquidwave]

Naja es wundert mich schon. Ich habe keine Erfahrung mit beiden Methoden. Ich dachte halt, das gleicht sich aus, da mit a[1:] ja immer eine Kopie erstellt wird (oder etwa nicht?), mit filter() jedoch wird ja nur "ausgeschlossen" und nicht andauernd eine Kopie erstellt.

Gruß

[sma]

Wenn schon, dann finde ich eine list comprehension einfacher als lambda und filter:

Code: Alles auswählen

a = [1, 2, 3, 4]

for e in [e for i, e in enumerate(a) if i > 1]:
	print e

Das lohnt sich aber alles nur dann, wenn das Objekt, über das mit iterieren will, ein Generator oder ähnliches und keine einfache Liste ist.

Stefan

[Leonidas]

Naja es wundert mich schon. Ich habe keine Erfahrung mit beiden Methoden. Ich dachte halt, das gleicht sich aus, da mit a[1:] ja immer eine Kopie erstellt wird (oder etwa nicht?), mit filter() jedoch wird ja nur "ausgeschlossen" und nicht andauernd eine Kopie erstellt.

Es wird nicht "andauernd" eine Kopie erstellt, sondern nur einmal. Und ``enumerate()`` erstellt implizit auch eine Kopie, denn irgendwie muss ja die Liste in die Form ``(0, erstes_element), (1, zweites_element), (2, drites_element)...`` kommen. Also es kopiert die Elemente, zählt hoch und erzeugt Tupel. Insgesamt ist das ja alleine schon mehr Aufwand als eine simple Kopie. Dann durchläufst du die Liste und rufst auf jedem Element das ``lambda`` auf - Funktionsaufrufe sind in Python vergleichsweise langsam, daher dauert das auch noch etwas. Schließlich wird dann von ``filter()`` noch eine weitere Kopie angelegt, die die gewünschten Elemente enthält.

Zum Vergleich: liste[1:] kopiert die Liste ohne das erste Element. Das wars.

[theliquidwave]

Ach so
Danke für die Erklärung. Wenn man sich das so durchliest erscheint es ja auch logisch, aber ich selber bin nicht drauf gekommen

Gruß

[Defnull]

Warum wurde islice() noch nicht genannt?

http://docs.python.org/library/itertool ... ols.islice

Das ist wie list[start:stop:step] nur das keine Kopie der Liste angelegt werden muss.

[theliquidwave]

Danke - dennoch:

Code: Alles auswählen

>>> Timer("""for x in a[1:]: pass""", """from itertools import islice; a = ["lol", "rofl", "omg", "penis"]""").timeit()
0.54007161254980929
>>> Timer("""for x in a[1:]: pass""", """from itertools import islice; a = ["lol", "rofl", "omg", "penis"]""").timeit()
0.52004960204510553
>>> Timer("""for x in islice(a, 1, None, 1): pass""", """from itertools import islice; a = ["lol", "rofl", "omg", "penis"]""").timeit()
0.59381402401695027
>>> Timer("""for x in islice(a, 1, None, 1): pass""", """from itertools import islice; a = ["lol", "rofl", "omg", "penis"]""").timeit()
0.5970785115089825

Gruß

[Leonidas]

Sieht bei großen Listen vermutlich anders aus. Vor allem auch beim Speicherverbrauch.

[sma]

Ich würde doch hoffen/vermuten, dass enumerate so implementiert ist:

Code: Alles auswählen

def enumerate(seq):
	i = 0
	for e in seq:
		yield i, e
		i += 1

und nicht so:

Code: Alles auswählen

def enumerate(seq):
	return zip(range(len(seq)), seq)

und daher keine Kopie der übergebenen Sequenz erzeugt, wie Leonidas es meinte.

Stefan

[theliquidwave]

Hi.
Auch bei 20 Einträgen ist a[1:] schneller und mehr Einträge kommen nur sehr sehr sehr selten vor, von daher werde ich diese verwenden

Gruß und Danke nochmals!

[cofi]

20 ist keine sonderlich grosse Laenge. Beim 100x liesse ihc mich da schon eher ueberzeugen.

[jbs]

Mein Vorschlag für enumerate:

Code: Alles auswählen

 enumerate = lambda seq: izip(count(), seq)

[Defnull]

Es geht dieses mal um Performance sparen

Auch bei 20 Einträgen ist a[1:] schneller und mehr Einträge kommen nur sehr sehr sehr selten vor

Du optimierst an der falschen Stelle.

[theliquidwave]

Wieso? Ich rufe die Funktion ca. 10 bis 15 mal pro Sekunde auf (unterschiedlich). Dort wird dann pro Spieler (bis zu 64...) jeder Checkpoint iteriert (können bis zu 20 sein). Das sind 1280 Durchgänge pro 1/10 Sekunde. Wo optimiere ich da falsch?

Gruß

[EyDu]

Also 12800 Zugriffe pro Sekunde sind nun wirklich nicht viel, eigentlich schon lächerlich wenig. Da musst du schon ein paar Größenordnungen drauf packen.

Optimiere also ggf. erst später und kümmere dich um die wichtigeren Dinge. Mit solchen Kleinigkeiten holst du eh nicht viel raus, strukturelle Änderungen machen schon viel mehr aus.

[theliquidwave]

Hi.
Echt, das ist wenig?
Das Problem ist aber auch noch, dass es sich ja um ein Plugin für einen Gameserver handelt. Es gibt also möglicherweise noch viele andere Plugins, die etwas öfters in der Sekunde berechnen, geschweige denn die Berechnungen vom Spiel selbst.

Ich weiß ja nicht ob die Abfrage groß ist, ich finde es jedoch schon beachtlich ^^

Code: Alles auswählen

if min((self.position1[0], self.position2[0])) > player.position[0] or 
player.position[0] > max((self.position1[0], self.position2[0])) or 
min((self.position1[1], self.position2[1])) > player.position[1] or 
player.position[1] > max((self.position1[1], self.position2[1])) or 
min((self.position1[2], self.position2[2])) > player.position[2] or 
player.position[2] > max((self.position1[2], self.position2[2])):
	return False

# weitere Aufrufe
return True

Gruß

[Defnull]

Was macht das Skript eigentlich, das du es alle 100ms laufen lassen musst? Dein Code gerade sieht aus wie Kollisionskontrolle, ist aber kaum lesbar.

Edit: OK, das ist ne Punk-in-Box Abfrage.

1) Die Klammern im min() und max() sind überflüssig und erzeugen unnötigerweise ein Tupel.
2) Könnte man da nicht ne deutlich einfachere Punkt-Kugel Abfrage vor schalten, die prüft, ob der Spieler überhaupt in der nähe der Checkpoint-Box ist? Oder gleich die Checkbox zu ner Checkkugel machen?