SortedCollection vs SortedContainers

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.
Sirius3
User
Beiträge: 17710
Registriert: Sonntag 21. Oktober 2012, 17:20

@Scholastik: darf ich es nocheinmal wiederholen: alle relevanten Teile Deines Beispielcodes sind schon in C implementiert. Geschwindigkeitswunder wirst Du nicht erwarten können. Der Algorithmus, den Du gerade verwendest, ist halt nicht geeignet.
Benutzeravatar
sparrow
User
Beiträge: 4164
Registriert: Freitag 17. April 2009, 10:28

@Scholastik:

Warum brauchst du die Daten denn überhaupt sortiert?
Denn du schreibst weiter oben, dass ein dict (was sich ja für diese Art der Datenhaltung regelrecht aufdrängt und mit Signalfackel auf sich aufmerksam machen will) in den Zugriffen ausgesprochen schnell ist, nur die Sortierung dauert.
Daher die Frage, warum sortieren, wenn das zeitkritische Element das Zeitnahe aufnehmen von Daten in die Datenstruktur ist. Für eine Visualisierung ist das Sortieren zum Beispiel nicht zeitkritisch.

Vom grünen Tisch wirkt das so, als würdest du den zweiten Schritt vor dem ersten tun. Du nimmst externe Tools, die hochoptimieten Code optimieren sollen, übersiehst dabei aber, dass dein Code nicht (für das gegebene Problem) optimiert ist.
Scholastik
User
Beiträge: 53
Registriert: Freitag 7. Juli 2017, 12:35

@Sirius:
du darfst dich wiederholen, aber den Sinn dahinter versteh ich nicht :D Mein Algorithmus, also bisect zu verwenden ist schon super (du darfst mir aber gerne sagen was genau noch besser ist und nicht nur allgemein dass irgendwelche "bäume" besser sein könnten, denn ich habe wie gesagt schon die gegenteilige Meinung gelesen -> es steht Behauptung gegen Behauptung) und dass cython nicht mehr viel hilft hatte ich ja auch oben schon selbst gemerkt. Pypy hingegen hat tatsächlich geholfen, weshalb ich mir nun mit numba ein ähnliches ergebnis erhofft habe, ohne dass ich gleich alles umstellen muss.
noisefloor hat geschrieben: Montag 14. Januar 2019, 07:26 Hallo,
also ich hatte mit Numba keine Problem. Funktionen dekorieren, laufen lassen, fertig. Numba war bei meinen Tests (stunpfes Testen auf Primzahlen) auch schneller als PyPy.
Ansonsten müsstest du den relevanten Codeteil und die _genaue_ Fehlermeldung von Python + Numba mal zeigen.

Gruß, noisefloor
Sagen dir meine genannten Einschränkungen denn nichts (also sollte es diese nicht geben?)? Neben verschachtelten Listen kann man scheinbar auch keine eigenen Funktionen in der dekorierten Funktion aufrufen (zumindest bei njit, mit jit hab ichs noch nicht probiert). Du kennst ja sortedCollection und du kennst meinen Code der die updates einpflegt. Wie/an welcher stelle würdest du da eine mit @jit oder @njit dekorierte Funktion ansetzen?

@sparrow:
na der Sinn davon real time orderbook daten zu haben, ist auch real time zu traden. Dh. ich muss mithilfe der orderbookdaten diverse Berechnungen durchführen, und das möglichst oft um innerhalb weniger milisekunden reagieren zu können. Im aktuellen Aufbau mache ich diese Berechnungen alle 0.1 sekunden, brauche also ein sortiertes orderbook alle 0.1 sekunden. Ich habe mir bereits Gedanken darüber gemacht, ob es sinnvoll wäre, das ganze nicht linear, sondern zb auf eventbassis oder ähnliches zu programmieren, aber das macht für meine trading strategie keinen Sinn. Denn 1) Wie will man bei zig updates alle 35ms irgendeine Berechnung auf Basis eines events anstoßen (das wären dann ja noch deutlich häufigere Berechnungen als alle 0.1 sekunden)? Und 2) darf die nächste Rechnung ohnehin erst angestoßen werden, wenn die vorherige fertig ist, bzw je nach Ergebnis der Berechnung, darauf reagiert wurde. Und ich glaube es gibt nur diese 2 Möglichkeiten, oder? (also entweder alle x sekunden berechnen und alles nacheinander machen, oder stattdessen auf ein event von außen warten und darauf dann reagieren)
Sirius3
User
Beiträge: 17710
Registriert: Sonntag 21. Oktober 2012, 17:20

@Scholastik: ich habe Dir exakt geschrieben, dass das Einfügen von Elementen in eine Liste eine O(n)-Operation ist, die langsam ist, die bei Bäumen, je nach Ausführung eine O(1) oder eine O(log(n))-Operation ist. Wo hast Du die gegenteilige Meinung gelesen, bitte Referenz.
Ich bin hier auch nicht da, Dir den fertigen Algorithmus zu liefern, sondern sage Dir nur, welcher besser ist, nicht im Konjunktiv, sondern mathematisch bewiesen.
Was Du sonst noch an Code hast, wo PyPy etwas hilft, weiß hier ja keiner.
Scholastik
User
Beiträge: 53
Registriert: Freitag 7. Juli 2017, 12:35

Sirius3 hat geschrieben: Montag 14. Januar 2019, 09:19 @Scholastik: ich habe Dir exakt geschrieben, dass das Einfügen von Elementen in eine Liste eine O(n)-Operation ist, die langsam ist, die bei Bäumen, je nach Ausführung eine O(1) oder eine O(log(n))-Operation ist. Wo hast Du die gegenteilige Meinung gelesen, bitte Referenz.
Ich bin hier auch nicht da, Dir den fertigen Algorithmus zu liefern, sondern sage Dir nur, welcher besser ist, nicht im Konjunktiv, sondern mathematisch bewiesen.
Was Du sonst noch an Code hast, wo PyPy etwas hilft, weiß hier ja keiner.
danke, habe jetzt mal nach den stichworten tree und real time orderbook gesucht und bin auf das hier gestoßen, welches wohl trees und C verwendet und bzgl O() schneller sein soll:
https://github.com/Crypto-toolbox/HFT-Orderbook
ich werd mal gucken, ob ich damit was zum laufen bekomme um es zu testen.

Pypy hat sowohl meinen Code im Eingangspost beschleunigt, als auch den testcode welcher 1 million updates durchspielt, bei dem wirklich nicht viel mehr code ist, als euch bekannt ist. Interessant find ich, dass der Code im Eingangspost mit pypy so wie er da steht tatsächlich langsamer ist, aber wenn man die "testliste" neu zusammenstellt, also zb "for i in range(1000): testliste.append([i,2])", dann ist pypy sogar 10 mal schneller als python. Aber naja, da ich pypy ohnehin nicht verwenden werde, ist das auch egal.
Benutzeravatar
__blackjack__
User
Beiträge: 13003
Registriert: Samstag 2. Juni 2018, 10:21
Wohnort: 127.0.0.1
Kontaktdaten:

@Scholastik: Bei Pypy muss man daran denken, dass das ein JIT-Compiler ist der ein bisschen Aufwärmzeit braucht. Das hatte __deets__ auch schon geschrieben. Der Compiler analysiert was Funktionen machen und übersetzt die dann in Maschinensprache. Das heisst beim ersten Aufruf von Funktionen sind die noch nicht schneller, weil da erst einmal die Python-Variante ausgeführt wird und *zusätzlich* geschaut wird was die mit welchen Datentypen so macht. Daraufhin wird dann Maschinencode erzeugt, und erst beim nächsten Aufruf mit passenden Typen wird *der* dann ausgeführt. Das sollte man beim Schreiben, oder mindestens beim Bewerten von Tests berücksichtigen.

Generell würde ich auch für solche Mikrotests nicht selbst eine Schleife schreiben die das millionenmal macht, sondern das `timeit`-Modul verwenden.
“Most people find the concept of programming obvious, but the doing impossible.” — Alan J. Perlis
Antworten