Эффективный способ поддерживать отсортированный список счетчиков доступа в Python

Question

Допустим, у меня есть список объектов. (Теперь все вместе: «У меня есть список объектов».) В веб-приложении, которое я пишу, каждый раз, когда приходит запрос, я выбираю один из этих объектов в соответствии с неуказанными критериями и использую его для обработки запрос. В основном так:

def handle_request(req):
    for h in handlers:
        if h.handles(req):
            return h
    return None

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

Очевидное решение - создать handlers список из (count, handler) пар, и каждый раз при выборе обработчика увеличивать счетчик и прибегать к списку.

    def handle_request(req):
        for h in handlers[:]:
            if h[1].handles(req):
                h[0] += 1
                handlers.sort(reverse=True)
                return h[1]
        return None

Но так как когда-либо будет только один элемент из строя, и я знаю, какой это будет элемент, похоже, что какая-то оптимизация должна быть возможной. Может быть, в стандартной библиотеке есть что-то, что особенно хорошо подходит для этой задачи? Или какая-то другая структура данных? (Даже если это не реализовано в Python) Или я должен / мог бы сделать что-то совершенно другое?

Answer 1

Алгоритм сортировки Python, timsort, довольно волшебен: если ваш список отсортирован за исключением одного элемента, он будет по сути (обнаруживать и) использовать этот факт, сортируя в O(N) времени. (Джош Блох, гуру Java, был настолько впечатлен презентацией о характеристиках производительности timsort, что начал кодировать ее для Java на своем ноутбуке - она ​​должна скоро стать стандартной сортировкой Java). Я просто делаю сортировку после каждого определения местоположения и приращения и очень сомневаюсь, что другие подходы могут победить timsort.

Редактировать : первая альтернатива, которая приходит на ум, конечно, это, возможно, «сдвинуть» только элемент, количество которого вы только что увеличили. Но сначала небольшая оптимизация, чтобы избежать копирования handlers ...):

def handle_request(req):
    for h in handlers:
        if h[1].handles(req):
            h[0] += 1
            handlers.sort(reverse=True)
            break
    else:
        return None
    return h[1]

теперь вариант "сдвиг вверх"

def handle_request(req):
    for i, h in enumerate(handlers):
        if h[1].handles(req):
            h[0] += 1
            for j in reversed(range(i+1)):
                if handlers[j][0] <= h[0]:
                    break
            if j < i:
                handlers[j+1:i+1] = handlers[j:i]
                handlers[j] = h
            break
    else:
        return None
    return h[1]

Я могу представить шаблоны доступа, где этот подход мог бы сэкономить немного времени - например, если распределение было настолько искажено, что большинство обращений были в обработчиках [0], это сделало бы небольшую работу, кроме одного сравнения (в то время как sort нужно около N из них даже в лучшем случае). Без репрезентативных образцов ваших шаблонов доступа я не могу подтвердить или опровергнуть это! -)

Answer 2

Несмотря на то, что timsort волшебен, использование list.sort () не очень хорошая идея, поскольку (как минимум) требуется, чтобы каждая соседняя пара записей каждый раз сравнивалась, чтобы убедиться, что список отсортирован.

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

Удивительно, но лучший подход для вашей ситуации - использовать что-то вроде пузырьковой сортировки. Поскольку все записи в порядке, кроме той, чей счетчик вы только что настроили, все, что может произойти, это то, что одна запись перемещается немного вверх в списке. А поскольку вы увеличиваете только на единицу, это не должно далеко продвинуться. Так что просто сравните его с предыдущей записью, и если они вышли из строя, поменяйте их местами. Что-то вроде:

def handle_request(req):
    for (i, h) in enumerate(handlers):
        if h[1].handles(req):
            h[0] += 1
            while i > 0 and handlers[i][0] > handlers[i-1][0]:
                handlers[i-1], handlers[i] = handlers[i], handlers[i-1]
                i -= 1
            return h[1]
    return None

(Конечно, если несколько потоков обращаются к массиву обработчиков, вам нужно выполнить какую-то синхронизацию.)

Answer 3

Звучит как работа для очереди с приоритетами (a.k.a. heapq). Python имеет реализацию очереди приоритетов как heapq в стандартной библиотеке. По сути, вы держите дерево / кучу с наиболее часто используемым или самым последним использованным элементом сверху.

Answer 4

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

class MRUSortedIterable:

    def __init__(self, data):
        self._data = list(data)
        self._i = 0

    def __iter__(self):
        if self._i:  # if previous use had a success, move to top
            self._data[0], self._data[1:self._i+1] = self._data[self._i], self._data[0:self._i]
        for self._i, value in enumerate(self._data):
            yield value
        self._i = 0  # reset on exhaustion (ie failed to find what we wanted)

Вы используете это так (например):

MY_DATA = MRUSortedIterable(a_list_of_objects)
...
def handler(criteria):
    for data in MY_DATA:
        if test(data, criteria):
            return data

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

ВАЖНО: Это не поточно-ориентированный (который, вероятно, был проблемой для вашего веб-сервера 2 года назад). Но это , imho, очень аккуратно ...

Если подумать, то это MRU, тогда как heapq с подсчетом доступа будет упорядочен по общему использованию. Таким образом, они, вероятно, работают немного по-другому (heapq, вероятно, лучше, если шаблоны доступа постоянны).

Answer 5

Я предполагаю, что все эти дополнительные вызовы sort () замедлят вас больше, чем ускорят. Мое предложение будет заключаться в том, чтобы запоминать handle_request (), используя такую ​​обертку (взято из здесь )

class Memoize:
    """Memoize(fn) - an instance which acts like fn but memoizes its arguments
    Will only work on functions with non-mutable arguments
    """
    def __init__(self, fn):
        self.fn = fn
        self.memo = {}
    def __call__(self, *args):
        if not self.memo.has_key(args):
            self.memo[args] = self.fn(*args)
        return self.memo[args]

Вы можете использовать его так:

handle_request = Memoize(handle_request)

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