Что можно использовать «TreeDict» (или Treemap) на практике?

Question

Я разрабатываю класс TreeDict в Python. Это в основном диктовка, которая позволяет вам получить свои пары ключ-значение в отсортированном порядке, как и класс коллекции Treemap в Java.

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

К сожалению, я не может думать о какой-либо реальной жизненной проблеме, которая потребует такого класса. Я подозреваю, что причина, по которой мы не сортировали dicts в Python, состоит в том, что на практике они не требуются достаточно часто, чтобы быть достойными этого, но я хочу, чтобы вас доказали неправильно.

Можете ли вы придумать какие-либо конкретные применения «TreeDict»? Любая проблема в реальной жизни, которая лучше всего будет решена этой структурой данных? Я просто хочу знать наверняка, стоит ли это.

Answer 1

Это полезно, когда вам нужно пройти Словарь по порядку ключей; который появляется иногда. Я на самом деле нашел его бесконечно более распространенным в некоторых конкурсах программирования, чем что-либо еще (думаю, ACM и т. Д.).

Самая полезная функция TreeMap - это когда вы хотите быстро найти ключ min или max; используя отсортированный словарь, это часто один вызов метода; и алгоритмически может быть выполнено в O (log (n)) времени, в отличие от повторения каждой клавиши, ищущей min/max, если коллекция не сортирована. В принципе, гораздо более дружелюбный интерфейс.

Одно из наиболее распространенных случаев, с которыми я сталкиваюсь, когда объекты идентифицируются определенным именем и вы хотите распечатать объекты, упорядоченные в соответствии с именем; скажем, сопоставление от имени каталога к числу файлов в каталоге.

Другое место, которое я использовал, находится в оболочке таблицы Excel; отображение из номера строки в объект строки. Это позволяет быстро найти последний индекс строки, без перебора по каждой строке.

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

Answer 2

Я часто использую Dict<DateTime, someClassOrValue> при работе с промышленным процессом data-- Valve начала открытия/закрытия, машины/остановки и т.д.

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

Однако, поскольку я смог использовать linq в C#, я обнаружил, что часто проще работать с IEnumerables и использовать методы расширения IQueryable для получения необходимой мне информации.

Answer 3

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

Answer 4

Они могут упростить реализацию различных алгоритмов.

Answer 5

Для всего сообщения «GROUP BY» требуется отсортированный словарь.

summary = sortedDefaultDict() 
for row in somePileOfData: 
    summary[row.group_by] += row.balance 
for k in sorted(summary.keys()): 
    print k, summary[k] 

Это делается так часто в приложениях для хранения данных, что трудно выразить, насколько это важно.

Если вызов функции sorted не работает, он экономит массу времени в долгосрочной перспективе.

Answer 6

Я видел несколько ответов, указывающих на функцию «ходить в упорядоченной последовательности», что действительно важно, но никто не выделяет другую большую функцию, которая «набирает первую запись с помощью ключа> = это». Это имеет много применений, даже когда нет реальной необходимости «ходить» оттуда.

Например (это произошло в недавно SO ответ), что вы хотите, чтобы генерировать псевдослучайные значения с заданными относительными частотами - то есть, вы дали, скажем, Dict d:

{'wolf': 42, 'sheep': 15, 'dog': 23, 'goat': 15, 'cat': 5} 

и нужен способ генерировать «волк» с вероятностью 42 из 100 (поскольку 100 - это общая относительная частота), «овец» 15 из 100 и т. Д .; и число отдельных значений может быть довольно большим, равно как и относительные частоты.

Затем сохраните заданные значения (в любом порядке) в качестве значений в карте деревьев, при этом соответствующие клавиши являются «общей суммарной частотой» вплоть до этой точки. То есть:

def preprocess(d): 
    tot = 0 
    for v in d: 
     tot += d[v] 
     treemap.insert(key=tot, value=v) 
    return tot, treemap 

Теперь, генерирует значение может быть довольно быстро (O(log(len(d)))), следующим образом:

def generate(tot, treemap, r=random): 
    n = r.randrange(tot) 
    return treemap.firstGTkey(n).value 

, где firstGTKey представляет собой метод, который возвращает первый элемент (с .key и .value атрибутами, в этот гипотетический пример) с ключом> данный аргумент. Я использовал этот подход с большими файлами, хранящимися как B-деревья, например (используя, например, bsddb.bt_open и метод set_location).

Answer 7

Вы видели это: http://code.activestate.com/recipes/576998/?

zuo