9

正の整数の 3 つの基本表現があります。

  1. unsigned long 変数の 10 進数 (例: unsigned long int NumDec = 200 )。
  2. 16 進数、文字列変数 (例: string NumHex = "C8" )
  3. バイナリ、文字列変数 (例: string NumBin = "11001000" )

最も効率的な方法で、3 つの表現すべての数値を変換できるようにしたいと考えています。つまり、次の 6 つの機能を実装します。

unsigned long int Binary2Dec(const string & Bin) {}
unsigned long int Hex2Dec(const string & Hex) {}
string Dec2Hex(unsigned long int Dec) {}
string Binary2Hex(const string & Bin) {}
string Dec2Binary(unsigned long int Dec) {}
string Hex2Binary(const string & Hex) {}

それらのそれぞれにとって最も効率的なアプローチは何ですか? C と C++ は使用できますが、boost は使用できません。

編集：「効率」とは、時間効率を意味します：最短の実行時間。

4

7 に答える 7

8

他の人が指摘しているように、私は、、sscanf()およびprintf()/またはから始めstrtoul()ます。ほとんどのアプリケーションで十分に高速であり、バグが発生する可能性は低くなります。ただし、これらの関数は、任意の基数で表される数値などの非ASCII文字セットを処理する必要があるため、予想よりも一般的であると言えます。一部のドメインでは、ライブラリ機能を打ち負かすことができます。

したがって、最初に測定し、これらの変換のパフォーマンスが本当に問題である場合は、次のようにします。

1）一部のアプリケーション/ドメインでは、特定の数値が非常に頻繁に表示されます。たとえば、ゼロ、100、200、19.95は非常に一般的であるため、関数を最適化して、一連のif（）ステートメントでそのような数値を変換することが理にかなっています。汎用ライブラリ関数にフォールバックします。2）最も一般的な100の数値の場合はテーブルルックアップを使用してから、ライブラリ関数にフォールバックします。大きなテーブルはキャッシュに収まらない可能性があり、共有ライブラリに対して複数の間接化が必要になる可能性があることに注意してください。パフォーマンスを低下させないように、これらを注意深く測定してください。

私の経験では、後者は古き良きC関数と比較的比較されていますが、ブーストlexical_cast関数も確認することをお勧めします。

多くの人がそれを言っていますが、何度も繰り返す価値があります。問題であるという証拠が得られるまで、これらの変換を最適化しないでください。最適化する場合は、新しい実装を測定して、より高速であることを確認し、バグが発生するため、独自のバージョンの単体テストが大量にあることを確認してください:-(

于 2009-05-04T21:23:14.620 に答える
4

sprintfとsscanfを使用することをお勧めします。

また、それがどのように実装されているかに興味がある場合は、glibcのソースコードであるGNUCライブラリを参照してください。

于 2009-05-04T10:04:18.903 に答える
3

これらのルーチンは、なぜそれほど時間効率がよくなければならないのでしょうか? そのような主張はいつも私を驚かせます。strtol() のような明白な変換メソッドが遅すぎると確信していますか、それとももっとうまくできるでしょうか? 通常、システム関数は非常に効率的です。一般性とエラーチェックをサポートするのが遅い場合がありますが、エラーの処理方法を考慮する必要があります。bin引数に '0' と '1' 以外の文字が含まれている場合はどうなりますか? アボート？大量のエラーを伝播しますか?

内部表現を表すのに「12 月」を使用しているのはなぜですか? Dec、Hex、および Bin は、文字列表現を参照するために使用する必要があります。について小数は何もありませんunsigned long。数値を 10 進数で示す文字列を扱っていますか? そうでなければ、ここで人々を混乱させ、さらに多くの人々を混乱させることになります。

2 進数と 16 進数のテキスト形式間の変換は、ルックアップ テーブルを使用して迅速かつ効率的に行うことができますが、10 進数のテキスト形式を含むものはより複雑になります。

于 2009-05-04T16:45:09.343 に答える
2

宿題の問題のように聞こえますが、一体何が...

簡単な答えは、longintから文字列に変換するために2つのルックアップテーブルを使用することです。各テーブルには256のエントリが必要です。1つはバイトを16進文字列にマップします：0-> "00"、1-> "01"など。もう1つはバイトをビット文字列にマップします：0-> "00000000"、1->"00000001"。

次に、long intの各バイトについて、正しい文字列を検索し、それらを連結する必要があります。

文字列からlongに戻すには、各文字の数値に16または2の適切な累乗を掛けて結果を合計することにより、16進文字列とビット文字列を10進数に戻すことができます。

編集：正しい文字列を見つけるために二分探索を行うことにより、逆変換に同じルックアップテーブルを使用することもできます。これには、log（256）=8回の文字列の比較が必要です。残念ながら、文字列の比較が整数の乗算と加算よりもはるかに高速であるかどうかを分析する時間がありません。

于 2009-05-04T10:01:19.503 に答える
2

それは何を最適化するかによって異なりますが、「効率的」とはどういう意味ですか? 変換が高速であること、メモリーの使用量が少ないこと、プログラマーの時間が少ないこと、コードを読む他のプログラマーからのWTFが少ないことが重要ですか?

読みやすさと実装の容易さのために、少なくとも と の両方Dec2Hex()をDec2Binary()を呼び出すだけで実装する必要がありますstrotul()。これは、少なくとも上記の単語の解釈のいくつかにとって非常に効率的です。

于 2009-05-04T09:49:09.093 に答える
1

タスクの半分について少し考えてみましょう。文字列化された基数nからunsignedlongに変換します。ここで、nは2の累乗です（2進数の場合は基数2、16進数の場合は基数16）。

入力が正しければ、この作業は比較、サブラクト、シフト、および1桁あたりにすぎません。あなたの入力が正気でないなら、まあ、それはそれが醜くなるところですよね？超高速で変換を行うことは難しくありません。すべての状況下でそれをうまく行うことは挑戦です。

それで、あなたの入力が正気であると仮定しましょう、そしてあなたの変換の核心はこれです：

unsigned long PowerOfTwoFromString(char *input, int shift)
{
    unsigned long val = 0;
    char upperLimit = 'a' + (1 << shift)
    while (*input) {
        char c = tolower(*input++);
        unsigned long digit = (c > 'a' && c < upperLimit) ? c - 'a' + 10 : c - '0';
        val = (val << shift) | digit;
    }
    return val;
 }

 #define UlongFromBinaryString(str) PowerOfTwoFromString(str, 1)
 #define UlongFromHexString(str) PowerOfTwoFromString(str, 4)

それがどれほど簡単かわかりますか？また、正常でない入力では失敗します。あなたの仕事のほとんどは、パフォーマンスではなく、入力を正気にすることになります。

現在、このコードは2シフトの力を利用しています。ベース4、ベース8、ベース32などに拡張するのは簡単です。2つのベースの非累乗では機能しません。それらのために、あなたの数学は変えなければなりません。あなたが得る

val = (val * base) + digit

これは、この一連の操作で概念的に同じです。ベースによる乗算はシフトと同等になります。したがって、代わりに完全に一般的なルーチンを使用する可能性があります。そして、入力をサニタイズしながらコードをサニタイズします。そしてその時点で、strtoulはおそらくあなたの最善の策です。strtoulのバージョンへのリンクは次のとおりです。ほぼすべての作業はエッジ条件の処理です。これにより、エネルギーをどこに集中させるべきか、つまり正しい、回復力のあるコードを見つけることができます。ビットシフトを使用することによる節約は、たとえば、悪い入力でクラッシュしないという節約と比較して最小限になります。

于 2009-05-04T17:28:53.263 に答える
0

マクロを使用して、フォーマットを入力としても使用しないのはなぜですか。あなたが少なくともCにいるなら。

#define TO_STRING( string, format, data) \
sprintf( string, "##format##", data)
// Int
TO_STRING(buf,%d,i);
// Hex ( Two char representation )
TO_STRING(buf,%02x,i);
// Binary
TO_STRING(buf,%b,i);

または、sprintf を直接使用することもできます。または、複数のマクロを使用することもできます。

#define INT_STRING( buf, data) \
sprintf( buf, "%d", data)
#define HEX_STRING( buf, data) \
sprintf( buf, "%x", data)
#define BIN_TO_STRING( buf, data) \
sprintf( buf, "%b", data)

BIN_TO_STRING( loc_buf, my_bin );
于 2009-05-04T16:09:15.687 に答える