Как спроектировать последний недавно использованный кеш?

Question

Как спроектировать последний недавно использованный кеш?

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

Каждый раз, когда вы посещаете предмет, проверяйте его в структуре данных. Если элемент был в кеше, обновите время его посещения. В противном случае вставьте его в кеш. Размер кэша фиксированный, если он заполнен, удалите самый старый элемент.

Мое решение:

1. Использовать карту

2. Инициализация: сортировка карты по f (visitTime) в порядке убывания. O (nlg n)

3. Если предмет посещен, найдите его на карте с помощью O (lg n).

4. Если это было на карте, обновите время O (1). Сортировать карту O (LG п).

5. Если нет, вставьте его в карту, а затем отсортируйте. O (LG N)

6. Если размер карты> фиксированный размер, удалите последний элемент O (1).

Другое решение:

1. Использовать хеш-таблицу

2. Сортировка O (n lgn).

3. Если предмет посещен, найдите его в талбе с помощью O (1).

4. Если это было в таблице, обновите время O (1). Сортировка таблицы O (n lg n).

5. Если нет, вставьте его в таблицу, а затем отсортируйте. O (n lg n)

6. Если размер таблицы> фиксированный размер, удалить последний элемент O (1).

Есть ли лучшие решения? O (n)?

Answer 1

Если вы используете двусвязный список, вы получите O (1) вставку (после поиска), O (1) удаление, O (n) поиск.

Предполагается, что вы вставляете новые элементы вfront:

Если кэш не заполнен, просто добавьте в начало (O (1)).

Если вам нужно обновить элемент, найдите его (O (n)),удалите его из связанного списка (O (1)), затем добавьте в начало (O (1)).

Если вам нужно удалить самый старый, чтобы вставить новый элемент, удалите конечный элемент (O(1)) и вставьте в начало (O (1)) [примечание: в этом случае сначала необходимо выполнить поиск по списку, чтобы определить, не находится ли элемент в кэше, поэтому O (n)].

Связанный список также может дать вам то же время, так как поиск оставит вас на последнем элементе.

Answer 2

Кэш LRU Python имеет O (1) вставку, удаление и поиск. Его дизайн использует двусвязный список записей (упорядоченный по возрастанию) и хеш-таблицу для поиска конкретной ссылки.

Вот упрощенная (но быстрая) версия, содержащая менее 40 строк очень простого Python. Не должно быть сложно перевести решение Python на C ++:

class LRU_Cache(object):

    def __init__(self, original_function, maxsize=1000):
        self.original_function = original_function
        self.maxsize = maxsize
        self.mapping = {}

        PREV, NEXT, KEY, VALUE = 0, 1, 2, 3
        self.head = [None, None, None, None]        # oldest
        self.tail = [self.head, None, None, None]   # newest
        self.head[NEXT] = self.tail

    def __call__(self, *key):
        PREV, NEXT, KEY, VALUE = 0, 1, 2, 3
        mapping, head, tail = self.mapping, self.head, self.tail
        sentinel = object()

        link = mapping.get(key, sentinel)
        if link is sentinel:
            value = self.original_function(*key)
            if len(mapping) >= self.maxsize:
                oldest = head[NEXT]
                next_oldest = oldest[NEXT]
                head[NEXT] = next_oldest
                next_oldest[PREV] = head
                del mapping[oldest[KEY]]
            last = tail[PREV]
            link = [last, tail, key, value]
            mapping[key] = last[NEXT] = tail[PREV] = link
        else:
            link_prev, link_next, key, value = link
            link_prev[NEXT] = link_next
            link_next[PREV] = link_prev
            last = tail[PREV]
            last[NEXT] = tail[PREV] = link
            link[PREV] = last
            link[NEXT] = tail
        return value

if __name__ == '__main__':
    p = LRU_Cache(ord, maxsize=3)
    for c in 'abcdecaeaa':
        print(c, p(c))

Answer 3

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

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

Answer 4

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

Редактировать: итератор std :: list действителен при добавлении и удалении элементов при условии, что итератор самого элемента ссылается нане удаляется.См. Последние строки в разделе Емкость и распределение в Википедии.

Answer 5

Посмотрите на boost :: multi_index .Одним из примеров, которые он показывает, является MRU List .

Answer 6

Вам не нужно сортировать контейнер.Просто добавьте элементы к карте или вектору и проведите по ним линейно, чтобы найти нужный элемент (или самый старый элемент).

Тогда это будет O(n).