xよりも10個の最大のパワーを見つけるための最速の方法
https://stackoverflow.com/questions/4513707
-
12-10-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
特定の数よりも10個の最大の最大のパワーを見つけるための迅速な方法はありますか？
私は現時点でこのアルゴリズムを使用していますが、自分の中で何かが死ぬときはいつでも死にます。
10**( int( math.log10(x) ) ) # python
pow( 10, (int) log10(x) ) // C
簡単に実装できます log10 と pow それぞれ1つのループで私の問題に機能しますが、それでも10進数に少し魔法があるのではないかと思います。
解決
別のアルゴリズムは次のとおりです。
i = 1;
while((i * 10) < x)
i *= 10;
他のヒント
ログとパワーは高価な操作です。速くしたい場合は、おそらくテーブルのIEEEバイナリ指数を調べて、10の近似電力を取得し、マンティッサが+1で変更を強制するかどうかを確認する必要があります。これは3または4でなければなりません 整数 マシンの命令（または、かなり小さな定数を持つO（1））。
与えられた表：
int IEEE_exponent_to_power_of_ten[2048]; // needs to be 2*max(IEEE_exponent)
double next_power_of_ten[600]; // needs to be 2*log10(pow(2,1024)]
// you can compute these tables offline if needed
for (p=-1023;p>1023;p++) // bounds are rough, see actual IEEE exponent ranges
{ IEEE_exponent_to_power_of_ten[p+1024]=log10(pow(2,p)); // you might have to worry about roundoff errors here
next_power_of_ten[log10(pow(2,p))+1024]=pow(10,IEEE_exponent_to_power_of_ten[p+1024]);
}
その後、あなたの計算は次のとおりです。
power_of_ten=IEEE_exponent_to_power_of_10[IEEE_Exponent(x)+1023];
if (x>=next_power_of_ten[power_of_ten]) power_of_ten++;
answer=next_power_of_ten[power_of_ten];
最後の時計ごとに絞り出すために、これをアセンブラーとして書く必要があるかもしれません。] [このコードはテストされていません。
ただし、Pythonでこれを行うことを主張する場合、通訳者のオーバーヘッドはログ/EXP時間を圧倒する可能性があり、それは問題ではないかもしれません。
それで、あなたは速くしたいですか、それともあなたは短期間で欲しいですか？
編集12/23：OPは、彼の「X」が不可欠であることを示しています。それが64（または32）ビット整数であるという仮定の下で、私の提案はまだ機能しますが、明らかに「IEEE_Exponent」はありません。ほとんどのプロセッサには、値の左手（最も重要な）部分（最も重要な）の部分、例えば主要なゼロを示す「最初の1つを見つける」命令があります。おそらく、これは本質64（または32）から値に対して2つのパワーを差し引いています。指数= 64 -LavingZerosが与えられると、2つの指数のパワーがあり、残りのアルゴリズムのほとんどは本質的に変更されていません（読者に残された変更）。
プロセッサにFind-first-Oneの命令がない場合、おそらく最善の策は、10のパワーを決定するためのバランスの取れた識別ツリーです。 64ビットの場合、そのようなツリーは最大18の比較で指数を決定します（10^18 ~~ 2^64）。
10のパワーの配列を作成します。xよりも小さい最大の値を検索します。
Xがかなり小さい場合、線形検索は、分岐の予測が少ないため、バイナリ検索よりも優れたパフォーマンスを提供することがわかります。
私の知る限り、漸近的に最も速い方法は、繰り返しの二乗を伴います。
func LogFloor(int value, int base) as int
//iterates values of the form (value: base^(2^i), power: 2^i)
val superPowers = iterator
var p = 1
var c = base
while c <= value
yield (c, p)
c *= c
p += p
endwhile
enditerator
//binary search for the correct power
var p = 0
var c = 1
for val ci, pi in superPowers.Reverse()
if c*ci <= value
c *= ci
p += pi
endif
endfor
return p
アルゴリズムは、nの対数時間と空間を取得します。これは、nの表現サイズに線形です。 [私は楽観的に単純化したので、時間の境界はおそらく少し悪いです
素朴なタイムズの10時までのアルゴリズムは、わずか32ビットの整数を扱う場合、おそらく十分に高速であるため、私は任意に大きな整数を想定しています（オーバーフローに注意してください！）。
これは言語に依存しないことを考えると、この数値が重要な2つの力を得ることができれば、x*2^yのy（これは数の保存方法ですが、私が使用したあらゆる言語でyにアクセスする簡単な方法）
z = int(y/(ln(10)/ln(2)))
（1つのフローティングポイント除算）
10^zまたは10^（z+1）は答えですが、10^zはまだそれほど単純ではありません（修正する必要があります）。
最速の方法はo（log（log（n））^2）、whileループはo（log（log（n））を取り、再帰的なコール有限時間（o（c）が表示される可能性があると思います。一定です）、最初の再帰呼び出しは、ログ（log（sqrt（n）））の時間秒を取得します。 n））および一定、機械の制限のため。
static long findPow10(long n)
{
if (n == 0)
return 0;
long i = 10;
long prevI = 10;
int count = 1;
while (i < n)
{
prevI = i;
i *= i;
count*=2;
}
if (i == n)
return count;
return count / 2 + findPow10(n / prevI);
}
Python：
10 **（len（str（int（x）））-1）
値について、C ++の次のバリエーションでメソッドをタイミングしました a 存在 size_t タイプ（インランスはパフォーマンスを向上させますが、相対的な順序を変更しません）。
1を試してください：番号を見つけるまで乗算します。
size_t try1( size_t a )
{
size_t scalar = 1ul;
while( scalar * 10 < a ) scalar *= 10;
return scalar;
}
2：Multiway if（ルックアップテーブルを使用してプログラムすることもできます）を試してください。
size_t try2( size_t a )
{
return ( a < 10ul ? 1ul :
( a < 100ul ? 10ul :
( a < 1000ul ? 100ul :
( a < 10000ul ? 1000ul :
( a < 100000ul ? 10000ul :
( a < 1000000ul ? 100000ul :
( a < 10000000ul ? 1000000ul :
( a < 100000000ul ? 10000000ul :
( a < 1000000000ul ? 100000000ul :
( a < 10000000000ul ? 1000000000ul :
( a < 100000000000ul ? 10000000000ul :
( a < 1000000000000ul ? 100000000000ul :
( a < 10000000000000ul ? 1000000000000ul :
( a < 100000000000000ul ? 10000000000000ul :
( a < 1000000000000000ul ? 100000000000000ul :
( a < 10000000000000000ul ? 1000000000000000ul :
( a < 100000000000000000ul ? 10000000000000000ul :
( a < 1000000000000000000ul ? 100000000000000000ul :
( a < 10000000000000000000ul ? 1000000000000000000ul :
10000000000000000000ul )))))))))))))))))));
}
試してみると、@Saaed AmiriのFindPOW10から修正されました。
size_t try3( size_t a )
{
if (a == 0)
return 0;
size_t i, j = 1;
size_t prev = 1;
while( j != 100 )
{
i = prev;
j = 10;
while (i <= a)
{
prev = i;
i *= j;
j *= j;
}
}
return prev;
}
4：Lookup Tableのインデックス作成@ira Baxterによると、カウントリーディングゼロ命令を使用してインデックスを付けます。
static const std::array<size_t,64> ltable2{
1ul, 1ul, 1ul, 1ul, 1ul, 10ul, 10ul, 10ul,
100ul, 100ul, 100ul, 1000ul, 1000ul, 1000ul,
1000ul, 10000ul, 10000ul, 10000ul, 100000ul,
100000ul, 100000ul, 1000000ul, 1000000ul,
1000000ul, 1000000ul, 10000000ul, 10000000ul,
10000000ul, 100000000ul, 100000000ul,
100000000ul, 1000000000ul, 1000000000ul,
1000000000ul, 1000000000ul, 10000000000ul,
10000000000ul, 10000000000ul, 100000000000ul,
100000000000ul, 100000000000ul, 1000000000000ul,
1000000000000ul, 1000000000000ul, 1000000000000ul,
10000000000000ul, 10000000000000ul, 10000000000000ul,
100000000000000ul, 100000000000000ul, 100000000000000ul,
1000000000000000ul, 1000000000000000ul, 1000000000000000ul,
1000000000000000ul, 10000000000000000ul, 10000000000000000ul,
10000000000000000ul, 100000000000000000ul, 100000000000000000ul,
100000000000000000ul, 100000000000000000ul, 1000000000000000000ul,
1000000000000000000ul };
size_t try4( size_t a )
{
if( a == 0 ) return 0;
size_t scalar = ltable2[ 64 - __builtin_clzl(a) ];
return (scalar * 10 > a ? scalar : scalar * 10 );
}
タイミングは次のとおりです（GCC 4.8）
for( size_t i = 0; i != 1000000000; ++i) try1(i) 6.6
for( size_t i = 0; i != 1000000000; ++i) try2(i) 0.3
for( size_t i = 0; i != 1000000000; ++i) try3(i) 6.5
for( size_t i = 0; i != 1000000000; ++i) try4(i) 0.3
for( size_t i = 0; i != 1000000000; ++i) pow(10,size_t(log10((double)i)))
98.1
Lookup/Multiway-ifはC ++のすべてを打ち負かしますが、整数が有限サイズであることを知っている必要があります。 try3 より遅い try1 このテストでは、ループエンド値の値が少ないため、多数 try3 ビート try1. 。 Pythonでは、整数が制限されていないため、物事は困難になります。 try2 と try3 固定制限まで数値をすばやく処理するには、非常に多くの数字を処理します。
Pythonでは、リストの理解を使用したルックアップは、おそらくマルチウェイIFよりも速いと思います。
# where we previously define lookuptable = ( 1, 10, 100, ..... )
scalar = [i for i in lookuptable if i < a][-1]
