TLDR; «Возможно, вы ожидаете, что это не будет длинным чтением, тогда вы не мирянин и не обычный человек».
Несмотря на то, что многие люди решили относиться к кодированию как к функции состояния, где важны только начальное и конечное состояния, это печальное заблуждение. Процесс не менее важен при написании кода, потому что он определяет эффективность и качество. Этот грех часто можно отнести к преднамеренному или непреднамеренному игнорированию концепции структур данных и алгоритмов, поэтому мы здесь сегодня. Поэтому это попытка сделать из грешников святых.
Тем не менее, возможно, вы провели большую часть своего времени в качестве инженера-программиста за написанием кода, который, как вы знаете, не должен быть живым, и решили прийти в себя и пойти прямо, сесть.
Я попытаюсь охватить концепцию с высокого уровня, а затем перейти к более низким уровням, но с самых элементарных точек. Пропустите любой аспект, который вам кажется скучным, но держите его при себе.
КРАТКАЯ ИСТОРИЯ
История структур данных и алгоритмов восходит к заре информатики, когда исследователи и программисты начали разрабатывать методы хранения и обработки данных. Концепция структуры данных относится к тому, как данные организованы и хранятся в памяти, а алгоритмы — это процедуры и шаги, используемые для обработки этих данных и управления ими.
Один из самых ранних примеров структур данных и алгоритмов можно проследить до изобретения счетов, ручного устройства, используемого для арифметических вычислений. Счеты — это форма структуры данных, которая организует данные в виде бусинок на стержнях, где каждая бусинка представляет значение.
Давайте рассмотрим более знакомый пример, чтобы вывести концепцию на более практический уровень.
ПРАКТИЧЕСКИЙ ПРИМЕР DSA
Давайте рассмотрим распространенный пример: список продуктов.
Список продуктов — это структура данных, которая позволяет нам систематизировать товары, которые нам нужно купить в магазине. Мы можем использовать различные алгоритмы для выполнения задач, связанных со списком продуктов, таких как добавление или удаление элементов, сортировка списка и поиск определенных элементов.
В этом примере список продуктов — это простая структура данных, которую можно представить в виде списка товаров. Каждый элемент в списке представляет собой фрагмент данных, связанный с определенным индексом или позицией в списке. Список позволяет нам организовать данные таким образом, чтобы к ним было легко получить доступ и манипулировать ими.
Алгоритмы используются для выполнения конкретных задач, связанных со списком продуктов. Например, мы можем использовать алгоритм для добавления элементов в список, добавляя их в конец списка. Мы также можем использовать алгоритм для удаления элементов из списка, удаляя их из списка или помечая их как завершенные.
Сортировка списка может быть достигнута с использованием различных алгоритмов, таких как сортировка по алфавиту или сортировка по категориям.
Поиск определенных элементов в списке можно выполнить с помощью алгоритма, который выполняет итерацию по списку и проверяет соответствие каждого элемента.
АЦП В КОМПЬЮТЕРНЫХ НАУКАХ
Поскольку цель здесь не в том, чтобы оставаться лежать вечно, и не в том, чтобы идти по магазинам с большей изощренностью, давайте перейдем к рассмотрению концепции в информатике.
Напомним, что структура данных — это способ организации и хранения данных в компьютере, обеспечивающий доступ к ним и их эффективное использование. Алгоритм, с другой стороны, представляет собой пошаговую процедуру решения проблемы или выполнения задачи. Алгоритмы используются для управления структурами данных и могут использоваться для выполнения различных операций, таких как поиск, сортировка и обход.
Тем не менее, существуют различные типы структур данных, каждая из которых имеет свои сильные и слабые стороны. Некоторыми из часто используемых структур данных являются массивы, связанные списки, стеки, очереди, деревья и графики.
СТРУКТУРЫ ДАННЫХ
Массивы — это самая простая и наиболее часто используемая структура данных. Они представляют собой набор элементов одного типа, расположенных в непрерывном блоке памяти. Массивы эффективны для доступа к отдельным элементам, но вставка или удаление элементов из массива может занять много времени, особенно для больших массивов.
Связанные списки – это динамическая структура данных, состоящая из последовательности узлов, где каждый узел содержит элемент данных и ссылку (указатель) на следующий узел в последовательности. Связанные списки эффективны для вставки или удаления элементов, но доступ к отдельным элементам может быть медленнее, чем в массиве.
Стеки – это структура данных, основанная на принципе "последний пришел – первый ушел" (LIFO). Элементы добавляются и удаляются из вершины стека. Стеки могут быть реализованы с использованием массивов или связанных списков.
Очереди — это структура данных, работающая по принципу "первым пришел - первым обслужен" (FIFO). Элементы добавляются сзади и удаляются спереди. Очереди также могут быть реализованы с использованием массивов или связанных списков.
Деревья – это иерархическая структура данных, состоящая из узлов, соединенных ребрами. Каждый узел имеет родительский узел и ноль или более дочерних узлов. Деревья эффективны для поиска, вставки и удаления элементов и обычно используются в таких приложениях, как файловые системы и базы данных.
Графики – это структура данных, состоящая из вершин (узлов), соединенных ребрами. Графы могут быть направленными (ребра имеют направление) и ненаправленными (ребра не имеют направления). Графики используются в различных приложениях, таких как социальные сети и дорожные сети.
АЛГОРИТМЫ
Алгоритмы используются для управления структурами данных и выполнения различных операций. Вот некоторые из часто используемых алгоритмов:
- Алгоритмы поиска, такие как линейный поиск и бинарный поиск, используются для поиска элемента в структуре данных.
- Алгоритмы сортировки, такие как пузырьковая сортировка, сортировка вставками и быстрая сортировка, используются для упорядочения элементов структуры данных в определенном порядке.
- Алгоритмы обхода, такие как поиск в глубину и поиск в ширину, используются для посещения всех узлов в дереве или графе.
- Жадные алгоритмы, такие как алгоритм Крускала и алгоритм Дейкстры, используются для решения задач оптимизации.
- Алгоритмы динамического программирования, такие как алгоритм последовательности Фибоначчи и алгоритм задачи о рюкзаке, используются для решения проблем путем их разбиения на более мелкие подзадачи.
Чтобы донести это до вас, давайте рассмотрим концепции, используя общий язык: Javascript (если вы думали о Python, я не сожалею, обещаю).
ОБЫЧНЫЕ ПРИМЕРЫ В JAVASCRIPT
Вот несколько распространенных примеров в JavaScript.
Структуры данных
- Массивы. Массив — это базовая структура данных в JavaScript, в которой хранится набор значений, которые могут относиться к любому типу данных. Массивы индексируются, то есть каждому значению присваивается уникальный числовой индекс, начинающийся с 0. Это обеспечивает быстрый и эффективный доступ к определенным значениям в массиве. Но это не может быть единственным преимуществом, не так ли?
Пример:
let numbers = [3, 5, 1, 9, 7]; // Accessing a value using index console.log(numbers[2]); // Output: 1 // Iterating over an array for(let i = 0; i < numbers.length; i++) { console.log(numbers[i]); }
В приведенном выше примере мы создаем массив чисел и получаем доступ к значению, используя его индекс. Мы также перебираем массив, используя цикл for для вывода каждого значения на консоль. Это пример алгоритма, который мы используем для обхода массива.
2. Объекты. Объекты — это еще одна распространенная структура данных в JavaScript, в которой хранится набор пар ключ-значение. Каждый ключ представляет собой строку, которая используется для доступа к соответствующему значению. Объекты используются для представления сложных структур данных и могут содержать вложенные объекты, массивы и функции.
Пример:
let person = { name: "John", age: 30, address: { street: "123 Main St", city: "New York", state: "NY" } }; // Accessing values using keys console.log(person.name); // Output: John console.log(person.address.city); // Output: New York
В приведенном выше примере мы создаем объект для хранения информации о человеке, включая его имя, возраст и адрес. Мы обращаемся к значениям, используя их ключи, что является примером алгоритма доступа к данным в объекте.
Алгоритмы
- Сортировка. Сортировка — это распространенный алгоритм, который используется для упорядочения элементов в определенном порядке. Существует множество алгоритмов сортировки, каждый из которых имеет свои преимущества и недостатки. Наиболее часто используемый алгоритм сортировки в JavaScript — это встроенный метод
sort()
.
Пример:
let fruits = ["banana", "apple", "orange", "grape"]; // Sorting an array using sort() method fruits.sort(); console.log(fruits); // Output: ["apple", "banana", "grape", "orange"]
В приведенном выше примере мы создаем массив фруктов и используем метод sort()
для сортировки массива в алфавитном порядке. Это пример алгоритма сортировки, встроенного в язык JavaScript.
2. Поиск. Поиск — это еще один распространенный алгоритм, который используется для поиска определенного значения в структуре данных. Наиболее часто используемый алгоритм поиска в JavaScript — это линейный поиск, который проверяет каждый элемент в структуре данных до тех пор, пока не найдет целевое значение.
Пример:
let numbers = [3, 5, 1, 9, 7]; // Linear search algorithm to find a value in an array function linearSearch(arr, target) { for(let i = 0; i < arr.length; i++) { if(arr[i] === target) { return i; } } return -1; } console.log(linearSearch(numbers, 9)); // Output: 3
В приведенном выше примере мы создаем массив чисел и определяем функцию для выполнения линейного поиска, чтобы найти определенное значение в массиве. Функция возвращает индекс целевого значения, если оно найдено, или -1, если оно не найдено.
ЗАКЛЮЧЕНИЕ
Теперь, возможно, вы все еще чувствуете себя потерянным и неудовлетворенным и уверены, что это не более широкое отражение других аспектов вашей жизни, что ж, тогда это нормально. Я бы порекомендовал этот курс от Freecodecamp, чтобы помочь вам лучше понять концепцию.
Однако понимание структур данных и алгоритмов во многом поможет улучшить производительность и качество кода, который вы пишете.
Один из практических примеров кодирования, в котором понимание структур данных и алгоритмов может иметь существенное значение, — это работа с большими наборами данных или выполнение сложных операций с данными. Допустим, у вас есть массив из 10 000 чисел в JavaScript, и вам нужно найти наибольшее число в массиве.
Без понимания структур данных и алгоритмов можно просто использовать базовый цикл для перебора массива и сравнения каждого числа, чтобы найти наибольшее из них. Вот пример того, как это может выглядеть
let arr = [/* 10,000 numbers */]; let largest = arr[0]; for (let i = 1; i < arr.length; i++) { if (arr[i] > largest) { largest = arr[i]; } } console.log(largest);
Хотя этот код будет работать, он не очень эффективен. Это требует перебора всего массива, даже если самое большое число найдено в начале цикла. С большим набором данных этот подход может стать очень медленным и неэффективным.
Лучшим подходом было бы использование более эффективного алгоритма, такого как алгоритм «разделяй и властвуй» для нахождения максимального элемента в массиве. Вот пример того, как это может выглядеть:
let arr = [/* 10,000 numbers */]; function findMax(arr, start, end) { if (start === end) { return arr[start]; } else { let mid = Math.floor((start + end) / 2); let leftMax = findMax(arr, start, mid); let rightMax = findMax(arr, mid + 1, end); return Math.max(leftMax, rightMax); } } console.log(findMax(arr, 0, arr.length - 1));
Этот алгоритм работает путем рекурсивного деления массива на более мелкие подмассивы и поиска максимального элемента в каждом подмассиве. Затем он сравнивает максимальные элементы подмассивов, чтобы найти общий максимальный элемент. Этот подход более эффективен, чем базовый цикл, потому что ему нужно всего лишь перебрать массив log₂(n) раз, где n — количество элементов в массиве.
В следующем наборе статей будут рассмотрены конкретные шаблоны DSA, с которыми следует ознакомиться.
Если вам нравится то, что вы читаете, я рад, что вы делаете. Если нет, то лучше послушай.