Пока у меня есть этот код, который считывает файл и сортирует его с помощью Ruby. Но это неправильно сортирует числа, и я думаю, что это будет неэффективно, учитывая, что файл может быть размером до 200 ГБ и содержит число в каждой строке. Можете ли вы предложить, что еще можно сделать?

 File.open("topN.txt", "w") do |file|
  File.readlines("N.txt").sort.reverse.each do |line|
    file.write(line.chomp<<"n")
  end
End
 

После того, как все здесь помогут, вот как выглядит мой код до сих пор…

 begin

  puts "What is the file name?"
  file = gets.chomp

  puts "Whats is the N number?"
  myN = Integer(gets.chomp)

rescue ArgumentError

  puts "That's not a number, try again"
  retry
end

topN = File.open(file).each_line.max(myN){|a,b| a.to_i <=> b.to_i}
puts topN
 

Сортировка 200 ГБ данных в памяти будет не очень производительной. Я бы написал небольшой вспомогательный класс, который запоминает только N самых больших элементов, добавленных на данный момент.

 class SortedList
  attr_reader :list

  def initialize(size)
    @list = []
    @size = size
  end

  def add(element)
    return if @min amp;amp; @min > element

    list.push(element)
    reorganize_list
  end

  private

  def reorganize_list
    @list = list.sort.reverse.first(@size)
    @min = list.last
  end
end
 

Инициализируйте экземпляр с помощью require N и просто добавьте значения, проанализированные из каждой строки, в этот экземпляр.

 sorted_list = SortedList.new(n)

File.readlines("N.txt").each do |line|
  sorted_list.add(line.to_i)
end

puts sorted_list.list
 

Предположим

 str = File.read(in_filename)
  #=> "117n106n143n147n63n118n146n93n"
 

Вы можете преобразовать эту строку в перечислитель, который перечисляет строки, использовать Enumerable#sort_by для сортировки этих строк в порядке убывания, объединить полученные строки (которые заканчиваются символами новой строки), чтобы сформировать строку, которую можно записать в файл:

 str.each_line.sort_by { |line| -line.to_i }.join
  #=> "147n146n143n118n117n106n93n63n"
 

Другой способ — преобразовать строку в массив целых чисел, отсортировать массив с помощью Array#sort, перевернуть полученный массив, а затем объединить элементы массива обратно в строку, которую можно записать в файл:

 str.each_line.map(amp;:to_i).sort.reverse.join("n") << "n"
  #=> "147n146n143n118n117n106n93n63n"
 

Давайте проведем быстрый тест.

 require 'benchmark/ips'

(str = 1_000_000.times.map { rand(10_000) }.join("n") << "n").size

Benchmark.ips do |x|
  x.report("sort_by") { str.each_line.sort_by { |line| -line.to_i }.join }
  x.report("sort")    { str.each_line.map(amp;:to_i).sort.reverse.join("n") << "n" }
  x.compare!
end

Comparison:
                sort:        0.4 i/s
             sort_by:        0.3 i/s - 1.30x  slower
 

Могучий sort снова побеждает!

Вы оставили этот комментарий на свой вопрос:

«Напишите программу 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]
  #=> "86752031n84524374n29347072n"
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(amp;: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]
 

Enumerable.max принимает аргумент, который указывает, сколько элементов будет возвращено, и блок, который определяет, как сравниваются элементы:

 N = 5
p File.open("test.txt").each_line.max(N){|a,b| a.to_i <=> b.to_i}
 

При этом не считывается весь файл в памяти; файл считывается построчно.