Сортировка большого 1 ГБ файла со 100-миллионным числом с использованием сортировки слияния

Моя задача - отсортировать 1GB-файл со 100 миллионами чисел, используя сортировку слияния без рекурсии. Моя идея состоит в том, чтобы разделить файл на 4 части, затем на 2 и в конце на один файл.

#include<iostream>
#include<fstream>
#include <cstdlib>
#include <vector>
#include <algorithm>
using namespace std;
std::vector <long> vec;

int i=0,numberOfpieces=0;
string line,filename;

//sorting and merge 2 files
void sort_merge(string result, string file1, string file2){ 

fstream wynik((result+".txt"), std::ios::out);

    string line, line2;
    long s1,s2;
    fstream sorted_1,sorted_2;
    sorted_1.open(file1+".txt");
    sorted_2.open(file2+".txt");

    getline(sorted_1,line);
    s1=atol(line.c_str());
    getline(sorted_2,line2);
    s2=atol(line2.c_str());

    do
    {
        if(s1==s2)
        {
            wynik<<s1<<endl;
            getline(sorted_1,line);
            s1=atol(line.c_str());
            getline(sorted_2,line2);
            s2=atol(line2.c_str());
        }
        if(s1<s2)
        {
            wynik<<s1<<endl;
            getline(sorted_1,line);
            s1=atol(line.c_str());
        }
        if(s1>s2)
        {
            wynik<<s2<<endl;
            getline(sorted_2,line2);
            s2=atol(line2.c_str());
        }
        if(sorted_1.eof())
        {
            do
            {
                wynik<<s2<<endl;
                getline(sorted_2,line2);
                s2=atol(line2.c_str());

            }
            while(!sorted_2.eof());
            break;
        }

        if(sorted_2.eof())
        {
            do
            {
                wynik<<s1<<endl;
                getline(sorted_1,line);
                s1=atol(line.c_str());
            }
            while(!sorted_1.eof());
        }

    }
    while (!sorted_1.eof() ||!sorted_2.eof());}


int main()
{
    fstream file;
    file.open("file.txt");
    if (file.good() == true )
    {
        do
        {
            for(i=1;i<=25000000;i++){ //splittining file into 4 pieces
            getline(file,line);
            vec.push_back(atol(line.c_str()));
            if(file.eof()){ //in case of last piece when quantity of numbers is less than 50
                break;
            }
            }
            sort(vec.begin(), vec.end() );//sorting vector
            std::string nm = std::to_string(numberOfpieces); //creating indyvidual name for piece
            filename="sorted_piece_"+nm+".txt";
            fstream sorted_piece(filename, std::ios::out);

            for ( auto &i : vec ) { //saving into file
                sorted_piece<< i <<endl;
            }

            numberOfpieces++;
            vec.clear();
        }
        while ( !file.eof() );
    }
string outFile;
string sorted1;
string sorted2;
int j=0,counti=0;

for(j=0;j<numberOfpieces;j+=2){//merging into 2 pieces
    std::string j1 = std::to_string(j);
    std::string j2 = std::to_string(j+1);
    std::string c = std::to_string(counti);
    outFile=c+"_sorted_piece";
    sorted1="sorted_piece_"+j1;
    sorted2="sorted_piece_"+j2;
    sort_merge(outFile,sorted1,sorted2);
    counti++;
}
outFile=numbersSorted;
sorted1=1_sorted_piece;
sorted2=2_sorted_piece;
sort_merge(outFile,sorted1,sorted2);//merging into 1 piece

return 0;
}

К сожалению, он медленный, и я точно не знаю, что это лучший способ его улучшить, потому что векторная сортировка имеет \ $ O (nlog (n)) \ $ сложность. Кроме того, мой алгоритм слияния двух файлов имеет \ $ O (n) \ $ сложность. Возможно, разделение на файлы занимает слишком много времени, но я не могу удерживать векторы, которые слишком длинны в ОЗУ.

30 голосов | спросил Adrian Wąt 21 J0000006Europe/Moscow 2017, 16:30:57

10 ответов


54

Не делайте этого

using namespace std;

Это плохая привычка, которая вызовет у вас много неприятностей. Пожалуйста, сломайте привычку, прежде чем она станет укорененной.

см. Почему «использование пространства имен std» считается плохой практикой?

Примечание. Причина, по которой «стандартная» библиотека использует пространство имен std::, заключается в том, что в качестве префикса не является большой нагрузкой.

Предпочитает '\n' над std::endl

Другие говорили об этом. Проблема заключается в том, что std::endl выполняет сброс потока (в дополнение к добавлению '\n'), в результате это делает использование потока очень неэффективным, поскольку вы нужно дождаться, чтобы записать каждое значение на диск, прежде чем продолжить.

Позвольте системе сбросить свой собственный внутренний буфер в оптимальное время. Он сделает это автоматически без какой-либо помощи.

Значение чтения

Я вижу, что вы не используете стандартный поток для преобразования целых чисел.

long value;
stream >> value;

, но, скорее, используя линейный считыватель, чем с помощью atol(), чтобы преобразовать строку в число.

Я предполагаю, что вы сделали соответствующие тесты скорости и обнаружили, что это быстрее в используемом вами масштабе, и вам не нужны все возможности, которые предоставляет оператор operator>>.

Если это правда, я бы завершил этот вызов, чтобы вы могли использовать atol() и operator>>, чтобы сделать ваш код более читаемым.

struct Number
{
    long value;
    static std::string  reusableBuffer;
    operator long() const {return value;}
    friend std::istream& operator>>(std::istream& str, Number& data) {
        std::getline(str, data.reusableBuffer);
        data.value = std::atol(data.reusableBuffer);
        return str;
    }
};

Теперь вы можете читать числа с помощью оператора operator>>, но все еще иметь скорость, которую вы подтвердили с помощью atol().

Никогда не проверяйте eof в цикле

while (!sorted_1.eof() ||!sorted_2.eof());}

Проблема заключается в том, что если в потоке есть ошибка, то вы попадаете в бесконечный цикл (если есть ошибка чтения из потока, она переходит в плохое состояние, пока вы не сбросите его. он откажется читать больше значений и, таким образом, никогда не достигнет конца файла.

Вместо того, чтобы тестировать eof(), вы должны проверить, чтобы поток был good() (если он достигает eof() или error(), тогда он больше не будет good(), чтобы ваш цикл все равно выходил правильно).

Простой способ проверить good() - просто использовать поток в булевом контексте (выражение, которое должно быть bool), и компилятор преобразует поток в bool, результаты которого в вызове good().

while(sorted_1 || sorted_2);

Объединить, я думаю, можно упростить.

Я думаю, что мы можем упростить этот алгоритм слияния.

Number number;
if (sorted1 >> number) {
    sorted1Value = number;
}
if (sorted2 >> number) {
    sorted2Value = number;
}
while (sorted1 && sorted2) {
    // Don't need to explicitly test if they are equal.
    // If they are equal always use the sorted1 file.
    // that way you get a stable sort (an important property for
    // sorted values in some situations).
    //
    // It also makes the code simpler.
    if (sorted1Value <= sorted2Value) {
        result << sorted1Value << "\n";
        sorted1 >> number;
        sorted1Value = number;
    }
    else {
        result << sorted2Value << "\n";
        sorted2 >> number;
        sorted2Value = number;
    }
}
// At this point one of the streams is empty.

Скопируйте один файл вдругой.

Когда вы объединили все значения из одного файла. Затем остальные числа из другого файла просто копируются в пункт назначения. Но нет необходимости тратить дополнительное время на преобразование этих чисел из текста в целое число, а затем обратно в текст. Просто скопируйте необработанные данные из одного файла в другой.

// At this point one of the streams is empty.
if (stream1) {
    result << sorted1Value;
    result << stream1.rdbuf()
}
if (stream2) {
    result << sorted2Value;
    result << stream2.rdbuf()
}

Промежуточный формат

Таким образом, промежуточные файлы не должны быть в удобочитаемой форме. Вы тратите много времени на преобразование целых чисел в текст и из него. Вместо этого вы можете записать двоичное представление числа в промежуточный файл и затем прочитать его обратно обратно в число при слиянии.

// writing
result.write(reinterpret_cast<char*>(&sorted1Value), sizeof(sorted1Value));

// reading
stream1.read(reinterpret_cast<char*>(&sorted1Value), sizeof(sorted1Value));

Объединение нескольких файлов.

В настоящее время вы выполняете операцию слияния 3 раза. Один раз объединить части 1 и 2 во временный файл. Затем вы объединяете 3 и 4 во второй временный файл и, наконец, объединяете временные файлы в выходной файл.

Слияние из разных потоков не настолько интенсивно. Таким образом, вы должны читать все временные файлы одновременно (в пределах до тех пор, пока у вас есть менее тысячи файлов деталей).

Итак, вы должны открыть все 4 файла temp и прочитать значения из них. Каждая итерация находит наибольшее значение из каждого из 4-х файлов, записывая это на выход и считывая следующее значение.

Глобальное состояние.

Глобальное состояние

std::vector <long> vec;

int i=0,numberOfpieces=0;
string line,filename;

Всегда считается плохой. Никогда не используйте его. Вы все равно можете получить такую ​​же эффективность, используя локальные значения в соответствующих местах.

Одна вещь, которую вы хотите сделать для повышения эффективности std::vector, заключается в том, чтобы зарезервировать ее размер. Таким образом, никогда не нужно перераспределять (что дорого).

vec.reserve(25000000);

Обратите внимание, что использование <= в цикле for очень необычно.

for(i=1;i<=25000000;i++)

Обычно это записывается как:

for(i = 0; i < 25000000; ++i)

Это потому, что индексы в массивы (векторы) всегда начинаются с нуля.

ответил Martin York 21 J0000006Europe/Moscow 2017, 19:12:04
46

Избегайте std::endl

По крайней мере, на первый взгляд, похоже, что вы сделали самый большой грех в C ++ относительно скорости ввода-вывода файлов: вы использовали std::endl, где все, что вы действительно хотел быть новой строкой ('\n').

Я не тестировал ваш конкретный код, но прошлый опыт показывает, что просто запись «\ n» вместо endl для завершения строки сама по себе значительно улучшит скорость вашего кода.

Увеличить размер прогона

Как только вы избавились от преждевременной пессимизации, следующий большой шаг в создании сортировки слияния будет выполняться как можно быстрее, чтобы максимизировать размеры отдельных создаваемых вами прогонов (где «прогон» является одним из промежуточных файлов , удерживая часть ввода в отсортированном порядке, который затем будет объединен для получения окончательного вывода).

Чтобы максимизировать размер выполнения, обычно запускать , считывая столько данных, сколько вы можете в выделенном объеме памяти. Затем вместо полной сортировки вы создаете кучу (например, с помощью std::make_heap). Затем возникает сложная часть: каждый раз, когда вы записываете значение на выход, вы читаете другое значение со входа. Затем вы проверяете, превышает ли это значение, которое вы только что выписали или нет. Если он больше, он все равно может перейти в текущий прогон, поэтому вы вставляете его в свою кучу и продолжаете.

Когда вы сталкиваетесь с чем-то меньшим, чем то, что уже было записано (поэтому его нельзя записать в текущий прогон), вы оставляете значение в верхней части памяти, а ваша текущая куча сжимается на один элемент.

Когда ваша текущая куча пуста, вы затем повторяете процесс: создайте кучу значений, которые вы читаете, и оставите их в верхней части памяти, и начните запись следующего прогона, считая следующее значение, вставив его, если возможно, и т. д.

Предполагая, что ваш вход в случайном порядке, это обычно позволяет приблизительно удвоить длину промежуточных прогонов, поэтому вам нужно всего лишь выполнить примерно половину слияния.

Однако довольно часто приходится иметь вход, который уже содержит некоторые пробеги чисел в отсортированном порядке. Когда /если это произойдет, это позволит вам воспользоваться преимуществами ранее существовавших заказов для повышения производительности (до такой степени, что если вход уже был полностью отсортирован, это «распознает» это и будет производить полностью отсортированный вывод за один цикл копирования вход для вывода, и это сделано.

Вам действительно нужен сортировка слияния?

100 миллионов целых 4 байта занимают чуть меньше 400 мегабайт оперативной памяти. Даже довольно устаревшая машина теперь будет иметь как минимум 4 гигабайта оперативной памяти, поэтому, если вы просто прочитали весь ввод в память, отсортировали ее и записали, вы использовали бы только 10% доступной памяти. Даже мой полу-устаревший (3-летний) сотовый телефон имеет 3 гигабайта оперативной памяти, поэтому даже в этом случае эта стратегия может быть вполне разумной.

Чтобы действительно оправдать использование сортировки слияния, нам просто нужно написать гораздо более обобщенную программу сортировки, которая фактически может использоваться на входах, которые превышают доступную память. Если вам действительно нужна сортировка слияния, мой совет будет заключаться в том, чтобы обобщить ее, по крайней мере, в какой-то степени - если вы будете хранить только 25 миллионов предметов в памяти сразу, это нормально - но, по крайней мере, обрабатывайте их до тех пор, пока вы не достигнете конец ввода, а не слепо предположить, что их может быть только 4.

ответил Jerry Coffin 21 J0000006Europe/Moscow 2017, 17:04:15
30
  1. Не используйте using namespace std; в глобальной области, это плохая привычка. Если вам действительно не нравится писать std:: снова и снова, тогда поместите его в область функций, где это необходимо. Но даже тогда избежать импорта целых пространств имен и вместо этого импортировать только определенные идентификаторы.

  2. Отступ не является согласованным, это может быть ошибка копирования-вставки, но это отвлекает.

  3. Проверьте верхнюю границу чисел. Если это менее 2 миллиардов (2 000 000 000), вы можете использовать int как векторный тип, уменьшая вдвое потребность в памяти.

  4. Зачем использовать глобальные переменные для вектора, строки, имени файла и т. д.? В этом нет необходимости.

  5. reserve() вектор, чтобы он не перераспределялся.

  6. Не храните номера внутри временных файлов в виде текста. Анализ текста медленнее, чем чтение байтов.

  7. Не используйте endl; что приведет к отключению выхода на выходе, когда это не должно произойти. Вместо этого просто напишите \n.

ответил ratchet freak 21 J0000006Europe/Moscow 2017, 17:16:52
11

Используйте свои знания о домене

Вы можете сравнивать числа без их разбора, вместо этого работая со строками. Сначала сравните знаковые знаки (если они есть), затем пропустите ведущие нули, затем сравните длину значимой части и только затем выполните сравнение (string).

Возможно, вы опустите некоторые из вышеперечисленных шагов, если знаете, что числа никогда не имеют ведущих нулей или всегда являются одним и тем же знаком - воспользуйтесь ограничениями, которые вы знаете!

Если вы знаете максимальную длину строки, вы можете прочитать в массив символов фиксированного размера вместо строки на фазе слияния.

Знайте свою стандартную библиотеку

Вместо переопределения слияния, почему бы не использовать std::merge() из <algorithm>? Вам нужны подходящие входные и выходные итераторы, но их легко организовать.

ответил Toby Speight 21 J0000006Europe/Moscow 2017, 19:28:01
6

Поскольку многие из нарушений уже были хорошо описаны в других ответах [1] [2] , Я прибегну к просто перечислению тех, которые сразу поражают меня:

  • Не компилируется на некоторых платформах из-за того, что он не включает все, что он использует (заголовок string в этом случае)
  • Не компилируется из-за некорректных numbersSorted, 1_sorted_piece и 2_sorted_piece
  • using namespace std;
  • Ненужные глобальные переменные
  • Ненужное прохождение параметров по значению
  • Неосторожное и непоследовательное отступы
  • Несколько плохой выбор имен функций и параметров. например Я бы предпочел что-то вроде

    void merge_files(std::string const& src1_filename
        , std::string const& src2_filename
        , std::string const& result_filename)
    
  • Плохое структурирование кода, малое повторное использование, много повторений, слишком сложные функции.
  • eof проверка
  • Ненужное использование std::endl
  • Не reserve - вектор, даже если вы знаете размер вперед
  • Магический номер (например, 25000000). Если мы будем жестко кодировать это, ожидаем ровно 100 миллионов номеров, я ожидаю, что для константы VALUE_COUNT ожидаемое количество, а вместо магического числа - выражение, использующее эту константу.
    • Написанный таким образом, который трудно разобрать для человека - я бы предпочел написать это значение как (25 * 1000 * 1000), так как сразу видно, что это 25 миллионов, и любой достойный компилятор будет выполнять этот расчет во время компиляции, поэтому нет никакой разницы в производительности.

Итак, давайте посмотрим на постановку проблемы:

  

Моя задача - сортировать 1GB-файл со 100 миллионами чисел, используя сортировку слияния без рекурсии.

Это выглядит как упражнение, поэтому, похоже, мы должны придерживаться требований.

  1.   

    сортировать 1GB файл со 100 миллионами номеров

    В этом не хватает некоторых деталей, но мы можем предположить, что это текст со средним значением 10 символов на номер. По меньшей мере один символ является разделителем, который дает нам в среднем 9 цифр на число, поэтому вполне можно предположить, что они находятся в диапазоне 32-битного целого числа.

    До сих пор так хорошо, хотя ваш код ввода мог иметь некоторую лучшую обработку ошибок и предоставлять осмысленные сообщения об ошибках, когда вход не соответствует вашим ожиданиям.

    Однако я думаю, что вы чрезмерно пессимистичны с необходимостью объединить файлы - как упоминалось в другом ответе , 100 миллионов 32-битных целых чисел принимают ~ 380 MiB, поэтому это не должно быть проблемой, связанной с этим временным буфером в адресном пространстве на большинстве существующих аппаратных средств. В этом случае я бы сохранил все просто и придерживался трехэтапного процесса - ввода, сортировки, вывода.

    Как таковой, я ожидал бы увидеть как минимум 3 функции, по одному для каждого из этих шагов.

  2.   

    с использованием сортировки слияния без рекурсии

    Для меня это требует итеративной реализации сортировки слияния и IMHO, даже если вы сделали некоторую попытку, выполнив 2 слияния верхнего уровня, вы потерпели неудачу здесь, поскольку вы используете стандартный sort на 25 миллионов значений.

    Итак, вернемся к как работает сортировка слияния :

      

    Концептуально сортировка слияния работает следующим образом:

         
    • Разделите несортированный список на n подписок, каждый из которых содержит 1 элемент (список из 1 элемента считается отсортированным).

    •   
    • Неоднократно объединять подсписчики для создания новых отсортированных подсписок до тех пор, пока не останется только 1 подписок. Это будетотсортированный список.

    •   

    Чтобы выполнить это итеративно, мы берем подход «снизу вверх». Мы можем концептуально относиться к нашему вектору целых чисел как к последовательности отсортированных подпоследовательностей (изначально длины 1 и с возможностью того, что последняя подпоследовательность короче остальных). Мы выполняем несколько проходов слияния, объединяя пары смежных подпоследовательностей:

    • Через 1 проход мы имеем список отсортированных подпоследовательностей длины 2
    • Через 2 прохода мы имеем список отсортированных подпоследовательностей длины 4
    • Через 3 прохода мы имеем список отсортированных подпоследовательностей длины 8
    • ...

    Здесь я ожидал бы увидеть, по крайней мере, функцию, которая выполняет один проход слияния с использованием заданной длины подпоследовательности, а также основную функцию сортировки, которая выполняет итерации проходов. Использование std::merge казалось бы законным подходом - если нет, то я уверен, что реализация уже обсуждена достаточно, так что нет необходимости в этом разбираться.

    Я думаю, что достойная реализация одного прохода слияния может выглядеть примерно как

    template<typename InputIt, typename OutputIt>
    void merge_pass(InputIt const& src_begin
        , InputIt const& src_end
        , OutputIt const& tgt_begin
        , std::size_t step_size)
    {
        InputIt input(src_begin);
        OutputIt output(tgt_begin);
    
        std::size_t const iter_count(std::distance(src_begin, src_end) / (step_size * 2));
        for (std::size_t i(0); i < iter_count; ++i) {
            InputIt const midpoint(std::next(input, step_size));
            InputIt const endpoint(std::next(midpoint, step_size));
    
            std::merge(input, midpoint, midpoint, endpoint, output);
    
            std::advance(input, step_size * 2);
            std::advance(output, step_size * 2);
        }
    
        // Handle the remainder
        std::size_t const remaining(std::distance(input, src_end));
        if (remaining > step_size) {
            // Second block is incomplete
            InputIt const midpoint(std::next(input, step_size));
    
            std::merge(input, midpoint, midpoint, src_end, output);
        } else if (remaining > 0) {
            // Second block is missing, the rest is already sorted
            std::copy(input, src_end, output);
        }
    }
    

    Теперь функция драйвера может выглядеть как

    template<typename T>
    void merge_sort(std::vector<T>& v)
    {
        uint32_t const PASS_COUNT(static_cast<uint32_t>(std::ceil(std::log2(v.size()))));
    
        std::vector<T> temp(v.size());
        for (uint32_t pass(0); pass < PASS_COUNT; ++pass) {
            merge_pass(v.begin(), v.end(), temp.begin(), 1 << pass);
            temp.swap(v); // NB: Swap is cheap
            // Now v contains sorted sub-sequences of double the size
            // and temp contains the old state, which we no longer care about
            // so we can overwrite it in the next iteration
        }
    }
    

    Сравнивая это, вы увидите, что этот алгоритм примерно в 2-3 раза медленнее стандартной сортировки. Учитывая простоту, это неплохо, и я считаю это вполне приемлемым.

Live Sample на Coliru

ответил Dan Mašek 26 J0000006Europe/Moscow 2017, 04:17:26
6

Ваш основной раздел должен быть разбит на более мелкие функции. У вас есть подробные сведения о том, как делается шаг, а затем другой совершенно другой шаг. На этом уровне я хочу написать резюме того, что делает , а не глубокие детали. У меня возникает ощущение, что единственная причина, по которой вы создали функцию sort_merge, - это значит, что вы можете ее вызывать более одного раза - иначе вы бы просто вспахали через , что , а также .

Существует ли функция на уровне один абстракции. Вы мысленно придумали разные шаги. Поэтому заставьте код отразить это. Это трудно объяснить, но здесь самый важный урок .


void sort_merge(string result, string file1, string file2){ 

Почему вы передаете строки по значению ? Нет необходимости копировать их.
const string& result и т. д.

Вам сказали не использовать директиву using в глобальной области. Но не делайте этого внутри каждой функции! Вместо этого перечислите то, что вы будете часто использовать в этом файле cpp (но not в файле .h) сразу после #includes. Например.

using std::string;
using std::cout;

s2=atol(line2.c_str());

Используйте более современные функции lexical_cast!

auto s2= lexical_cast<long>(line2);

, и вы также увидите, что вы инициализируете, где вы заявляете! Не используйте локальную переменную long s1,s2; вверху вверх, а затем сначала используйте их позже. И, определите только одну переменную за оператор.

А, но зачем читать строку string , а затем конвертировать в long, когда fstream может просто читать длинный непосредственно ?


if (file.good() == true )

Не делайте явные тесты против true! Itâ € ™ s уже bool, так зачем вам нужен еще один тест, чтобы быть уверенным, что true == true? Это просто глупо. Условие принимает значение bool - для него не требуется сравнение верхнего уровня как часть синтаксиса.

if ((file.good() == true ) == true)

нет конца этому! Просто

if (file.good())

Или еще лучше, использовать встроенный тест правды в комплекте для оптимизации этого точного случая:

if (file)

В этом случае eof отличается, но подумайте об этом: это обычный способ. Вы пытаетесь читать, и это терпит неудачу. Вам не нужно проверять наличие eof перед .

ответил JDługosz 22 J0000006Europe/Moscow 2017, 08:44:45
2

Основная идея полностью неверна. Разделение файла на 4, а затем слияние на 2, а затем 1 точно ничего не делает, если части не отсортированы, что вы, вероятно, не можете выполнить в памяти с объемом данных, которые у вас есть. И двухстороннее слияние - наименее эффективный способ слияния.

Это не в первую очередь кодирование. Речь идет о минимизации количества проходов над внешними данными. Это хорошо изученный предмет примерно за последние 60 лет. Дональд Кнут посвятил Том III «Искусство программирования» . I strong предлагает вам прочитать его,

В обложке вы должны:

  1. Распространять начальные пробеги с помощью замены.
  2. Выполнять сбалансированное или многофазное слияние этих файлов повторно, используя стандартные алгоритмы, которые уже существуют для этой цели. Посмотрите их.
ответил user207421 22 J0000006Europe/Moscow 2017, 06:19:49
2

Вы видели библиотеку STXXL ? Это облегчит вам выбор, поскольку он поддерживает внешнее ядро, используя stxxl::sort(...). Вам не нужно ничего делать, кроме загрузки больших чисел в соответствующий контейнер.

ответил sam juan 22 J0000006Europe/Moscow 2017, 22:18:09
0

Если все числа являются уникальными 32-разрядными положительными целыми числами, вы можете легко отсортировать числа в памяти:

1) выделите массив бит в памяти из 2 ^ 32 записей: (2 ^ 32/8) байтов, затем очистите его до нулей

2) преобразовать каждое входное число в индекс битового массива и установить соответствующий бит в массиве

3) после того, как все входные номера обработаны, выведите числа, соответствующие установленным элементам бит-бита, по порядку из массива

Но это, вероятно, чрезмерное упрощение вашей проблемы!

(Строго говоря, вышесказанное представляет собой «сортировку распределения /ведра»)

ответил MikeW 5 J000000Wednesday17 2017, 17:05:38
-1

Z-Tree - это новая структура структуры данных при разбиении и ветвлении битов. С Z-Tree вы можете отсортировать файл объемом 1 ГБ в памяти с временной сложностью O (n). Гораздо быстрее, чем сортировка слияния.

ответил Pegasus 12 thEurope/Moscowp30Europe/Moscow09bEurope/MoscowTue, 12 Sep 2017 02:54:31 +0300 2017, 02:54:31

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132