En ce moment, jeExiste-t-il un meilleur moyen de trouver l'emplacement d'un élément minimum dans un tableau?
def min(array,starting,ending)
minimum = starting
for i in starting+1 ..ending
if array[i]<array[minimum]
minimum = i
end
end
return minimum
end
Y at-il une meilleure "mise en œuvre" en Ruby? Celui-ci semble toujours c-ish. Merci.
Si vous voulez trouver l'index de l'élément minimal, vous pouvez utiliser Enumerable#enum_for à obtenir un tableau de paires d'éléments-index, et trouver le minimum de ceux avec Enumerable#min (qui sera également le minimum de la matrice d'origine).
% irb
irb> require 'enumerator'
#=> true
irb> array = %w{ the quick brown fox jumped over the lazy dog }
#=> ["the", "quick", "brown", "fox", "jumped", "over", "the", "lazy", "dog"]
irb> array.enum_for(:each_with_index).min
#=> ["brown", 2]
Si vous voulez lié à des indices de tableau spécifiques:
irb> start = 3
#=> 3
irb> stop = 7
#=> 7
irb> array[start..stop].enum_for(:each_with_index).min
#=> ["fox", 0]
irb> array[start..stop].enum_for(:each_with_index).min.last + start
#=> 3
Ceci est l'algorithme standard pour trouver l'élément minimum dans un tableau, il peut être préférable de faire trier le tableau avant que cette fonction ne soit appelée.
Sinon, je ne peux pas trouver un moyen plus efficace de le faire. Plus précisément, le temps linéaire en notation O est le meilleur que nous pouvons faire.
Je suis désolé je voulais dire Y a-t-il une meilleure implémentation pour le même algorithme dans Ruby? – unj2
Si ce n'est pas simplement une question académique, pourquoi ne pas simplement utiliser la méthode sort native de Ruby? Il est implémenté en utilisant un algorithme quicksort, et est considéré comme assez rapide.
a = [3, 4, 5, 1, 7, 5]
a.sort![0] # => 1
Sur les «grandes» listes, cela va coûter beaucoup plus cher. O (n * log (n)) au lieu de O (n) –
Le temps augmente d'un facteur important et je ne peux pas intégrer le sous-programme dans une autre méthode comme Selection_Sort. – unj2
D'accord. Je pensais que, pour une raison ou pour une autre, il fallait que cela se produise. –
Fondamentalement, c'est le meilleur que vous pouvez faire, si vous pouvez écrire un peu plus succinctement:
def minval(arr)
arr.inject {|acc,x| (acc && acc < x ? acc : x)}
end
Je pense que l'OP voulait l'indice de la valeur minimale, plutôt que la valeur elle-même. Ce qui rend l'injection un peu plus difficile. –
Et, vous n'avez même pas besoin d'utiliser autre chose que: arr.min pour obtenir la valeur minimale. –
Bien que ce soit intelligent, je ne peux pas l'utiliser. – unj2
Il y a une façon plus simple et ça marche pour moi en Ruby 1.9.2:
a = [6, 9, 5, 3, 0, 6]
a.find_index a.min
Je pense que cela passera par le tableau deux fois ... – Agush
que voulez-vous signifie "mieux"? Plus efficace ou ce qui nécessite moins de lignes de code? – Rahul
Désolé, je voulais dire une meilleure implémentation dans ruby. – unj2