Сортировка значений для Python?

Question

Меня интересует реализация dict для Python, которая обеспечивает итеративный интерфейс для отсортированных значений.То есть dict с функцией "sortedvalues()".

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

Обратите внимание, что я также не спрашиваю о сортировке по ключам (для этого вопроса есть отличные ответы в Сортировка ключей в Python и Python 2.6 TreeMap / SortedDictionary? ).

Answer 1

Одним из решений является написание класса, который наследует от dict, но также поддерживает список ключей, отсортированных по их значению (sorted_keys), вместе со списком соответствующих (отсортированных) значений (sorted_values).

Затем можно определить метод __setitem__(), который использует модуль bisect, чтобы быстро узнать позицию k, где новая пара (ключ, значение) должна быть вставлена ​​в два списка.Затем вы можете вставить новый ключ и новое значение как в сам словарь, так и в два списка, которые вы поддерживаете, с помощью sorted_values[k:k] = [new_value] и sorted_keys[k:k] = [new_key];к сожалению, временная сложность такой вставки составляет O(n) (то есть O(n^2) для всего словаря).

Другой подход к вставке упорядоченного элемента заключается в использовании модуля heapq и вставке * 1016.* пары в нем.Это работает в O(log n) вместо подхода, основанного на списках предыдущего абзаца.

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

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

Answer 2

Вот еще одна, более простая идея:

• Вы создаете класс, который наследуется от dict.
• Вы используете кеш: вы сортируете ключи только при итерации по словарю и помечаете словарь как отсортированный; вставки должны просто добавлять в список ключей.

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

Answer 3

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

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

Обновление : хитрость, которая может работать для вас, заключается в использовании двойной структуры:

1. обычного dict для хранения пар ключ-значение как обычно

2. любой вид отсортированного списка, например, с использованием bisect

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

Если вам также необходимо знать ключи, сохраните (значение, ключ) пар в вашем списке.

Обновление 2 : попробуйте этот класс:

import bisect
class dictvs(dict):
    def __init__(self):
        self._list = []

    def __setitem__(self, key, value):
        old = self.get(key)
        if old is None:
            bisect.insort(self._list, value)
            dict.__setitem__(self, key, value)
        else:
            oldpos = bisect.bisect_left(self._list, old)
            newpos = bisect.bisect_left(self._list, value)
            if newpos > oldpos:
                newpos -= 1
                for i in xrange(oldpos, newpos):
                    self._list[i] = self._list[i + 1]
            else:
                for i in xrange(oldpos, newpos, -1):
                    self._list[i] = self._list[i - 1]
            self._list[newpos] = value
            dict.__setitem__(self, key, value)

    def __delitem__(self, key):
        old = self.get(key)
        if old is not None:
            oldpos = bisect.bisect(self._list, old)
            del self._list[oldpos]
        dict.__delitem__(self, key)

    def values(self):
        return list(self._list)

Это еще не полный dict, но я думаю.Я не проверял удаления, а только небольшой набор обновлений.Вы должны сделать для него больший модульный тест и сравнить возвращение values() с возвращением sorted(dict.values(instance)).Это просто, чтобы показать, как обновить отсортированный список с bisect

Answer 4

Вы можете использовать skip dict . Это словарь Python, который постоянно сортируется по значению.

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

1. Какой самый высокий / самый низкий пункт?
2. Какие предметы имеют значение между X и Y?