Кратко: декларативный стиль описывает «что» (набор данных / условие), императивный — «как» (пошаговый алгоритм). На примере «найти все простые числа до $N$» — приведу пример в SQL (декларативно) и в Python (императивно, Эратосфен).
1) Декларативный пример (PostgreSQL):
```sql
-- Найти простые числа от 2 до N (проверка делимости до sqrt(n))
WITH nums AS (
SELECT generate_series(2, :N) AS n
)
SELECT n
FROM nums
WHERE NOT EXISTS (
SELECT 1
FROM generate_series(2, floor(sqrt(n))) AS d
WHERE n % d = 0
)
ORDER BY n;
```
Комментарий: запрос описывает множество чисел и условие «нет делителя», СУБД решает, как выполнять (сканирование, параллелизм, индексы и т.д.). По сути это наивная проверка делимости — асимптотика близка к $O(N\sqrt{N})$ в худшем случае (в зависимости от оптимизации СУБД).
2) Императивный пример (Python, решето Эратосфена):
```python
def primes_upto(N):
if N < 2:
return []
sieve = [True] * (N + 1)
sieve[0] = sieve[1] = False
p = 2
while p * p <= N:
if sieve[p]:
for m in range(p*p, N+1, p):
sieve[m] = False
p += 1
return [i for i, is_prime in enumerate(sieve) if is_prime]
```
Комментарий: этот алгоритм имеет время примерно $O(N\log \log N)$ и память $O(N)$, легко оптимизируется (битовые массивы, шаг по нечётным и т.д.).
Сравнение преимуществ и ограничений
- Декларативная парадигма (SQL):
- Плюсы:
- Коротко и выразительно: описываете «что» нужно получить.
- СУБД может автоматически оптимизировать выполнение, использовать параллелизм, кэш, индексы.
- Хороша для задач, ориентированных на наборы данных и выражения выборки/фильтрации.
- Меньше явного состояния — проще формально анализировать.
- Минусы:
- Трудно выразить и эффективно реализовать сложные пошаговые алгоритмы (например, быстрые реализации решета с битовыми операциями).
- Ограничения языка/движка: рекурсия и циклы в SQL менее удобны и могут быть медленнее.
- Произвольный контроль памяти/производительности — в руках СУБД; сложно добиться низкоуровневой оптимизации.
- Асинхронность/параллелизм зависят от движка; не всегда предсказуемы.
- Императивная парадигма (Python/процедурный код):
- Плюсы:
- Полный контроль над алгоритмом и оптимизациями (структуры данных, низкоуровневые представления, параллельные примитивы).
- Легко реализовать эффективные алгоритмы (решето с битами, сегментированное решето для больших $N$).
- Явный поток управления — проще профилировать и отлаживать производительность.
- Минусы:
- Код может быть длиннее и сложнее логически (нужно управлять состоянием).
- При неумелой реализации можно получить худшую производительность, чем простая декларативная выборка в СУБД для больших таблиц.
- Для больших данных требуется забота о распределении/параллелизме.
Практическая рекомендация:
- Если данные уже в СУБД и $N$ невелик/средний — декларативный запрос удобен.
- Если нужна высокая производительность, масштабирование на большие $N$ или специализированные оптимизации — императивная реализация (в памяти, с битовыми массивами/сегментированным решетом) предпочтительна.
- Часто разумно комбинировать: вычисления «тяжёлой» части в процедурном коде, а фильтрацию/агрегацию оставлять СУБД.