Câu hỏi Kiểm tra nếu một giá trị tồn tại trong một mảng trong Ruby


Tôi có một giá trị 'Dog' và một mảng ['Cat', 'Dog', 'Bird'].

Làm thế nào để kiểm tra xem nó tồn tại trong mảng mà không lặp qua nó? Có cách nào đơn giản để kiểm tra nếu giá trị tồn tại, không có gì hơn?


1109
2017-12-31 17:49


gốc


sử dụng .bao gồm? phương pháp. Nó trả về một boolean đó là những gì bạn muốn. Trong trường hợp của bạn chỉ cần gõ: ['Mèo', 'Chó', 'Chim'] .bao gồm ('Chó') và nó sẽ trả về giá trị boolean đúng. - Jwan622
không sử dụng bao gồm?  phương pháp nếu bạn muốn kiểm tra bội số lần cho giá trị khác nhau để có mặt trong mảng hay không vì bao gồm? mỗi lần sẽ lặp qua mảng lấy hoạt động O (n) để tìm kiếm mỗi lần, thay vào đó hãy tạo một băm hash = arr.map {|x| [x,true]}.to_h, bây giờ kiểm tra xem hash.has_key? 'Dog' trả về đúng hay không - aqfaridi
Bạn không thể thực sự làm điều đó hoàn toàn "mà không lặp qua nó". Đó là một cách hợp lý, máy tính không thể biết chắc chắn liệu mảng có chứa phần tử mà không lặp qua các phần tử để kiểm tra xem có bất kỳ phần tử nào trong số đó là tìm kiếm hay không. Trừ khi nó trống rỗng, tất nhiên. Sau đó, tôi đoán bạn không cần một vòng lặp. - tradeJmark


Các câu trả lời:


Bạn đang tìm include?:

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

1664
2017-12-31 17:51



Cú pháp thay thế: %w(Cat Dog Bird).include? 'Dog' - scarver2
Đôi khi tôi muốn nó là "chứa" không bao gồm. Tôi luôn nhận được nó trộn lẫn với bao gồm. - Henley Chiu
Hãy để tôi lưu ý rằng nội bộ, #include? vẫn thực hiện lặp. Các coder được lưu từ viết vòng lặp một cách rõ ràng, mặc dù. Tôi đã thêm một câu trả lời thực hiện nhiệm vụ thực sự mà không cần lặp. - Boris Stitnicky
@ HenleyChiu tôi được gọi là [ 'Dog', 'Bird', 'Cat' ].has? 'Dog'
@AlfonsoVergara Có, bất kỳ giải pháp cho một mảng phải làm một số loại looping nội bộ; không có cách nào để kiểm tra thành viên của một mảng mà không có vòng lặp. Nếu bạn không muốn thực hiện bất kỳ vòng lặp nào trong nội bộ, bạn cần phải sử dụng một cấu trúc dữ liệu khác, chẳng hạn như bảng băm hoàn hảo với các khóa có kích thước cố định. Cho rằng không có cách nào để kiểm tra thành viên trong một mảng mà không lặp lại nội bộ, tôi giải thích câu hỏi có nghĩa là "mà không cần phải viết vòng lặp một cách rõ ràng" - Brian Campbell


Đây là một in? phương pháp trong ActiveSupport (một phần của Rails) kể từ v3.1, như được chỉ ra bởi @campaterson. Vì vậy, trong Rails, hoặc nếu bạn require 'active_support', bạn có thể viết:

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

OTOH, không có in nhà điều hành hoặc #in? trong Ruby, mặc dù nó đã được đề xuất trước đó, đặc biệt là Yusuke Endoh một thành viên đỉnh cao của ruby-core.

Như được chỉ ra bởi những người khác, phương pháp ngược lại include? tồn tại, cho tất cả Enumerables bao gồm Array, Hash, Set, Range:

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

Lưu ý rằng nếu bạn có nhiều giá trị trong mảng của mình, tất cả chúng sẽ được kiểm tra một lần sau giá trị kia (tức là O(n)), trong khi tra cứu cho một băm sẽ là thời gian không đổi (tức là O(1)). Vì vậy, nếu bạn mảng là hằng số, ví dụ, nó là một ý tưởng tốt để sử dụng một Bộ thay thế. Ví dụ:

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

A bài kiểm tra nhanh tiết lộ rằng gọi include? trên một yếu tố 10 Set nhanh hơn khoảng 3,5 lần so với gọi nó tương đương Array (nếu không tìm thấy phần tử).

Một lưu ý đóng cửa cuối cùng: cảnh giác khi sử dụng include? trên một Range, có sự tinh tế, vì vậy hãy tham khảo tài liệu và so sánh với cover?...


206
2018-05-15 12:50



Trong khi Ruby không bao gồm #in? trong cốt lõi của nó, nếu bạn đang sử dụng Rails, nó có sẵn. api.rubyonrails.org/classes/Object.html#method-i-in-3F (Tôi biết đây là một câu hỏi của Ruby, không phải là Rails, nhưng nó có thể giúp bất cứ ai muốn sử dụng #in? trong Rails. Có vẻ như nó đã được thêm vào trong Rails 3.1 apidock.com/rails/Object/in%3F - campeterson
+1 cho Set, bị bỏ qua. - Jared Beck


Thử

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

157
2017-12-31 17:52



đây là cú pháp cũ hơn, hãy nhìn ^^^ @ brian's answer - jahrichie
@jahrichie chính xác những gì bạn xem xét "cú pháp cũ" trong câu trả lời này, các dấu ngoặc đơn tùy chọn? - Dennis
Tôi đồng ý @ Dennis, đây không phải là cũ hơn, dấu ngoặc đơn là tùy chọn và trong hầu hết các trường hợp THỰC HÀNH TỐT .... hãy thử sử dụng bao gồm không có dấu ngoặc đơn trong một dòng nếu câu ví dụ, ý tôi là tùy thuộc vào trường hợp của bạn nên hoặc phải sử dụng dấu ngoặc vuông hay không (không liên quan đến cú pháp ruby ​​"cũ") - d1jhoni1b


Sử dụng Enumerable#include:

a = %w/Cat Dog Bird/

a.include? 'Dog'

Hoặc, nếu một số thử nghiệm được thực hiện,1 bạn có thể loại bỏ vòng lặp (thậm chí là include? có) và đi từ Trên) đến O (1) với:

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


1. Tôi hy vọng điều này là hiển nhiên nhưng để đầu ra phản đối: có, chỉ cần một vài tra cứu, Hash [] và oppose transpose thống trị hồ sơ và mỗi Trên) chính họ.


44
2017-12-31 17:52





Nếu bạn muốn kiểm tra bởi một khối, bạn có thể thử bất kỳ? hoặc tất cả ?.

%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  

Chi tiết có tại đây: http://ruby-doc.org/core-1.9.3/Enumerable.html
Nguồn cảm hứng của tôi đến từ đây: https://stackoverflow.com/a/10342734/576497


41
2018-05-20 09:08



Rất hữu ích nếu bạn muốn kiểm tra bất kỳ / tất cả các chuỗi được bao gồm trong một chuỗi / hằng số - thanikkal


Một vài câu trả lời gợi ý Array#include?, nhưng có một cảnh báo quan trọng: Nhìn vào nguồn, thậm chí Array#include? thực hiện lặp:

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

Cách kiểm tra sự hiện diện của từ mà không lặp lại là bằng cách xây dựng một trie cho mảng của bạn. Có rất nhiều triển khai trie ra khỏi đó (google "ruby trie"). tôi sẽ sử dụng rambling-trie trong ví dụ này:

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 }

Và bây giờ chúng tôi đã sẵn sàng để kiểm tra sự hiện diện của các từ khác nhau trong mảng của bạn mà không lặp qua nó, trong O(log n) thời gian, với cùng một cú pháp đơn giản như Array#include?, sử dụng sublinear Trie#include?:

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

28
2018-06-10 16:23



a.each do ... end Umm ... không chắc đó không phải là vòng lặp - Doorknob
Lưu ý rằng điều này thực sự bao gồm một vòng lặp; bất cứ điều gì không phải là O (1) bao gồm một số loại vòng lặp. Nó chỉ xảy ra là một vòng lặp trên các ký tự của chuỗi đầu vào. Cũng lưu ý hơn câu trả lời đã được đề cập Set#include? cho những người quan tâm về hiệu quả; kết hợp với việc sử dụng các ký hiệu thay vì chuỗi, nó có thể là trường hợp trung bình O (1) (nếu bạn sử dụng chuỗi, sau đó chỉ cần tính toán băm là O (n) trong đó n là độ dài của chuỗi). Hoặc nếu bạn muốn sử dụng thư viện của bên thứ ba, bạn có thể sử dụng hàm băm hoàn hảo là trường hợp xấu nhất O (1). - Brian Campbell
AFAIK, Set sử dụng băm để lập chỉ mục các thành viên của nó, vì vậy trên thực tế Set#include?  Nên phức tạp O (1) cho một phân phối tốt Set (cụ thể hơn O (kích thước đầu vào) cho băm, và O (log (n / bucket-number)) cho việc tìm kiếm) - Uri Agassi
Chi phí tạo và duy trì trie cũng nhiều như vậy. Nếu bạn đang thực hiện nhiều thao tác tìm kiếm trên mảng, thì chi phí bộ nhớ và thời gian của một trie và duy trì nó đáng giá, nhưng đối với một hoặc thậm chí hàng trăm hoặc hàng nghìn kiểm tra, O (n) là hoàn toàn phù hợp. Một tùy chọn khác mà không yêu cầu thêm phụ thuộc sẽ là sắp xếp mảng hoặc duy trì nó theo thứ tự sắp xếp, trong trường hợp đó một phép tìm kiếm nhị phân O (lg n) có thể được sử dụng để kiểm tra sự bao gồm. - speakingcode
@speakingcode, bạn có thể đúng với quan điểm thực dụng. Nhưng OP yêu cầu "kiểm tra nếu giá trị tồn tại, không có gì hơn, không có vòng lặp". Khi tôi viết câu trả lời này, có nhiều giải pháp thực dụng ở đây, nhưng không có giải pháp nào thực sự đáp ứng yêu cầu của người yêu cầu. Quan sát của bạn rằng BST có liên quan đến cố gắng là chính xác, nhưng đối với chuỗi, trie là công cụ thích hợp cho công việc, thậm chí Wikipedia biết rằng nhiều. Sự phức tạp của việc xây dựng và duy trì một trie được thực hiện tốt là rất thuận lợi. - Boris Stitnicky


Ruby có 11 phương pháp để tìm các phần tử trong một mảng.

Người ưa thích là include?

Hoặc để truy cập lặp lại, tạo một bộ và sau đó gọi include? hoặc là member?

Đây là tất cả,

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

Tất cả đều trở lại truegiá trị ish nếu phần tử có mặt.

include? là phương pháp được ưu tiên. Nó sử dụng ngôn ngữ C for vòng lặp nội bộ phá vỡ khi một phần tử khớp với nội bộ rb_equal_opt/rb_equalchức năng. Nó không thể có hiệu quả hơn nhiều trừ khi bạn tạo một bộ để kiểm tra thành viên lặp đi lặp lại.

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? không được xác định lại trong Array và sử dụng triển khai không được tối ưu hóa từ Enumerable mô-đun theo nghĩa đen liệt kê tất cả các phần tử.

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

Đã dịch sang mã Ruby, điều này sẽ làm như sau

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

Cả hai include? và member? có O(n) thời gian phức tạp kể từ khi cả hai tìm kiếm mảng cho sự xuất hiện đầu tiên của giá trị dự kiến.

Chúng tôi có thể sử dụng một bộ để có được O(1) thời gian truy cập với chi phí phải tạo ra một biểu diễn băm của mảng đầu tiên. Nếu bạn liên tục kiểm tra tư cách thành viên trên cùng một mảng thì khoản đầu tư ban đầu này có thể thanh toán nhanh chóng. Set không được thực hiện trong C nhưng là lớp Ruby đơn giản, vẫn là O(1) thời gian truy cập của cơ sở @hash làm cho điều này đáng giá.

Đây là việc thực hiện Set lớp học,

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

Như bạn có thể thấy Set lớp học vừa tạo nội bộ @hash ví dụ, ánh xạ tất cả các đối tượng đến true và sau đó kiểm tra tư cách thành viên bằng Hash#include? được triển khai với O(1) thời gian truy cập trong Hash lớp học.

Tôi sẽ không thảo luận về 7 phương pháp khác vì chúng đều kém hiệu quả hơn.

Thậm chí còn có nhiều phương pháp hơn với O(n) phức tạp vượt quá 11 được liệt kê ở trên, nhưng tôi quyết định không liệt kê chúng kể từ khi quét toàn bộ mảng thay vì phá vỡ ở trận đấu đầu tiên.

Đừng dùng những thứ này,

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

23
2017-12-25 23:40



Thật trớ trêu khi nói rằng Ruby có chính xác 11 cách để làm bất cứ điều gì! Không sớm hơn bạn nói rằng ai đó sẽ chỉ ra rằng bạn đã bỏ lỡ # 12, sau đó # 13, v.v. Để làm cho quan điểm của tôi, tôi sẽ gợi ý những cách khác, nhưng trước tiên hãy để tôi đặt câu hỏi 11 cách bạn đã liệt kê. Đầu tiên, bạn khó có thể đếm index và find_index (hoặc là find và detect) như các phương thức riêng biệt, vì chúng chỉ là các tên khác nhau cho cùng một phương thức. Thứ hai, tất cả các biểu thức kết thúc bằng > 0 không chính xác, mà tôi chắc chắn là một sự giám sát. (cont.) - Cary Swoveland
...arr.index(e)ví dụ, trả về 0 nếu arr[0] == e. Bạn sẽ nhớ lại arr.index(e) trả về nil nếu e không phải bây giờ. index không thể được sử dụng, tuy nhiên, nếu một người đang tìm kiếm nil trong arr. (Cùng một vấn đề với rindex, không được liệt kê.). Chuyển đổi mảng thành một tập hợp và sau đó sử dụng các phương thức thiết lập là một chút căng. Tại sao không chuyển đổi thành băm (với các khóa từ mảng và các giá trị tùy ý), sau đó sử dụng các phương thức băm? Ngay cả khi chuyển đổi thành một tập hợp là OK, có các phương pháp thiết lập khác có thể được sử dụng, chẳng hạn như !arr.to_set.add?(e). (cont.) - Cary Swoveland
... Như đã hứa, đây là một vài phương pháp có thể được sử dụng: arr.count(e) > 0, arr != arr.dup.delete(e) , arr != arr - [e] và arr & [e] == [e]. Người ta cũng có thể sử dụng select và reject. - Cary Swoveland


Nếu bạn không muốn lặp lại, không có cách nào để làm điều đó với Mảng. Thay vào đó, bạn nên sử dụng Tập hợp.

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

Đặt làm việc nội bộ như băm, vì vậy Ruby không cần phải lặp lại bộ sưu tập để tìm các mục, vì như tên của nó, nó tạo ra các băm và tạo một bản đồ bộ nhớ sao cho mỗi điểm băm đến một điểm nhất định trong bộ nhớ. Ví dụ trước được thực hiện với một Hash:

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

Nhược điểm là Bộ và khóa băm chỉ có thể bao gồm các mục duy nhất và nếu bạn thêm nhiều mục, Ruby sẽ phải khôi phục toàn bộ nội dung sau một số mục nhất định để xây dựng bản đồ mới phù hợp với không gian phím lớn hơn. Để biết thêm về điều này, tôi khuyên bạn nên xem MountainWest RubyConf 2014 - Big O trong Hash tự chế bởi Nathan Long 

Đây là điểm chuẩn:

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

Và kết quả:

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

16
2018-05-29 19:58



Nếu bạn sử dụng phát hiện, sau đó bạn có thể ít nhất là giảm vòng lặp. phát hiện sẽ dừng lại ở mục đầu tiên 'được phát hiện' (khối được chuyển cho mục được đánh giá là đúng). Ngoài ra, bạn có thể phát hiện những gì cần làm nếu không có gì được phát hiện (bạn có thể vượt qua trong một lambda). - aenw
@aenw không include? dừng lại ở lần truy cập đầu tiên? - Kimmo Lehto
bạn hoàn toàn đúng. Tôi rất quen với việc sử dụng phát hiện mà tôi đã quên mất về việc bao gồm. cảm ơn cho bình luận của bạn - nó đảm bảo rằng tôi làm mới kiến ​​thức của tôi. - aenw


Đây là một cách khác để thực hiện việc này: sử dụng phương thức chỉ mục # Array.

Nó trả về chỉ mục của lần xuất hiện đầu tiên của phần tử trong mảng.

thí dụ:

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

index () cũng có thể lấy một khối

ví dụ

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

ở đây, trả về chỉ mục của từ đầu tiên trong mảng chứa chữ 'o'.


15
2017-10-02 17:22



index vẫn lặp qua mảng, nó chỉ trả về giá trị của phần tử. - the Tin Man


Có nhiều cách để thực hiện việc này. Một vài trong số đó là như sau:

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

2.in? a  #=> true

8.in? a #=> false

a.member? 1 #=> true

a.member? 8 #=> false

8
2018-04-29 10:12



Lưu ý rằng Object#in? chỉ được thêm vào Rails (tức là ActiveSupport) v3.1 +. Nó không có sẵn trong lõi Ruby. - Tom Lord


Sự thật thú vị,

Bạn có thể dùng * để kiểm tra thành viên mảng trong case biểu thức.

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

Chú ý một chút * trong mệnh đề when, điều này sẽ kiểm tra thành viên trong mảng.

Tất cả các hành vi ma thuật thông thường của toán tử splat đều được áp dụng, ví dụ như nếu array không thực sự là một mảng mà là một phần tử duy nhất nó sẽ khớp với phần tử đó.


6
2017-12-25 23:48