Почему эта программа сталкивается с бесконечным l oop, когда я использую основную сортировку с базой 2 ^ 20 для сортировки массива размером 5 миллионов?

Question

Я постараюсь объяснить проблему как можно более четко:

• Пользователь вводит 2 числа, n и q.
• мы берем первые n чисел Фибоначчи и модуль каждого из них с q и помещаем результат модуля в обр. Таким образом, arr теперь имеет n элементов. До сих пор программа работает просто отлично.
• Теперь нам нужно отсортировать arr, используя radix sort. Когда тестовые случаи малы, например, n = 5 q = 100, n = 15 q = 13, n = 1000000 q = 1000000, сортировка по основанию работает очень хорошо, и я получаю правильный вывод.
• программа сталкивается с бесконечным l oop при сортировке, когда n = 5000000 и q = 1000000000 (длина массива 5000000), а наибольшее число в массиве - 999999973.
• После сортировки сортировка есть некоторые вычисления по модулю арифметики c, которые можно игнорировать, так как они работают нормально и не имеют ошибок.

Может ли кто-нибудь помочь мне проверить мой алгоритм сортировки? Также прямо сейчас я выбрал базу 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;
    }
}

Answer 1

Проблема бесконечной l oop находится в этой строке

    for (long int shift = 0; (m >> shift) > 0; shift += 20)

Если предположить, что это выполняется на процессоре X86, используются только младшие биты счетчика сдвигов, поэтому для 32-разрядного целого числа используются только младшие 5 бит (от 0 до 31) счетчика сдвигов, а для 64-битного целого числа используются только младшие 6 бит (от 0 до 63). Большинство компиляторов не будут компенсировать это ограничение. (Первоначально 8086/8088/80186 не маскировал счетчик сдвигов, это началось с 80286).

Другая проблема из вашего предыдущего вопроса состояла в том, что (i + 1) * arr [i] может быть больше чем 32 бита. Предыдущий вопрос имел сумму, определенную как long long int. Код также может быть определен как long long int (или он может использовать приведение перед выполнением умножения). Исправления отмечены в комментариях. Я не знаю, должна ли сумма быть% q, поэтому я оставил ее как long long int value.

        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, который используется для объявления 64-битного целого числа в случае Visual Studio. Я не знаю о других компиляторах. Если long int составляет 32 бита, то это похоже на потенциальную проблему:

    fib = (first + second) % q;

, потому что first + second может суммироваться, чтобы быть отрицательным числом, а знак остатка будет таким же, как знак дивиденд. Отрицательные числа будут проблемой для кода сортировки радиуса, который вы используете. Объявление fib как unsigned int или long long int позволит избежать этой проблемы.

---

Что касается выбора базы, вероятно, было бы лучше иметь все логики c в контрсортировке, и переименуйте его в radix sort. Использование базы 2 ^ 8 и выполнение 4 проходов было бы быстрее (из-за подгонки счетчиков / индексов в кеше L1). Как я упоминал выше, и arr, и output должны быть объявлены как целые числа без знака. Направление сортировки по основанию будет меняться с каждым из 4 проходов: arr-> output, output-> arr, arr-> output, output-> arr, исключая необходимость копирования.

---

Другой Оптимизация представляет собой гибридную радикальную сортировку MSD (наиболее значимая ди git) / LSD (наименее значимая ди git) для массива, намного большего, чем весь кэш. Предполагая, что используется основание 2 ^ 8 == 256, затем на первом проходе создаются 256 логических бинов, каждый из которых затем помещается в кэш, а затем каждый из 256 логических бинов сортируется с использованием 3 проходов сортировки радиуса LSD. В моей системе (Intel 3770K, 64-разрядная версия Win 7 Pro) время сортировки 36 миллионов 32-разрядных целых чисел без знака сократилось менее чем на 6%, с 0,37 до 0,35 секунды, что является точкой убывающей отдачи.