Y at-il une meilleure façon de trouver l'emplacement d'un élément minimum dans un tableau?

Question

En ce moment j'ai

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 encore c-ish. Merci.

Answer 1

Si vous voulez trouver l'index de l'élément minimal, vous pouvez utiliser pour Enumerable#enum_for obtenir un tableau de paires éléments-index, et de trouver le minimum de ceux qui ont Enumerable#min (qui sera également le minimum du tableau 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

Answer 2

En fait, 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

Answer 3

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

Answer 4

Ceci est l'algorithme standard pour trouver l'élément minimum dans un tableau, il peut être mieux en ayant déjà le tableau est trié avant que cette fonction est 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 grand O est le meilleur que nous pouvons faire.

Answer 5

Si ce n'est pas simplement une question académique, pourquoi ne pas simplement utiliser la méthode native de Ruby sort? Il est mis en œuvre en utilisant un algorithme de tri rapide, et est considéré comme assez rapide.

a = [3, 4, 5, 1, 7, 5]
a.sort![0] # => 1