文字列比較なしで、数値部分文字列を数学的に見つける
https://stackoverflow.com/questions/231917
-
04-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
これはもともと私が職場で遭遇した問題でしたが、現在は自分の好奇心のために解決しようとしているものです。
int 'a'にint 'b'が可能な限り最も効率的な方法で含まれているかどうかを調べたい。いくつかのコードを書きましたが、何を書いても文字列に解析し、indexOfを使用することは数学的に行うよりも2倍高速です。
メモリは（理由の範囲内で）問題ではなく、単なる処理速度です。
これは数学的に行うために書いたコードです：
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;
}
私が使用している文字列メソッドは次のとおりです。これは上記の数学的なメソッドよりも優れているようです。
private static boolean findStringMatch(int a, int b) {
return String.valueOf(a).indexOf(String.valueOf(b)) != -1;
}
だからこれは私の仕事を完了するために本当に必要ではありませんが、数学的にそれを行う方法をさらに最適化する方法、または全く新しいアプローチを誰かが考えられるかどうか疑問に思っていました。繰り返しになりますが、メモリは問題ありません。ただのスピードで撮影しています。
私は誰もがこれに関して提供しなければならないものを見たり聞いたりすることに本当に興味があります。
編集：「含む」と言うとき、どこでもかまいません。たとえば、findMatch（1234、23）== true
編集：このがらくたは判読できず、不必要だと言っている皆のために：あなたは要点を見逃しています。ポイントは、実稼働コードで使用する答えを考え出すのではなく、興味深い問題を探し出すことでした。
解決
これはKibbeeの方針に沿っていますが、彼がこれを投稿して解決する前に、少し興味をそそられました。
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 );
300文字は議論をするには少なすぎるので、Pyrolisticalに返信するためにこのメインの投稿を編集しています。
OPとは異なり、ネイティブにコンパイルされたindexOfがプリミティブを持つJavaコードよりも高速であることは驚くことではありませんでした。したがって、私の目標は、Javaコード全体で数十億回と呼ばれるネイティブメソッドよりも高速だと思ったものを見つけることではありませんでした。
OPは、これが本番の問題ではなく、アイドルの好奇心に沿っていることを明らかにしたので、私の答えはその好奇心を解決します。私が推測したのは、彼が生産でそれを解決しようとしていたとき、速度が問題だったということでしたが、アイドルの好奇心として、<！> quot;この方法は何百万回と呼ばれます<！> quot;もはや適用されません。彼は1人のポスターに説明しなければならなかったので、それは生産コードとしてもはや追求されないので、複雑さはもはや重要ではありません。
Plusは、<！> quot; 123 <！> quotを見つけることができるページ上の唯一の実装を提供します。 <！> quot; 551241238 <！> quot;であるため、正確性が外部の懸念事項でない限り、それを提供します。また、Javaプリミティブを使用して数学的に問題を解決するが、最適化されたネイティブコードに勝るアルゴリズムである<！> quot;のソリューションスペース。 空の場合があります。
さらに、リンゴとリンゴを比較したかどうかは、コメントから明らかではありません。機能仕様はf（int、int）-<！> gt;です。ブール値、f（String、String）-<！> gt;ブール（indexOfのドメインの一種）。したがって、このようなものをテストしない限り（これはまだ私のものを打ち負かす可能性があり、私はひどく驚かないでしょう。）、追加のオーバーヘッドは might 余分な40％を使い果たします。
boolean findMatch( int a, int b ) {
String s_a = "" + a;
String s_b = "" + b;
return s_a.indexOf( s_b ) > -1;
}
同じ基本手順を実行します。 log 10 （a）encoding + log 10 （b）encoding +実際に一致するものを見つけるO（ n ）ここで< em> n は最大の対数です。
他のヒント
また、書きたい関数が読めないことに注意してください-別の開発者はあなたが何をしているのか理解できません。 （ここでどのような問題が発生したかをご覧ください。）一方、文字列バージョンは完全に明確です。
私が考えることができる唯一の最適化は、独自に文字列への変換を行い、変換を行うときに数字を比較することです（右から左）。最初にbのすべての数字を変換し、次にbの最初の数字（右から）で一致が見つかるまでaの右から変換します。 bのすべてが一致するか、不一致が見つかるまで比較します。不一致が見つかった場合は、bの最初の数字と一致するところまで戻り、aに進んで最初からやり直してください。
IndexOfは、左を除いて、基本的に同じ逆追跡アルゴリズムを実行する必要があります。実際の数値に応じて、これはより高速になる場合があります。数字がランダムであれば、すべてを変換する必要がない場合が何度もあるはずだからです。
あなたの関数は実際にはかなりうまくいっているように見えますが、少し改善されています：
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;
}
ただ、aがbよりも小さいのにふさわしくないので、見続けるのではないでしょうか？ 解決策を見つけたら幸運と投稿！
これは興味深い問題です。 String.classの関数の多くは実際にはネイティブであるため、Stringを破るのは難しい提案です。しかし、ここにヘルパーがいます：
ヒント1：異なる単純な整数演算には異なる速度があります。
サンプルプログラムでの簡単な計算により、次のことが示されました。
% ~ T
* ~ 4T
/ ~ 7T
したがって、乗算またはモジュロを優先して、できるだけ少ない除算を使用する必要があります。減算、加算、および比較演算子は、これらのすべてを水中から吹き飛ばします。また、<！> quot; final <！> quot;を使用します。可能な限り、JVMが特定の最適化を実行できるようにします。スピードアップ<！> quot; getLength <！> quot;関数：
private static int getLength(final int b) {
int len = 0;
while (b > exponents[len]) {
len++;
}
return len + 1
}
これにより、機能が約7倍向上します。 b <！> gt;の場合、indexOutOfBounds例外が発生します。指数の最大値。これを解決するために、次のことができます。
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;
}
bが大きすぎると少し遅くなり、不正確な長さになりますが、例外はスローされません。
ヒント2：不要なオブジェクト/プリミティブの作成とメソッド呼び出しは、ランタイムに追加されます。
<！> quot; getLength <！> quot;と推測しています。他の場所では呼び出されません。そのため、最適化の観点からは、不要なメソッド呼び出しとオブジェクト<！> quot; len <！> quot;の作成という別の関数を用意するのが良いかもしれません。そのコードを使用する場所に配置できます。
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;
}
また、<！> quot; a <！> lt; = b <！> quot;も含めるように、whileループを変更しました。私はそれをテストしていませんし、繰り返しごとのペナルティが繰り返しを無駄にしないという事実に勝るかどうかはわかりません。賢い数学を使用して除算を取り除く方法があると確信していますが、今は考えられません。
うーん、たぶん質問を完全に誤解しているかもしれませんが、.....
// Check if A is inside B lol
bool Contains (int a, int b)
{
return (a <= b);
}
特定の数字列が別の数字列内にあるかどうかを知りたい場合を除きます。
その場合、それを文字列に変換することは、それを計算するために数学を行うよりも速くなります。
これはあなたの質問には一切答えませんが、とにかくアドバイスです：-）
メソッド名findMatchはあまり説明的ではありません。この場合、静的メソッドContainerBuilder.number(int)があり、ContainerBuilderが返されます。このメソッドにはcontainsメソッドがあります。このようにして、コードは次のようになります。
boolean b = number(12345).contains(234);
長期的にはいくつかのアドバイスがあります！
ああ、私も言いたい、 <！> quot; contains <！> quot;
の意味を定義する必要があるこれをバイナリで計算する方法はありますか？明らかに、別の文字のバイナリ整数を含む整数のバイナリ値は、decicalが同じことを意味するわけではありません。ただし、使用できるバイナリトリックはありますか？ 12345のような数値を0001 0010 0011 0100 0101に変換し、そこに23（0010 0011）が含まれているかどうかを判断するためにビットシフトを実行します。文字セットは10文字しかないため、2バイトの値を1バイトに格納することで計算時間を短縮できます。
編集
このアイデアを少し拡張します。 2つの整数AとBがあり、AにBが含まれているかどうかを知りたい場合は、最初に2つのことを確認します。 AがBより小さい場合、AにBを含めることはできません。A= Bの場合、AにはBが含まれます。この時点で、文字列に変換できます*。 AにBと同じ数の文字番号が含まれている場合、等しい場合を除き、AにはBは含まれませんが、等しい場合はここにいません。したがって、両方の文字列が同じ長さの場合、aにはbは含まれません。 。この時点で、Aの長さはBより長くなります。したがって、この投稿の最初の部分で述べたように、文字列をパックされたバイナリ値に変換できます。これらの値を整数の配列に格納します。ここで、配列の整数値のビット単位のANDを実行し、結果がAの場合、AにはBが含まれます。次に、Bの整数の配列を左4ビットにシフトし、再度比較を行います。 Bの左からビットをポップし始めるまでこれを行います。
*前の段落の*は、この手順をスキップできることを意味します。文字列をまったく使用せずにこれを行う方法があるかもしれません。最初の段落で説明したパックされたバイナリ表現を取得するためにできる、ちょっとしたバイナリトリックがあるかもしれません。使用できるバイナリトリック、または先ほど説明した整数を10進値に変換する簡単な数学が必要です。
この関数をコードのどこで使用しているのか尋ねることはできますか？おそらく現在解決中の問題を解決する別の方法がありますが、これははるかに高速です。これは、友人がギターを完全に再調整するように頼んだときのようなもので、ボトムストリングを1段下げて同等の結果を得たと気づく前にそれをしました。
