在一个字符串数组中查找字符串的最快方法

Question

脚本必须验证预定义IP是否存在于一个大的IP数组中。目前我编写该函数的方式如下（假设“ips”是我的IP数组，“ip”是预定义IP）。

ips.each do |existsip|
  if ip == existsip
    puts "ip exists"
    return 1
  end
end
puts "ip doesn't exist"
return nil

有没有更快的方法做同样的事情？

编辑：我可能表达不清楚。我可以使用array.include?，但我想知道的是：array.include?是能够给我最快结果的方法吗？

- Cocotton

---

使用哈希表或集合代替数组。 - Phrogz

可能是 http://stackoverflow.com/questions/6140554/ruby-on-rails-2-search-string-in-hash 的重复问题。 - Joseph Le Brech

@JosephLeBrech 这里的问题是关于搜索数组。 - Hunter McMillen

根据更新后的问题，答案是根本不使用字符串数组。下面使用Set类的答案是更好的方法。 - Don Cruickshank

如果绝对速度很关键，使用符号而不是字符串来表示IP地址可能会带来一些好处（在您首先切换到使用哈希或集合之后）。 - Phrogz

Answer 1

你可以使用Set。它是基于哈希实现的，对于大数据集来说速度更快-O(1)。

require 'set'
s = Set.new ['1.1.1.1', '1.2.3.4']
# => #<Set: {"1.1.1.1", "1.2.3.4"}> 
s.include? '1.1.1.1'
# => true 

- Aliaksei Kliuchnikau

---

或者在你的情况下：s = Set.new(ips) - Phrogz

@Cocotton: 更快的方法。你也可以使用一个以IP地址为键，'true'为值的哈希表。 - steenslag

这里显而易见的缺点是 Set 更快，但构建 Set 可能是一个代价高昂的操作，因此你不会想要构建一个 Set 来查询它很少的次数。 - Marc Talbot

针对一个包含1240万个短字符串的数组： a=('a'..'zzzzz').to_a; time{ a.include?('0') } #=> 0.71s; time{ Set.new(a) } #=> 11.2s，可以发现，创建集合所需的额外开销必须值得即时查询的性能收益。请注意不要改变原文意思。 - Phrogz

支持@Phrogz的说法，请检查两种#include? 方法的源代码和此依据：https://gist.github.com/vadviktor/66e524c591b2604ce2d7 - Ikon

Answer 2

你可以使用Array#include方法来返回true/false。 http://ruby-doc.org/core-1.9.3/Array.html#method-i-include-3F

if ips.include?(ip) #=> true
  puts 'ip exists'
else
  puts 'ip  doesn\'t exist'
end

- ericraio

Answer 3

ips = ['10.10.10.10','10.10.10.11','10.10.10.12']

ip = '10.10.10.10'
ips.include?(ip) => true

ip = '10.10.10.13'
ips.include?(ip) => false

点击此处查看文档

- dku.rajkumar

---

但是这个方法真的比我的方法更快吗？因为这个源代码似乎实际上和我的代码做了几乎相同的事情。 - Cocotton

当然更快。我在我的项目中使用过它。此外，既然Ruby中有一个方法，为什么我们要写额外的代码呢？ - dku.rajkumar

@dku.rajkumar 想说，因为 .include? 是在 Array 类的 C 级别上实现的，所以它应该更快。 - Ikon

Answer 4

更快的方法是：

if ips.include?(ip)
  puts "ip exists"
  return 1
else
  puts "ip doesn't exist"
  return nil
end

- Don Cruickshank

---

略微更快，因为each在C中而不是Ruby中出现，但对于哈希表或集合来说仍然是O(n)与O(1)的比较。 - Phrogz

Answer 5

你尝试过使用Array#include?函数吗？

http://ruby-doc.org/core-1.9.3/Array.html#method-i-include-3F

从源代码中可以看出，它几乎完全相同，只是本地化了。

- Peter Ehrlich

---

这仍然是一个O(n)时间复杂度的操作，因为它必须搜索数组中的每个项（即使它在C中）。 - Phrogz

我知道枚举可以排序，但我不知道如何搜索这样一个已排序的数组。可以创建一个索引数据库列来完成这项工作。 - Peter Ehrlich

即使是二分查找也是O(log n)。在哈希表中进行哈希并查找项是一个与存储的项数无关的常数时间操作。 - Phrogz