Алгоритм структуры данных C #

Question

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

Q. У меня есть машина с 512 МБ / 1 ГБ оперативной памяти, и мне нужно отсортировать файл (XML или любой другой) размером 4 ГБ. Как я буду действовать? Какова будет структура данных и какой алгоритм сортировки я буду использовать и как?

Как вы думаете, это достижимо? Если да, то не могли бы вы объяснить?

Заранее спасибо!

Answer 1

Ответ, который может понадобиться интервьюеру, может быть, как вам удается эффективно отсортировать набор данных, который превышает системную память. Следующий раздел взят из Википедии :

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

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

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

Один из способов обойти эту проблему, который хорошо работает, когда сложные записи (например, в реляционной базе данных) сортируется по небольшому ключу поле, чтобы создать индекс в массив, а затем отсортировать индекс, а чем весь массив. (Сортированный версия всего массива может затем быть произведенным с одним проходом, читая из индекса, но часто даже это ненужный, так как отсортированный Индекс адекватен.) Потому что индекс намного меньше, чем весь массив, это может легко поместиться в памяти, где весь массив не будет, эффективно устранение проблемы замены диска. Эта процедура иногда называется "сортировка по тегам". [5]

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

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

Answer 2

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

Вот псевдокод:

function sortFile(file)
    if fileTooBigForMemory(file)
       pair<firstHalfOfFile, secondHalfOfFile> = breakIntoTwoHalves()
       sortFile(firstHalfOfFile)
       sortFile(secondHalfOfFile)
    else
       sortCharactersInFile(file)
    endif

    MergeTwoHalvesInOrder(firstHalfOfFile, secondHalfOfFile)
end

Два известных алгоритма, которые попадают в категорию «разделяй и властвуй»: сортировка слиянием и алгоритм быстрой сортировки Таким образом, вы можете использовать их для реализации.

Что касается структуры данных, может подойти массив символов, содержащий символы в файле. Если вы хотите быть более объектно-ориентированным, поместите его в класс с именем File:

class File {
    private char[] characters;
    //methods to access and mutate 'characters'
}

Answer 3

Разделите ваш файл на куски, которые помещаются в память. Сортируйте каждый кусок, используя быструю сортировку, и сохраните его в отдельный файл. Затем объедините файлы результатов, и вы получите свой результат.

Answer 4

В Guido van Rossum есть хороший пост blog , в котором есть что предложить. Помните, что код написан на Python.

Answer 5

Я бы использовал многоканальное слияние. Есть отличная книга под названием Управление гигабайтами , в которой показано несколько разных способов сделать это. Они также используются для сортировки на основе файлов, размер которых превышает объем физической памяти. Посмотрите на странице 240 довольно подробный алгоритм сортировки фрагментов на диске.

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

Скажем, у вас есть файл 4 ГБ, и вы хотите загрузить максимум 512 МБ. Это означает, что вам нужно разбить файл на минимум 8 блоков. Если вы не уверены, сколько дополнительных издержек будет использовать ваш тип, вы можете даже удвоить это число, чтобы быть безопасным до 16 кусков.

Затем 16 файлов сортируются по одному за раз в гарантированном порядке. Итак, теперь у вас есть отсортированные файлы в диапазоне 0-15.

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

Я использовал такую ​​систему в C # для сортировки больших коллекций спам-слов из электронных писем. Первоначальная система требовала, чтобы все они загружались в ОЗУ, чтобы отсортировать их и создать словарь для подсчета спама. Когда размер файла превысил 2 ГБ, структурам памяти требовалось 6 ГБ ОЗУ и более 24 часов на сортировку из-за подкачки и виртуальной машины. Новая система, использующая фрагмент выше, отсортировала весь файл менее чем за 40 минут. Это было впечатляющее ускорение для такого простого изменения.

Я играл с различными вариантами загрузки (1/4 системной памяти на чанк и т. Д.). Оказалось, что для нашей ситуации лучшим вариантом было около 1/10 системной памяти. Тогда у Windows было достаточно памяти для приличной буферизации файлового ввода-вывода, чтобы компенсировать увеличение файлового трафика. И машина осталась очень чувствительной к другим процессам, работающим на ней.

И да, мне очень нравится задавать подобные вопросы и в интервью. Просто чтобы посмотреть, могут ли люди мыслить нестандартно. Что вы делаете, когда вы не можете просто использовать .Sort () в списке?

Answer 6

вот один пример симуляции виртуальной памяти на C #

источник: http://msdn.microsoft.com/en-us/library/aa288465(VS.71).aspx

// indexer.cs
// arguments: indexer.txt
using System;
using System.IO;

// Class to provide access to a large file
// as if it were a byte array.
public class FileByteArray
{
    Stream stream;      // Holds the underlying stream
                        // used to access the file.
// Create a new FileByteArray encapsulating a particular file.
    public FileByteArray(string fileName)
    {
        stream = new FileStream(fileName, FileMode.Open);
    }

    // Close the stream. This should be the last thing done
    // when you are finished.
    public void Close()
    {
        stream.Close();
        stream = null;
    }

    // Indexer to provide read/write access to the file.
    public byte this[long index]   // long is a 64-bit integer
    {
        // Read one byte at offset index and return it.
        get 
        {
            byte[] buffer = new byte[1];
            stream.Seek(index, SeekOrigin.Begin);
            stream.Read(buffer, 0, 1);
            return buffer[0];
        }
        // Write one byte at offset index and return it.
        set 
        {
            byte[] buffer = new byte[1] {value};
            stream.Seek(index, SeekOrigin.Begin);
            stream.Write(buffer, 0, 1);
        }
    }

    // Get the total length of the file.
    public long Length 
    {
        get 
        {
            return stream.Seek(0, SeekOrigin.End);
        }
    }
}

// Demonstrate the FileByteArray class.
// Reverses the bytes in a file.
public class Reverse 
{
    public static void Main(String[] args) 
    {
        // Check for arguments.
        if (args.Length == 0)
        {
            Console.WriteLine("indexer <filename>");
            return;
        }

        FileByteArray file = new FileByteArray(args[0]);
        long len = file.Length;

        // Swap bytes in the file to reverse it.
        for (long i = 0; i < len / 2; ++i) 
        {
            byte t;

            // Note that indexing the "file" variable invokes the
            // indexer on the FileByteStream class, which reads
            // and writes the bytes in the file.
            t = file[i];
            file[i] = file[len - i - 1];
            file[len - i - 1] = t;
        }

        file.Close();
    } 
}

Используйте приведенный выше код для прокрутки своего собственного класса массива. Тогда просто используйте любые алгоритмы сортировки массива.

Answer 7

Просто симулируйте виртуальную память, перегрузите оператор индекса массива, []

Найдите реализацию быстрой сортировки, которая сортирует массив в C ++ или C #. перегрузить оператор индексатора [], который будет читать и сохранять в файл. Таким образом, вы можете просто подключить существующие алгоритмы сортировки, вы просто измените то, что происходит за кадром на этих []