Во-первых, я собираюсь много говорить о Наруто, потому что это мой рамен (серьезно, если вы не смотрели это шоу, что вы вообще делаете?). Теперь, когда вы слышите «алгоритмы», вы можете просто подумать о сложных математических задачах или магии внутреннего кода. Но знаете что? Точно так же, как шиноби нуждаются в своих основных методах, разработчикам интерфейсов нужны алгоритмы. В этой статье мы углубимся в то, почему каждый кодер должен разбираться в алгоритмах. Всегда найдется один человек, говорящий: «Зачем возиться с алгоритмами? Разве они не просто… скучны? Но вот в чем дело: осваивать алгоритмы для разработчика все равно, что совершенствовать Расенган для ниндзя. Это не просто навык, это способ изменить правила игры. 🌀🖥️
1. Алгоритмы повсюду
Прежде чем погрузиться в специфику разработки интерфейса, важно понять, что алгоритмы лежат в основе каждого вычислительного процесса. Будь то сортировка списка имен, фильтрация определенных данных или даже просто загрузка веб-страницы, алгоритм работает.
2. Динамика веб-страниц
Веб-страницы динамичны по своей природе. Они содержат элементы, которые перемещаются, изменяются, скрываются и выполняют множество других действий. Используйте анимацию, адаптивный дизайн и интерактивные элементы, такие как ползунки или раскрывающиеся меню. Эффективная реализация этих функций требует глубокого понимания алгоритмов. Получить структуру и содержание веб-страницы в реальном времени — это все равно, что пытаться вспомнить ту идею компании-единорога стоимостью в миллиард долларов, о которой вы мечтали прошлой ночью (снова).
Например, поиск всех изображений на странице может показаться простой задачей. Однако рассмотрим сценарий, в котором изображения вложены в различные контейнеры, некоторые из них загружаются асинхронно, а другие скрыты за определенными действиями пользователя. Эффективный алгоритм обеспечит оптимизацию поиска и манипулирования, сократив потребление времени и ресурсов.
3. Оптимизация производительности
Производительность веб-сайта имеет первостепенное значение. Медленная загрузка веб-сайтов может отпугнуть пользователей и повлиять на рейтинг в поисковых системах. Хотя на скорость сайта влияет множество факторов, неэффективные алгоритмы могут значительно замедлить отрисовку страницы и интерактивность.
Используя оптимальные алгоритмы, разработчики могут обеспечить более быструю визуализацию веб-страниц, плавное воспроизведение анимации и плавное взаимодействие с пользователем. Это не только обеспечивает лучший пользовательский опыт, но также может повлиять на бизнес-показатели, такие как коэффициент конверсии.
4. Мир за пределами бэкенда
Существует распространенное заблуждение, что на бэкенде происходят все «серьезные» вычисления, а на фронтенде в основном идет представление. Но по мере того, как веб-приложения становятся все более изощренными, все больше логики передается на сторону клиента. Такие фреймворки, как React, Vue и Angular, позволяют разработчикам создавать интерактивные одностраничные приложения (SPA), в которых основная часть обработки данных происходит в браузере. Здесь эффективные алгоритмы играют ключевую роль в обеспечении бесперебойного взаимодействия с пользователем.
5. Улучшение навыков решения проблем
Хорошее понимание алгоритмов позволяет разработчикам методично подходить к проблемам. Столкнувшись с проблемой, они могут разбить ее на более мелкие части, решить каждую часть с помощью соответствующей алгоритмической стратегии, а затем объединить решения. Такой структурированный подход к решению проблем бесценен не только в написании кода, но и во многих других аспектах работы разработчика.
Ярким примером является участие Ричарда Фейнмана (одного из моих героев) в расследовании катастрофы космического корабля "Челленджер". Вместо того, чтобы увязнуть в запутанных теориях, он классно продемонстрировал уязвимость уплотнительного кольца к холоду, просто сжав образец материала в зажиме и погрузив его в ледяную воду. Материал не упругий, что свидетельствует о снижении его устойчивости при низких температурах. Подход Фейнмана подчеркивает, что иногда суть решения проблем заключается в сведении сложности к ее простейшей форме, что является основным принципом алгоритмического мышления.
Давайте обсудим практический пример, который является одной из моих любимых тем: просмотр веб-страниц. Это концепция, которая может касаться как фронтенд-, так и бэкэнд-разработки, но они традиционно больше связаны с бэкэнд-процессами. Давайте углубимся в их отношения как с фронтенд-, так и с бэкенд-разработкой.
Веб-скрапинг относится к извлечению данных с веб-сайтов.
Обычно это включает:
- Получение веб-страницы. Обычно для этого требуется отправить HTTP-запрос на сервер веб-сайта и получить ответ в формате HTML, что является внутренней операцией.
- Анализ данных: после получения ответа HTML интересующие данные извлекаются путем анализа содержимого HTML. Это можно сделать с помощью различных библиотек или инструментов, предназначенных для этой цели.
- Хранение данных: после извлечения данные часто сохраняются в базах данных или файлах, что является еще одной внутренней операцией.
В то время как фактический синтаксический анализ технически может быть выполнен во внешнем интерфейсе с использованием функций манипулирования JavaScript и DOM, на практике парсинг в значительной степени является бэкэнд-задачей из-за необходимости управлять HTTP-запросами, обрабатывать хранилище и часто обрабатывать большие объемы данных.
Знание структуры HTML и того, как ее пройти, важно как для веб-скрапинга, так и для веб-скрейпинга. Это понимание в первую очередь относится к домену внешнего интерфейса, но становится очень актуальным при применении этих навыков в контексте парсинга, который часто работает в бэкэнд-системах.
Как знание домена внешнего интерфейса поможет в задачах парсинга веб-страниц?
1. Понимание структуры HTML:
Когда дело доходит до просмотра веб-страниц, структура HTML определяет способ извлечения данных. Вот почему понимание структуры HTML имеет решающее значение:
- Семантическое значение: теги HTML обеспечивают семантическое значение контента. Зная разницу между тегами ‹div›, ‹article›, ‹nav› и другими тегами, можно определить контекст извлеченных данных.
- Иерархия данных: элементы в HTML вложены друг в друга, создавая между ними иерархические отношения. Знакомство с этой иерархией позволяет более точно находить данные.
- Атрибуты и метаданные: часто важные данные или ссылки находятся не только в тегах, но и в атрибутах, таких как href в тегах ‹a› или src в тегах ‹img›. Знание того, где искать, имеет решающее значение для эффективного парсинга.
2. Обход дерева HTML:
Иерархическая природа HTML делает его древовидной структурой. Обход этого дерева является основополагающим аспектом как разработки внешнего интерфейса, так и веб-скрейпинга:
- Манипуляции с DOM: разработчики внешнего интерфейса используют методы манипулирования DOM (объектная модель документа) для взаимодействия с веб-страницами с помощью JavaScript. Такие инструменты, как document.querySelector или библиотеки, такие как jQuery, предлагают методы для навигации и изменения DOM.
- Библиотеки и инструменты очистки. Бэкэнд-процессы, участвующие в очистке, используют специализированные библиотеки, такие как Beautiful Soup (Python), Cheerio (JavaScript) или Scrapy (Python), для обхода дерева HTML. Эти библиотеки предоставляют методы, которые отражают приемы манипулирования DOM во внешнем интерфейсе, но предназначены для внутренней обработки. Пользователь предоставляет селекторы или шаблоны, а библиотека извлекает соответствующие данные.
В приложении:
Чтобы эффективно извлекать данные с помощью парсинга веб-страниц, можно сделать следующее:
- Проверка веб-страницы. Используя инструменты разработчика браузера, разработчик или специалист по данным проверяет структуру веб-страницы, чтобы определить, как организованы данные и какие теги/атрибуты содержат нужную информацию.
- Создание селекторов: на основе проверки они создают селекторы CSS или выражения XPath для нацеливания на интересующие данные.
- Используйте инструмент очистки: созданные селекторы затем используются в сочетании с библиотекой очистки или инструментом для программного извлечения данных.
Вот пример из реальной жизни: просмотр веб-страниц для поиска новых продуктов и их сведений, таких как цены и скидки. Мне нужно было увидеть, находится ли тег a (ссылка) внутри div и что у тега a есть дочерние элементы, которые являются тегами изображения (что означает, что изображение кликабельно и, вероятно, является реальным продуктом). Мы можем искать свойства изображений, такие как минимальная ширина 70 пикселей.
Этот пример представляет собой комбинацию нескольких требований, которые включают как обход DOM, так и проверку свойств. Сначала разберем требования:
- Тег ‹a› должен быть потомком ‹div›.
- У тега ‹a› должны быть дочерние теги ‹img›.
- Изображение должно иметь свойство ширины не менее 70 пикселей.
Алгоритмический подход:
- Пройдитесь по всему DOM.
- Если узел представляет собой тег ‹a› и существует его ближайший родительский элемент ‹div›:
- Проверьте его детей.
- Если один из его дочерних элементов является тегом ‹img› и имеет ширину 70 пикселей или более, сохраните тег ‹a›.
Пример кода для такой задачи в JavaScript:
function findProductImageLinks(node) {
const result = [];
if (!node) return result;
if (node.tagName === 'A' && node.closest('div')) { // Ensuring <a> tag is a descendant of a <div>
for (let child of node.children) {
if (child.tagName === 'IMG' && child.width >= 70) { // Checking for <img> child with a width of 70px or more
result.push(node);
break; // Once a valid <img> is found, no need to check the remaining children of this <a> tag
}
}
}
for (let child of node.children) {
result.push(...findProductImageLinks(child));
}
return result;
}
// Usage:
const productImageLinks = findProductImageLinks(document.body);
console.log(productImageLinks);
Подход к этой проблеме неалгоритмическим способом может включать избыточные проверки, неполное использование доступных методов браузера или делать предположения, которые могут привести к ошибкам.
давайте посмотрим на наивный подход:
- Найдите все теги ‹a› на странице.
- Для каждой ссылки проверьте, есть ли у нее дочерние элементы.
- Если у него есть дочерние элементы, выполните итерацию по всем элементам на странице и посмотрите, не являются ли какие-либо из них элементами ‹div›, содержащими рассматриваемый тег ‹a›.
- Для каждого дочернего элемента ссылки проверьте, является ли это изображением. Если это так, получите его атрибут ширины.
- Сравните атрибут ширины как подстроку, чтобы увидеть, больше ли он 70 пикселей или равен ему.
function poorlyFindProductImageLinks() {
const allLinks = document.querySelectorAll('a'); // Get all <a> tags
const results = [];
for (let link of allLinks) {
const allDivs = document.querySelectorAll('div'); // Get all <div> tags for every link (highly inefficient!)
let isInsideDiv = false;
for (let div of allDivs) {
if (div.innerHTML.includes(link.outerHTML)) { // Checking if <div> contains the <a> tag by comparing their HTML (prone to errors)
isInsideDiv = true;
break;
}
}
if (!isInsideDiv) continue;
for (let child of link.children) {
if (child.tagName === 'IMG') {
const widthStr = child.getAttribute('width'); // Assuming width is always explicitly set as an attribute (might be unreliable)
if (widthStr && parseInt(widthStr) >= 70) {
results.push(link);
break;
}
}
}
}
return results;
}
// Usage:
const badProductImageLinks = poorlyFindProductImageLinks();
console.log(badProductImageLinks);
Проблемы с этим наивным подходом:
- Избыточные DOM-запросы: мы запрашиваем все элементы ‹div› для каждого тега ‹a›, что расточительно.
- Ненадежные проверки: Использование innerHTML.includes() для проверки того, содержит ли ‹div› элемент ‹a›, подвержено ошибкам. Этот метод может иметь ложные срабатывания, если точная строка HTML присутствует в другом месте.
- Предположения: предположение о том, что ширина изображения всегда доступна как явный атрибут, ненадежно. CSS или встроенные размеры изображения могут определять реальную отображаемую ширину.
- Производительность: этот подход не оптимизирован и будет очень медленным, особенно на страницах со значительным количеством элементов.
Чтобы проиллюстрировать разницу во времени и пространственной сложности, используя секунды для времени и мегабайты для пространства вместо нотации O, я сделаю некоторые предположения. Эти значения являются гипотетическими и будут значительно различаться в зависимости от фактических данных, производительности браузера, аппаратного обеспечения и многого другого.
Вот предположения:
Средняя информация о странице:
- Количество тегов ‹a› (n): 100
- Количество тегов ‹div› (d): 1000
- Средняя длина содержимого HTML (l): 100 символов.
- Среднее количество детей для тега ‹a›: 5
Предположения о времени выполнения:
- Базовая операция (например, доступ к элементу или проверка свойства): 0,00001 секунды (10 микросекунд).
- Операция сопоставления строк (например, innerHTML.includes()): 0,0001 секунды на символ.
Предположения о требованиях к пространству:
- Хранение ссылки на элемент: 0,1 МБ (это сильно завышенная оценка, чтобы подчеркнуть использование пространства)
Но сначала нам нужно понять очень важные понятия, такие как пространственная и временная сложность. Мы не можем обсуждать алгоритмы без них.
Сложность пространства: представьте, что у вас есть книжная полка, и вы хотите хранить на ней свои книги. Сложность пространства будет заключаться в том, сколько места на полке будет использовано в зависимости от количества книг, которые у вас есть. Если вам нужна совершенно новая полка для каждой отдельной книги (что было бы глупо), это высокая сложность пространства. Но если все книги поместятся на одной полке, независимо от того, сколько у вас их, это несложно.
Временная сложность: Теперь подумайте о том, чтобы найти книгу на этой полке. Если вы можете найти любую книгу мгновенно, независимо от того, сколько книг у вас есть, это означает низкую временную сложность. Но если поиск книги занимает больше времени, когда вы добавляете новые книги на полку, это высокая временная сложность.
В аналогии с книжной полкой
O(n) (читается как «Порядок n» или просто «O из n») представляет ситуацию, когда требуемое время или пространство увеличивается линейно с количеством книг (n).
По сути, O(n) означает, что потребность в ресурсах (будь то время или пространство) растет прямо пропорционально количеству предметов (в данном случае книг), с которыми вы имеете дело.
Итак, почему это не всегда хороший способ исследовать вещи?
Ну, в реальном мире не все ситуации равны. Допустим, у вас есть супербыстрый (с малой временной сложностью) метод поиска среди 10, 100 или даже 1000 книг. Но когда вы достигаете миллиона книг, это становится ужасно медленным. Однако другой метод может быть немного медленнее для 1000 книг, но намного быстрее для миллиона.
Если бы вы судили только по эффективности с 1000 книг, вы бы выбрали первый метод. Но если вы знаете, что будете иметь дело с огромными библиотеками, то второй способ явно лучше. Вот почему время и пространственная сложность не могут быть единственными факторами, которые вы принимаете во внимание. Иногда реальный контекст и ожидаемый масштаб играют решающую роль в выборе правильного подхода.
Теперь, используя приведенные выше предположения, давайте рассчитаем, а затем построим таблицу как для алгоритмического, так и для наивного подходов.
Итак, вернемся к нашему примеру
Временная сложность алгоритмического подхода:
O(n) время: 100 × 0,00001 = 0,001 секунды
Наивный подход:
O(n×d×l) время: 100 × 1000 × 100 × 0,0001 = 1 секунда
Космическая сложность:
Алгоритмический подход:
Максимальное пространство:
O(n+d) = 100 + 1000= 1100 ссылок
Размер:
1100 × 0.1 = 110 MB
Наивный подход:
Максимальное пространство:
O(n+d) = 100 + 1000 = 1100 ссылок
Размер:
1100×0.1 = 110 MB
Оба подхода имеют одинаковую сложность пространства, потому что они хранят ссылки на элементы DOM, и наши предположения о размере хранилища одинаковы для обоих, но мы рассмотрим улучшение для этого позже.
Эта таблица демонстрирует, что, хотя пространственная сложность с точки зрения хранения может существенно не отличаться между хорошим алгоритмическим подходом и наивным (с учетом наших предположений), разница во временной сложности может быть огромной. Задержка обработки в одну секунду, особенно при взаимодействии в реальном времени, может заметно ухудшить пользовательский опыт.
Давайте реализуем идеи по оптимизации использования пространства в контексте примера парсинга веб-страниц, где мы идентифицируем определенные теги ‹a› внутри элементов ‹div›. Мы покажем более эффективный способ извлечения и хранения соответствующих данных и сравним результаты.
const relevantLinks = [];
document.querySelectorAll('div a').forEach(link => {
if (link.querySelector('img[width="70"]')) {
// Only store the href attribute to save space
relevantLinks.push(link.href);
}
});
Оптимизации:
- Используя селектор div a, мы сразу же сужаем список до тегов ‹a› внутри элементов ‹div›, что сокращает данные, которые мы первоначально обрабатываем.
- Вместо того, чтобы хранить полные DOM-ссылки соответствующих тегов ‹a›, мы храним только их атрибуты href. Это значительно уменьшает объем пространства, которое занимает каждый хранимый элемент.
Давайте сломаем это снова
Среднее количество тегов ‹a› в элементах ‹div› (n): 100
Средняя длина строки атрибутов href: 100 символов.
Пространство, необходимое для хранения символа: 0,000002 МБ (2 байта для кодировки UTF-16 в JavaScript)
Хранение ссылки на строку (например, href): 0,0001 МБ (очень сильное завышение)
Потребность в площади:
Хранение атрибутов href для всех релевантных ссылок: n * средняя длина строки * пробел на символ = 100 * 100 * 0,000002 МБ = 0,02 МБ
Хранение ссылок на эти строки в массиве релевантных ссылок: n * пробел на ссылку = 100 * 0,0001 МБ = 0,01 МБ.
Общий объем = 0,02 МБ + 0,01 МБ = 0,03 МБ.
Поскольку мы находимся на фактической ссылке, а не на всем объекте, сохраняя только атрибут href каждой ссылки, а не полную ссылку DOM, мы используем значительно меньше места. Атрибут href — это строка, а строки занимают гораздо меньше места в памяти, чем целые узлы DOM со всеми их свойствами и методами.
Мы также можем ограничиться только тегами ‹a› внутри элементов ‹div›, чтобы обрабатывать меньше элементов и впоследствии хранить меньше данных. Когда мы храним только необходимые данные (в данном случае атрибуты href), использование пространства сводится к минимуму.
Разница между алгоритмическим и неалгоритмическим подходами ошеломляет как во времени, так и в пространстве. С точки зрения времени алгоритмический подход в 1000 раз быстрее (0,001 секунды против 1 секунды), что означает улучшение на 99,9%. Теперь, когда мы смотрим на пространство, в то время как наше первоначальное сравнение показало, что обе стратегии используют 110 МБ, оптимизированный подход требует только 0,03 МБ. Это знаменует собой существенное сокращение пространства более чем на 99,97%. С практической точки зрения это означает, что на каждую 1000 операций, которая занимала почти 17 минут при наивном подходе, теперь потребуется меньше секунды при алгоритмическом подходе, и вместо примерно 11 ГБ пространства (более 10 операций) мы бы нужно всего около 0,3 МБ. Величину этой эффективности невозможно переоценить.
Скачок в производительности после оптимизации вашего кода похож на переход от попытки переместить бумажный шарик по столу с жалким ударом носа (мы все были там) прямо к взрыву сюрикен-расенгана.
Заключение
Подводя итог, алгоритмы повсюду, и, зная о них, мы можем сделать наши веб-приложения более эффективными, отзывчивыми и удобными для пользователя. Поскольку веб-технологии продолжают развиваться, важность понимания и эффективного применения алгоритмов будет только возрастать. Если вы только начинаете или являетесь опытным разработчиком, расширение ваших знаний в области алгоритмов поможет вам выйти на передний план современной веб-разработки.
Откройте для себя мир знаний на LearningJournal.dev! Мой блог охватывает широкий спектр тем, от технологий и личного развития до образа жизни и текущих событий. Я стараюсь предоставлять привлекательный, информативный и наводящий на размышления контент, который расширит ваш кругозор и подстегнет ваше любопытство. Присоединяйтесь ко мне в этом путешествии обучения и роста, когда мы изучаем новые идеи и делимся ценными знаниями, которые помогут вам расти как лично, так и профессионально.
