0

古いint x = 54897数字のインデックス (0 ベース) と、その数字の新しい値があるとします。新しい値を取得する最速の方法は何ですか?

例

x = 54897
index = 3
value = 2
y = f(x, index, value) // => 54827

編集：最速とは、間違いなくより高速なパフォーマンスを意味します。文字列処理はありません。

4

5 に答える 5

3

最も単純なケースでは (数字が LSB から MSB に番号付けされ、最初の数字が 0 であることを考慮して)、古い数字を知っていれば、次のように簡単に実行できます。

num += (new_digit - old_digit) * 10**pos;

実際の問題には、次のものが必要です。

1) の MSB ファースト バージョンで、posコストが 1log()または最大log10(MAX_INT)で 10 分の 1 になる可能性があります (二分探索を使用して改善できます)。

pos2)せいぜい 2 分割 (またはステップ 1 の結果を使用してゼロ) を必要とする桁。

また、浮動小数点数を BCD に保存できる x86 の特別な fpu 命令を使用することもできます (どれだけ遅いかわかりません)。

更新: 最初のステップは、次のようなバイナリ検索を使用して、除算なしでさらに高速に実行できます。

int my_log10(unsigned short n){
    // short: 0.. 64k -> 1.. 5 digits 
    if (n < 1000){  // 1..3
        if (n <  10) return 1;
        if (n < 100) return 2;
        return 3;
    } else { // 4..5
        if (n < 10000) return 4;
        return 5;
    }
}
于 2010-10-04T18:41:52.127 に答える
2

インデックスが最下位桁から始まる場合、次のようなことができます

p = pow(10,index);
x = (x / (p*10) * (p*10) + value * p + x % p).

しかし、インデックスが後方にあるため、おそらく文字列が適しています。また、読みやすく、保守しやすくなります。

于 2010-10-04T18:34:51.817 に答える
1

  1. 「マスク」を計算しMます: 10 を 乗しますindex。ここで、indexは右からゼロベースのインデックスです。左からインデックスする必要がある場合は、indexそれに応じて再計算してください。

  2. 「プレフィックス」を計算するPRE = x / (M * 10) * (M * 10)

  3. 「サフィックス」を計算するSUF = x % M

  4. 新しい「中間部分」を計算しますMID = value * M

  5. 新しい番号を生成しnew_x = PRE + MID + POSTます。

PS ruslikの答えは、よりエレガントにそれを行います:)

于 2010-10-04T18:37:55.873 に答える
1

You need to start by figuring out how many digits are in your input. I can think of two ways of doing that, one with a loop and one with logarithms. Here's the loop version. This will fail for negative and zero inputs and when the index is out of bounds, probably other conditions too, but it's a starting point.

def f(x, index, value):
    place = 1
    residual = x
    while residual > 0:
        if index < 0:
            place *= 10
        index -= 1
        residual /= 10
    digit = (x / place) % 10
    return x - (place * digit) + (place * value)

P.S. This is working Python code. The principle of something simple like this is easy to work out, but the details are so tricky that you really need to iterate it a bit. In this case I started with the principle that I wanted to subtract out the old digit and add the new one; from there it was a matter of getting the correct multiplier.

于 2010-10-04T18:42:06.680 に答える
0

パフォーマンスについて話している場合は、コンピューティング プラットフォームを具体的に説明する必要があります。

数値をそれぞれ 4 ビットの 10 進数のペアに変換することで、これにアプローチします。

次に、変更が必要なペアをバイトとして見つけて処理します。

次に、番号を元に戻します。

これを非常にうまく行うアセンブラがあります。

于 2010-10-04T18:31:14.077 に答える