Для чего можно использовать TreeDict (или Treemap) на практике?
Я разрабатываю класс TreeDict в Python. Это в основном диктат, который позволяет вам получать его пары ключ-значение в отсортированном порядке, точно так же, как класс коллекции Treemap в Java.
Я реализовал некоторые функциональные возможности, основанные на способе использования уникальных индексов в реляционных базах данных, например, функции, позволяющие извлекать значения, соответствующие диапазону ключей, ключам, большим, меньшим или равным определенному значению в отсортированном порядке, строкам. или кортежи, которые имеют определенный префикс в отсортированном порядке и т. д.
К сожалению, я не могу придумать ни одной реальной проблемы, которая потребует такого класса. Я подозреваю, что причина, по которой мы не отсортировали диктанты в Python, заключается в том, что на практике они не требуются достаточно часто, чтобы того стоить, но я хочу оказаться неправым.
Можете ли вы вспомнить какие-либо конкретные применения TreeDict? Любая реальная проблема, которую лучше всего решить с помощью этой структуры данных? Я просто хочу знать наверняка, стоит ли это того.
7 ответов
Это полезно, когда вам нужно пройти словарь в порядке ключей; который приходит в случае. На самом деле я обнаружил, что в определенных соревнованиях по программированию он встречается гораздо чаще, чем во всех других (например, ACM и т. Д.).
Наиболее полезная функция TreeMap - это когда вы хотите быстро найти ключ min или max; используя отсортированный словарь, это часто - единственный вызов метода; и алгоритмически может быть сделано за O(log(n)), в отличие от итерации по каждому ключу в поисках мин / макс, если коллекция не отсортирована. В основном, намного более дружественный интерфейс.
Один из наиболее распространенных случаев, с которыми я сталкиваюсь, - это когда объекты идентифицируются по определенному имени, и вы хотите распечатать объекты, упорядоченные в соответствии с именем; скажем, сопоставление имени каталога с количеством файлов в каталоге.
Еще одно место, где я его использовал, - это оболочка для электронных таблиц Excel; отображение номера строки в объект строки. Это позволяет быстро найти индекс последней строки, не просматривая каждую строку.
Кроме того, это полезно, когда вы можете легко определить отношение сравнения для ключей, но не обязательно функцию хеширования, как это необходимо для HashMaps. Лучший (хотя и слабый) пример, который я могу придумать, это строковые ключи без учета регистра.
Я видел несколько ответов, указывающих на функцию "ходить в упорядоченной последовательности", которая действительно важна, но ни один из них не выделяет другую важную функцию, которая "находит первую запись с ключом>= это". У этого есть много применений, даже когда нет никакой реальной потребности "идти" оттуда.
Например (это появилось в недавнем SO-ответе), скажем, вы хотите сгенерировать псевдослучайные значения с заданными относительными частотами - т.е. 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. Это в основном позволяет хранить все в словаре в отсортированном порядке. Я знаю, что в приложении, над которым я сейчас работаю, такой класс используется для запроса структуры данных.
Почти для всех отчетов "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/?
цзо
Я часто использую Dict<DateTime, someClassOrValue> при работе с данными производственного процесса - открытие / закрытие клапана, запуск / останов оборудования и т. д.
Сортировка ключей особенно полезна, когда мне нужно сравнить промежутки времени между событиями запуска / остановки или открытия / закрытия за приемлемое время.
Однако, поскольку я смог использовать linq в C#, я обнаружил, что часто проще просто работать с IEnumerables и использовать методы расширения IQueryable для получения необходимой мне информации.