Для чего можно использовать TreeDict (или Treemap) на практике?

Question

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

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

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

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

Answer 1

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

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

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

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

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

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 2

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

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

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

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

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

Answer 3

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

Answer 4

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

цзо

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

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

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

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

Answer 7

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