Die Suche nach numerischen Teil mathematisch, ohne String-Vergleich
https://stackoverflow.com/questions/231917
-
04-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Dies war ursprünglich ein Problem, das ich in bei der Arbeit lief, aber es ist jetzt etwas, was ich nur versucht, mich für meine eigene Neugier zu lösen.
Ich möchte herausfinden, ob int ‚a‘ den int ‚b‘ enthält auf die effizienteste Art und Weise möglich. Ich schrieb einige Code, aber es scheint, egal, was ich schreibe, es in einen String-Parsing und dann indexOf verwendet, ist doppelt so schnell wie es mathematisch zu tun.
Der Speicher ist kein Problem (innerhalb Grund), nur reine Verarbeitungsgeschwindigkeit.
Dies ist der Code, den ich geschrieben habe, es mathematisch zu tun:
private static int[] exponents = {10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000 };
private static boolean findMatch(int a, int b) {
if (b > a) return false;
if (a == b) return true;
int needleLength = getLength(b);
int exponent = exponents[needleLength];
int subNum;
while (a >= 1) {
subNum = a % exponent;
if (subNum == b)
return true;
a /= 10;
}
return false;
}
private static int getLength(int b) {
int len = 0;
while (b >= 1) {
len++;
b /= 10;
}
return len;
}
Hier ist die String-Methode Ich verwende, die die mathematische Methode zu übertrumpfen scheint über:
private static boolean findStringMatch(int a, int b) {
return String.valueOf(a).indexOf(String.valueOf(b)) != -1;
}
So obwohl dies nicht wirklich notwendig für mich, meine Arbeit zu vollenden, wundere ich ich mich, ob jemand von irgendeiner Weise denken konnte weiter meinen Weg zu optimieren sie mathematisch zu tun, oder einen völlig neuen Ansatz zusammen. Wieder Speicher ist kein Problem, ich drehe nur für reine Geschwindigkeit.
Ich bin wirklich daran interessiert, etwas niemand zu sehen oder hören auf diese zu bieten hat.
EDIT: Wenn ich sage, enthält ich überall sein kann bedeuten, so zum Beispiel findMatch (1234, 23) == true
EDIT: Für alle sagen, dass dieser Mist ist nicht lesbar und unnötig: Sie den Punkt sind vermisst. Der Punkt war, zu erhalten auf ein interessantes Problem Geek aus, nicht mit einer Antwort kommen in Produktionscode verwendet werden.
Lösung
Dies ist entlang Kibbee Linie, aber ich habe ein wenig fasziniert von dieser, bevor er veröffentlicht und arbeitete this out:
long mask ( long n ) {
long m = n % 10;
long n_d = n;
long div = 10;
int shl = 0;
while ( n_d >= 10 ) {
n_d /= 10;
long t = n_d % 10;
m |= ( t << ( shl += 4 ));
}
return m;
}
boolean findMatch( int a, int b ) {
if ( b < a ) return false;
if ( a == b ) return true;
long m_a = mask( a ); // set up mask O(n)
long m_b = mask( b ); // set up mask O(m)
while ( m_a < m_b ) {
if (( m_a & m_b ) == m_a ) return true;
m_a <<= 4; // shift - fast!
if ( m_a == m_b ) return true;
} // O(p)
return false;
}
void testContains( int a, int b ) {
print( "findMatch( " + a + ", " + b + " )=" + findMatch( a, b ));
}
testContains( 12, 120 );
testContains( 12, 125 );
testContains( 123, 551241238 );
testContains( 131, 1214124 );
testContains( 131, 1314124 );
Da 300 Zeichen ist viel zu wenig in ein Argument zu machen, ich bin der Bearbeitung dieses Haupt Beitrag Pyrolistical zu reagieren.
Im Gegensatz zum OP war ich nicht so überrascht, dass eine native kompilierte indexOf war schneller als Java-Code mit Primitiven. So war mein Ziel, etwas, das ich nicht gedacht, zu finden war schneller als eine native Methode zig Millionen Mal in aller Java-Code genannt.
Die OP machte deutlich, dass dies nicht ein Produktionsproblem und mehr entlang der Linien eines Leerlauf Neugier, so meine Antwort, dass Neugier löst. Meine Vermutung war, dass Geschwindigkeit ein Problem war, als er versuchte, es in der Produktion zu lösen, sondern als reine Neugier: „Diese Methode Millionen von Zeiten wird als“ nicht mehr gilt. Als er auf ein Plakat zu erklären hatte, ist es nicht mehr als Produktionscode verfolgt, so dass die Komplexität keine Rolle mehr spielt.
Außerdem ist es bietet die einzige Implementierung auf der Seite, die die „123“ in „551241238“ zu finden verwaltet, so dass, wenn eine Fremd Richtigkeit Sorge ist, ist es, dass zur Verfügung stellt. Auch der Lösungsraum „ein Algorithmus, der das Problem mathematisch mit Hilfe von Java-Primitiven aber Beats optimierten nativen Code löst“ könnte sein, LEER .
Außerdem ist es nicht klar, aus Ihrem Kommentar, ob Sie Äpfel mit Äpfeln verglichen. Die funktionelle spec ist f (int, int) -> boolean, nicht f (String, String) -> boolean (die Art der Domäne von indexOf ist). Also, wenn Sie so etwas wie dies getestet (die Mine noch schlagen konnte, und ich würde nicht furchtbar überrascht sein.), Um den zusätzlichen Aufwand Macht isst etwas von diesem Überschuss 40%.
boolean findMatch( int a, int b ) {
String s_a = "" + a;
String s_b = "" + b;
return s_a.indexOf( s_b ) > -1;
}
Es tut die gleichen grundlegenden Schritte. log 10 (a) Codierung + log 10 (b) Codierung + tatsächlich das Spiel zu finden, die auch O ( n ) ist, wo < em> n ist der größte Logarithmus.
Andere Tipps
Es sollte schnelle String Art und Weise sein, weil Ihr Problem Text ist, nicht mathematisch. Beachten Sie, dass die Ihre „enthält“ Beziehung sagt nichts über die Zahlen, es sagt nur etwas über ihre dezimal Darstellungen.
Beachten Sie auch, dass die Funktion, die Sie schreiben wollen, werden nicht lesbar sein - ein anderer Entwickler werden nie verstehen, was Sie tun. (Sehen Sie, was Mühe, die Sie mit, dass hatten hier.) Die String-Version, auf der anderen Seite, ist völlig klar.
Die einzige Optimierung, die ich denken kann, ist die Umstellung auf Zeichenfolge auf eigene Faust zu tun und Ziffern vergleichen (von rechts nach links), wie Sie die Konvertierung zu tun. Zunächst alle Ziffern von b konvertieren, dann von rechts einem konvertieren, bis Sie ein Spiel auf der ersten Ziffer b (von rechts) zu finden. Vergleichen Sie bis alle b Streichhölzer oder Sie treffen eine Nichtübereinstimmung. Wenn Sie eine fehlende Übereinstimmung getroffen, bis zu dem Punkt ansetzen, wo Sie passen zum ersten Ziffer b beginnen, vorab in einem und von vorn beginnen.
IndexOf haben im Grunde den gleichen zurück Tracking-Algorithmus zu tun, außer von der linken Seite. In Abhängigkeit von den tatsächlichen Zahlen kann dies schneller sein. Ich denke, wenn die Zahlen zufällig sind, sollte es da sein sollte, viele Male, wenn es nicht alle ein konvertieren muss.
Sieht aus wie Ihre Funktion ist eigentlich ziemlich gut, aber eine kleine Verbesserung:
private static boolean findMatch(int a, int b) {
if (b > a) return false;
if (a == b) return true;
int needleLength = getLength(b);
int exponent = exponents[needleLength];
int subNum;
while (a > b) {
subNum = a % exponent;
if (subNum == b)
return true;
a /= 10;
}
return false;
}
Nur weil einmal, dass ein kleiner ist als b, ist nicht würdig hält suchen, es ist nicht? Viel Glück und Post, wenn Sie finden die Lösung!
Dies ist ein interessantes Problem. Viele String.class Funktionen sind eigentlich einheimische Herstellung schlagen String eine schwierige Angelegenheit. Aber hier einige Helfer:
TIP. 1: Verschiedene einfache Integer-Operationen haben unterschiedliche Geschwindigkeiten
Durch die schnelle Berechnungen in Beispielprogramme zeigten:
% ~ T
* ~ 4T
/ ~ 7T
So Sie so wenig wie möglich Abteilung für Multiplikation oder Modulo verwenden möchten. Nicht gezeigt sind Subtraktion, Addition und Vergleichsoperatoren, weil sie alle diese aus dem Wasser zu blasen. Auch „final“ so viel wie möglich mit ermöglicht die JVM bestimmte Optimierungen zu tun. Beschleunigen Sie "getLength" Funktion:
private static int getLength(final int b) {
int len = 0;
while (b > exponents[len]) {
len++;
}
return len + 1
}
Das gibt über eine 7x Verbesserung der Funktion. Sie erhalten eine IndexOutOfBounds Ausnahme, wenn b> Ihren max in Exponenten. Zu lösen, können Sie haben:
private static int getLength(final int b) {
int len = 0;
final int maxLen = exponents.length;
while (len < maxLen && b > exponents[len]) {
len++;
}
return len + 1;
}
Das ist etwas langsamer und gibt Ihnen eine falsche Länge, wenn b zu groß ist, aber es ist nicht eine Ausnahme aus.
TIP. 2: Unnötige Objekt / primitive Erstellung und Methodenaufrufe hinzufügen, Zeit laufen
Ich vermute, dass „getLength“ wird nirgendwo anders genannt, also, während es schön sein könnte, eine eigene Funktion zu haben, von einer Optimierung Standpunkt seines unnötigen Methodenaufruf und Erstellung des Objekt „len“. Wir können diesen Code in Ordnung bringen, wo wir sie verwenden.
private static boolean findMatch(int a, final int b) {
if (b > a) return false;
if (a == b) return true;
int needleLength = 0;
while (b > exponents[len]) {
needleLength ++;
}
needleLength++;
final int exponent = exponents[needleLength];
int subNum;
while (a >= 1 && a <= b) {
subNum = a % exponent;
if (subNum == b)
return true;
a /= 10;
}
return false;
}
Beachten Sie auch, mich unten geändert while-Schleife umfasst auch „a <= b“. Ich habe nicht, dass und nicht sicher, ob die pro-Iteration Strafe schlägt die Tatsache getestet, dass Sie keine Wiederholungen verschwenden. Ich bin sicher, es gibt einen Weg der Division mit cleverer Mathematik, um loszuwerden, aber ich kann es jetzt nicht denken.
Ähm, ich bin total wohl die Frage Missverständnis, aber .....
// Check if A is inside B lol
bool Contains (int a, int b)
{
return (a <= b);
}
Es sei denn, Sie wollen wissen, ob eine bestimmte Folge von Zahlen in einer anderen Folge von Zahlen ist.
In diesem Fall ist es in einen String konvertiert wird schneller sein als die Mathematik zu tun, um es herauszufinden.
Dieses in keiner Weise beantwortet Ihre Frage, was auch immer, aber es ist auf jeden Fall Rat: -)
Der Name der Methode findMatch ist nicht sehr aussagekräftig. In diesem Fall würde ich eine statische Methode ContainerBuilder.number(int) habe, die ein ContainerBuilder zurückgegeben, die das Verfahren contains auf sich. Auf diese Weise Ihren Code wird:
boolean b = number(12345).contains(234);
Ragt ein paar Ratschläge für lange Sicht!
Oh ja, ich meinte auch sagen, sollten Sie definieren, was man unter "enthält"
Gibt es eine Möglichkeit, dies in binär zu berechnen? Offensichtlich ist der binäre Wert einer ganzen Zahl die binäre Zahl von einem anderen Zeichen enthält, bedeutet nicht, dass die decical das gleiche tut. Allerdings ist es eine Art von binärer trickary das verwendet werden könnte? Vielleicht eine numer wie 12345-0001 0010 0011 0100 0101, konvertiert und dann einige etwas tun Verschiebung, wenn 23, um herauszufinden, (0010 0011) in dort enthalten ist. Da Ihr Zeichensatz nur 10 Zeichen ist, können Sie die Rechenzeit von Speicher 2 Zeichen Werte in einem einzigen Byte abgeholzt.
EDIT
Aufbauend auf dieser Idee ein bisschen. wenn Sie 2 ganze Zahlen haben, A und B, und wollen wissen, ob A B enthält, überprüfen Sie zwei Dinge zuerst. wenn A kleiner als B ist, dann enthält A nicht B. Wenn A = B dann A enthält B. An dieser Stelle können Sie sie in Strings konvertieren *. Wenn A die gleiche Anzahl von Zeichen Zahlen wie B enthält, dann ist A nicht B enthalten, es sei denn, sie gleich sind, aber wir würden nicht hier sein, wenn sie gleich sind, also wenn beide Strings gleich lang sind, ein nicht enthält b . An diesem Punkt wird die Länge von A länger als B. So, jetzt können Sie die Saiten ihre gepackten binären Werte umwandeln, wie ich im ersten Teil dieses Beitrags zur Kenntnis genommen. Bewahren Sie diese Werte in einem Array von ganzen Zahlen. Jetzt haben Sie eine bitweise UND-Verknüpfung der Integer-Werte im Array, und wenn das Ergebnis A ist, dann A enthält B. Nun Sie das Array von ganzen Zahlen für B verschieben, nach links 4 Bits, und wieder die conparison tun. bis Sie diese Startbits aus links von B. knallen
* Das * im vorigen Absatz bedeutet, dass Sie der Lage sein kann, diesen Schritt zu überspringen. Es kann ein Weg, dies zu tun, ohne Saiten überhaupt verwendet wird. Es könnte einige Phantasie binäre Trick sein, das Sie tun können, die gepackte binäre Darstellung bekommen ich im ersten Absatz diskutiert. Es sollte eine gewisse binäre Trick sein kann, oder einige schnelle Mathematik verwenden, die eine ganze Zahl auf den Dezimalwert umwandeln will ich vor diskutiert.
Kann ich fragen, wo Sie verwenden diese Funktion in Ihrem Code? Vielleicht ist es eine andere Möglichkeit, das Problem zu lösen, ist es derzeit zu lösen, die viel schneller sein würden. Dies könnte, wie wenn mein Freund mich fragte vollständig Abstimmung wieder seine Gitarre, und ich habe es vor der Realisierung mir die tiefste Saite durch einen Ganzton und bekam ein gleichwertiges Ergebnis nur konnte gesenkt werden.
