Web-разработка

С 0,4с до 0,005с: оптимизация UI-эффекта с помощью бинарного поиска

18.02.2026

Несколько недель назад я работал над градиентным эффектом прожектора для веб-интерфейса, который отслеживает курсор мыши и постепенно подсвечивает ближайшие карты в сетке. Это распространенный UI-паттерн, используемый такими платформами, как Windows во многих сеточных структурах, WhatsApp для десктопа во всплывающих окнах выбора стикеров или GIF-изображений, а также во многих других случаях.

Пример использования градиентного эффекта прожектора (всплывающее окно календаря Windows 10).

Естественно, как человек, работающий в веб-сфере, я задался вопросом: можно ли воссоздать этот эффект с помощью HTML, CSS и ванильного JavaScript?

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

Дисклеймер: все замеры производительности проводились с помощью встроенного метода JavaScript performance.now() на одном и том же компьютере в идентичных условиях.

Наивный подход

Мой первоначальный подход был довольно простым и прямолинейным. Представьте себе сетку карт 10 × 10, каждая из которых имеет идентичный радиальный градиент. К элементу-контейнеру сетки привязано событие mousemove, которое обновляет позицию градиента для всех карт, используя свойства offsetX и offsetY объекта события при каждом его срабатывании. Учтя несколько подводных камней со свойствами смещения события, получаем радиальный градиент, который, казалось бы, отслеживает курсор мыши, тем самым подсвечивая ближайшие карты на своем пути — словно прожектор, преследующий курсор по всему полю. Отсюда и название — градиентный прожектор.

Мой первоначальный прототип, созданный на основе наивного подхода (сетка 10 на 10)

Хотя этот подход визуально давал желаемый результат, у него была очевидная проблема с точки зрения выполнения — приходилось пересчитывать позицию градиента для всех 100 карт индивидуально каждый раз, когда срабатывало событие. Если вы достаточно долго работаете в веб-разработке, то понимаете, насколько ресурсоемкими могут быть анимации градиентов даже для одного элемента. А теперь представьте, что это масштабируется в 100 раз.

O(n)!? Скорее “О, нет(n)!”

То, что слишком ресурсоемкие визуальные эффекты масштабируются линейно в зависимости от количества элементов, отображаемых в браузере, не лучшим образом скажется при масштабировании. Учитывая, насколько требовательными становятся веб-сайты, нетрудно представить какой-нибудь продвинутый сайт, использующий такой эффект градиентного прожектора в разделе «Галерея», где могут находиться сотни, если не тысячи элементов. В информатике сложность такой наивной реализации определяется как O(n). Это означает, что объем ресурсов, необходимых для выполнения кода/алгоритма, будет линейно масштабироваться в зависимости от размера входных данных, обрабатываемых алгоритмом. Таким образом, если для одного элемента требуется X ресурсов, то для десяти элементов потребуется в 10 раз больше ресурсов.

Алгоритмическая сложность O(n) сама по себе не является чем-то плохим; более того, она может быть предпочтительнее, если лучше или более осуществима, чем альтернативная. Все зависит от характера задачи, требуемой оптимизации и того, насколько ресурсоемкие операции выполняются алгоритмом. В моем случае сложность O(n) была неприемлема.

Реализация кода и результаты

Ниже приведен HTML-код, который я использовал для создания эффекта. Как наивный, так и оптимизированный подход используют один и тот же HTML-файл.

<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Gradient Spotlight</title>
</head>

<style>
    * {
        margin: 0;
        padding: 0;
        box-sizing: border-box;
    }


    body {
        background: hsl(0, 0%, 4%);
    }


    #grid-title {
        font-size: 3.5rem;
        color: transparent;
        text-align: center;
        font-family: Arial, Helvetica, sans-serif;
        margin: 10px 0px;
        background-image: linear-gradient(90deg, hsl(168, 94%, 51%) 0%, 48%, hsl(230, 76%, 52%) 70%);
        background-clip: text;
    }

    .transluscent-grid {
        display: grid;
        gap: 20px;
        width: 80%;
        margin: auto;
        grid-template-columns: repeat(10, 1fr);
        overflow: visible;
    }

    .card {
        --gx: 100;
        --gy: 100;
        --gsize: 400;
        --g_opacity: 0;
        --gpadding_first_stop: hsla(0, 0%, 5%, 1);
        --gpadding: radial-gradient(calc(var(--gsize) * 1%) calc(var(--gsize) * 1%) at calc(var(--gx) * 1%) calc(var(--gy) * 1%) in hsl longer hue, var(--gpadding_first_stop) 0%, hsla(0, 0%, 5%, 1) 35%);
        --gborder: radial-gradient(calc(var(--gsize) * 1%) calc(var(--gsize) * 1%) at calc(var(--gx) * 1%) calc(var(--gy) * 1%) in hsl longer hue,
                hsla(0, 0%, 25%, var(--g_opacity)) 0%,
                hsla(0, 0%, 15%, var(--g_opacity)) 25%,
                hsla(0, 0%, 6%, var(--g_opacity)) 50%,
                hsla(0, 0%, 4%, var(--g_opacity)) 70%);
        aspect-ratio: 1/1.2;
        border-radius: 10px;
        border: 2px solid transparent;
        background-image: var(--gpadding), var(--gborder);
        background-origin: border-box;
        background-clip: padding-box, border-box;
    }
</style>

<body>
    <div class="viewport-container">
     <h1 id="grid-title">Gradient Spotlight</h1>
    <div class="transluscent-grid">
        <!-- 100 cards here -->
      <div class="card"></div>
      <div class="card"></div>
      <div class="card"></div>
       <!-- More cards... -->
   </div>
    </div>
</body>
</html>

HTML-код для эффекта градиентного прожектора. Тег скрипта намеренно опущен.

JavaScript (наивный подход):

const cards = document.querySelectorAll(".card");

let mouseEventPending = null;
let rafScheduled = false;

// Регулировка частоты вызова событий для плавной анимации.
function throttledMouseMove(event) {
    mouseEventPending = event;
    if (!rafScheduled) {
        rafScheduled = true;
        requestAnimationFrame(() => {
            mouseMoveHandler(mouseEventPending);
            rafScheduled = false;
        });
    }
}

document.querySelector(".viewport-container").addEventListener("mousemove", throttledMouseMove);

function mouseMoveHandler(e) {
    cards.forEach(card => {
        const targetRect = e.target.getBoundingClientRect();
        const { top, left, width, height } = card.getBoundingClientRect();
        const xOffset = e.offsetX + targetRect.left;
        const yOffset = e.offsetY + targetRect.top;
        const gradientXPos = ((xOffset - left) / width) * 100;
        const gradientYPos = ((yOffset - top) / height) * 100;


        card.style.setProperty("--g_opacity", 1)
        card.style.setProperty("--gpadding_first_stop", "hsla(0, 0%, 7.2%, 1)")
        card.style.setProperty("--gx", gradientXPos)
        card.style.setProperty("--gy", gradientYPos)
    });

};

Проблемы этого подхода

Сложность O(n): каждое движение мыши обрабатывает каждую карту.

Ненужные манипуляции с DOM: карты за пределами радиуса градиента все равно обновляются.

Дорогие вычисления: getBoundingClientRect() и вычисления перерисовки градиента выполняются для каждой карты в каждом кадре.

Отсутствие пространственного восприятия: алгоритм не знает, какие карты находятся рядом с мышью.

Результат? Эффект, который выглядел нормально при 100 картах, при 5000 картах превратился в слайд-шоу. Такое количество карт может показаться чрезмерным, но даже при 300 картах была заметна задержка между движениями курсора и обновлением градиента.

В таблице ниже показана производительность этого подхода при увеличении размера сетки. Цифры были получены путем вычисления среднего времени выполнения 100 событий mousemove с помощью встроенного метода JavaScript performance.now().

Таблица с кратким обзором результатов наивного подхода

Как видно, в конфигурации с 5000 картами обновление положения градиента при каждом движении мыши занимает почти полсекунды. Не знаю, как вы, но я видел слайды презентаций, которые двигались быстрее.

Мы определенно можем добиться лучших результатов!

Время думать пространственно (бинарный поиск)

Я пришел к выводу, что для решения этой задачи может подойти бинарный поиск, поскольку она обладает свойством, называемым монотонностью. Грубо говоря, это означает, что задача демонстрирует некую последовательность, которая изменяется только в одном направлении.

В данном случае рассмотрим столбцы, составляющие сетку; если начнем с центра градиентного прожектора и будем двигаться наружу влево или вправо, то столбец карт, с которым столкнемся, естественно, будет только удаляться от центра градиента и, следовательно, становиться все менее освещенным им. Это будет продолжаться до тех пор, пока мы не достигнем границы, за которой оказываемся вне радиуса градиента, а значит, карточки здесь не нужно обновлять. Монотонное поведение здесь заключается в том, что по мере движения наружу яркость градиента будет только постепенно уменьшаться; ни в коем случае не произойдет обратного. Та же логика может быть применена к строкам, но в направлениях вверх и вниз.

Помимо монотонности, внутренний порядок в расположении сетки был многообещающим, поскольку алгоритм бинарного поиска требует некоторого порядка в последовательности.

С учетом этих двух свойств задачи стратегия стала понятной. При каждом событии mousemove бинарный поиск определял столбцы, находящиеся на упомянутой мной границе слева и справа, а id всех карточек между этими столбцами сохранялись в Set(). Этот процесс повторялся для строк: в Set() сохранялись id всех карточек между строками, ограничивающими верхнюю и нижнюю границы градиента. Пересечение id в обоих Set() давало набор карточек, которые должны быть освещены градиентом. Все остальные карточки в сетке можно было безопасно игнорировать.

Я подготовил GIF, чтобы проиллюстрировать процесс. Пунктирная фиолетовая окружность представляет градиент, а желтые подсвеченные карточки — это единственные карточки, которые действительно должны обновляться.

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

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

Оптимизированная реализация

Начинаем с функции инициализации, которая организует карточки для бинарного поиска:

let gridCards = [],
    cardPositionsVertical = [],
    cardPositionsHorizontal = [],
    gradientSizePercent = null,
    firstCardRect = null,
    gradientRadiusX = null,
    gradientRadiusY = null,
    previouslyLitCards = new Set();

/**
 * Инициализация позиций карт и создание отсортированных массивов для операций бинарного поиска.
 */
function Initialize() {
    gridCards = [...document.querySelectorAll(".card")];
    gradientSizePercent = Number(getComputedStyle(gridCards[0]).getPropertyValue("--gsize")) / 100;
    firstCardRect = gridCards[0].getBoundingClientRect();
    gradientRadiusX = gradientSizePercent * firstCardRect.width / 2;
    gradientRadiusY = gradientSizePercent * firstCardRect.height / 2;
    cardPositionsVertical = [];
    cardPositionsHorizontal = [];

    gridCards.forEach((card, index) => {
        const rect = card.getBoundingClientRect();
        const scrollX = window.scrollX;
        const scrollY = window.scrollY;

        // Сохранение вертикальных границ для построчного поиска.
        cardPositionsVertical.push({
            id: index,
            top: rect.top + scrollY,
            bottom: rect.bottom + scrollY
        });

        // Сохранение горизонтальных границ для поиска по столбцам.
        cardPositionsHorizontal.push({
            id: index,
            left: rect.left + scrollX,
            right: rect.right + scrollX
        });
    });

    // Сортировка массивов для включения бинарного поиска.
    cardPositionsVertical.sort((a, b) => a.top - b.top);
    cardPositionsHorizontal.sort((a, b) => a.left - b.left);
}

Далее выполняем важнейшую часть оптимизации — функцию бинарного поиска:

function binarySearch(totalCards, sortedCardPositions, gradientSide, gradientBoundary) {
    let left = 0, right = totalCards - 1, mid = -1;

    while (left <= right) {
        mid = left + Math.floor((right - left) / 2);
        if (sortedCardPositions[mid][gradientSide] <= gradientBoundary) {
            left = mid + 1;
        } else if (sortedCardPositions[mid][gradientSide] > gradientBoundary) {
            right = mid - 1;
        }
    }

    return mid
}

function findCardsInGradientRange(cursorPosition, gradientRadius, sortedCardPositions, trailingSideProperty, leadingSideProperty, totalCards) {
    const gradientStartBound = cursorPosition - gradientRadius;
    const gradientEndBound = cursorPosition + gradientRadius;

    const rangeStartIndex = binarySearch(totalCards, sortedCardPositions, trailingSideProperty, gradientStartBound);
    const rangeEndIndex = binarySearch(totalCards, sortedCardPositions, leadingSideProperty, gradientEndBound)

    const cardsInRange = new Set();
    for (let i = rangeStartIndex; i <= rangeEndIndex; i++) {
        cardsInRange.add(sortedCardPositions[i].id);
    }

    return cardsInRange;
}

Затем следует функция пересечения Set(), которая определяет карточки, подлежащие обновлению:

// Я избегаю использования встроенного метода пересечения множеств для совместимости со старыми браузерами.
function findSetIntersection(setA, setB) {
  // Перебирание меньшего набора для сокращения среднего количества итераций.
    if (setA.size > setB.size) {
        [setA, setB] = [setB, setA];
    }

    const intersection = new Set();

    for (const element of setA.values()) {
        if (setB.has(element)) {
            intersection.add(element);
        }
    }

    return intersection;
}

Наконец, у нас есть обработчик событий mousemove:

function handleMouseMovement(e) {
    const totalCards = gridCards.length;
    const absoluteMouseY = e.offsetY + e.target.getBoundingClientRect().top;
    const absoluteMouseX = e.offsetX + e.target.getBoundingClientRect().left;

    // Находим карты в диапазоне градиента по обеим осям.
    const cardsInVerticalRange = findCardsInGradientRange(
        absoluteMouseY + window.scrollY,
        gradientRadiusY,
        cardPositionsVertical,
        "bottom",
        "top",
        totalCards
    );

    const cardsInHorizontalRange = findCardsInGradientRange(
        absoluteMouseX + window.scrollX,
        gradientRadiusX,
        cardPositionsHorizontal,
        "right",
        "left",
        totalCards
    );

    // Находим карты, находящиеся в обоих диапазонах (пересечение = карточки под градиентом).
    const currentlyLitCards = findSetIntersection(cardsInVerticalRange, cardsInHorizontalRange);

    // Удаляем градиент с карт, которые больше не подсвечиваются.
    for (const cardId of previouslyLitCards.values()) {
        if (!currentlyLitCards.has(cardId)) {
            const cardElement = gridCards[cardId];
            removeGradientFromCard(cardElement);
        }
    }

    // Применяем градиент к текущим подсвеченным картам.
    for (const cardId of currentlyLitCards.values()) {
        const cardElement = gridCards[cardId];
        applyGradientToCard(e, cardElement);
    }

    // Обновляем состояние для следующего кадра.
    previouslyLitCards = currentlyLitCards;
}

Можете ознакомиться с полным примером кода на Codepen.

Результаты

Чтобы по-настоящему оценить эффект от этой оптимизации, я подготовил как количественное, так и качественное сравнение производительности обоих алгоритмов. Как и прежде, показатели производительности основаны на среднем времени выполнения 100 событий mousemove:

Таблица, показывающая разницу в производительности между наивным подходом и подходом с бинарным поиском

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

Видео с параллельным сравнением наивной реализации и реализации с бинарным поиском (сетка 500 на 10)

Комментарий по поводу масштабирования

Цифры из таблицы наглядно показывают фундаментальную разницу между линейным и логарифмическим масштабированием:

Неэффективная версия (O(n)): Производительность ухудшается пропорционально количеству карт. Увеличение с 10 до 5000 карт приводит к ухудшению производительности в 200 раз (0,002 с → 0,400 с).

Эффективная версия (O(log n)): Производительность практически не зависит от масштаба. Даже при увеличении количества карт в 500 раз время выполнения увеличивается лишь примерно в 2 раза (0,002 с → 0,005 с).

Переломный момент наступает примерно при 50 картах — ниже этого порога издержки бинарного поиска делают наивный подход немного быстрее. Но стоит перейти к крупномасштабному использованию с сотнями или тысячами элементов, как оптимизированная версия начинает работать экспоненциально лучше.

Почему это так эффективно

От O(n) к O(log n): Бинарный поиск сокращает пространство поиска логарифмически, поэтому количество шагов, необходимых для нахождения цели, значительно меньше количества просматриваемых элементов.

Пространственное восприятие: Учитываются только карты в радиусе градиента.

Дифференциальные обновления: В DOM обновляются только карты, изменившие свое состояние.

Предварительно вычисленные позиции: Ресурсоемкие вычисления выполняются один раз при инициализации.

Операции на основе Set: Согласно MDN Web Docs, метод has() у объекта Set в среднем быстрее, чем метод includes() у Array, поэтому я предпочел хранить элементы в Set для поиска.

Ключевые выводы

Выбор алгоритма важнее, чем кажется

Разница между O(n) и O(log n) может показаться академической на курсах по информатике, но в реальной веб-разработке с тысячами DOM-элементов — это разница между удобным интерфейсом и слайд-шоу.

Анализируйте предметную область задачи

Это была не совсем проблема «веб-разработки» — это была проблема пространственного поиска, которая оказалась реализована на JavaScript. Определение типа задачи напрямую привело к решению.

Измеряйте все

Оптимизация производительности без измерений — это просто догадки. Код с использованием performance.now() был критически важным для понимания реального эффекта от изменений.

Предварительные вычисления — мощный инструмент

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

Отслеживание состояния предотвращает ненужную работу

Отслеживая, какие карты были подсвечены ранее, оптимизированная версия обновляет только те карты, состояние которых действительно изменилось, сводя манипуляции с DOM к абсолютному минимуму.

Фундаментальный принцип

Этот пример иллюстрирует фундаментальный принцип оптимизации производительности: наибольший выигрыш дают улучшения на уровне алгоритмов, а не микро-оптимизации.

Вместо того, чтобы пытаться выжать несколько миллисекунд из существующего подхода O(n), стоило отступить на шаг назад и переосмыслить задачу как проблему пространственного поиска — это привело к улучшению почти на два порядка.

«Следует инвертировать задачи всякий раз, когда это возможно. Многие сложные, казалось бы, неразрешимые задачи становятся простыми, если рассматривать их в инвертированном виде», — Якоби (в вольном переводе).

Применительно к этой задаче, вместо того чтобы пытаться обновлять многие элементы, чтобы выделить немногие, я инвертировал проблему и задался вопросом: как можно обработать немногие элементы, чтобы игнорировать многие?

С 0,4с до 0,005с: оптимизация UI-эффекта с помощью бинарного поиска

Наивный подход

O(n)!? Скорее “О, нет(n)!”

Реализация кода и результаты

Проблемы этого подхода

Время думать пространственно (бинарный поиск)

Оптимизированная реализация

Результаты

Комментарий по поводу масштабирования

Почему это так эффективно

Ключевые выводы

Фундаментальный принцип

Читайте также

Обзор инструментов для автоформатирования кода Python

3 функции Pandas, которые стоит использовать чаще

Элементы архитектуры веб-приложений

Тесты

Насколько хорошо вы разбираетесь в Kotlin?

Хорошо ли вы разбираетесь в структурах данных и алгоритмах?

Разбираетесь в AngularJS?