TLDR; «Возможно, вы ожидаете, что это не будет длинным чтением, тогда вы не мирянин и не обычный человек».

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

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

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

КРАТКАЯ ИСТОРИЯ

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

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

Давайте рассмотрим более знакомый пример, чтобы вывести концепцию на более практический уровень.

ПРАКТИЧЕСКИЙ ПРИМЕР DSA

Давайте рассмотрим распространенный пример: список продуктов.

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

В этом примере список продуктов — это простая структура данных, которую можно представить в виде списка товаров. Каждый элемент в списке представляет собой фрагмент данных, связанный с определенным индексом или позицией в списке. Список позволяет нам организовать данные таким образом, чтобы к ним было легко получить доступ и манипулировать ими.

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

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

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

АЦП В КОМПЬЮТЕРНЫХ НАУКАХ

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

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

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

СТРУКТУРЫ ДАННЫХ

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

Связанные списки – это динамическая структура данных, состоящая из последовательности узлов, где каждый узел содержит элемент данных и ссылку (указатель) на следующий узел в последовательности. Связанные списки эффективны для вставки или удаления элементов, но доступ к отдельным элементам может быть медленнее, чем в массиве.

Стеки – это структура данных, основанная на принципе "последний пришел – первый ушел" (LIFO). Элементы добавляются и удаляются из вершины стека. Стеки могут быть реализованы с использованием массивов или связанных списков.

Очереди — это структура данных, работающая по принципу "первым пришел - первым обслужен" (FIFO). Элементы добавляются сзади и удаляются спереди. Очереди также могут быть реализованы с использованием массивов или связанных списков.

Деревья – это иерархическая структура данных, состоящая из узлов, соединенных ребрами. Каждый узел имеет родительский узел и ноль или более дочерних узлов. Деревья эффективны для поиска, вставки и удаления элементов и обычно используются в таких приложениях, как файловые системы и базы данных.

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

АЛГОРИТМЫ

Алгоритмы используются для управления структурами данных и выполнения различных операций. Вот некоторые из часто используемых алгоритмов:

  • Алгоритмы поиска, такие как линейный поиск и бинарный поиск, используются для поиска элемента в структуре данных.
  • Алгоритмы сортировки, такие как пузырьковая сортировка, сортировка вставками и быстрая сортировка, используются для упорядочения элементов структуры данных в определенном порядке.
  • Алгоритмы обхода, такие как поиск в глубину и поиск в ширину, используются для посещения всех узлов в дереве или графе.
  • Жадные алгоритмы, такие как алгоритм Крускала и алгоритм Дейкстры, используются для решения задач оптимизации.
  • Алгоритмы динамического программирования, такие как алгоритм последовательности Фибоначчи и алгоритм задачи о рюкзаке, используются для решения проблем путем их разбиения на более мелкие подзадачи.

Чтобы донести это до вас, давайте рассмотрим концепции, используя общий язык: Javascript (если вы думали о Python, я не сожалею, обещаю).

ОБЫЧНЫЕ ПРИМЕРЫ В JAVASCRIPT

Вот несколько распространенных примеров в JavaScript.

Структуры данных

  1. Массивы. Массив — это базовая структура данных в 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

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

Алгоритмы

  1. Сортировка. Сортировка — это распространенный алгоритм, который используется для упорядочения элементов в определенном порядке. Существует множество алгоритмов сортировки, каждый из которых имеет свои преимущества и недостатки. Наиболее часто используемый алгоритм сортировки в 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, с которыми следует ознакомиться.

Если вам нравится то, что вы читаете, я рад, что вы делаете. Если нет, то лучше послушай.