Вы оставили этот комментарий на свой вопрос:
«Напишите программу topN, для которой задано число N, и файл произвольно большого размера, содержащий отдельные числа в каждой строке (например, файл 200 ГБ), выведет наибольшие N чисел, начиная с самого высокого.»
Эта проблема мне кажется несколько отличной от описанной в вопросе, а также представляет собой более интересную проблему. Я рассмотрел эту проблему в этом ответе.
Код
def topN(fname, n, m=n)
raise ArgumentError, "m cannot be smaller than n" if m < n
f = File.open(fname)
best = Array.new(n)
n.times do |i|
break best.replace(best[0,i]) if f.eof?
best[i] = f.readline.to_i
end
best.sort!.reverse!
return best if f.eof?
new_best = Array.new(n)
cand = Array.new(m)
until f.eof?
rd(f, cand)
merge_arrays(best, new_best, cand)
end
f.close
best
end
def rd(f, cand)
cand.size.times { |i| cand[i] = (f.eof? ? -Float::INFINITY : f.readline.to_i) }
cand.sort!.reverse!
end
def merge_arrays(best, new_best, cand)
cand_largest = cand.first
best_idx = best.bsearch_index { |n| cand_largest > n }
return if best_idx.nil?
bi = best_idx
cand_idx = 0
nbr_to_compare = best.size-best_idx
nbr_to_compare.times do |i|
if cand[cand_idx] > best[bi]
new_best[i] = cand[cand_idx]
cand_idx += 1
else
new_best[i] = best[bi]
bi += 1
end
end
best[best_idx..-1] = new_best[0, nbr_to_compare]
end
Примеры
Давайте создадим файл с 10 миллионами представлений целых чисел, по одному на строку.
require 'time'
FName = 'test'
(s = 10_000_000.times.with_object('') { |_,s| s << rand(100_000_000).to_s << "\n" }).size
s[0,27]
#=> "86752031\n84524374\n29347072\n"
File.write(FName, s)
#=> 88_888_701
Затем создайте простой метод для вызова topN с различными аргументами, а также для отображения времени выполнения.
def try_one(n, m=n)
t = Time.now
a = topN(FName, n, m)
puts "#{(Time.new-t).round(2)} seconds"
puts "top 5: #{a.first(5)}"
puts "bot 5: #{a[n-5..n-1]}"
end
При тестировании я обнаружил, что установка m меньше n никогда не была желательной с точки зрения вычислительного времени. Требование, чтобы m >= n допускало небольшое упрощение кода и небольшое повышение эффективности. Поэтому я сделал m >= n требованием.
try_one 100, 100
9.44 seconds
top 5: [99999993, 99999993, 99999991, 99999971, 99999964]
bot 5: [99999136, 99999127, 99999125, 99999109, 99999078]
try_one 100, 1000
9.53 seconds
top 5: [99999993, 99999993, 99999991, 99999971, 99999964]
bot 5: [99999136, 99999127, 99999125, 99999109, 99999078]
try_one 100, 10_000
9.95 seconds
top 5: [99999993, 99999993, 99999991, 99999971, 99999964]
bot 5: [99999136, 99999127, 99999125, 99999109, 99999078]
Здесь я проверил случай получения 100 наибольших значений с различным количеством строк файла для чтения за раз m. Как видно, метод нечувствителен к этому последнему значению. Как и ожидалось, самые большие 5 значений и самые маленькие 5 значений (из 100 возвращаемых) одинаковы во всех случаях.
try_one 1_000
9.31 seconds
top 5: [99999993, 99999993, 99999991, 99999971, 99999964]
bot 5: [99990425, 99990423, 99990415, 99990406, 99990399]
try_one 1000, 10_000
9.24 seconds
Время, необходимое для возврата 1000 самых больших значений, фактически немного меньше, чем время для возврата самых больших 100. Я полагаю, что это не воспроизводимо. Лучшие 5, конечно, такие же, как и при возврате 100 самых больших значений. Поэтому я не буду отображать эту строку ниже. Наименьшее 5 значений из 1000 возвращенных, конечно, меньше, чем когда возвращаются самые большие 100 значений.
try_one 10_000
12.15 seconds
bot 5: [99898951, 99898950, 99898946, 99898932, 99898922]
try_one 100_000
13.2 seconds
bot 5: [98995266, 98995259, 98995258, 98995254, 98995252]
try_one 1_000_000
14.34 seconds
bot 5: [89999305, 89999302, 89999301, 89999301, 89999287]
Объяснение
Обратите внимание, что повторно используются три массива, best, cand и new_best. В частности, я заменяю содержимое этих массивов много раз, вместо того, чтобы постоянно создавать новые (потенциально очень большие) массивы, оставляя потерянные массивы для сбора мусора. Небольшое тестирование показало, что этот подход улучшил производительность.
Мы можем создать небольшой пример и затем выполнить вычисления.
fname = 'temp'
File.write(fname, 20.times.map { rand(100) }.join("\n") << "\n")
#=> 58
Этот файл содержит представления целых чисел в следующем массиве.
arr = File.read(fname).lines.map(&:to_i)
#=> [9, 66, 80, 64, 67, 67, 89, 10, 62, 94, 41, 16, 0, 22, 68, 72, 41, 64, 87, 24]
отсортировано, это:
arr.sort_by! { |n| -n }
#=> [94, 89, 87, 80, 72, 68, 67, 67, 66, 64, 64, 62, 41, 41, 24, 22, 16, 10, 9, 0]
Давайте предположим, что мы хотим 5 самых больших значений.
arr[0,5]
#=> [94, 89, 87, 80, 72]
Сначала задайте два параметра: n, количество самых больших возвращаемых значений и m, количество строк для чтения из файла за раз.
n = 5
m = 5
Расчет следующий.
m < n
#=> false, so do not raise ArgumentError
f = File.open(fname)
#=> #<File:temp>
best = Array.new(n)
#=> [nil, nil, nil, nil, nil]
n.times { |i| f.eof? ? (return best.replace(best[0,i])) : best[i] = f.readline.to_i }
best
#=> [9, 66, 80, 64, 67]
best.sort!.reverse!
#=> [80, 67, 66, 64, 9]
f.eof?
#=> false, so do not return
new_best = Array.new(n)
#=> [nil, nil, nil, nil, nil]
cand = Array.new(m)
#=> [nil, nil, nil, nil, nil]
puts "best=#{best}".rjust(52)
until f.eof?
rd(f, cand)
merge_arrays(best, new_best, cand)
puts "cand=#{cand}, best=#{best}"
end
f.close
best
#=> [94, 89, 87, 80, 72]
Отображается следующее.
best=[80, 67, 66, 64, 9]
cand=[94, 89, 67, 62, 10], best=[94, 89, 80, 67, 67]
cand=[68, 41, 22, 16, 0], best=[94, 89, 80, 68, 67]
cand=[87, 72, 64, 41, 24], best=[94, 89, 87, 80, 72]