Tri d'un tableau de chaînes de caractères en Ruby

J'ai appris tableau deux méthodes de tri en Ruby:

array = ["one", "two", "three"]
array.sort.reverse!

ou:

array = ["one", "two", "three"]
array.sort { |x,y| y<=>x }

Et je ne suis pas en mesure de différencier entre les deux. Quelle méthode est la meilleure et comment exactement sont-ils différents dans l'exécution?

Ces poils d'une question. C'est la même méthode #sort, et pour la mise en œuvre deatils, n'hésitez pas à consulter code source C, ruby-doc.org/core-2.0/Array.html#method-i-sort.
Aparté: Si vous avez besoin d'un discbased en Ruby qui prend en charge la plupart des Énumérable les méthodes et les trie et stocke les données uniques, vous voudrez peut-être regarder à SortedSet.

InformationsquelleAutor poorvank | 2013-05-19

31

Les deux lignes d'en faire de même (créer un nouveau tableau, qui est l'inverse triés). L'argument principal est sur la lisibilité et la performance. array.sort.reverse! est plus lisible que array.sort{|x,y| y<=>x} - je pense que nous pouvons convenir ici.

Pour la performance de la partie, j'ai créé un rapide test de script, ce qui donne la suite sur mon système (ruby 1.9.3p392 [x86_64-linux]):
```
                              user     system      total        real
array.sort.reverse        1.330000   0.000000   1.330000 (  1.334667)
array.sort.reverse!       1.200000   0.000000   1.200000 (  1.198232)
array.sort!.reverse!      1.200000   0.000000   1.200000 (  1.199296)
array.sort{|x,y| y<=>x}   5.220000   0.000000   5.220000 (  5.239487)
```
Temps d'exécution sont assez constante pour plusieurs exécutions de l'indice de référence de script.

array.sort.reverse (avec ou sans !) est beaucoup plus rapide que array.sort{|x,y| y<=>x}. Donc, je recommande.

Voici le script de Référence:
```
#!/usr/bin/env ruby
require 'benchmark'

Benchmark.bm do|b|
  master = (1..1_000_000).map(&:to_s).shuffle
  a = master.dup
  b.report("array.sort.reverse      ") do
    a.sort.reverse
  end

  a = master.dup
  b.report("array.sort.reverse!     ") do
    a.sort.reverse!
  end

  a = master.dup
  b.report("array.sort!.reverse!    ") do
    a.sort!.reverse!
  end

  a = master.dup
  b.report("array.sort{|x,y| y<=>x} ") do
    a.sort{|x,y| y<=>x}
  end
end
```
- Un mineur de raffinement est de créer le tableau d'une époque: master = (1..1000000).map(&:to_s).shuffle et puis définissez a = master.clone avant chaque rapport de référence, de sorte qu'ils sont tous de tri exactement la même chose. J'ai aussi augmenté la taille de 1_000_000, et ajout d'une référence pour a.sort!.reverse!. Sur mon système (ruby 2.0.0p195 [x86_64-darwin12.3.0]) à l'aide sur place a.sort!.reverse! est sorti vainqueur.
- reverse! dans cette réponse, c'est gaspiller de l'UC. C'est en essayant de modifier un tableau temporaire créé lors de sort a remis son tableau, ce qui n'aide pas.
- quelque part DONC, j'ai une grande référence de tester différentes façons de faire un tri dans l'ordre décroissant. reverse est plus rapide que l'utilisation sort_by ou sort avec inversée ou annulés les résultats dans le bloc, ce qui nous a surpris. sort!.reverse! est plus rapide car sa mutation le tableau d'origine.
- le sens parfait pour moi. C'est pourquoi j'ai ajouté que la référence spécifique lorsque je l'ai essayé.
- J'ai appliqué votre suggestion. Il est intéressant de noter array.sort.reverse! est légèrement plus rapide pour 1.9.3.
- En regardant votre référence, il apparaît que vous avez changé l'étiquette, mais pas le code. Je pense que pour avoir un impact basé sur de l'Étain de raisonnement de l'Homme.
- Merci. Il y a un moment, quand il est trop tard pour écrire du code, et on doit mieux d'aller au lit 🙂
InformationsquelleAutor tessi
6

Il n'y a vraiment pas de différence ici. Les deux méthodes renvoient un nouveau tableau.

Pour les besoins de cet exemple, le plus simple est mieux. Je recommande array.sort.reverse car il est beaucoup plus lisible que l'alternative. En passant blocs de méthodes comme sort doit être enregistrée pour des tableaux plus complexes structures de données et les classes définies par l'utilisateur.

Edit: Tout destructive méthodes (tout se terminant par un !) sont bon pour la performance des jeux, il a été souligné qu'ils ne sont pas nécessaire pour retourner une mise à jour de tableau, ou quoi que ce soit d'ailleurs. Il est important de garder cela à l'esprit, car array.sort.reverse! pourrait très probablement de retour nil. Si vous souhaitez utiliser une méthode destructive sur un nouvellement généré tableau, vous devez préfère les appeler .reverse! sur une ligne distincte au lieu d'avoir un one-liner.

Exemple:
```
array = array.sort
array.reverse!
```
devrait être préféré à
```
array = array.sort.reverse!
```
- L'OP est juste l'apprentissage de Ruby et ne devrait pas être si anal sur la performance à ce stade. Je m'en tiens à ma recommandation.
- Il n'est jamais trop tôt pour apprendre à propos de la performance 🙂
- cependant l'appel destructeur inverse sur le Tableau temporaire créé avec tri précédent est une mauvaise pratique. Il n'est nulle part documenté reverse! doit retourner une mise à jour du tableau. Il a seulement mettre à jour l'objet appelé. Le premier est une tâche de la non-destructive version.
- Bon point! J'ai édité mon post pour refléter cela.
InformationsquelleAutor James Brewer
3

Inverse! est plus Rapide

Il n'y a souvent pas de substitut pour l'analyse comparative. Alors qu'il fait probablement pas de différence en plus courte, les scripts, le #inverse! la méthode est beaucoup plus rapide que le tri à l'aide de la "vaisseau spatial" de l'opérateur. Par exemple, sur l'IRM Ruby 2.0, et compte tenu de la référence ci-après code:
```
require 'benchmark'

array = ["one", "two", "three"]
loops = 1_000_000

Benchmark.bmbm do |bm|
    bm.report('reverse!')  { loops.times {array.sort.reverse!} }
    bm.report('spaceship') { loops.times {array.sort {|x,y| y<=>x} }}
end
```
le système vous signale que #inverse! est presque deux fois plus rapide que d'utiliser le combiné opérateur de comparaison.
```
                user     system      total        real
reverse!    0.340000   0.000000   0.340000 (  0.344198)
spaceship   0.590000   0.010000   0.600000 (  0.595747)
```
Mon conseil: utiliser celle qui est la plus sémantiquement pertinente dans un contexte donné, sauf si vous êtes en cours d'exécution dans une boucle serrée.
- C'est en fait un x-wing 🙂
InformationsquelleAutor Todd A. Jacobs
2

Comparaison avec d'aussi simple que votre exemple, il n'y a pas beaucoup de différence, mais comme la formule pour la comparaison devient compliqué, il est préférable d'éviter d'utiliser <=> avec un bloc parce que le bloc que vous transmettez seront évalués pour chaque élément du tableau, provoquant la redondance. Considérez ceci:
```
array.sort{|x, y| some_expensive_method(x) <=> some_expensive_method(y)}
```
Dans ce cas, some_expensive_method sera évaluée pour chaque paire possible de l'élément de array.

Dans votre cas particulier, l'utilisation d'un bloc avec <=> peut être évité avec reverse.
```
array.sort_by{|x| some_expensive_method(x)}.reverse
```
Ce qui est appelé Schwartzian transformer.
- Comment avez-vous "tri inverse" avec sort_by? Parce que c'est ce que l'OP est en train de faire.
- Ma réponse n'était pas assez bon. Je l'ai montée.
- Merci de m'indiquer le terme "Schartzian transformer" - ne connaissais pas ce modèle a un nom 🙂
InformationsquelleAutor sawa

En jouant avec tessi repères sur ma machine, j'ai obtenu quelques résultats intéressants. Je suis en cours d'exécution ruby 2.0.0p195 [x86_64-darwin12.3.0], c'est à dire, la dernière version de Ruby 2 sur un OS X système. J'ai utilisé bmbm plutôt que bm de l'indice de Référence du module. Mes horaires sont:

Rehearsal -------------------------------------------------------------
array.sort.reverse:         1.010000   0.000000   1.010000 (  1.020397)
array.sort.reverse!:        0.810000   0.000000   0.810000 (  0.808368)
array.sort!.reverse!:       0.800000   0.010000   0.810000 (  0.809666)
array.sort{|x,y| y<=>x}:    0.300000   0.000000   0.300000 (  0.291002)
array.sort!{|x,y| y<=>x}:   0.100000   0.000000   0.100000 (  0.105345)
---------------------------------------------------- total: 3.030000sec

                                user     system      total        real
array.sort.reverse:         0.210000   0.000000   0.210000 (  0.208378)
array.sort.reverse!:        0.030000   0.000000   0.030000 (  0.027746)
array.sort!.reverse!:       0.020000   0.000000   0.020000 (  0.020082)
array.sort{|x,y| y<=>x}:    0.110000   0.000000   0.110000 (  0.107065)
array.sort!{|x,y| y<=>x}:   0.110000   0.000000   0.110000 (  0.105359)

Tout d'abord, notez que dans la Répétition de la phase de sort! à l'aide d'un bloc de comparaison est le gagnant clair. Matz doit avoir réglé le diable hors de lui en Ruby 2!

L'autre chose que je trouve extrêmement bizarre était de savoir comment beaucoup d'amélioration array.sort.reverse! et array.sort!.reverse! exposées dans la production de passe. Il était tellement extrême, il m'a fait me demander si j'avais quelque vissé vers le haut et transmis ces données sont triées, j'ai donc ajouté explicite vérifie triés ou d'inversion de données triées avant d'effectuer chaque test.

Ma variante de tessi du script suit:

#!/usr/bin/env ruby
require 'benchmark'
class Array
def sorted?
(1...length).each {|i| return false if self[i] < self[i-1] }
true
end
def reversed?
(1...length).each {|i| return false if self[i] > self[i-1] }
true
end
end
master = (1..1_000_000).map(&:to_s).shuffle
Benchmark.bmbm(25) do|b|
a = master.dup
puts "uh-oh!" if a.sorted?
puts "oh-uh!" if a.reversed?
b.report("array.sort.reverse:") { a.sort.reverse }
a = master.dup
puts "uh-oh!" if a.sorted?
puts "oh-uh!" if a.reversed?
b.report("array.sort.reverse!:") { a.sort.reverse! }
a = master.dup
puts "uh-oh!" if a.sorted?
puts "oh-uh!" if a.reversed?
b.report("array.sort!.reverse!:") { a.sort!.reverse! }
a = master.dup
puts "uh-oh!" if a.sorted?
puts "oh-uh!" if a.reversed?
b.report("array.sort{|x,y| y<=>x}:") { a.sort{|x,y| y<=>x} }
a = master.dup
puts "uh-oh!" if a.sorted?
puts "oh-uh!" if a.reversed?
b.report("array.sort!{|x,y| y<=>x}:") { a.sort!{|x,y| y<=>x} }
end

InformationsquelleAutor pjs

Vous devez vous connecter pour publier un commentaire.

Inverse! est plus Rapide