1

我正在使用 C++。允许使用 STL 中的排序。

我有一个int数组，如下所示：

1 4 1 5 145 345 14 4

这些数字存储在char*中（我从二进制文件中读取它们，每个数字 4 个字节）

我想用这个数组做两件事：

  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 替换为 2）并将其视为long*（强制排序每次取 2 个 int）。但是我无法对其进行编码，我什至不确定它是否会起作用。

我希望我足够清楚，感谢您的帮助:)

4

3 回答 3

2

这是我能想到的最节省内存的布局。显然，我正在使用的向量将被您正在使用的数据 blob 替换，假设 endian-ness 都处理得很好。下面代码的前提很简单。

  1. 成对生成 1024 个随机值，每对包含 1 到 500 之间的第一个数字，1 到 50 之间的第二个数字。

  2. 迭代整个列表，将所有偶数索引值及其以下奇数索引兄弟翻转。

  3. 将整个事物发送到std::qsort，项目宽度为两(2) 个int32_t值，计数为原始向量的一半。

  4. 比较器函数首先对立即值进行排序，如果第一个值相等，则对第二个值进行排序。

下面的示例对 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，将输入中的“第一个”数字放在较低值的一半中，并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))。

如果您可以继续使用对，则可以保存最终转换。保存该转换的另一种方法是使用具有两个整数步长和两个整数交换的手动编码排序：更多的工作 - 并且可能仍然很难像经过良好调整的库排序一样高效。

于 2013-02-09T10:38:54.407 回答
0

一次做一件事。首先，给你的数据一些*结构*结构。好像每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 回答