Для какой структуры подходит алгоритм filter

Алгоритм Filter: Для какой структуры данных подходит

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

Основное назначение Filter

Filter - это алгоритм для выбора элементов из коллекции по условию. Он подходит для упорядоченных (линейных) структур данных.

Структуры данных, подходящие для Filter

1. Массив (Array) - идеален

const numbers = [1, 2, 3, 4, 5];
const evens = numbers.filter(n => n % 2 === 0);
console.log(evens); // [2, 4]

Почему Array идеален:

• Элементы расположены линейно с индексами 0, 1, 2, ...
• Быстрый доступ к каждому элементу O(1)
• Сложность filter O(n) - нужно проверить каждый элемент

2. Связный список (Linked List)

class Node {
  constructor(value, next = null) {
    this.value = value;
    this.next = next;
  }
}

// Фильтрация связного списка
function filterLinkedList(head, predicate) {
  let dummy = new Node(0);
  let current = dummy;
  let node = head;
  
  while (node) {
    if (predicate(node.value)) {
      current.next = new Node(node.value);
      current = current.next;
    }
    node = node.next;
  }
  
  return dummy.next;
}

Сложность: O(n) - нужно пройти по всем узлам

3. Список (List) - в других языках

# Python
numbers = [1, 2, 3, 4, 5]
evens = list(filter(lambda x: x % 2 == 0, numbers))
print(evens)  # [2, 4]

4. Очередь (Queue)

class Queue {
  constructor() {
    this.items = [];
  }
  
  filter(predicate) {
    return new Queue(this.items.filter(predicate));
  }
}

5. Стек (Stack)

class Stack {
  constructor() {
    this.items = [];
  }
  
  filter(predicate) {
    return new Stack(this.items.filter(predicate));
  }
}

Структуры, НЕ подходящие для Filter

1. Двоичное дерево поиска (BST)

class TreeNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

// Filter НЕ подходит напрямую!
// Потому что структура BST оптимизирована для поиска, не для фильтрации
// Нужно перейти в массив или список сначала

Лучше использовать обход в глубину или ширину:

function filterBST(node, predicate, result = []) {
  if (!node) return result;
  
  if (predicate(node.value)) {
    result.push(node.value);
  }
  
  filterBST(node.left, predicate, result);
  filterBST(node.right, predicate, result);
  
  return result;
}

2. Граф (Graph)

// Filter не применяется к графам напрямую
// Нужно предварительно:
// - Обойти граф DFS/BFS
// - Собрать нужные вершины
// - Потом применить условие

3. Хеш-таблица (Map, Object) - нужна адаптация

// JavaScript Object
const person = { name: 'John', age: 30, city: 'NYC' };

// Filter работает, но нужно преобразование
const filtered = Object.entries(person)
  .filter(([key, value]) => typeof value === 'string')
  .reduce((acc, [key, value]) => ({ ...acc, [key]: value }), {});

console.log(filtered); // { name: 'John', city: 'NYC' }

Сложность времени Filter

Для разных структур:

Структура          Сложность   Почему
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Массив             O(n)        Линейный доступ
Связный список     O(n)        Нужно пройти через все узлы
Дерево (сбалан.)  O(n)        Все узлы нужно проверить
Граф               O(V + E)    Вершины + ребра
Хеш-таблица        O(n)        Итерация по всем элементам

Практические примеры

Пример 1: Фильтрация пользователей

interface User {
  id: number;
  name: string;
  age: number;
  isActive: boolean;
}

const users: User[] = [
  { id: 1, name: 'Alice', age: 25, isActive: true },
  { id: 2, name: 'Bob', age: 30, isActive: false },
  { id: 3, name: 'Charlie', age: 22, isActive: true },
];

// Фильтр по возрасту
const adults = users.filter(u => u.age >= 25);

// Фильтр по активности
const activeUsers = users.filter(u => u.isActive);

// Комбинированный фильтр
const activeAdults = users.filter(u => u.age >= 25 && u.isActive);

Пример 2: Фильтрация в контексте DOM

// Получить все активные элементы
const elements = document.querySelectorAll('.item');
const activeElements = Array.from(elements).filter(el => 
  el.classList.contains('active')
);

Пример 3: Фильтрация в Stream (Java/Python парадигма)

// JavaScript поток данных
const result = [1, 2, 3, 4, 5]
  .filter(n => n > 2)
  .map(n => n * 2)
  .reduce((a, b) => a + b, 0);

console.log(result); // (3*2 + 4*2 + 5*2) = 24

Когда НЕ использовать Filter

1. Когда нужен быстрый поиск одного элемента

// Плохо - O(n)
const user = users.filter(u => u.id === 5)[0];

// Хорошо - O(1) в хеш-таблице или O(log n) в BST
const userMap = new Map(users.map(u => [u.id, u]));
const user = userMap.get(5);

2. Когда нужны сложные условия на больших данных

// Если фильтровать 1,000,000 элементов с сложной логикой
// Рассмотри индексирование, БД запросы, etc.

Оптимизация Filter

1. Используй более специфичные методы

// Медленно
const firstOdd = numbers.filter(n => n % 2 !== 0)[0];

// Быстро - O(n) вместо O(n) + доступ к массиву
const firstOdd = numbers.find(n => n % 2 !== 0);

2. Используй ленивое вычисление (Generators)

function* lazyFilter(arr, predicate) {
  for (const item of arr) {
    if (predicate(item)) {
      yield item;
    }
  }
}

const result = lazyFilter(bigArray, x => x > 100);
// Элементы вычисляются по требованию, а не сразу

Заключение

Filter подходит для:

• Массивов и списков (идеально)
• Связных списков
• Очередей и стеков
• Практически любых линейных упорядоченных структур

Filter НЕ подходит для:

• Деревьев и графов (нужны специализированные обходы)
• Когда нужен быстрый поиск (используй map/индекс)
• Больших наборов данных (рассмотри БД запросы)

Сложность: Всегда O(n) - нужно проверить каждый элемент минимум один раз. Оптимизируй на уровне алгоритма, а не самого filter.