Das war ursprünglich ein Problem, mit dem ich bei der Arbeit zu tun hatte, aber jetzt versuche ich es nur aus Neugierde zu lösen.
Ich möchte herausfinden, ob int 'a' das int 'b' so effizient wie möglich enthält. Ich habe etwas Code geschrieben, aber es scheint egal, was ich schreibe, es in eine Zeichenkette zu zerlegen und dann indexOf doppelt so schnell zu benutzen wie mathematisch.
Speicher ist kein Problem (im Rahmen des Zumutbaren), einfach die Verarbeitungsgeschwindigkeit.
Dies ist der Code, den ich geschrieben habe, um es mathematisch zu machen:
%Vor%Hier ist die String-Methode, die ich verwende, die die obige mathematische Methode zu übertrumpfen scheint:
%Vor%Obwohl dies für meine Arbeit nicht wirklich erforderlich ist, habe ich mich nur gefragt, ob irgendjemand irgendeinen Weg finden könnte, meine mathematische Vorgehensweise oder einen völlig neuen Ansatz weiter zu optimieren. Wieder ist die Erinnerung kein Problem, ich schieße nur auf schiere Geschwindigkeit.
Ich bin wirklich daran interessiert, etwas zu sehen oder zu hören, was irgendjemand zu bieten hat.
BEARBEITEN: Wenn ich sage contains ich meine, kann überall sein, also zum Beispiel findMatch (1234, 23) == true
BEARBEITEN: Für jeden, der sagt, dass dieser Mist nicht lesbar und unnötig ist: Sie verpassen den Punkt. Es ging darum, ein interessantes Problem zu lösen, und keine Antwort für den Produktionscode zu finden.
Dies ist entlang Kibbees Linie, aber ich wurde ein wenig davon fasziniert, bevor er gepostet und ausgearbeitet hat:
%Vor%Da 300 Zeichen viel zu wenig sind, um ein Argument zu erstellen, bearbeite ich diesen Hauptbeitrag, um auf Pyrolistic zu antworten.
Im Gegensatz zum OP war ich nicht so überrascht, dass ein nativer kompilierter indexOf schneller war als Java-Code mit Primitiven. Mein Ziel war es also nicht, etwas zu finden, von dem ich dachte, dass es schneller war als eine native Methode, die zig Mal im Java-Code genannt wird.
Das OP machte klar, dass dies kein Produktionsproblem war und mehr im Sinne einer faulen Neugier, so löst meine Antwort diese Neugier. Meine Vermutung war, dass Geschwindigkeit ein Problem war, als er versuchte, es in der Produktion zu lösen, aber als eine untätige Neugier, "Diese Methode wird Millionen und Abermillionen Male genannt werden", trifft nicht mehr zu. Da er einem Poster erklären musste, wird es nicht mehr als Produktionscode verfolgt, daher spielt die Komplexität keine Rolle mehr.
Außerdem bietet es die einzige Implementierung auf der Seite, die es schafft, die "123" in "551241238" zu finden, so dass, sofern die Korrektheit nicht von äußerer Bedeutung ist, dies gewährleistet ist. Auch der Lösungsraum von "einem Algorithmus, der das Problem mathematisch mit Java-Primitiven löst, aber optimierten nativen Code übertrifft" könnte auch EMPTY sein.
Außerdem ist aus Ihrem Kommentar nicht klar, ob Sie Äpfel mit Äpfeln verglichen haben oder nicht. Die funktionale Spezifikation ist f (int, int) - & gt; Boolean, nicht f (String, String) - & gt; Boolean (das ist die Domäne von indexOf ). Also, es sei denn, du hast so etwas getestet (was meinen noch immer schlagen könnte, und ich wäre nicht sehr überrascht). Der zusätzliche Aufwand könnte etwas von diesem übermäßigen 40% aufzehren.
Es macht die gleichen grundlegenden Schritte. log 10 <(a) encoding + log 10 <(b) encoding + tatsächlich findet die Übereinstimmung, die auch O ( n ) wo
Es sollte schnellere Zeichenfolge sein, weil Ihr Problem Text, nicht mathematisch ist. Beachten Sie, dass die "contains" -Beziehung nichts über die Zahlen sagt, sondern nur etwas über ihre dezimalen Darstellungen.
Beachten Sie auch, dass die Funktion, die Sie schreiben möchten, nicht lesbar ist - ein anderer Entwickler wird nie verstehen, was Sie tun. (Sehen Sie, welche Schwierigkeiten Sie damit hatten.) Die String-Version dagegen ist vollkommen klar.
Die einzige Optimierung, die ich mir vorstellen kann, besteht darin, die Umwandlung in eine eigene Zeichenfolge durchzuführen und die Ziffern (rechts nach links) zu vergleichen, während Sie die Konvertierung durchführen. Konvertieren Sie zuerst alle Ziffern von b und konvertieren Sie dann von rechts auf a, bis Sie eine Übereinstimmung an der ersten Ziffer von b finden (von rechts). Vergleichen Sie, bis alle Übereinstimmungen von b übereinstimmen oder Sie einen Konflikt gefunden haben. Wenn Sie eine Nichtübereinstimmung treffen, gehen Sie zurück zu dem Punkt, an dem Sie mit der ersten Ziffer von b beginnen, und fahren Sie mit a fort und beginnen Sie erneut.
IndexOf muss grundsätzlich den gleichen Rückverfolgungsalgorithmus durchführen, außer von links. Abhängig von den tatsächlichen Zahlen kann dies schneller sein. Ich denke, wenn die Zahlen zufällig sind, sollte es sein, da es viele Male geben sollte, wenn es nicht alle von a konvertieren muss.
Sieht so aus, als ob Ihre Funktion eigentlich ziemlich gut ist, aber eine kleine Verbesserung:
%Vor%Nur weil das a kleiner als b ist, schaut es nicht würdig aus, nicht wahr? Viel Glück und Post wenn Sie die Lösung finden!
Das ist ein interessantes Problem. Viele der Funktionen von String.class sind eigentlich nativ, was String zu einem schwierigen Vorschlag macht. Aber hier sind ein paar Helfer:
TIPP 1: Verschiedene einfache ganzzahlige Operationen haben unterschiedliche Geschwindigkeiten.
Durch schnelle Berechnungen in Beispielprogrammen zeigte sich:
%Vor%Sie wollen also so wenig Aufteilung wie möglich für Multiplikation oder Modulo verwenden. Nicht gezeigt sind Subtraktions-, Additions- und Vergleichsoperatoren, weil sie alle aus dem Wasser blasen. Außerdem ermöglicht die Verwendung von "final" so viel wie möglich, dass die JVM bestimmte Optimierungen durchführt. Beschleunigen Sie Ihre "getLength" -Funktion:
%Vor%Das ergibt eine ca. 7-fache Verbesserung der Funktion. Sie erhalten eine indexOutOfBounds-Ausnahme, wenn b & gt; Ihr Maximum in Exponenten. Um das zu lösen, können Sie haben:
%Vor%Das ist etwas langsamer und gibt Ihnen eine falsche Länge, wenn b zu groß ist, aber es wird keine Ausnahme ausgelöst.
TIPP 2: Unnötige Objekt- / Grundelement-Erstellung und Methodenaufrufe erhöhen die Laufzeit.
Ich nehme an, dass "getLength" nirgendwo sonst aufgerufen wird, also ist es zwar schön, eine separate Funktion zu haben, aber vom Standpunkt der Optimierung aus ist es eine unnötige Methodenaufruf und Erstellung des Objekts "len". Wir können diesen Code dort einsetzen, wo wir ihn verwenden.
%Vor%Beachten Sie auch, dass ich die untere While-Schleife geändert habe, um auch "a & lt; = b" einzuschließen. Ich habe das nicht getestet und bin mir nicht sicher, ob die Per-Iteration-Penalty die Tatsache übertrifft, dass Sie keine Iterationen verschwenden. Ich bin mir sicher, dass es einen Weg gibt, die Division mit cleverer Mathematik loszuwerden, aber ich kann jetzt nicht daran denken.
Ähm, ich verstehe die Frage wahrscheinlich völlig falsch, aber .....
%Vor%Es sei denn, Sie möchten wissen, ob eine bestimmte Zahlenfolge innerhalb einer anderen Zahlenfolge liegt.
In diesem Fall ist die Umwandlung in eine Zeichenfolge schneller als die Berechnung, um es herauszufinden.
Die einzige Optimierung, die ich mir vorstellen kann, besteht darin, die Umwandlung in eine eigene Zeichenfolge durchzuführen und die Ziffern (rechts nach links) zu vergleichen, während Sie die Konvertierung durchführen. Konvertieren Sie zuerst alle Ziffern von b und konvertieren Sie dann von rechts auf a, bis Sie eine Übereinstimmung an der ersten Ziffer von b finden (von rechts). Vergleichen Sie, bis alle Übereinstimmungen von b übereinstimmen oder Sie einen Konflikt gefunden haben. Wenn Sie eine Nichtübereinstimmung treffen, gehen Sie zurück zu dem Punkt, an dem Sie mit der ersten Ziffer von b beginnen, und fahren Sie mit a fort und beginnen Sie erneut.
IndexOf muss grundsätzlich den gleichen Rückverfolgungsalgorithmus durchführen, außer von links. Abhängig von den tatsächlichen Zahlen kann dies schneller sein. Ich denke, wenn die Zahlen zufällig sind, sollte es sein, da es viele Male geben sollte, wenn es nicht alle von a konvertieren muss.
Sieht so aus, als ob Ihre Funktion eigentlich ziemlich gut ist, aber eine kleine Verbesserung:
%Vor%Nur weil das a kleiner als b ist, schaut es nicht würdig aus, nicht wahr? Viel Glück und Post wenn Sie die Lösung finden!
Dies ist entlang Kibbees Linie, aber ich wurde ein wenig davon fasziniert, bevor er gepostet und ausgearbeitet hat:
%Vor%Da 300 Zeichen viel zu wenig sind, um ein Argument zu erstellen, bearbeite ich diesen Hauptbeitrag, um auf Pyrolistic zu antworten.
Im Gegensatz zum OP war ich nicht so überrascht, dass ein nativer kompilierter indexOf schneller war als Java-Code mit Primitiven. Mein Ziel war es also nicht, etwas zu finden, von dem ich dachte, dass es schneller war als eine native Methode, die zig Mal im Java-Code genannt wird.
Das OP machte klar, dass dies kein Produktionsproblem war und mehr im Sinne einer faulen Neugier, so löst meine Antwort diese Neugier. Meine Vermutung war, dass Geschwindigkeit ein Problem war, als er versuchte, es in der Produktion zu lösen, aber als eine untätige Neugier, "Diese Methode wird Millionen und Abermillionen Male genannt werden", trifft nicht mehr zu. Da er einem Poster erklären musste, wird es nicht mehr als Produktionscode verfolgt, daher spielt die Komplexität keine Rolle mehr.
Außerdem bietet es die einzige Implementierung auf der Seite, die es schafft, die "123" in "551241238" zu finden, so dass, sofern die Korrektheit nicht von äußerer Bedeutung ist, dies gewährleistet ist. Auch der Lösungsraum von "einem Algorithmus, der das Problem mathematisch mit Java-Primitiven löst, aber optimierten nativen Code übertrifft" könnte auch EMPTY sein.
Außerdem ist aus Ihrem Kommentar nicht klar, ob Sie Äpfel mit Äpfeln verglichen haben oder nicht. Die funktionale Spezifikation ist f (int, int) - & gt; Boolean, nicht f (String, String) - & gt; Boolean (das ist die Domäne von findMatch ). Also, es sei denn, du hast so etwas getestet (was meinen noch immer schlagen könnte, und ich wäre nicht sehr überrascht). Der zusätzliche Aufwand könnte etwas von diesem übermäßigen 40% aufzehren.
Es macht die gleichen grundlegenden Schritte. log 10 <(a) encoding + log 10 <(b) encoding + tatsächlich findet die Übereinstimmung, die auch O ( n ) wo
Das war ursprünglich ein Problem, mit dem ich bei der Arbeit zu tun hatte, aber jetzt versuche ich es nur aus Neugierde zu lösen.
Ich möchte herausfinden, ob int 'a' das int 'b' so effizient wie möglich enthält. Ich habe etwas Code geschrieben, aber es scheint egal, was ich schreibe, es in eine Zeichenkette zu zerlegen und dann indexOf doppelt so schnell zu benutzen wie mathematisch.
Speicher ist kein Problem (im Rahmen des Zumutbaren), einfach die Verarbeitungsgeschwindigkeit.
Dies ist der Code, den ich geschrieben habe, um es mathematisch zu machen:
%Vor%Hier ist die String-Methode, die ich verwende, die die obige mathematische Methode zu übertrumpfen scheint:
%Vor%Obwohl dies für meine Arbeit nicht wirklich erforderlich ist, habe ich mich nur gefragt, ob irgendjemand irgendeinen Weg finden könnte, meine mathematische Vorgehensweise oder einen völlig neuen Ansatz weiter zu optimieren. Wieder ist die Erinnerung kein Problem, ich schieße nur auf schiere Geschwindigkeit.
Ich bin wirklich daran interessiert, etwas zu sehen oder zu hören, was irgendjemand zu bieten hat.
BEARBEITEN: Wenn ich sage contains ich meine, kann überall sein, also zum Beispiel findMatch (1234, 23) == true
BEARBEITEN: Für jeden, der sagt, dass dieser Mist nicht lesbar und unnötig ist: Sie verpassen den Punkt. Es ging darum, ein interessantes Problem zu lösen, und keine Antwort für den Produktionscode zu finden.
Ähm, ich verstehe die Frage wahrscheinlich völlig falsch, aber .....
%Vor%Es sei denn, Sie möchten wissen, ob eine bestimmte Zahlenfolge innerhalb einer anderen Zahlenfolge liegt.
In diesem Fall ist die Umwandlung in eine Zeichenfolge schneller als die Berechnung, um es herauszufinden.
Das ist ein interessantes Problem. Viele der Funktionen von String.class sind eigentlich nativ, was String zu einem schwierigen Vorschlag macht. Aber hier sind ein paar Helfer:
TIPP 1: Verschiedene einfache ganzzahlige Operationen haben unterschiedliche Geschwindigkeiten.
Durch schnelle Berechnungen in Beispielprogrammen zeigte sich:
%Vor%Sie wollen also so wenig Aufteilung wie möglich für Multiplikation oder Modulo verwenden. Nicht gezeigt sind Subtraktions-, Additions- und Vergleichsoperatoren, weil sie alle aus dem Wasser blasen. Außerdem ermöglicht die Verwendung von "final" so viel wie möglich, dass die JVM bestimmte Optimierungen durchführt. Beschleunigen Sie Ihre "getLength" -Funktion:
%Vor%Das ergibt eine ca. 7-fache Verbesserung der Funktion. Sie erhalten eine indexOutOfBounds-Ausnahme, wenn b & gt; Ihr Maximum in Exponenten. Um das zu lösen, können Sie haben:
%Vor%Das ist etwas langsamer und gibt Ihnen eine falsche Länge, wenn b zu groß ist, aber es wird keine Ausnahme ausgelöst.
TIPP 2: Unnötige Objekt- / Grundelement-Erstellung und Methodenaufrufe erhöhen die Laufzeit.
Ich nehme an, dass "getLength" nirgendwo sonst aufgerufen wird, also ist es zwar schön, eine separate Funktion zu haben, aber vom Standpunkt der Optimierung aus ist es eine unnötige Methodenaufruf und Erstellung des Objekts "len". Wir können diesen Code dort einsetzen, wo wir ihn verwenden.
%Vor%Beachten Sie auch, dass ich die untere While-Schleife geändert habe, um auch "a & lt; = b" einzuschließen. Ich habe das nicht getestet und bin mir nicht sicher, ob die Per-Iteration-Penalty die Tatsache übertrifft, dass Sie keine Iterationen verschwenden. Ich bin mir sicher, dass es einen Weg gibt, die Division mit cleverer Mathematik loszuwerden, aber ich kann jetzt nicht daran denken.
Kann ich fragen, wo Sie diese Funktion in Ihrem Code verwenden? Vielleicht gibt es einen anderen Weg, um das Problem zu lösen, das es gerade löst, was viel schneller wäre. Das könnte so sein, als ob mein Freund mich bat, seine Gitarre komplett neu zu stimmen, und ich tat es, bevor ich bemerkte, dass ich die untere Saite um einen ganzen Schritt hätte senken und ein äquivalentes Ergebnis erzielen können.
Das beantwortet in keinster Weise Ihre Frage, aber es ist trotzdem ein Rat: -)
Der Methodenname ContainerBuilder.number(int) ist nicht sehr aussagekräftig. In diesem Fall hätte ich eine statische Methode ContainerBuilder , die eine contains zurückgegeben hat, für die die Methode %code% vorhanden ist. Auf diese Weise wird dein Code zu:
Gibt Tipps für die Zukunft!
Oh ja, ich wollte auch sagen, Sie sollten definieren, was Sie mit "contains" meinen
Gibt es eine Möglichkeit, dies in Binärform zu berechnen? Offensichtlich bedeutet der Binärwert einer Ganzzahl, die die binäre Ganzzahl eines anderen Zeichens enthält, nicht, dass die Dezikative dasselbe tut. Gibt es jedoch eine Art von Binär-Trick, das verwendet werden könnte? Vielleicht konvertieren Sie eine Zahl wie 12345 in 0001 0010 0011 0100 0101, und dann ein bisschen verschieben, um herauszufinden, ob 23 (0010 0011) darin enthalten ist. Da Ihr Zeichensatz nur aus 10 Zeichen besteht, können Sie die Rechenzeit reduzieren, indem Sie 2 Zeichen in einem Byte speichern.
BEARBEITEN
Auf diese Idee etwas erweitert. Wenn Sie 2 ganze Zahlen, A und B haben und wissen wollen, ob A B enthält, überprüfen Sie zuerst 2 Dinge. Wenn A kleiner als B ist, kann A nicht B enthalten. Wenn A = B, dann enthält A B. An dieser Stelle können Sie sie in Strings * umwandeln. Wenn A die gleiche Anzahl von Zeichennummern wie B enthält, enthält A nicht B, es sei denn, sie sind gleich, aber wir wären nicht hier, wenn sie gleich sind. Wenn also beide Strings die gleiche Länge haben, enthält a kein b . An diesem Punkt wird die Länge von A länger als B sein. So können Sie nun die Strings in ihre gepackten Binärwerte konvertieren, wie ich im ersten Teil dieses Posts notiert habe. Speichern Sie diese Werte in einem Array mit Ganzzahlen. Nun machst du ein bitweises UND der Integer-Werte in deinem Array, und wenn das Ergebnis A ist, dann enthält A B. Jetzt verschiebst du das Array der ganzen Zahlen für B nach links 4 Bits und führst den Vergleich erneut durch. Tun Sie dies, bis Sie beginnen, Bits von der linken Seite von B herauszupicken.
* Das * im vorherigen Absatz bedeutet, dass Sie diesen Schritt möglicherweise überspringen können. Es kann einen Weg geben, dies zu tun, ohne Strings zu verwenden. Es könnte einen raffinierten Binärtrick geben, den Sie tun können, um die gepackte Binärdarstellung zu erhalten, die ich im ersten Absatz besprochen habe. Es sollte einen binären Trick geben, den Sie verwenden können, oder eine schnelle Mathematik, die eine Ganzzahl in den zuvor besprochenen Dezimalwert umwandelt.
Es sollte schnellere Zeichenfolge sein, weil Ihr Problem Text, nicht mathematisch ist. Beachten Sie, dass die "contains" -Beziehung nichts über die Zahlen sagt, sondern nur etwas über ihre dezimalen Darstellungen.
Beachten Sie auch, dass die Funktion, die Sie schreiben möchten, nicht lesbar ist - ein anderer Entwickler wird nie verstehen, was Sie tun. (Sehen Sie, welche Schwierigkeiten Sie damit hatten.) Die String-Version dagegen ist vollkommen klar.
Gibt es eine Möglichkeit, dies in Binärform zu berechnen? Offensichtlich bedeutet der Binärwert einer Ganzzahl, die die binäre Ganzzahl eines anderen Zeichens enthält, nicht, dass die Dezikative dasselbe tut. Gibt es jedoch eine Art von Binär-Trick, das verwendet werden könnte? Vielleicht konvertieren Sie eine Zahl wie 12345 in 0001 0010 0011 0100 0101, und dann ein bisschen verschieben, um herauszufinden, ob 23 (0010 0011) darin enthalten ist. Da Ihr Zeichensatz nur aus 10 Zeichen besteht, können Sie die Rechenzeit reduzieren, indem Sie 2 Zeichen in einem Byte speichern.
BEARBEITEN
Auf diese Idee etwas erweitert. Wenn Sie 2 ganze Zahlen, A und B haben und wissen wollen, ob A B enthält, überprüfen Sie zuerst 2 Dinge. Wenn A kleiner als B ist, kann A nicht B enthalten. Wenn A = B, dann enthält A B. An dieser Stelle können Sie sie in Strings * umwandeln. Wenn A die gleiche Anzahl von Zeichennummern wie B enthält, enthält A nicht B, es sei denn, sie sind gleich, aber wir wären nicht hier, wenn sie gleich sind. Wenn also beide Strings die gleiche Länge haben, enthält a kein b . An diesem Punkt wird die Länge von A länger als B sein. So können Sie nun die Strings in ihre gepackten Binärwerte konvertieren, wie ich im ersten Teil dieses Posts notiert habe. Speichern Sie diese Werte in einem Array mit Ganzzahlen. Nun machst du ein bitweises UND der Integer-Werte in deinem Array, und wenn das Ergebnis A ist, dann enthält A B. Jetzt verschiebst du das Array der ganzen Zahlen für B nach links 4 Bits und führst den Vergleich erneut durch. Tun Sie dies, bis Sie beginnen, Bits von der linken Seite von B herauszupicken.
* Das * im vorherigen Absatz bedeutet, dass Sie diesen Schritt möglicherweise überspringen können. Es kann einen Weg geben, dies zu tun, ohne Strings zu verwenden. Es könnte einen raffinierten Binärtrick geben, den Sie tun können, um die gepackte Binärdarstellung zu erhalten, die ich im ersten Absatz besprochen habe. Es sollte einen binären Trick geben, den Sie verwenden können, oder eine schnelle Mathematik, die eine Ganzzahl in den zuvor besprochenen Dezimalwert umwandelt.
Kann ich fragen, wo Sie diese Funktion in Ihrem Code verwenden? Vielleicht gibt es einen anderen Weg, um das Problem zu lösen, das es gerade löst, was viel schneller wäre. Das könnte so sein, als ob mein Freund mich bat, seine Gitarre komplett neu zu stimmen, und ich tat es, bevor ich bemerkte, dass ich die untere Saite um einen ganzen Schritt hätte senken und ein äquivalentes Ergebnis erzielen können.
Tags und Links java performance integer substring contains