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: - 基数排序基数 256 [已接受]

结论

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

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

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

非常感谢@rcgldr提供的基于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 移动数，这对缓存更友好。