print - ruby select




Überprüfen Sie, ob in einem Array in Ruby ein Wert vorhanden ist (16)

Ich habe einen Wert 'Dog' und ein Array ['Cat', 'Dog', 'Bird'] .

Wie überprüfe ich, ob es im Array existiert, ohne es zu durchlaufen? Gibt es eine einfache Möglichkeit zu überprüfen, ob der Wert existiert, nicht mehr?


Dies ist eine weitere Möglichkeit: Verwenden Sie die Array # -Indexmethode.

Es gibt den Index des ersten Auftretens des Elements im Array zurück.

Beispiel:

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

index () kann auch einen Block nehmen

beispielsweise

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

Geben Sie hier den Index des ersten Wortes im Array zurück, das den Buchstaben 'o' enthält.


Dies wird Ihnen nicht nur sagen, dass es existiert, sondern auch, wie oft es erscheint:

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

Es gibt ein in? Methode in ActiveSupport (Teil von Rails) seit v3.1, wie von @campaterson hingewiesen. Innerhalb von Rails oder wenn Sie require 'active_support' , können Sie schreiben:

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

OTOH, gibt es keine in Operator oder #in? Methode in Ruby selbst, obwohl es zuvor vorgeschlagen wurde, insbesondere von Yusuke Endoh ein erstklassiges Mitglied der Rubin-Kern.

Wie von anderen hingewiesen, umfassen die umgekehrte Methode include? existiert für alle Enumerable s einschließlich Array , Hash , Set , Range :

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

Beachten Sie, dass wenn Sie viele Werte in Ihrem Array haben, diese alle nacheinander überprüft werden (zB O(n) ), während die Suche nach einem Hash eine konstante Zeit ist (dh O(1) ). Wenn Sie also zum Beispiel ein Array konstant haben, ist es Set stattdessen ein Set verwenden. Z.B:

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

Ein kurzer Test zeigt, dass Anrufe include? auf einem 10-Element- Set ist etwa 3,5 mal schneller als das Aufrufen des entsprechenden Array (wenn das Element nicht gefunden wird).

Eine abschließende Schlussnotiz: Seien Sie vorsichtig bei der Verwendung von include? Bei einer Range gibt es Feinheiten, beziehen Sie sich also auf das Dokument und vergleichen Sie mit dem cover? ...


Es gibt mehrere Möglichkeiten, dies zu erreichen. Einige von ihnen sind wie folgt:

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

2.in? a  #=> true

8.in? a #=> false

a.member? 1 #=> true

a.member? 8 #=> false

Für was es wert ist, The Ruby Docs sind eine erstaunliche Ressource für diese Art von Fragen.

Ich würde auch die Länge des Arrays, durch das Sie suchen, beachten. Die include? Methode wird eine lineare Suche mit O (n) Komplexität ausführen, die je nach Größe des Arrays ziemlich hässlich werden kann.

Wenn Sie mit einem großen (sortierten) Array arbeiten, würde ich in Erwägung ziehen, einen binären Suchalgorithmus zu schreiben, der nicht zu schwierig sein sollte und den schlimmsten Fall von O (log n) hat.

Oder wenn Sie Ruby 2.0 verwenden, können Sie bsearch .


Hier ist eine weitere Möglichkeit, dies zu tun:

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

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

Mehrere Antworten schlagen Array#include? , aber es gibt eine wichtige Einschränkung: Blick auf die Quelle, sogar Array#include? macht Looping:

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;
}

Die Art, das Wort Präsenz ohne Schleifen zu testen, besteht darin, einen Trie für Ihr Array zu konstruieren. Es gibt viele Trie-Implementierungen (google "ruby trie"). Ich werde in diesem Beispiel " rambling-trie :

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 }

Und jetzt sind wir bereit, das Vorhandensein verschiedener Wörter in Ihrem Array zu testen, ohne es in O(log n) -Zeit mit derselben syntaktischen Einfachheit wie Array#include? , unter Verwendung von sublinearem Trie#include? :

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

Ruby hat 11 Methoden, um Elemente in einem Array zu finden.

Die bevorzugte ist include?

Oder für den wiederholten Zugriff, Erstellen eines Sets und dann Aufruf von include? oder member?

Hier sind sie alle,

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

Alle geben einen true ish-Wert zurück, wenn das Element vorhanden ist.

include? ist die bevorzugte Methode. Es verwendet intern eine C-Sprache for Schleife, die bricht, wenn ein Element den internen rb_equal_opt/rb_equal Funktionen entspricht. Es kann nicht viel effizienter werden, wenn Sie nicht einen Satz für wiederholte Mitgliedsprüfungen erstellen.

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? wird in der Array Klasse nicht neu definiert und verwendet eine nicht optimierte Implementierung aus dem Enumerable Modul, die alle Elemente wörtlich aufzählt.

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;
}

In Ruby-Code übersetzt, tut dies Folgendes

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

Beide include? und member? haben O(n) Zeitkomplexität, da beide das Array nach dem ersten Auftreten des erwarteten Wertes durchsuchen.

Wir können einen Satz verwenden, um die Zugriffszeit O(1) auf Kosten der Erstellung einer Hash-Darstellung des Arrays zu erhalten. Wenn Sie wiederholt die Mitgliedschaft auf dem gleichen Array überprüfen, kann sich diese Anfangsinvestition schnell auszahlen. Set ist nicht in C implementiert, aber als @hash Ruby-Klasse macht es immer noch die O(1) Zugriffszeit des zugrundeliegenden @hash .

Hier ist die Implementierung der Set Klasse,

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

Wie Sie sehen können, erstellt die Set Klasse nur eine interne @hash Instanz, ordnet alle Objekte zu true und prüft dann die Mitgliedschaft mit Hash#include? was mit O(1) Zugriffszeit in der Hash Klasse implementiert wird.

Ich werde die anderen 7 Methoden nicht diskutieren, da sie alle weniger effizient sind.

Es gibt sogar noch mehr Methoden mit O(n) -Komplexität, die über die oben aufgeführten 11 hinausgehen, aber ich entschied, sie nicht aufzulisten, da das gesamte Array gescannt wird, anstatt beim ersten Treffer zu brechen.

Benutze diese nicht,

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

Versuchen

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

Verwenden Sie Enumerable#include :

a = %w/Cat Dog Bird/

a.include? 'Dog'

Oder, wenn eine Reihe von Tests durchgeführt werden, 1 können Sie die Schleife loswerden (die sogar include? ) Und gehen Sie von O (n) zu O (1) mit:

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

1. Ich hoffe, dass dies offensichtlich ist, um Einwände abzuwenden: Ja, für nur ein paar Nachschlagewerke dominieren die Hash- und Transponier-Ops das Profil und sind jeweils O (n) .


Wenn Sie keine Schleife machen wollen, gibt es keine Möglichkeit, dies mit Arrays zu tun. Sie sollten stattdessen ein Set verwenden.

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

Sätze arbeiten intern wie Hashes, also muss Ruby nicht durch die Sammlung laufen, um Elemente zu finden, da, wie der Name andeutet, es Hashes der Schlüssel generiert und eine Speicherzuordnung erstellt, so dass jeder Hash auf einen bestimmten Punkt im Speicher zeigt. Das vorherige Beispiel mit einem Hash:

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

Der Nachteil ist, dass Sets und Hash-Schlüssel nur eindeutige Elemente enthalten können und wenn Sie viele Elemente hinzufügen, muss Ruby das Ganze nach einer bestimmten Anzahl von Elementen erneut zusammenstellen, um eine neue Map zu erstellen, die zu einem größeren Schlüsselbereich passt. Für mehr darüber empfehle ich Ihnen MountainWest RubyConf 2014 - Big O in einem hausgemachten Hash von Nathan Long

Hier ist ein Benchmark:

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

Und die Ergebnisse:

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

Wenn Sie mehr Wert auf mehr haben ... können Sie versuchen:

Beispiel: Wenn Cat und Dog im Array existieren:

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

Anstatt von:

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

Hinweis: Mitglied? und enthalten? sind gleich.

Dies kann die Arbeit in einer Linie erledigen!


Wenn wir nicht include? möchten include? das funktioniert auch:

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

Wie wäre es mit diesem Weg?

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

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

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




arrays