Jusqu'à présent, j'ai ce code qui lit un fichier et le trie en utilisant Ruby. Mais cela ne trie pas correctement les nombres et je pense que ce sera inefficace, étant donné que le fichier peut atteindre 200 Go et contient un numéro sur chaque ligne. Pouvez-vous suggérer quoi faire d'autre?
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
Après que tout le monde ait aidé ici, voici à quoi ressemble mon code jusqu'à présent ...
File.open("topN.txt", "w") do |file|
File.readlines("N.txt").sort.reverse.each do |line|
file.write(line.chomp<<"\n")
end
End
4 Réponses :
Supposons
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(&: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
Vous pouvez convertir cette chaîne en un énumérateur qui énumère les lignes, utilisez Enumerable # sort_by pour trier ces lignes par ordre décroissant, joignez les lignes résultantes (qui se terminent par des retours à la ligne) pour former une chaîne qui peut être écrite file:
str.each_line.map(&:to_i).sort.reverse.join("\n") << "\n"
#=> "147\n146\n143\n118\n117\n106\n93\n63\n"
Une autre façon est de convertir la chaîne en tableau d'entiers, trier le tableau en utilisant Array # sort , inversez le tableau résultant, puis joignez les éléments du tableau dans une chaîne qui peut être écrite file:
str.each_line.sort_by { |line| -line.to_i }.join
#=> "147\n146\n143\n118\n117\n106\n93\n63\n"
Faisons un test rapide.
str = File.read(in_filename) #=> "117\n106\n143\n147\n63\n118\n146\n93\n"
Le puissant tri gagne à nouveau !
Hou la la! votre réponse est excellente même avec des repères. laissez-moi voir si je peux l'exécuter.
Im essayant de comprendre comment utiliser le benchmark sur mon code mis à jour car j'ai besoin de connaître la complexité du temps d'exécution / de l'espace.
Vous voyez comment j'ai utilisé le benchmark . Si vous mettez votre code dans une méthode, par exemple francisco , ajoutez simplement une ligne x.report ("sort_by") {francisco (str)} . Cela ne vous aidera cependant pas à déterminer la complexité du temps et de l'espace. Ces mesures sont obtenues à partir d'une analyse de votre code.
Le tri de 200 Go de données en mémoire ne sera pas très performant. J'écrirais une petite classe d'assistance qui ne se souvient que des N plus gros éléments ajoutés jusqu'à présent.
sorted_list = SortedList.new(n)
File.readlines("N.txt").each do |line|
sorted_list.add(line.to_i)
end
puts sorted_list.list
Initialisez une instance avec le require N et ajoutez simplement les valeurs analysées de chaque ligne à cette instance.
class SortedList
attr_reader :list
def initialize(size)
@list = []
@size = size
end
def add(element)
return if @min && @min > element
list.push(element)
reorganize_list
end
private
def reorganize_list
@list = list.sort.reverse.first(@size)
@min = list.last
end
end
intéressant ... quand j'ai fourni cette liste ... 15 7 25 1 9 3 45100 65 Le programme ne triera que les 5 premiers même si je mets N à 20 ou toute autre valeur ....
Oui, car j'ai initialisé mon exemple SortedList.new (5) avec 5 . Utilisez plutôt une variable pour votre N : SortedList.new (n) . J'ai mis à jour ma réponse.
Enumerable.max prend un argument qui spécifie le nombre d'éléments qui seront retournés, et un bloc qui spécifie comment les éléments sont comparés:
N = 5
p File.open("test.txt").each_line.max(N){|a,b| a.to_i <=> b.to_i}
Cela ne lit pas le fichier entier en mémoire; le fichier est lu ligne par ligne.
Merci pour votre réponse! cette ligne remplacera-t-elle l'un de mes codes d'origine? comment puis-je créer un programme en cours à partir de cette ligne unique?
@FranciscoCantu C'est maintenant un programme complet, avec une variable N et une sortie à l'écran.
Vous avez laissé ce commentaire sur votre question:
"Ecrivez un programme, topN, qui a donné un nombre N et un fichier arbitrairement volumineux contenant des nombres individuels sur chaque ligne (par exemple un fichier de 200 Go), produira les N nombres les plus grands , le plus élevé en premier. "
Ce problème me semble quelque peu différent de celui décrit dans la question, et constitue également un problème plus intéressant. J'ai abordé ce problème dans cette réponse.
Code
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]
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]
n = 5 m = 5
Créons un fichier avec 10 millions de représentations d'entiers, une par ligne. Ensuite, créez une méthode simple pour appeler Lors des tests, j'ai trouvé que définir Ici j'ai testé le cas de la production du Le temps nécessaire pour renvoyer les 1 000 valeurs les plus élevées est , en fait, un peu moins que les temps pour retourner le plus grand 100. Je suppose que ce n'est pas reproductible. Les 5 premiers sont bien sûr les mêmes que lors du renvoi des 100 plus grandes valeurs. Je n'afficherai donc pas cette ligne ci-dessous. Les 5 plus petites valeurs des 1000 renvoyées sont bien sûr plus petites que lorsque les 100 plus grandes valeurs sont renvoyées. Explication Notez que réutilisez trois tableaux, Nous pouvons créer un petit exemple, puis parcourir les calculs. Ce fichier contient des représentations d'entiers dans le tableau suivant. Trié, c'est: Supposons que nous voulons les 5 plus grandes valeurs. Tout d'abord, définissez les deux paramètres: Le calcul suit. Ce qui suit est affiché. arr[0,5]
#=> [94, 89, 87, 80, 72]
topN avec différents arguments et aussi afficher les temps d'exécution. 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]
m moins de n n'était jamais souhaitable en termes de calcul temps. Exiger que m> = n a permis une petite simplification du code et une petite amélioration de l'efficacité. J'ai donc fait de m> = n une exigence. 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]
100 code > les plus grandes valeurs avec un nombre différent de lignes du fichier à lire à la fois m . Comme on le voit, la méthode est insensible à cette dernière valeur. Comme prévu, les 5 valeurs les plus élevées et les 5 valeurs les plus petites (sur les 100 renvoyées) sont identiques dans tous les cas. fname = 'temp'
File.write(fname, 20.times.map { rand(100) }.join("\n") << "\n")
#=> 58
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 et new_best . Plus précisément, je remplace le contenu de ces tableaux plusieurs fois plutôt que de créer continuellement de nouveaux tableaux (potentiellement très volumineux), laissant les tableaux orphelins à récupérer. Un petit test a montré que cette approche améliorait les performances. 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
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]
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
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
n , le nombre de valeurs les plus élevées à renvoyer, et m , le nombre de lignes à lire à partir du fichier à la fois. 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
def rd(f, cand)
cand.size.times { |i| cand[i] = (f.eof? ? -Float::INFINITY : f.readline.to_i) }
cand.sort!.reverse!
end
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
Pouvez-vous donner un exemple de ligne contenant un nombre? Avez-vous vraiment besoin de réécrire le fichier? Ou simplement imprimer ce plus grand nombre?
Fondamentalement, la façon dont cela fonctionne est que chacun contiendra un numéro individuel, puis le lira et affichera d'abord le plus grand nombre.
que voulez-vous dire par le plus grand nombre en premier? qu'y a-t-il après? Pouvez-vous simplement montrer un exemple très basique de fichier d'entrée et de sortie attendu?
Le fichier ne contient que des chaînes bien sûr, mais elles peuvent représenter des nombres (
"123'," -43.78 "`). Sont-elles toutes des représentations d'entiers ou pourraient-elles être flottantes numéros de points?Ecrire un programme, topN, qui étant donné un nombre N et un fichier arbitrairement volumineux contenant des nombres individuels sur chaque ligne (par exemple un fichier de 200 Go), produira les N nombres les plus grands, les plus élevés en premier
Que signifie «cela ne trie pas les nombres correctement»? Comment seraient-ils triés correctement? Comment sont-ils mal triés? Pourquoi est-ce incorrect? Quel ordre utilisez-vous pour les trier?
Votre dernier commentaire suggère que votre problème est un peu différent de ce que vous avez décrit, en ce sens que le fichier est «arbitrairement» volumineux. Cela me laisse penser que vous devrez peut-être utiliser une procédure telle que celle décrite à la fin de ma réponse.