Блог

Главная - Вопросы по программированию - map::lower_bound() эквивалент для класса dict в python?

map::lower_bound() эквивалент для класса dict в python?

#python #unordered-map

#python #stl

Вопрос:

Я пишу некоторый код, который требует от меня извлечения нижней границы ключа (для простоты игнорируйте ключи, которые лежат ниже наименьшего ключа в коллекции).

В C используется std::map (как наиболее сопоставимый тип данных) Я бы просто использовал lower_bound() для возврата итератора.

Мой Pythonfoo не настолько хорош, но я предполагаю, что (в случае, если в Python еще нет способа сделать это), это было бы хорошим использованием лямбда-функции …

Каков Pythonic способ получения ключа нижней границы для данного индекса?

На случай, если вопрос слишком абстрактный, это то, что я на самом деле пытаюсь сделать:

У меня есть Python dict, проиндексированный по дате. Я хочу иметь возможность использовать дату для поиска dict и возвращать значение, связанное с нижней границей указанного ключа.

Следующий фрагмент:

 mymap = { datetime.date(2007, 1, 5): 'foo',
          datetime.date(2007, 1, 10): 'foofoo',
          datetime.date(2007, 2, 2): 'foobar',
          datetime.date(2007, 2, 7): 'foobarbar' }

mydate = datetime.date(2007, 1, 7)

# fetch lbound key for mydate from mymap
def mymap_lbound_key(orig):
    pass # return the lbound for the key

Я действительно не хочу перебирать ключи в поисках первого ключа <= предоставленный ключ, если только нет лучшей альтернативы …

Ответ №1:

dict Класс Python не обладает такой функциональностью; вам нужно было бы написать его самостоятельно. Конечно, было бы удобно, если бы ключи были уже отсортированы, не так ли, чтобы вы могли выполнять двоичный поиск по ним и избегать перебора их всех? В этом ключе я бы взглянул на sorteddict класс в blist пакете. http://pypi.python.org/pypi/blist /

Ответ №2:

если у вас каким-то образом перегружена дата, чтобы она могла сравнивать, загляните в модуль bisect.

пример минимального целочисленного кодирования:

 from bisect import bisect_left

data = {
    200 : -100,
    -50 : 0,
    51 : 100,
    250 : 200
}

keys = list(data.keys())

print data[  keys[ bisect_left(keys, -79) ]  ]

Ответ №3:

Когда мне нужно что-то, напоминающее карту c , я использую SortedDict. Вы можете использовать irange для получения итератора по элементам, превышающим заданный ключ — я думаю, именно так std::lower_bound и работает.

код:

 from sortedcontainers import SortedDict
sd = SortedDict()
sd[105] = 'a'
sd[102] = 'b'
sd[101] = 'c'

#SortedDict is sorted on insert, like std::map
print(sd)

# sd.irange(minimum=<key>) returns an iterator beginning with the first key not less than <key>
print("min = 100", list(sd.irange(minimum=100)))
print("min = 102", list(sd.irange(minimum=102)))
print("min = 103", list(sd.irange(minimum=103)))
print("min = 106", list(sd.irange(minimum=106)))

вывод:

 SortedDict(None, 1000, {101: 'c', 102: 'b', 105: 'a'})
min = 100 [101, 102, 105]
min = 102 [102, 105]
min = 103 [105]
min = 106 []

Комментарии:

1. Я не хочу создавать список; просто хочу выяснить, насколько «далеко» находится итератор, возвращаемый sd.irange(minimum=<key>) , с самого начала. В C я бы сделал что-то вроде sd.lower_bound(key)-sd.begin() . Есть ли способ сделать это ? Заранее благодарю.

2. next(sd.irange(minimum=103)) - sd.keys()[0] Делает то, что вы хотите? Он находит разницу между первым ключом над границей и первым ключом. В данном случае это 105 — 101 = 4. Если это так, имейте в виду, что next() возникнет исключение StopIteration, если никакие элементы не превышают границы.

3. Спасибо! Кроме того, существует ли «стратегия» для решения таких проблем в Python, которая обычно может быть решена в C с использованием красно-черного дерева (std::map)? Ваш метод работает, но все это больше похоже на «взлом», а не на идиоматическое питоновское действие, отсюда и мой вопрос.

4. Я собираюсь рискнуть и сказать «вероятно». В экосистеме python много закоулков. Но мой путь увел меня от деревьев к более общим структурам, таким как ориентированные графики, поэтому я действительно не знаю, какой уголок или трещину порекомендовать для вас. Извините.

Ответ №4:

Все еще не уверен, что такое «нижняя граница»: последняя дата до / после даты запроса?

В любом случае, поскольку dict не налагает внутренний порядок на свои ключи, вам нужна другая структура. Храните свои ключи в некоторой структуре, которая сохраняет их отсортированными и позволяет выполнять быстрый поиск.

Самым простым решением было бы просто сохранить даты, отсортированные, в списке (дата, значение) и выполнить двоичный поиск, чтобы увеличить нужный регион. Если вам нужна лучшая производительность, я думаю, что b-дерево — это то, что вам нужно.