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

问题描述 投票：2回答：2

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

问题描述

问题描述非常简单：

您将获得两个数组A和B，相应地包含n和m个元素。您需要排序的数字是Ai * Bj，1 <= i <= n且1 <= j <= m。简单来说，第一个数组的每个元素都应该与第二个数组的每个元素相乘。

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

1 <= n，m <= 6000

1 <= Ai，Bj <= 40000

内存限制：512MB

时间限制：2秒

到目前为止我的解

首先，我使用Java，使用Arrays.sort，给出最大的n，m。我们需要对大小为36000000的数组进行排序。然后遍历数组中的每个第十个元素以获得总和。这通过了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 :: sort这样的C ++中的内置排序方法不稳定，因为它基本上是一个快速排序，但是当数据格式不利于快速排序时，它会切换到合并排序，但一般来说它是内置最快的C ++（除此之外） qsort，stable_sort）。
  • 对于Java，有3种类型的排序，一种是使用Arrays.sort（primitive []），它使用引擎下的合并排序，Arrays.sort（Object []）使用Timsort和Collections.sort，它们基本上调用Arrays.sort。做重量级的加工。

非常感谢@rcgldr他的基数排序基础256 C ++代码，它就像一个冠军，更糟糕的情况是6000 * 6000元素，最大运行时间是1.187秒。

  • 有趣的是，std :: sort的C ++仅在最后3个最大的测试用例中失败，它可以在输入大小为6000 * 3000时正常工作。
java c++ algorithm sorting
2个回答
1
投票

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

如果我们首先将两个数组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();
}

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

然后，如果每个生成器还有另一列，我们将其添加回队列。这是根据观察结果，在预先排序的输入的输出中存在大小为n的m个子阵列。队列保存每个子阵列的所有m当前最小值，并且该组中的最小值是整个列表中剩余的最小值。删除并重新添加生成器后，它会确保top值是结果中的下一个最小项。

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

Naive溶液是O（nm log nm）。

我从上面的解决方案中找到的性能瓶颈是插入队列的成本，而且我的性能提升了，但我认为它并不是更加快速的algorithmically。

1
投票

在O（mn）中合并所有这些排序的子数组

产品<2 ^ 31，因此32位整数就足够了，基数排序基数256就可以了。每10个项目的总和可能需要64位。

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

您是否可以使用SIMD / xmm寄存器来执行A和B（A o.x B）的外积乘法？

基本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⌈log2（n）⌉）对n个排序的运行进行排序，每个运行大小为m。在我的系统上，对6000个整数的6000次运行进行排序大约需要1.7秒，而且我不知道矩阵乘法需要多长时间。

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

在具有16个寄存器的系统上，其中8个用作工作和结束索引或运行指针，4路合并排序（没有堆）可能会快一点（大约15％），它是相同的操作总数，1.5 x比较数，但0.5 x移动数，这是一个更多的缓存友好。

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.