0

数値範囲間の設定ビット数を計算するために、このコードを作成しました。私のプログラムは正常にコンパイルされ、適切な出力が得られます。大量の入力と「制限時間超過」に時間がかかりすぎています。

#define forn(i, n) for(long int i = 0; i < (long int)(n); i++)
#define ford(i, n) for(long int i = (long int)(n) - 1; i >= 0; i--)
#define fore(i, a, n) for(long int i = (int)(a); i < (long int)(n); i++)


long int solve(long int i) {
    i = i - ((i >> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
    return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
}

int main() {
    freopen("C:/Projects/CodeChef/SetBits/input.txt", "rt", stdin);
    freopen("C:/Projects/CodeChef/SetBits/output.txt", "wt", stdout);

    int tt;
    long long int num1;
    long long int num2;
    scanf("%d", &tt);
    forn(ii, tt) {
        unsigned long int bits = 0;
        unsigned long long int total_bits = 0;
        scanf("%lld",&num1);
        scanf("%lld",&num2);
        fore(jj, num1, num2+1) {
                bits = solve(jj);
                total_bits += bits;
                }

        printf("%lld\n",total_bits);
    }

    return 0;
}

テストケースの例:-

サンプル入力: 3

-2 0

-3 4

-1 4

サンプル出力:

63

99

37

最初のケースでは、-2 には 31 個の 1 が含まれ、その後に 0 が続きます。-1 には 32 個の 1 が含まれ、0 には 0 個の 1 が含まれます。したがって、合計は 63 です。

2 番目のケースの場合、答えは 31 + 31 + 32 + 0 + 1 + 1 + 2 + 1 = 99 です。

大きな値を持つテスト ケース:-

10

-1548535525 662630637

-1677484556 -399596060

-2111785037 1953091095

643110128 1917824721

-1807916951 491608908

-1536297104 1976838237

-1891897587 -736733635

-2088577104 353890389

-2081420990 819160807

-1585188028 2053582020

時間を短縮するためにコードを最適化する方法に関する提案。すべての役立つ提案と回答は、投票していただければ幸いです。:)

4

1 に答える 1

1

あなたが何をしているのかはよくわかりませんが、コードを大幅にクリーンアップでき、関数をインライン化できることは知っています。

また、私はあなたのコードを「言い換える」自由を取りました.CのようにC++を使用していますが、それらの定義は厳しいものであり、ファイルをstdioにマッピングすることはさらに悪いことです. コードをテストまたはコンパイルしていませんが、すべてあります。

#include <fstream>

inline long int solve(long int i) {
    i = i - ((i >> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
    return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
}

int main() {
    long first, last;
    unsigned count;
    std::ifstream inf("C:/Projects/CodeChef/SetBits/input.txt");
    std::ofstream off("C:/Projects/CodeChef/SetBits/output.txt");
    inf >> count;
    for(unsigned i=0u; i!=count; ++i) {
        inf >> first >> last;
        long total=0;
        ++last;
        for(long t=first; t!=last; ++t) {
            total+=solve(t);
        }
        off << total << '\n';
    }
    return 0;
}

これをスピードアップする方法についてのいくつかのアイデア:

  • 計算された値の std::map を作成し、それらが以前に処理されている場合は、再計算するのではなくそれらを使用できます。
  • 同じことを行いますが、単一の値ではなく範囲を保存しますが、それは難しいでしょう。値がマップに存在するかどうかを確認し、前処理された値がなくなるまでマップをインクリメントすることができます。その場合、反復のためにそれらの処理を開始します。
  • 番号と次の間に簡単なシーケンスがあるかどうかを確認してください。最初の値を計算してから、それをインクリメントすることができます。
  • そのようなシーケンスのための O(1) アルゴリズムがあるかもしれません
  • intel TBB を見て、tbb::parallel for のようなものを使用して各コアに作業を分散します。これは、このような小さなメモリを扱っているため、大きなチャンク サイズで本当に良いリターンが得られるはずです。
于 2012-04-11T14:22:56.380 に答える