为什么我用基数 2^20 实现基数排序对 500 万大小的数组进行排序时，这个程序 运行 陷入无限循环？
Why does this program run into an infinite loop when I implement radix sort with base 2^20 to sort an array of size 5 million?
我将尝试尽可能清楚地解释问题：
- 用户输入了 2 个数字，n 和 q。
- 我们取前 n 个斐波那契数并用 q 对每个数取模并将模数结果放入 arr。所以 arr 现在有 n 个元素。到这里程序运行良好。
- 我们现在必须使用基数排序对 arr 进行排序。当测试用例很小时，例如 n=5 q=100，n=15 q=13，n=1000000 q=1000000，基数排序工作得很好，我得到了正确的输出。
- 当 n=5000000 和 q=1000000000（数组长度为 5000000）且数组中的最大数为 999999973 时，程序 运行s 在排序时陷入无限循环。
- sorting sorting 后有一些模算术计算可以忽略，因为它们工作正常并且没有错误。
有人可以帮我检查一下我的排序算法吗？同样，现在我选择基数为 2^20 进行基数排序。我们是根据什么来选择底座的？数组中最大数的长度？
n=5000000 和 q=1000000000 的正确输出是 973061125（仅供参考，如果有人决定 运行 程序并检查）。
#include<iostream>
#include<algorithm>
using namespace std;
void countsort(long int* arr, long int n,long int shift)
{
long int* count = new long int[1048576];
for (int i = 0; i < 1048576; i++)
count[i] = 0;
long int *output=new long int[n];
long int i, last;
for (i = 0; i < n; i++)
{
++count[(arr[i] >> shift) & 1048575];
}
for (i = last = 0; i < 1048576; i++)
{
last += count[i];
count[i] = last - count[i];
}
for (i = 0; i < n; i++)
{
output[count[(arr[i] >> shift) & 1048575]++] = arr[i];
}
for (i = 0; i < n; i++)
{
arr[i] = output[i];
}
delete[] output;
delete[] count;
}
int main()
{
int trials = 0;
cin >> trials;
while (trials--)
{
long int n = 0;
long int q = 0;
cin >> n;
cin >> q;
long int first = 0, second = 1, fib = 0;
long int* arr = new long int[n];
arr[0] = second;
long int m = 0;
for (long int i = 1; i < n; i++)
{
fib = (first + second) % q;
first = second;
second = fib;
arr[i] = fib;
if (m < arr[i])
m = arr[i];
}
//m is the largest integer in the array
// this is where radix sort starts
for (long int shift = 0; (m >> shift) > 0; shift += 20)
{
countsort(arr, n, shift);
}
long long int sum = 0;
for (long int i = 0; i < n; i++)
{
sum = sum + ((i + 1) * arr[i]) % q;
}
sum = sum % q;
cout << sum << endl;
}
}
死循环问题出在这一行
for (long int shift = 0; (m >> shift) > 0; shift += 20)
假设这是 运行 在 X86 处理器上，仅使用移位计数的低位，因此对于 32 位整数，仅使用移位的低 5 位（0 到 31）使用 count，对于 64 位整数，仅使用低 6 位（0 到 63）。大多数编译器不会补偿此限制。 （原来的8086/8088/80186没有屏蔽shift count，这个是从80286开始的）
您先前问题的另一个问题是 (i + 1) * arr[i] 可以大于 32 位。先前的问题将 sum 定义为 long long int。代码也可以将我定义为 long long int（或者它可以在进行乘法运算之前使用强制转换）。评论中指出的修复。我不知道 sum 是否应该是 % q，所以我将它保留为 long long int 值。
for (int shift = 0; m > 0; shift += 20) // fix
{
countsort(arr, n, shift);
m >>= shift; // fix
}
long long int sum = 0; // fix (long long)
for (long long int i = 0; i < n; i++) // fix (long long)
{
sum = sum + ((i + 1) * arr[i]) % q;
}
sum = sum;
cout << sum << endl;
不知道你用的是什么编译器，所以不知道long int是32位的还是64位的。您之前的问题代码将 sum 声明为 long long int，用于在 Visual Studio 的情况下声明 64 位整数。我不知道其他编译器。如果 long int 是 32 位，那么这个 like 就是一个潜在的问题：
fib = (first + second) % q;
因为 first + second 的和可以是负数，余数的符号与被除数的符号相同。负数将成为您使用的基数排序代码的问题。将 fib 声明为 unsigned int 或 long long int 将避免此问题。
至于选择基数，最好将所有逻辑都放在计数排序中，并将其重命名为基数排序。使用 base 2^8 并进行 4 次传递会更快（由于适合 L1 缓存的计数/索引）。正如我上面提到的，arr 和输出都应该声明为无符号整数。基数排序的方向将随着 4 次遍历中的每一次而改变：arr->output、output->arr、arr->output、output->arr，无需复制。
另一个优化是混合 MSD（最高有效数字）/LSD（最低有效数字）基数排序，用于比所有缓存大得多的数组。假设使用 base 2^8 == 256，那么第一遍创建 256 个逻辑 bin，然后每个逻辑 bin 都适合缓存，然后使用 3 LSD 基数排序遍对 256 个逻辑 bin 中的每一个进行排序。在我的系统（Intel 3770K，Win 7 Pro 64 位）上，排序 3600 万个 32 位无符号整数的时间减少了不到 6%，从 0.37 秒减少到 0.35 秒，一个递减点 returns.
我将尝试尽可能清楚地解释问题：
- 用户输入了 2 个数字，n 和 q。
- 我们取前 n 个斐波那契数并用 q 对每个数取模并将模数结果放入 arr。所以 arr 现在有 n 个元素。到这里程序运行良好。
- 我们现在必须使用基数排序对 arr 进行排序。当测试用例很小时，例如 n=5 q=100，n=15 q=13，n=1000000 q=1000000，基数排序工作得很好，我得到了正确的输出。
- 当 n=5000000 和 q=1000000000（数组长度为 5000000）且数组中的最大数为 999999973 时，程序 运行s 在排序时陷入无限循环。
- sorting sorting 后有一些模算术计算可以忽略，因为它们工作正常并且没有错误。
有人可以帮我检查一下我的排序算法吗？同样，现在我选择基数为 2^20 进行基数排序。我们是根据什么来选择底座的？数组中最大数的长度？ n=5000000 和 q=1000000000 的正确输出是 973061125（仅供参考，如果有人决定 运行 程序并检查）。
#include<iostream>
#include<algorithm>
using namespace std;
void countsort(long int* arr, long int n,long int shift)
{
long int* count = new long int[1048576];
for (int i = 0; i < 1048576; i++)
count[i] = 0;
long int *output=new long int[n];
long int i, last;
for (i = 0; i < n; i++)
{
++count[(arr[i] >> shift) & 1048575];
}
for (i = last = 0; i < 1048576; i++)
{
last += count[i];
count[i] = last - count[i];
}
for (i = 0; i < n; i++)
{
output[count[(arr[i] >> shift) & 1048575]++] = arr[i];
}
for (i = 0; i < n; i++)
{
arr[i] = output[i];
}
delete[] output;
delete[] count;
}
int main()
{
int trials = 0;
cin >> trials;
while (trials--)
{
long int n = 0;
long int q = 0;
cin >> n;
cin >> q;
long int first = 0, second = 1, fib = 0;
long int* arr = new long int[n];
arr[0] = second;
long int m = 0;
for (long int i = 1; i < n; i++)
{
fib = (first + second) % q;
first = second;
second = fib;
arr[i] = fib;
if (m < arr[i])
m = arr[i];
}
//m is the largest integer in the array
// this is where radix sort starts
for (long int shift = 0; (m >> shift) > 0; shift += 20)
{
countsort(arr, n, shift);
}
long long int sum = 0;
for (long int i = 0; i < n; i++)
{
sum = sum + ((i + 1) * arr[i]) % q;
}
sum = sum % q;
cout << sum << endl;
}
}
死循环问题出在这一行
for (long int shift = 0; (m >> shift) > 0; shift += 20)
假设这是 运行 在 X86 处理器上，仅使用移位计数的低位，因此对于 32 位整数，仅使用移位的低 5 位（0 到 31）使用 count，对于 64 位整数，仅使用低 6 位（0 到 63）。大多数编译器不会补偿此限制。 （原来的8086/8088/80186没有屏蔽shift count，这个是从80286开始的）
您先前问题的另一个问题是 (i + 1) * arr[i] 可以大于 32 位。先前的问题将 sum 定义为 long long int。代码也可以将我定义为 long long int（或者它可以在进行乘法运算之前使用强制转换）。评论中指出的修复。我不知道 sum 是否应该是 % q，所以我将它保留为 long long int 值。
for (int shift = 0; m > 0; shift += 20) // fix
{
countsort(arr, n, shift);
m >>= shift; // fix
}
long long int sum = 0; // fix (long long)
for (long long int i = 0; i < n; i++) // fix (long long)
{
sum = sum + ((i + 1) * arr[i]) % q;
}
sum = sum;
cout << sum << endl;
不知道你用的是什么编译器，所以不知道long int是32位的还是64位的。您之前的问题代码将 sum 声明为 long long int，用于在 Visual Studio 的情况下声明 64 位整数。我不知道其他编译器。如果 long int 是 32 位，那么这个 like 就是一个潜在的问题：
fib = (first + second) % q;
因为 first + second 的和可以是负数，余数的符号与被除数的符号相同。负数将成为您使用的基数排序代码的问题。将 fib 声明为 unsigned int 或 long long int 将避免此问题。
至于选择基数，最好将所有逻辑都放在计数排序中，并将其重命名为基数排序。使用 base 2^8 并进行 4 次传递会更快（由于适合 L1 缓存的计数/索引）。正如我上面提到的，arr 和输出都应该声明为无符号整数。基数排序的方向将随着 4 次遍历中的每一次而改变：arr->output、output->arr、arr->output、output->arr，无需复制。
另一个优化是混合 MSD（最高有效数字）/LSD（最低有效数字）基数排序，用于比所有缓存大得多的数组。假设使用 base 2^8 == 256，那么第一遍创建 256 个逻辑 bin，然后每个逻辑 bin 都适合缓存，然后使用 3 LSD 基数排序遍对 256 个逻辑 bin 中的每一个进行排序。在我的系统（Intel 3770K，Win 7 Pro 64 位）上，排序 3600 万个 32 位无符号整数的时间减少了不到 6%，从 0.37 秒减少到 0.35 秒，一个递减点 returns.