将一个数组的每个元素乘以另一个数组的每个元素，并对新的超大型数组进行排序。

Question

免责声明这是我课程的练习，而不是正在进行的比赛。

问题描述

问题的描述非常直截了当：

给出两个数组，A和B，相应地包含n和m元素。对于1 <= i <= n和1 <= j <= m，需要排序的数字是Ai*Bj。简单地说，第一个数组的每个元素都应该乘以第二个数组的每个元素。

设C是这个排序的结果，是一个元素的非递减序列.打印这个序列中每十分之一元素的和，即C1 + C11 + C21 +.。

1 <= n，m <= 6000

1 <= Ai，Bj <= 40000

内存限制:512 Memory

时限:2秒

到目前为止我的解决方案

首先，我使用Java，使用Arrays.sort，给定最大的n，m。我们需要排序一个大小为36000000的数组。然后遍历数组中的每10个元素，得到和。这通过了23个测试用例，其余的得到了TLE。

然后我切换到C++，也使用了内置排序方法，结果稍微好一点，通过了29个测试用例。

我的观察

给出这个输入

4 4
7 1 4 9
2 7 8 11

如果我们先对两个数组A和B进行排序，然后将它们相乘，我们得到

2 8 14 18 7 28 49 63 8 32 56 72 11 44 77 99

它是一个具有m排序子数组的数组。但是，我想不出有什么好的解决方案来合并O(mn)中的所有排序子数组，或者它周围的某个地方。或者我们需要从不同的角度来看待这个问题，把两个数组中的每一个元素相乘是否有什么特殊的性质呢？

更新1: -使用MinHeap -不够快。TLE

更新2:使用k种方式合并的仍然不够快。TLE

更新3: -我忘了提到A和B中元素的范围，所以我刚刚更新了它。

更新4: -基排序基256接受

结论

通过这个问题，我了解了更多关于一般排序的知识，以及一些在Java和C++中使用库进行排序的有用信息。

• 在std：：C++中构建排序方法是不稳定的，因为它基本上是一个快速排序，但是当数据格式不适合快速排序时，它切换到合并排序，但通常它是最快的内置排序C++ (除了qsort，stable_sort)。
• 对于Java来说，有三种类型的排序，一种是使用Arrays.sort(primitive[])，它在引擎盖下使用合并排序，Arrays.sort(Object[])使用Timsort，而Collections.sort基本上是调用Arrays.sort来完成其繁重的处理工作。

非常感谢@rcgldr的基本基256 C++代码，它的工作方式就像一个champ，有6000*6000个元素，最大运行时间是1.187s。

• 有趣的是，std：：类C++只在最后三个最大的测试用例上失败，它可以很好地工作，输入的大小为6000*3000。

Answer 1

将所有排序子数组合并到O(mn)中

产品是< 2^31，所以32位整数是足够的，一个基排序基256，将工作。每10项之和可能需要64位。

Update -您在评论中没有提到256 in的内存限制，我只是注意到了这一点。输入数组大小为6000*6000*4 = 137.33MB。分配一个工作数组一半大小的原始数组(四舍五入: work_size = (1+original_size)/2 )，最坏的情况是3000*6000元素(< 210 of总空间所需)。将原始(产品)数组视为两半，并使用基排序对原始数组的两部分进行排序。将下排序的一半移动到工作数组中，然后将工作数组与原始数组的上半部分合并回原始数组。在我的系统中(英特尔3770K3.5GHz，Win 7 Pro 64位)，两个基排序将花费不到0.4秒(每个0.185秒)，每次合并3000*6000个整数将花费大约0.16秒，不到0.6秒的排序部分。使用这种方法，在进行乘法之前，不需要对A或B排序。

是否允许使用SIMD / xmm寄存器进行A和B(Ao.xB)的外部乘积？

基256个基排序的示例C++代码：

//  a is input array, b is working array
uint32_t * RadixSort(uint32_t * a, uint32_t *b, size_t count)
{
size_t mIndex[4][256] = {0};            // count / index matrix
size_t i,j,m,n;
uint32_t u;
    for(i = 0; i < count; i++){         // generate histograms
        u = a[i];
        for(j = 0; j < 4; j++){
            mIndex[j][(size_t)(u & 0xff)]++;
            u >>= 8;
        }       
    }
    for(j = 0; j < 4; j++){             // convert to indices
        m = 0;
        for(i = 0; i < 256; i++){
            n = mIndex[j][i];
            mIndex[j][i] = m;
            m += n;
        }       
    }
    for(j = 0; j < 4; j++){             // radix sort
        for(i = 0; i < count; i++){     //  sort by current lsb
            u = a[i];
            m = (size_t)(u>>(j<<3))&0xff;
            b[mIndex[j][m]++] = u;
        }
        std::swap(a, b);                //  swap ptrs
    }
    return(a);
}

可以使用合并排序，但速度更慢。假设m >= n，那么常规的2路合并排序将用O(mn⌈long 2(N)⌉)对n个排序的运行进行排序，每个排序的大小为m。在我的系统中，对6000个整数的排序大约需要1.7秒，我不知道矩阵乘法需要多长时间。

使用堆或其他形式的优先级队列只会增加开销。传统的双向合并排序比k路合并排序要快得多.

在有16个寄存器(其中8个用作工作和结束索引或指向运行的指针)的系统上，4路合并排序(没有堆)可能会更快一些(大约15%)，相同的操作总数，1.5 x比较数，但0.5 x移动次数，这更有利于缓存。

Answer 2

你的答案的线索在于你的观察..。

如果我们先对两个数组A和B进行排序，然后将它们相乘，我们得到了2 8 14 18 7 28 49 63 8 32 56 72 11 44 77 99，它是一个具有m排序子数组的数组。

因此，有n个数据序列被排序，问题是使用这些序列来生成答案。

提示1:您能使用优先级队列解决这个问题吗？队列中的元素数将与生成的排序列表数相同。

使用

#include <vector>
#include <algorithm>
#include <random>
#include <queue>

给定以下结构(C++)

// helper to catch every tenth element.
struct Counter {
    int mCount;
    double mSum;
    Counter() : mCount(0), mSum(0) {}
    void push_back(int val)
    {
        if (mCount++ % 10 == 0)
        {
            mSum += val;
        }
    }
    double sum() { return mSum; }
};

// Storage in the priority queue for each of the sorted results.
struct Generator {
    int i_lhs;
    int i_rhs;
    int product;
    Generator() : i_lhs(0), i_rhs(0), product(0) {}
    Generator(size_t lhs, size_t rhs, int p) : i_lhs(lhs), i_rhs(rhs), product(p)
    {
    }
 };

// comparitor to get lowest value product from a priority_queue
struct MinHeap
{
    bool operator()(const Generator & lhs, const Generator & rhs)
    {
        if (lhs.product > rhs.product) return true;
        return false;
    }
};

我量过..。

double Faster(std::vector<int> lhs, std::vector<int>  rhs)
{
    Counter result;
    if (lhs.size() == 0 || rhs.size() == 0) return 0;

    std::sort(lhs.begin(), lhs.end());
    std::sort(rhs.begin(), rhs.end());
    if (lhs.size() < rhs.size()) {
        std::swap(lhs, rhs);
    }
    size_t l = 0;
    size_t r = 0;
    size_t lhs_size = lhs.size();
    size_t rhs_size = rhs.size();
    std::priority_queue<Generator, std::vector< Generator >, MinHeap > queue;
    for (size_t i = 0; i < lhs_size; i++) {
        queue.push(Generator(i, 0, lhs[i] * rhs[0]));
    }
    Generator curr;
    while (queue.size()) {
        curr = queue.top();
        queue.pop();
        result.push_back(curr.product);
        curr.i_rhs++;
        if( curr.i_rhs < rhs_size ){
            queue.push(Generator(curr.i_lhs, curr.i_rhs, lhs[curr.i_lhs] * rhs[curr.i_rhs]));
        }
    }
    return result.sum();
 }

要比下面的简单实现更快

double Naive(std::vector<int> lhs, std::vector<int>  rhs)
{
    std::vector<int> result;
    result.reserve(lhs.size() * rhs.size());
    for (size_t i = 0; i < lhs.size(); i++) {
        for (size_t j = 0; j < rhs.size(); j++) {
            result.push_back(lhs[i] * rhs[j]);
        }
    }
    std::sort(result.begin(), result.end());
    Counter aCount;
    for (size_t i = 0; i < result.size(); i++) {
        aCount.push_back(result[i]);
    }
    return aCount.sum();
}

对输入向量排序比对输出向量排序快得多。对于每一行，我们创建一个生成器，它将遍历所有列。当前产品作为优先级值添加到队列中，一旦生成了所有生成器，就会将它们从队列中读取出来。

然后，如果每个生成器还剩下另一列，则将其添加到队列中。这是因为观察到，在预先排序的输入的输出中有m个大小为n的子数组。队列保存每个子数组的所有m当前最小值，而该集合中最小的是整个列表中最小的剩余值。当一个生成器被删除并重新添加时，它确保top值是结果的下一个最小项。

循环仍然是O(nm)，因为每个生成器只创建一次，读取的最小值是O(1)，插入队列的是O( log )。我们为每一行做了一次，所以O( nm * log n+ nm)简化为O( nm log N )。

初始溶液为O( nm )。

我从上面的解决方案中发现的性能瓶颈是插入队列的成本，我在这方面提高了性能，但我不认为algorithm“快得多”。