Есть ли метод «lower_bound» в Ruby?

Question

В C++, std::map#lower_bound просматривает элемент и возвращает на нем итератор, или если он отсутствует на карте, возвращает итератор ближайшего элемента на карте, который меньше.

Есть ли способ в Ruby с таким же поведением, как std::map#lower_bound для примера Hash? Если нет, следует ли мне расширить класс Hash с помощью моего метода или есть комбинация функций для достижения того же эффекта/сложности?

Answer 1

Есть жемчужина rbtree. Он отображает ключи как значения хеша, но сохраняет свои элементы в порядке возрастания ключа. Интерфейс почти идентичен интерфейсу Hash.

gem install rbtree 

Пример:

require "rbtree" 

rbtree = RBTree["a", 20, "b", 40, "c", 60, "d", 80, "e", 100] 

itlow = rbtree.lower_bound("b") 
itup = rbtree.upper_bound("d") 

rbtree.bound(itlow.first, itup.first) do |k, v| 
    puts "- #{[k, v]}" 
end 

Выход:

-- ["b", 40] 
-- ["c", 60] 
-- ["d", 80] 

Answer 2

Рубин Хэши не имеют такой возможности, потому что нет никакого способа, чтобы найти ближайший элемент в хэш элемент, который не существует в Hash. Это свойство всех хешей, а не только Ruby Hashes. Два элемента могут храниться очень далеко друг от друга, даже если их значения очень близки - все зависит от используемой хеш-функции.

Причина, по которой map.lower_bound возможна в C++, состоит в том, что std :: map - это дерево, а не хеш, и поэтому поиск по дереву предполагает посещение всех (log n) слоев дерева (в худшем случае) независимо существует ли ключ или нет. Как говорит Саид, используйте rbtree (или некоторую другую сбалансированную древовидную структуру данных, например https://github.com/Kanwei/Algorithms/), если вам требуется поведение с более низким значением.

Answer 3

Предложение по использованию дерева вместо хэша, вероятно, является лучшим. Но вы можете использовать более грубую силу для получения этих значений.

def get_lower_bound(hash, dt) 
     lb_key = nil 
     lb_val = nil 
     hash.each do |key, val| 
      if lb_key == nil or lb_key <= key and key <= dt 
       lb_key = key 
       lb_val = val 
      end 
     end 
     lb_val 
    end 

    def get_upper_bound(hash, dt) 
     ub_key = nil 
     ub_val = nil 
     hash.each do |key, val| 
      if ub_key == nil or ub_key >= key and key >= dt 
       ub_key = key 
       ub_val = val 
      end 
     end 
     ub_val 
    end