найти абсолютные значения для каждого целочисленного значения в файле

Question

В ответ на недавнее интервью

Есть файл журнала, содержащий миллион целых чисел.Каждое целое число имеет длину 32 бита.Определенные целочисленные значения в файле журнала могут повторяться.Вы можете прочитать файл журнала последовательно.Вы также можете читать и записывать во временные файлы последовательно;Нет ограничений на количество файлов, которые могут быть открыты в любое время.Однако вы можете хранить в памяти не более 2000 целых чисел в любой момент времени.

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

Answer 1

Это запутанный вопрос.Разве вы не можете просто прочитать 2000 чисел, отсортировать их, а затем записать во временный файл?Сделайте это 500 раз, а затем выполните N-way слияние.Каждое число будет загружено в память дважды.

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

Answer 2

Открыть 2 ³² временных файлов, по одному на каждое целое число. Прочитайте последовательно через файл журнала один раз. Всякий раз, когда вы читаете целое число n , пишите '1' во временный номер файла n . Затем создайте гистограмму, просматривая все временные файлы. Каждое целое число считывается в память только один раз, поэтому это алгоритм O (n).

Answer 3

Реализация B-дерева на основе файла.

Имена файлов - это GUID.

Содержимое файла: число видимых счетчиков файл левого узла файл правого узла

После одного прохода сложность может быть получена из сложности B-дерева.

И ваша историграмма неявно присутствует в структуре.

Answer 4

1. Хранить в памяти 2000 int = размер буфер

2. Нет ограничений для файлов для чтения / записи = каждый счетчик чисел будет сохранен в одном файле.

3. Числа длиной 32 бита = Каждый файл это одно число и имя файла это 32-битный, который представляет целое число (можно использовать целое значение а также)

4. Показать гистограмму (означает, что необходимо)

псевдокод:

count = 2000
HashMap<number, number> = new 

code:readbuffer
while count != 0 
read NextNumber
if HashMap.HasKey NextNumber then HashMap[NextNumber]++
else HashMap[NextNumber]=1
count --;
end while 

code:flushbuffer
foreach Key in HashMap 
 if exists FileName Key.ToBinnary 
  FileValue += HashMap[HashKey]
 else WriteNewFile FileName=Key.toBinnay; SetValue = 1
end foreach


code: histogram
each file name is the number;
each file value is the count. 

Расходы: readbuffer

Считанный порядковый номер = 2M (M = Миллион)

Map.HasKey = (поиск ключа в записи 2000 года, в худшем случае номера там нет, РЕЗЮМЕ (∑2000) x2M)

SetValue на карте та же стоимость, что и выше

Итого: (2M) + (2Mx∑2000) x2

Расходы: флешбуфер File.exists 2M

Расходы: гистограмма 2M

Всего = 6M + 4Mx∑2000