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

Question

免责声明这是我类(class)的练习，而不是来自正在进行的比赛。

问题描述

问题描述很直接:

给定两个数组，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:- 基数排序 base 256 [已接受]

结论

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

• C++ 中内置的排序方法如 std::sort 不稳定，因为它基本上是快速排序，但当数据格式不适合快速排序时，它会切换到归并排序，但通常它是最快的内置的 C++ 类型(除了 qsort、stable_sort)。

• 对于 Java，有 3 种排序类型，一种是 Arrays.sort(primitive[])，它在底层使用归并排序，Arrays.sort(Object[])，它使用 Timsort 和 Collections.sort它基本上调用 Arrays.sort 来完成繁重的处理工作。

非常感谢@rcgldr 的 radix sort base 256 C++ 代码，它在 6000*6000 个元素的更坏情况下工作得很好，最长运行时间为 1.187s。

• 有趣的是，C++ 的 std::sort 仅在最后 3 个最大的测试用例中失败，它在 6000*3000 大小的输入下工作正常。

Answer 1

merge all of these sorted subarray in O(mn)

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

更新 - 你没有在你的评论中提到 256MB 的内存限制，我刚刚注意到这一点。输入数组大小为 6000*6000*4 = 137.33MB。分配原始数组一半大小的工作数组(四舍五入:work_size = (1+original_size)/2 )，最坏情况，3000*6000 个元素(< 210MB 所需总空间)。将原始(产品)数组视为两半，并使用基数排序对原始数组的两半进行排序。将排序后的下半部分移动到工作数组中，然后将工作数组与原始数组的上半部分合并回原始数组。在我的系统(Intel 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 秒，而且我不知道矩阵乘法需要多长时间。

使用堆或其他形式的优先级队列只会增加开销。传统的 2 路归并排序比使用堆的 k 路归并排序更快。

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