Jak sprawdzić, czy wartość istnieje w tablicy w Ruby

Mam wartość 'Dog' i tablicę ['Cat', 'Dog', 'Bird'].

Jak sprawdzić, czy istnieje w tablicy bez zapętlania jej? Czy istnieje prosty sposób sprawdzenia, czy wartość istnieje, nic więcej?

Poszukujesz include?:

>> ['Cat', 'Dog', 'Bird'].include? 'Dog'
=> true

Jest in?metoda w ActiveSupport(część Rails) od v3.1, jak podkreślił @campaterson. Więc w Railsach lub jeśli możesz require 'active_support', możesz napisać:

'Unicorn'.in?(['Cat', 'Dog', 'Bird']) # => false

OTOH, w samym Rubimie nie ma inoperatora ani #in?metody, mimo że był on wcześniej proponowany, w szczególności przez Yusuke Endoh, czołowego członka rubinowego rdzenia.

Jak wskazano przez innych, sposobem odwróconej include?występuje dla wszystkich EnumerableS tym Array, Hash, Set, Range:

['Cat', 'Dog', 'Bird'].include?('Unicorn') # => false

Zauważ, że jeśli masz wiele wartości w tablicy, wszystkie zostaną sprawdzone jedna po drugiej (tj. O(n)), Podczas gdy wyszukiwanie skrótu będzie miało stały czas (tj O(1).). Jeśli więc tablica jest stała, na przykład dobrym pomysłem jest użycie zestawu . Na przykład:

require 'set'
ALLOWED_METHODS = Set[:to_s, :to_i, :upcase, :downcase
                       # etc
                     ]

def foo(what)
  raise "Not allowed" unless ALLOWED_METHODS.include?(what.to_sym)
  bar.send(what)
end

Szybkie badanie ujawnia, że dzwoniąc include?na 10 elementu Setwynosi około 3,5x szybciej niż nazywając ją na ekwiwalentArray (jeśli element nie zostanie znaleziony).

Ostatnia uwaga końcowa: bądź ostrożny przy użyciu include?na Range, są subtelności, więc zapoznaj się z dokumentem i porównaj z cover?...

Próbować

['Cat', 'Dog', 'Bird'].include?('Dog')

Użyj Enumerable#include:

a = %w/Cat Dog Bird/

a.include? 'Dog'

Lub, jeśli wykonano wiele testów, ¹ możesz pozbyć się pętli (która nawet include?ma) i przejść od O (n) do O (1) za pomocą:

h = Hash[[a, a].transpose]
h['Dog']

Jeśli chcesz sprawdzić przez blok, możesz spróbować any?lub all?.

%w{ant bear cat}.any? {|word| word.length >= 3}   #=> true  
%w{ant bear cat}.any? {|word| word.length >= 4}   #=> true  
[ nil, true, 99 ].any?                            #=> true  

Aby uzyskać więcej informacji, zobacz Wyliczalny .

Inspiracją dla mnie było „ oceń, czy tablica zawiera jakieś rubiny ”

Ruby ma jedenaście metod wyszukiwania elementów w tablicy.

Preferowanym jest include?lub, w celu wielokrotnego dostępu, utwórz Zestaw, a następnie zadzwoń include?lubmember? .

Oto wszystkie z nich:

array.include?(element) # preferred method
array.member?(element)
array.to_set.include?(element)
array.to_set.member?(element)
array.index(element) > 0
array.find_index(element) > 0
array.index { |each| each == element } > 0
array.find_index { |each| each == element } > 0
array.any? { |each| each == element }
array.find { |each| each == element } != nil
array.detect { |each| each == element } != nil

Wszystkie zwracają a true wartość ish, jeśli element jest obecny.

include?jest preferowaną metodą. Wykorzystuje forwewnętrznie pętlę języka C, która pęka, gdy element pasuje do rb_equal_opt/rb_equalfunkcji wewnętrznych . Nie może stać się o wiele bardziej wydajny, jeśli nie utworzysz zestawu do wielokrotnych kontroli członkostwa.

VALUE
rb_ary_includes(VALUE ary, VALUE item)
{
  long i;
  VALUE e;

  for (i=0; i<RARRAY_LEN(ary); i++) {
    e = RARRAY_AREF(ary, i);
    switch (rb_equal_opt(e, item)) {
      case Qundef:
        if (rb_equal(e, item)) return Qtrue;
        break;
      case Qtrue:
        return Qtrue;
    }
  }
  return Qfalse;
}

member?nie jest przedefiniowany w Arrayklasie i używa niezoptymalizowanej implementacji z Enumerablemodułu, która dosłownie wylicza wszystkie elementy:

static VALUE
member_i(RB_BLOCK_CALL_FUNC_ARGLIST(iter, args))
{
  struct MEMO *memo = MEMO_CAST(args);

  if (rb_equal(rb_enum_values_pack(argc, argv), memo->v1)) {
    MEMO_V2_SET(memo, Qtrue);
    rb_iter_break();
  }
  return Qnil;
}

static VALUE
enum_member(VALUE obj, VALUE val)
{
  struct MEMO *memo = MEMO_NEW(val, Qfalse, 0);

  rb_block_call(obj, id_each, 0, 0, member_i, (VALUE)memo);
  return memo->v2;
}

Przetłumaczone na kod Ruby robi to o:

def member?(value)
  memo = [value, false, 0]
  each_with_object(memo) do |each, memo|
    if each == memo[0]
      memo[1] = true 
      break
    end
  memo[1]
end

Zarówno include?imember? mają O (n) od złożoności przeszukaniu tablicę do pierwszego wystąpienia wartości oczekiwanej.

Możemy użyć Zestawu, aby uzyskać czas dostępu O (1) kosztem konieczności najpierw utworzenia reprezentacji Hash tablicy. Jeśli wielokrotnie sprawdzasz członkostwo w tej samej tablicy, ta początkowa inwestycja może się szybko zwrócić. Setnie jest zaimplementowany w C, ale jako zwykła klasa Ruby, wciąż czas dostępu O (1) instrumentu bazowego@hash sprawia, że ​​jest to opłacalne.

Oto implementacja klasy Set:

module Enumerable
  def to_set(klass = Set, *args, &block)
    klass.new(self, *args, &block)
  end
end

class Set
  def initialize(enum = nil, &block) # :yields: o
    @hash ||= Hash.new
    enum.nil? and return
    if block
      do_with_enum(enum) { |o| add(block[o]) }
    else
      merge(enum)
    end
  end

  def merge(enum)
    if enum.instance_of?(self.class)
      @hash.update(enum.instance_variable_get(:@hash))
    else
      do_with_enum(enum) { |o| add(o) }
    end
    self
  end

  def add(o)
    @hash[o] = true
    self
  end

  def include?(o)
    @hash.include?(o)
  end
  alias member? include?

  ...
end

Jak widać klasa Set po prostu tworzy @hashinstancję wewnętrzną , mapuje wszystkie obiekty, truea następnie sprawdza członkostwo za pomocąHash#include? którego jest implementowany czas dostępu O (1) w klasie Hash.

Nie będę omawiać pozostałych siedmiu metod, ponieważ wszystkie są mniej wydajne.

W rzeczywistości istnieje jeszcze więcej metod o złożoności O (n) powyżej 11 wymienionych powyżej, ale postanowiłem ich nie wymieniać, ponieważ skanują one całą tablicę, a nie psują się przy pierwszym dopasowaniu.

Nie używaj tych:

# bad examples
array.grep(element).any? 
array.select { |each| each == element }.size > 0
...

Sugeruje kilka odpowiedzi Array#include?, ale jest jedna ważna uwaga: patrząc na źródło, nawet Array#include?wykonuje pętlę:

rb_ary_includes(VALUE ary, VALUE item)
{
    long i;

    for (i=0; i<RARRAY_LEN(ary); i++) {
        if (rb_equal(RARRAY_AREF(ary, i), item)) {
            return Qtrue;
        }
    }
    return Qfalse;
}

Sposobem na sprawdzenie obecności słowa bez zapętlania jest zbudowanie trie dla tablicy. Istnieje wiele implementacji Trie (Google „Ruby Trie”). Użyję rambling-triew tym przykładzie:

a = %w/cat dog bird/

require 'rambling-trie' # if necessary, gem install rambling-trie
trie = Rambling::Trie.create { |trie| a.each do |e| trie << e end }

A teraz jesteśmy gotowi przetestować obecność różnych słów w tablicy bez zapętlania jej w O(log n)czasie, z tą samą prostotą składniową, jak Array#include?przy użyciu sublinear Trie#include?:

trie.include? 'bird' #=> true
trie.include? 'duck' #=> false

Jeśli nie chcesz zapętlać, nie możesz tego zrobić za pomocą tablic. Zamiast tego powinieneś użyć zestawu.

require 'set'
s = Set.new
100.times{|i| s << "foo#{i}"}
s.include?("foo99")
 => true
[1,2,3,4,5,6,7,8].to_set.include?(4) 
  => true

Zestawy działają wewnętrznie jak Hashes, więc Ruby nie musi przeglądać kolekcji w celu znalezienia elementów, ponieważ jak sama nazwa wskazuje, generuje skróty kluczy i tworzy mapę pamięci, dzięki czemu każdy skrót wskazuje na określony punkt w pamięci. Poprzedni przykład wykonany za pomocą skrótu:

fake_array = {}
100.times{|i| fake_array["foo#{i}"] = 1}
fake_array.has_key?("foo99")
  => true

Minusem jest to, że zestawy i klucze skrótu mogą zawierać tylko unikalne przedmioty, a jeśli dodasz dużo przedmiotów, Ruby będzie musiała przerobić całą rzecz po określonej liczbie przedmiotów, aby zbudować nową mapę, która pasuje do większej przestrzeni na klucze. Aby dowiedzieć się więcej na ten temat, polecam obejrzeć „ MountainWest RubyConf 2014 - Big O in a Homemade Hash” autorstwa Nathana Longa .

Oto punkt odniesienia:

require 'benchmark'
require 'set'

array = []
set   = Set.new

10_000.times do |i|
  array << "foo#{i}"
  set   << "foo#{i}"
end

Benchmark.bm do |x|
  x.report("array") { 10_000.times { array.include?("foo9999") } }
  x.report("set  ") { 10_000.times { set.include?("foo9999")   } }
end

A wyniki:

      user     system      total        real
array  7.020000   0.000000   7.020000 (  7.031525)
set    0.010000   0.000000   0.010000 (  0.004816)

Jest to inny sposób, aby to zrobić: użyj Array#index metody.

Zwraca indeks pierwszego wystąpienia elementu w tablicy.

Na przykład:

a = ['cat','dog','horse']
if a.index('dog')
    puts "dog exists in the array"
end

index() może również wziąć blok:

Na przykład:

a = ['cat','dog','horse']
puts a.index {|x| x.match /o/}

Zwraca indeks pierwszego słowa w tablicy zawierającej literę „o”.

Śmieszny fakt,

Możesz użyć, *aby sprawdzić członkostwo w tablicy w casewyrażeniach.

case element
when *array 
  ...
else
  ...
end

Zwróć uwagę na trochę * w klauzuli when, która sprawdza członkostwo w tablicy.

Obowiązuje wszystkie zwykłe magiczne zachowanie operatora splat, więc na przykład, jeśli arraytak naprawdę nie jest tablicą, ale pojedynczym elementem, dopasuje ten element.

Istnieje wiele sposobów osiągnięcia tego celu. Kilka z nich to:

a = [1,2,3,4,5]

2.in? a  #=> true

8.in? a #=> false

a.member? 1 #=> true

a.member? 8 #=> false

Jeśli chcesz sprawdzić wielokrotność razy dla dowolnego klucza, przekonwertuj arrna hash, a teraz zaznacz O (1)

arr = ['Cat', 'Dog', 'Bird']
hash = arr.map {|x| [x,true]}.to_h
 => {"Cat"=>true, "Dog"=>true, "Bird"=>true}
hash["Dog"]
 => true
hash["Insect"]
 => false

Wydajność skrótu # has_key? w porównaniu z tablicą # include?

Parametr Hash # has_key? Tablica # include

Złożoność czasowa Operacja O (1) Operacja O (n) 

Typ dostępu Uzyskuje dostęp do skrótu [klawisz], jeśli przechodzi przez każdy element
                        zwraca dowolną wartość z tablicy do niej
                        true jest zwracane do znalezionych wartości w tablicy
                        Hash # has_key? połączenie
                        połączenie    

W przypadku jednorazowego sprawdzenia korzystanie include?jest w porządku

Dzięki temu dowiesz się nie tylko, że istnieje, ale także ile razy się pojawia:

 a = ['Cat', 'Dog', 'Bird']
 a.count("Dog")
 #=> 1

Za to, co jest warte, dokumenty Ruby są niesamowitym źródłem tego rodzaju pytań.

Zwróciłbym również uwagę na długość przeszukiwanej tablicy. Theinclude?Metoda będzie uruchomić przeszukiwanie liniowe z O (N) złożoności, które można uzyskać bardzo brzydki zależności od rozmiaru tablicy.

Jeśli pracujesz z dużą (posortowaną) tablicą, rozważę napisanie algorytmu wyszukiwania binarnego, który nie powinien być zbyt trudny i ma najgorszy przypadek O (log n).

Lub jeśli używasz Ruby 2.0, możesz skorzystać z bsearch.

Możesz spróbować:

Przykład: jeśli Cat i Dog istnieją w tablicy:

(['Cat','Dog','Bird'] & ['Cat','Dog'] ).size == 2   #or replace 2 with ['Cat','Dog].size

Zamiast:

['Cat','Dog','Bird'].member?('Cat') and ['Cat','Dog','Bird'].include?('Dog')

Uwaga: member?iinclude? są takie same.

To może wykonać pracę w jednej linii!

Jeśli nie chcemy tego używać, include?działa to również:

['cat','dog','horse'].select{ |x| x == 'dog' }.any?

['Cat', 'Dog', 'Bird'].detect { |x| x == 'Dog'}
=> "Dog"
!['Cat', 'Dog', 'Bird'].detect { |x| x == 'Dog'}.nil?
=> true

Co powiesz na ten sposób?

['Cat', 'Dog', 'Bird'].index('Dog')

Jeśli próbujesz to zrobić w teście jednostkowym MiniTest , możesz użyć assert_includes. Przykład:

pets = ['Cat', 'Dog', 'Bird']
assert_includes(pets, 'Dog')      # -> passes
assert_includes(pets, 'Zebra')    # -> fails 

Jest na to odwrócenie.

Załóżmy, że tablica jest [ :edit, :update, :create, :show ], być może, całymi siedmioma grzechami śmiertelnymi / uspokajającymi .

I dalej zabawka z pomysłem wyciągnięcia prawidłowej akcji z jakiegoś sznurka:

"my brother would like me to update his profile"

Następnie:

[ :edit, :update, :create, :show ].select{|v| v if "my brother would like me to update his profile".downcase =~ /[,|.| |]#{v.to_s}[,|.| |]/}

Jeśli chcesz zwrócić wartość nie tylko prawda lub fałsz, użyj

array.find{|x| x == 'Dog'}

Zwróci „Pies”, jeśli istnieje na liście, w przeciwnym razie zero.

Oto jeszcze jeden sposób, aby to zrobić:

arr = ['Cat', 'Dog', 'Bird']
e = 'Dog'

present = arr.size != (arr - [e]).size

array = [ 'Cat', 'Dog', 'Bird' ]
array.include?("Dog")

ma wiele sposobów na znalezienie elementu w dowolnej tablicy, ale najprostszym sposobem jest „w?” metoda.

example:
arr = [1,2,3,4]
number = 1
puts "yes #{number} is present in arr" if number.in? arr

jeśli nie chcesz używać include?, możesz najpierw owinąć element w tablicy, a następnie sprawdzić, czy zawinięty element jest równy przecięciu tablicy i owiniętego elementu. Zwróci wartość logiczną opartą na równości.

def in_array?(array, item)
    item = [item] unless item.is_a?(Array)
    item == array & item
end

Zawsze uważam za interesujące przeprowadzenie testów porównawczych, aby zobaczyć względną szybkość różnych sposobów robienia czegoś.

Znalezienie elementu tablicy na początku, w środku lub na końcu wpłynie na wszelkie wyszukiwania liniowe, ale prawie nie wpłynie na wyszukiwanie względem zbioru.

Konwersja tablicy na zestaw spowoduje trafienie w czas przetwarzania, więc utwórz zestaw z tablicy raz lub zacznij od zestawu od samego początku.

Oto kod testu porównawczego:

# frozen_string_literal: true

require 'fruity'
require 'set'

ARRAY = (1..20_000).to_a
SET = ARRAY.to_set

DIVIDER = '-' * 20

def array_include?(elem)
  ARRAY.include?(elem)
end

def array_member?(elem)
  ARRAY.member?(elem)
end

def array_index(elem)
  ARRAY.index(elem) >= 0
end

def array_find_index(elem)
  ARRAY.find_index(elem) >= 0
end

def array_index_each(elem)
  ARRAY.index { |each| each == elem } >= 0
end

def array_find_index_each(elem)
  ARRAY.find_index { |each| each == elem } >= 0
end

def array_any_each(elem)
  ARRAY.any? { |each| each == elem }
end

def array_find_each(elem)
  ARRAY.find { |each| each == elem } != nil
end

def array_detect_each(elem)
  ARRAY.detect { |each| each == elem } != nil
end

def set_include?(elem)
  SET.include?(elem)
end

def set_member?(elem)
  SET.member?(elem)
end

puts format('Ruby v.%s', RUBY_VERSION)

{
  'First' => ARRAY.first,
  'Middle' => (ARRAY.size / 2).to_i,
  'Last' => ARRAY.last
}.each do |k, element|
  puts DIVIDER, k, DIVIDER

  compare do
    _array_include?        { array_include?(element)        }
    _array_member?         { array_member?(element)         }
    _array_index           { array_index(element)           }
    _array_find_index      { array_find_index(element)      }
    _array_index_each      { array_index_each(element)      }
    _array_find_index_each { array_find_index_each(element) }
    _array_any_each        { array_any_each(element)        }
    _array_find_each       { array_find_each(element)       }
    _array_detect_each     { array_detect_each(element)     }
  end
end

puts '', DIVIDER, 'Sets vs. Array.include?', DIVIDER
{
  'First' => ARRAY.first,
  'Middle' => (ARRAY.size / 2).to_i,
  'Last' => ARRAY.last
}.each do |k, element|
  puts DIVIDER, k, DIVIDER

  compare do
    _array_include? { array_include?(element) }
    _set_include?   { set_include?(element)   }
    _set_member?    { set_member?(element)    }
  end
end

Co po uruchomieniu na moim laptopie z systemem Mac OS powoduje:

Ruby v.2.7.0
--------------------
First
--------------------
Running each test 65536 times. Test will take about 5 seconds.
_array_include? is similar to _array_index
_array_index is similar to _array_find_index
_array_find_index is faster than _array_any_each by 2x ± 1.0
_array_any_each is similar to _array_index_each
_array_index_each is similar to _array_find_index_each
_array_find_index_each is faster than _array_member? by 4x ± 1.0
_array_member? is faster than _array_detect_each by 2x ± 1.0
_array_detect_each is similar to _array_find_each
--------------------
Middle
--------------------
Running each test 32 times. Test will take about 2 seconds.
_array_include? is similar to _array_find_index
_array_find_index is similar to _array_index
_array_index is faster than _array_member? by 2x ± 0.1
_array_member? is faster than _array_index_each by 2x ± 0.1
_array_index_each is similar to _array_find_index_each
_array_find_index_each is similar to _array_any_each
_array_any_each is faster than _array_detect_each by 30.000000000000004% ± 10.0%
_array_detect_each is similar to _array_find_each
--------------------
Last
--------------------
Running each test 16 times. Test will take about 2 seconds.
_array_include? is faster than _array_find_index by 10.000000000000009% ± 10.0%
_array_find_index is similar to _array_index
_array_index is faster than _array_member? by 3x ± 0.1
_array_member? is faster than _array_find_index_each by 2x ± 0.1
_array_find_index_each is similar to _array_index_each
_array_index_each is similar to _array_any_each
_array_any_each is faster than _array_detect_each by 30.000000000000004% ± 10.0%
_array_detect_each is similar to _array_find_each

--------------------
Sets vs. Array.include?
--------------------
--------------------
First
--------------------
Running each test 65536 times. Test will take about 1 second.
_array_include? is similar to _set_include?
_set_include? is similar to _set_member?
--------------------
Middle
--------------------
Running each test 65536 times. Test will take about 2 minutes.
_set_member? is similar to _set_include?
_set_include? is faster than _array_include? by 1400x ± 1000.0
--------------------
Last
--------------------
Running each test 65536 times. Test will take about 4 minutes.
_set_member? is similar to _set_include?
_set_include? is faster than _array_include? by 3000x ± 1000.0

Zasadniczo wyniki mówią mi, aby użyć zestawu do wszystkiego, jeśli mam szukać włączenia, chyba że mogę zagwarantować, że pierwszy element jest tym, którego chcę, co jest mało prawdopodobne. Wstawianie elementów do skrótu jest nieco obciążone, ale czasy wyszukiwania są o wiele szybsze, nie sądzę, że powinno to być kiedykolwiek brane pod uwagę. Ponownie, jeśli musisz go przeszukać, nie używaj tablicy, użyj zestawu. (Lub hash.)

Im mniejsza tablica, tym szybciej będą działać metody tablic, ale nadal nie nadążą, choć w małych tablicach różnica może być niewielka.

„First”, „Middle” i „Ostatni” odzwierciedlać użycie first, size / 2a lastza ARRAYza element poszukiwany. Ten element będzie używany podczas wyszukiwania zmiennych ARRAYi SET.

Niewielkie zmiany zostały wprowadzone do metod, które w porównaniu do > 0ponieważ badanie powinno być >= 0dla indexprób typu.

Więcej informacji na temat Fruity i jego metodologii można znaleźć w README .