1

私はC++を使用しています。STL からの並べ替えの使用が許可されます。

次のように、 intの配列があります。

1 4 1 5 145 345 14 4

数値はchar *に格納されます（バイナリファイルから読み取り、数値ごとに4バイト）

この配列で2つのことをしたい：

  1. 各数字をその後の数字と入れ替える

    4 1 5 1 345 145 4 14

  2. 2 のグループごとに並べ替えます

    4 1 4 14 5 1 345 145

段階的にコーディングすることはできますが、効率的ではありません。私が求めているのはスピードです。O(n log n) は素晴らしいでしょう。

また、この配列は 500MB を超える可能性があるため、メモリ使用量が問題になります。

私の最初のアイデアは、配列を最後から並べ替え (数字を 2 つずつ入れ替える)、それをlong*として扱うことでした (並べ替えが毎回 2 int を取るように強制するため)。しかし、私はそれをコーディングすることができず、それが機能するかどうかさえわかりません.

私はあなたの助けに感謝します:)

4

3 に答える 3

2

これは、私が思いつくことができる最もメモリ効率の良いレイアウトです。明らかに、エンディアンがすべて適切に処理されていると仮定すると、使用しているベクトルは使用しているデータブロブに置き換えられます。以下のコードの前提は単純です。

  1. 1024 個のランダムな値をペアで生成します。各ペアは、1 から 500 までの最初の数値と 1 から 50 までの 2 番目の数値で構成されます。

  2. リスト全体を反復し、すべての偶数インデックス値を次の奇数インデックス値で反転します。

  3. 2つstd::qsortの値のアイテム幅と元のベクトルの半分のカウントで全体を送信します。int32_t

  4. コンパレータ関数は、最初に即値でソートし、最初の値が等しい場合は 2 番目の値でソートします。

以下のサンプルは、1024 個のアイテムに対してこれを行います。134217728 アイテム (正確には 536870912 バイト) の出力なしでテストしたところ、わずかな macbook air ラップトップでは約 15 秒で、実際の並べ替えでは約 10 秒しかかからず、かなり印象的な結果が得られました。理想的に最も重要なことは、データ ベクトルを超えて追加のメモリ割り当てが必要ないことです。はい、純粋主義者には、私は呼び出しスタック スペースを使用しますが、それは q-sort が使用するためです。

あなたがそれから何かを得ることを願っています。

注: 出力の最初の部分のみを表示しますが、探しているものが表示されることを願っています。

#include <iostream>
#include <fstream>
#include <algorithm>
#include <iterator>
#include <cstdint>


// a most-wacked-out random generator. every other call will
//  pull from a rand modulo either the first, or second template
//  parameter, in alternation.
template<int N,int M>
struct randN
{
    int i = 0;
    int32_t operator ()()
    {
        i = (i+1)%2;
        return (i ? rand() % N : rand() % M) + 1;
    }
};

// compare to integer values by address.
int pair_cmp(const void* arg1, const void* arg2)
{
    const int32_t *left = (const int32_t*)arg1;
    const int32_t *right = (const int32_t *)arg2;
    return (left[0] == right[0]) ? left[1] - right[1] : left[0] - right[0];
}

int main(int argc, char *argv[])
{
    // a crapload of int values
    static const size_t N = 1024;

    // seed rand()
    srand((unsigned)time(0));

    // get a huge array of random crap from 1..50
    vector<int32_t> data;
    data.reserve(N);
    std::generate_n(back_inserter(data), N, randN<500,50>());

    // flip all the values
    for (size_t i=0;i<data.size();i+=2)
    {
        int32_t tmp = data[i];
        data[i] = data[i+1];
        data[i+1] = tmp;
    }

    // now sort in pairs. using qsort only because it lends itself
    //  *very* nicely to performing block-based sorting.
    std::qsort(&data[0], data.size()/2, sizeof(data[0])*2, pair_cmp);
    cout << "After sorting..." << endl;
    std::copy(data.begin(), data.end(), ostream_iterator<int32_t>(cout,"\n"));
    cout << endl << endl;

    return EXIT_SUCCESS;
}

出力

After sorting...
1
69
1
83
1
198
1
343
1
367
2
12
2
30
2
135
2
169
2
185
2
284
2
323
2
325
2
347
2
367
2
373
2
382
2
422
2
492
3
286
3
321
3
364
3
377
3
400
3
418
3
441
4
24
4
97
4
153
4
210
4
224
4
250
4
354
4
356
4
386
4
430
5
14
5
26
5
95
5
145
5
302
5
379
5
435
5
436
5
499
6
67
6
104
6
135
6
164
6
179
6
310
6
321
6
399
6
409
6
425
6
467
6
496
7
18
7
65
7
71
7
84
7
116
7
201
7
242
7
251
7
256
7
324
7
325
7
485
8
52
8
93
8
156
8
193
8
285
8
307
8
410
8
456
8
471
9
27
9
116
9
137
9
143
9
190
9
190
9
293
9
419
9
453
于 2013-02-09T10:37:48.760 に答える
2

入力とプラットフォームの両方にいくつかの追加の制約があれば、考えているようなアプローチを使用できる可能性があります。これらの制約には、

  • 入力には正の数のみが含まれています (つまり、符号なしとして扱うことができます)
  • uint8_tお使いのプラットフォームが提供uint64_tする<cstdint>
  • 既知のエンディアンを持つ単一のプラットフォームに対処します。

その場合、入力を 8 バイトのグループに分割し、バイト シャッフルを実行して、各グループをuint64_t下位半分の入力からの「最初の」番号を持つ1 つとして配置std::sortし、結果の配列で実行します。エンディアンによっては、ソートされた各 8 バイト グループを期待される順序で uint32_t のペアとして再配置するために、さらにバイト シャッフルを行う必要がある場合があります。

これを自分でコーディングできない場合は、このアプローチをとらないことを強くお勧めします。

より優れた移植性の高いアプローチ (明確に指定されていないバイナリ ファイル形式から開始することにより、固有の非移植性があります) は次のようになります。

std::vector<int> swap_and_sort_int_pairs(const unsigned char buffer[], size_t buflen) {
   const size_t intsz = sizeof(int);
   // We have to assume that the binary format in buffer is compatible with our int representation
   // we also require an even number of integers
   assert(buflen % (2*intsz) == 0);

   // load pairwise
   std::vector< std::pair<int,int> > pairs;
   pairs.reserve(buflen/(2*intsz));
   for (const unsigned char* bufp=buffer; bufp<buffer+buflen; bufp+= 2*intsz) {
      // It would be better to have a more portable binary -> int conversion
      int first_value = *reinterpret_cast<int*>(bufp);
      int second_value = *reinterpret_cast<int*>(bufp + intsz);
      // swap each pair here
      pairs.emplace_back( second_value, firstvalue );
   }
   // less<pair<..>> does lexicographical ordering, which is what you are looking ofr
   std::sort(pairs.begin(), pairs.end());

   // convert back to linear vector 
   std::vector<int> result;
   result.reserve(2*pairs.size());
   for (auto& entry : pairs) {
      result.push_back(entry.first);
      result.push_back(entry.second);
   }
   return result;
}

最初の解析/スワップ パス (とにかく必要) と最終的な変換の両方が O(N) であるため、合計の複雑さは依然として (O(N log(N)) です。

ペアで引き続き作業できる場合は、最終的な変換を保存できます。その変換を節約するもう 1 つの方法は、2 int のストライドと 2 int のスワップを使用して手動でコード化された並べ替えを使用することです。はるかに多くの作業が必要になりますが、適切に調整されたライブラリの並べ替えほど効率的である可能性は依然としてあります。

于 2013-02-09T10:38:54.407 に答える
0

一度に 1 つのことを行います。まず、データに何らかの*構造*を与えます。各8バイトがフォームの単位を形成しているようです

struct unit {
    int key;
    int value;
}

エンディアンが正しければ、O(1) で reinterpret_cast を使用してこれを行うことができます。そうでない場合は、O(n) の変換作業を行う必要があります。O(n log n) の検索作業と比較すると、どちらも消えます。

これらのユニットの配列がある場合、次のように std::sort を使用できます。

bool compare_units(const unit& a, const unit& b) {
    return a.key < b.key;
}

std::sort(array, length, compare_units);

このソリューションの鍵は、最初に「スワッピング」とバイト解釈を行い、次にソートを行うことです。

于 2013-02-09T10:15:59.610 に答える