Ниже — сравнение пяти парадигм программирования на одном и том же примере: реализация кэша с политикой LRU (least-recently-used). Для каждой парадигмы — краткий подход/пример, асимптотика, преимущества/ограничения и когда выбирать.

1) Императивный стиль (низкоуровневое управление состоянием)

Идея: явные структуры данных + мутация состояния. Типичная реализация: хеш-таблица для O(1) доступа + двусвязный список для поддержания порядка LRU.

Пример (псевдокод, C-подобный):
struct Node { key, value; Node prev; Node next; }
struct LRU {
int capacity;
hashmap<Key, Node> map;
Node head; // most recent
Node* tail; // least recent
}

function move_to_head(node):
// удалить node из его места и вставить в head

function get(key):
node = map.get(key)
if node == null: return null
move_to_head(node)
return node.value

function put(key, value):
node = map.get(key)
if node != null:
node.value = value
move_to_head(node)
return
node = new Node(key,value)
map.put(key,node)
insert_at_head(node)
if map.size > capacity:
remove = tail
remove_tail()
map.remove(remove.key)

Асимптотика: get/put — O(1) время, O(n) память.

Плюсы:

Высокая производительность и предсказуемость.Низкая накладная стоимость и контроль памяти.Подходит для встраиваемых/реальных систем, где важна скорость/память.

Минусы:

Больше «боилерплейта» (ручная работа с указателями/инвариантами).Сложнее обеспечить безопасность при конкуренции (требуются блокировки).

Когда выбирать:

Когда нужна максимальная производительность и контроль.В системах с ограниченными ресурсами (embedded, real-time).

2) Объектно‑ориентированный подход

Идея: инкапсулировать состояние и логику в классах/объектах, использовать полиморфизм и композицию.

Пример (Python-подобный, классическая реализация):
class LRUCache:
def init(self, capacity):
self.capacity = capacity
self.map = {} # key -> node
self.head = Node() # dummy head
self.tail = Node() # dummy tail
link(head, tail)

def _remove(self, node): ...
def _add_to_front(self, node): ...

def get(self, key):
node = self.map.get(key)
if not node: return None
self._remove(node); self._add_to_front(node)
return node.value

def put(self, key, value):
if key in self.map:
node = self.map[key]; node.value = value
self._remove(node); self._add_to_front(node)
return
node = Node(key,value)
self.map[key] = node; self._add_to_front(node)
if len(self.map) > self.capacity:
lru = self.tail.prev
self._remove(lru); del self.map[lru.key]

Асимптотика: get/put — O(1).

Плюсы:

Хорошая инкапсуляция и читаемость.Легче расширять (наследование, декораторы) — e.g. разные политики вытеснения.Часто отражает моделирование предметной области.

Минусы:

При неблагоразумном дизайне — избыточность/сложная иерархия.В многопоточном контексте нужно явно синхронизировать методы.

Когда выбирать:

В больших приложениях, где важна модульность, расширяемость и понятная структура (backend-сервисы, библиотеки).

3) Функциональный (чисто функциональный, без мутации)

Идея: состояние не мутирует, каждая операция возвращает новую версию кэша. Можно использовать персистентные структуры (Map, Sequence, Finger trees) для эффективности.

Пример (Haskell-подход, упрощённо):
-- Cache только функционально: get :: Key -> Cache -> (Maybe Value, Cache)
data Cache = Cache { capacity :: Int
, mapKV :: Map Key Value
, order :: [Key] } -- head = most recent

get k c =
case Map.lookup k (mapKV c) of
Nothing -> (Nothing, c)
Just v ->
let order' = k : filter (/= k) (order c) -- переместить в начало (O(n))
in (Just v, c { order = order' })

put k v c =
if Map.member k (mapKV c)
then let map' = Map.insert k v (mapKV c)
order' = k : filter (/= k) (order c)
in c { mapKV = map', order = order' }
else
let map' = Map.insert k v (mapKV c)
order' = k : order c
(map'', order'') = if Map.size map' > capacity c
then let lru = last order' in (Map.delete lru map', init order')
else (map', order')
in c { mapKV = map'', order = order'' }

Асимптотика: в этом простом варианте операции — O(n) из‑за фильтра по списку. Можно улучшить до O(log n) или O(1) амортизированно, используя более сложные персистентные DS (finger trees, indexed maps), но они сложнее.

Плюсы:

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

Минусы:

Возможен накладной копирования и более сложные структуры для эффективности.Реализация эффективного O(1) LRU в чисто функциональном стиле требует продвинутых персистентных структур.

Когда выбирать:

Когда важна корректность, воспроизводимость и безопасность при параллелизме.В функциональных стек‑проектах (F#, Haskell, Clojure) или при необходимости легко версионировать состояния (undo/redo).

4) Логическая парадигма (Prolog)

Идея: представить состояние как набор фактов/правил или как аргумент функции перехода; можно моделировать операции как трансформации состояния либо пользоваться динамическими фактами (assert/retract) для имитации мутации.

Пример (Prolog с динамическим состоянием — императивная манипуляция базы фактов):
:- dynamic cache_state/2. % cache_state(MapAsList, OrderList)

% Инициализация: cache_state([], []).
get(Key, Value) :-
retract(cache_state(Map, Order)),
( member((Key,Value), Map) ->
delete(Order, Key, OrderWithout), NewOrder = [Key|OrderWithout],
assert(cache_state(Map, NewOrder))
; assert(cache_state(Map, Order)), fail ).

put(Key, Value) :-
retract(cachestate(Map, Order)),
( select((Key,), Map, MapWithout) -> Map1 = [(Key,Value)|MapWithout], Order1 = [Key|select_remove(Order, Key)]
; Map1 = [(Key,Value)|Map], Order1 = [Key|Order],
( length(Map1, N), capacity(C), N > C -> lastelement(Order1, LRU), delete(Map1, (LRU,), Map2), remove_last(Order1, NewOrder), Map1 = Map2, Order1 = NewOrder ; true )
),
assert(cache_state(Map1, Order1)).

(Примечание: пример иллюстративен; в Prolog удобнее хранить состояния явно и писать предикаты-переходы.)

Асимптотика: обычно линейная при наивной реализации; можно оптимизировать с индексами/отдельными фактами.

Плюсы:

Удобно описывать правила и соотношения, прототипировать логику вытеснения/политик.Полезно в задачах логического вывода, поиска, ограничений.

Минусы:

Имплементация mutable LRU выходит за рамки «чистого» логического программирования (чаще используются динамические факты — это императивно).Эффективность и масштабирование часто хуже, чем у императивных/ООП‑реализаций.

Когда выбирать:

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

5) Декларативный подход (на примере SQL/БД)

Идея: хранить кэш в декларативно управляемом хранилище (таблица), описывать операции через запросы и транзакции. БД выполняет детали реализации (индексы, удаление старых записей).

Пример (SQL):
CREATE TABLE cache (
key TEXT PRIMARY KEY,
value BLOB,
last_access TIMESTAMP
);
-- get:
BEGIN;
SELECT value FROM cache WHERE key = :k;
UPDATE cache SET last_access = CURRENT_TIMESTAMP WHERE key = :k;
COMMIT;

-- put:
BEGIN;
INSERT INTO cache(key, value, last_access) VALUES(:k,:v,CURRENT_TIMESTAMP)
ON CONFLICT(key) DO UPDATE SET value=excluded.value, last_access=excluded.last_access;
-- удалить лишние записи, если превышен capacity:
DELETE FROM cache WHERE key IN (
SELECT key FROM cache ORDER BY last_access ASC LIMIT (
SELECT MAX(0, (SELECT COUNT(*) FROM cache) - :capacity)
)
);
COMMIT;

Асимптотика: зависит от СУБД и индексов; с индексом по last_access удаление — O(log n) или лучше на уровне СУБД.

Плюсы:

Простота: декларативно описать «хранить последние N по времени».Транзакционность, устойчивость, возможность шардинга/репликации.Подходит для кэша, разделяемого между процессами/машинами.

Минусы:

Задержки и накладные расходы СУБД; не всегда подходит для сверх‑низкой латентности.Невыгодно для встраиваемых/вплотную работающих систем (по сравнению с in-memory O(1)).

Когда выбирать:

Если нужно централизованное, устойчивое и многопользовательское хранилище кэша.Для кэша, где важны консистентность/репликация/аналитика (например, shared cache между микросервисами).

Краткое сравнение и рекомендации

Производительность (минимальная латентность, O(1)): императивный / ООП с hashmap + двусвязный список.Безопасность при параллелизме и простота рассуждений: функциональный (иммутабельность), особенно если используются персистентные структуры.Модульность/расширяемость/интеграция с OO-системой: ООП.Быстрая декларативная реализация для разделяемого/устойчивого кэша: SQL/декларативная СУБД.Прототипирование политик/правил/инференций: логическое программирование (Prolog) — удобен для выражения правил вытеснения, но не для высокоскоростного кэша.

Заключение
Выбор парадигмы зависит от требований: если нужна максимальная скорость и контроль — императив/ООП; если важна корректность и конкурентность — функциональный (или ООП с хорошо продуманной синхронизацией); если цель — совместное, транзакционное хранение — декларативный (SQL); логика хороша для моделирования и верификации правил, но не как высокопроизводительная реализация LRU. Если хотите, могу привести полноценную реализацию (на каком языке и в какой парадигме вам интереснее?) с реальным кодом и тестами.