Самый быстрый способ найти строку в массив строк

17

Сценарий должен проверить, присутствует ли один предопределенный 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? но я хотел бы знать: Is array.include? метод, который даст мне самый быстрый результат?

    
задан Cocotton 16.02.2012 в 16:25
источник
  • Использовать хеш или набор вместо массива –  Phrogz 16.02.2012 в 16:28
  • Прочтите ruby-doc.org/core-1.9.3/Enumerable.html перед любым программированием на Ruby. –  tokland 16.02.2012 в 16:30
  • Вы можете использовать include? метод, определенный в классе Array, чтобы сделать эту операцию более аккуратной, я не уверен, что она значительно увеличит скорость поиска –  Hunter McMillen 16.02.2012 в 16:30
  • возможный дубликат stackoverflow.com/questions/6140554/... –  Joseph Le Brech 16.02.2012 в 16:31
  • @JosephLeBrech Вопрос здесь в поиске массива. –  Hunter McMillen 16.02.2012 в 16:38
Показать остальные комментарии

5 ответов

31

Вы можете использовать Установить . Он реализован поверх Hash и будет быстрее для больших наборов данных - 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 16.02.2012 в 16:29
источник
  • Или в вашем случае: s = Set.new (ips) –  Phrogz 16.02.2012 в 16:32
  • Здравствуйте, снова Alex :). Исключить исходный код метода кажется почти тем же, что и мой. Или это быстрее? –  Cocotton 16.02.2012 в 16:36
  • @Cocotton: намного быстрее. Вы также можете использовать хэш с ключами ip и «true» в качестве значений. –  steenslag 16.02.2012 в 16:49
  • Очевидное предостережение здесь состоит в том, что Set выполняется быстрее, но построение Set может быть дорогостоящей операцией, поэтому вы не захотите строить набор, чтобы запрашивать его несколько раз. –  Marc Talbot 16.02.2012 в 17:11
  • Для массива из 12,4 миллионов коротких строк: a = ('a' .. 'zzzzz'). to_a; time {a.include? ('0')} # => 0.71s; time {Set.new (a)} # => 11.2s; так что да, накладные расходы на создание набора должны быть полезны для повышения производительности мгновенных запросов. –  Phrogz 15.05.2012 в 21:49
Показать остальные комментарии
4

Вы можете использовать метод include Array #, чтобы вернуть true / false.

Ссылка

if ips.include?(ip) #=> true
  puts 'ip exists'
else
  puts 'ip  doesn\'t exist'
end
    
ответ дан ericraio 16.02.2012 в 16:34
источник
3

Более быстрый способ:

if ips.include?(ip)
  puts "ip exists"
  return 1
else
  puts "ip doesn't exist"
  return nil
end
    
ответ дан Don Cruickshank 16.02.2012 в 16:29
источник
  • Немного быстрее, поскольку каждый из них встречается в C вместо Ruby, но он все еще O (n) по сравнению с O (1) для Hash или Set. –  Phrogz 16.02.2012 в 16:33
2

Вы пытались включить Array # include? функция?

Ссылка

Из источника вы можете видеть почти то же самое, кроме изначально.

    
ответ дан Peter Ehrlich 16.02.2012 в 16:29
источник
  • Это все еще операция O (n), так как она должна искать каждый элемент в массиве (даже если он находится на C). –  Phrogz 16.02.2012 в 16:33
  • Я знаю, что перечисление можно сортировать, но я не знаю, как искать такой отсортированный массив. Для выполнения задания можно сделать индексный столбец базы данных. –  Peter Ehrlich 16.02.2012 в 18:54
  • Даже двоичный поиск - O (log n). Хеширование элемента и поиск его в хеш-таблице - это операция с постоянным временем, которая не связана с количеством сохраненных элементов. –  Phrogz 16.02.2012 в 23:04
2
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

проверьте Documentaion здесь

    
ответ дан dku.rajkumar 16.02.2012 в 16:29
источник
  • Но разве это быстрее, чем мой метод? Потому что исходный код этого, похоже, делает практически то же самое, что и мое. –  Cocotton 16.02.2012 в 16:36
  • , конечно, быстрее .. У меня есть в моем проекте .. Кроме того, когда есть метод в рубине, зачем нам писать дополнительный код. –  dku.rajkumar 16.02.2012 в 16:39
  • @ dku.rajkumar хотел сказать, что он должен быть быстрее, чем .include? реализуется на уровне C в классе Array. –  Ikon 14.07.2015 в 15:40