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

StackOverflow https://stackoverflow.com/questions/1014247

Вопрос

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

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

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

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

Это было полезно?

Решение

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

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

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

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

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

Другие советы

Я видел несколько ответов, указывающих на " ходить в упорядоченной последовательности " особенность, которая действительно важна, но ни одна не выделяет другую большую особенность, которая является " найдите первую запись с ключом > = this " ;. Это имеет множество применений, даже когда нет реальной необходимости & Quot; walk & Quot; оттуда.

Например (это появилось в недавнем 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).

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

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

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

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

Почти все " 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 не работает, в долгосрочной перспективе это сэкономит массу времени.

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

цзо

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top