我有一个值“狗”和一个数组[“猫”、“狗”、“鸟”]。
如何在不循环的情况下检查数组中是否存在它?是否有一种简单的方法来检查该值是否存在?
我有一个值“狗”和一个数组[“猫”、“狗”、“鸟”]。
如何在不循环的情况下检查数组中是否存在它?是否有一种简单的方法来检查该值是否存在?
当前回答
['Cat', 'Dog', 'Bird'].detect { |x| x == 'Dog'}
=> "Dog"
!['Cat', 'Dog', 'Bird'].detect { |x| x == 'Dog'}.nil?
=> true
其他回答
如果你想检查一个街区,你可以试试吗?还是全部?。
%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
有关详细信息,请参见Enumerable。
我的灵感来自于“评估数组中是否有任何项目”
如果不想循环,则无法使用数组进行循环。您应该改用Set。
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
设置在内部像Hashes一样工作,因此Ruby不需要在集合中循环查找项,因为顾名思义,它会生成键的哈希值,并创建内存映射,以便每个哈希值指向内存中的某个点。前面的示例使用Hash完成:
fake_array = {}
100.times{|i| fake_array["foo#{i}"] = 1}
fake_array.has_key?("foo99")
=> true
缺点是Set和Hash键只能包含唯一的项,如果你添加了很多项,Ruby将不得不在一定数量的项之后重新散列整个项,以构建适合更大键空间的新映射。有关这方面的更多信息,我建议您观看“MountainWest RubyConf 2014-Nathan Long自制哈希中的大O”。
这里有一个基准:
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
结果是:
user system total real
array 7.020000 0.000000 7.020000 ( 7.031525)
set 0.010000 0.000000 0.010000 ( 0.004816)
还有一种方法可以做到这一点:
arr = ['Cat', 'Dog', 'Bird']
e = 'Dog'
present = arr.size != (arr - [e]).size
有几个答案建议阵列#包括?,但有一个重要的警告:查看源代码,甚至是Array#include?确实执行循环:
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;
}
在不循环的情况下测试单词存在的方法是为数组构造一个trie。有很多trie实现(谷歌“ruby trie”)。我将在本例中使用随机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 }
现在,我们已经准备好测试数组中各种单词的存在,而无需在O(log n)时间内对其进行循环,语法简单性与array#include?,使用子线Trie#include?:
trie.include? 'bird' #=> true
trie.include? 'duck' #=> false
我总是觉得运行一些基准测试来查看各种方法的相对速度很有趣。
在开始、中间或结束处查找数组元素将影响任何线性搜索,但几乎不会影响对集合的搜索。
将一个数组转换为一个集合会导致处理时间的减少,所以从一个数组创建一次集合,或者从一开始就创建一个集合。
以下是基准代码:
# 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
在我的Mac OS笔记本电脑上运行时,会导致:
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
基本上,如果我要搜索包含,结果告诉我对所有内容都使用Set,除非我能保证第一个元素是我想要的,这不太可能。在哈希表中插入元素时会有一些开销,但搜索速度要快得多,我认为这不应该是一个考虑因素。同样,如果您需要搜索它,请不要使用数组,而是使用集合。(或哈希。)
Array越小,Array方法运行得越快,但它们仍然无法跟上,尽管在小数组中,差异可能很小。
“First”、“Middle”和“Last”反映了所搜索元素在ARRAY中使用First、size/2和Last。搜索ARRAY和SET变量时将使用该元素。
对与>0进行比较的方法进行了轻微更改,因为索引类型测试的测试应为>=0。
有关Fruity及其方法的更多信息,请参见其README。