Перевод статьи «A Step Towards Computing as a Science».
Алгоритм это шаги, которые нужно предпринять для решения проблемы. Структура данных это данные, организованные таким образом, чтобы доступ к ним был эффективным. Алгоритмы используются для решения самых разнообразных задач, связанных с определенной структурой данных (например, поиск или упорядочивание).
Применительно к компьютерам, алгоритм это способ действий (например, линейный и бинарный поиск, сортировка пузырьком, выбором или вставками), а структура данных это то, над чем вы осуществляете эти действия (например, массив, пары «ключ-значение»). Все это позволяет вам методично искать, сортировать или создавать упорядоченные наборы данных.
Простая структура данных
Массив
Массив напоминает пронумерованные ячейки (где номера это индексы), расположенные по порядку, от самого маленького индекса до самого большого (в примере это индексы 0 и 2). Каждая ячейка закреплена на своем месте, а ее порядковый номер определяется ее «этикеткой» – индексом.
С помощью этого индекса вы можете обратиться к любой ячейке (элементу массива), чтобы посмотреть ее содержимое (arrayName[2]), добавить или заменить содержимое (arrayName[2] = “Sherlock Holmes”). Можно добавить в массив новое содержимое в новой ячейке, поместив ее в конец вашей коллекции. Здесь вам поможет метод push: (arrayName.push(“The Memoirs of Sherlock Holmes”)).
Новая ячейка получит следующий по порядку индекс, в нашем случае это 3. Чтобы вернуться к первоначальному виду массива, можно воспользоваться методом pop: (arrayName.pop()).
С помощью метода shift можно удалить первый элемент массива (arrayName.shift()), но при этом изменятся все индексы следующих элементов.
Теперь ваша коллекция Sherlock Holmes находится в ячейке с индексом 1. Метод unshift позволяет добавить новый элемент не в конец, а в начало массива: (arrayName.shift(“Dr. Strange”)).
А теперь ячейка с Dr. Strange будет иметь индекс 0, а Sherlock Holmes – индекс 2.
Поиск в структуре данных
Линейный поиск
Линейный (последовательный) поиск это «прогулка» вдоль массива ячеек (например, от ячейки с индексом 0 до ячейки с индексом 16). По пути вы открываете каждую ячейку и проверяете, не является ли ее содержимое тем, что вы ищете (например, число 37).
Итак, мы движемся от начала коллекции (скажем, индекса 0) к ее концу (длина массива минус единица) в поисках определенного содержимого. Не найдя его в текущей ячейке, мы перемещаемся к следующей, и так – аж пока не найдем искомое.
Бинарный поиск
Бинарный (двоичный) поиск это поиск в массиве ячеек, содержимое которых упорядочено определенным образом (например, числа по возрастанию или буквы в алфавитном порядке).
Мы прыгаем к ячейке посередине массива и проверяем ее содержимое, совпадает ли оно с тем, что мы ищем. Если содержимое этой ячейки больше искомого, мы отпрыгиваем назад, к ячейке посередине между нашей текущей позицией и предыдущей. В противном случае мы перемещаемся вперед, к ячейке, находящейся посередине между нашей текущей позицией и конечной.
Итак, мы перемещаемся между самым маленьким индексом (изначально – 0), серединным (8) и самым большим (изначально – 16). Серединная позиция это всегда половина суммы самого маленького и самого большого индексов. В поисках числа 37 мы все время прыгаем к серединной ячейке. Если ее содержимое меньше искомого (< 37), мы движемся вперед. При этом самым маленьким индексом теперь становится индекс нашей текущей ячейки, увеличенный на единицу (8 + 1 = 9). Теперь высчитываем новую серединную позицию ((9 + 16) / 2 ≈ 12).
Другими словами, вы продвигаетесь в поиске вперед, обновляя значение самого маленького индекса и пересчитывая значение индекса серединной ячейки. И наоборот, если случился «перелет», вы возвращаетесь назад, обновляя значение самого большого индекса и пересчитывая значение серединного.
Это и есть бинарный поиск. Вы постоянно оцениваете, находится ли искомое в первой или второй половине коллекции.
Сортировка структуры данных
Сортировка пузырьком
Сортировка пузырьком осуществляется путем постоянной перемены местами больших значений с меньшими. В результате самое большое значение «пузырьком» всплывает кверху.
Итак, предположим, что ваша коллекция начинается с индекса 0. Вы меняете местами содержимое элемента с текущим индексом (i) с содержимым элемента, имеющего следующий индекс (i + 1), если индекс (i) имеет более высокое значение. Затем вы переходите к следующей паре индексов (i + 1 и i + 2), и так далее.
В какой-то момент вы доберетесь до ячейки с наибольшим значением в вашей коллекции. Ее содержимое будет все время перемещаться вперед, как пузырек воздуха – вверх. Проходы по всей коллекции продолжаются, пока вся она не будет отсортирована от самого низкого до самого высокого значения содержимого ячеек.
Поскольку при каждой итерации последняя ячейка будет иметь самое большое значение, в каждой следующей итерации последние ячейки исключаются и больше не сравниваются.
Сортировка выбором
Сортировка выбором осуществляется путем непрерывного выбора наименьшего значения и перемещения его к одному концу.
В этом случае вы проходите всю коллекцию в поисках наименьшего значения. Найдя его, вы меняете местами содержимое этой ячейки с содержимым ячейки, имеющей наименьший индекс (изначально – 0). Процесс повторяется, но поскольку наименьшее значение уже заняло свою позицию, остальные пересматриваются, начиная с ячейки со следующим индексом (1).
С каждой итерацией длина участка массива, который нужно пройти, уменьшается на единицу. Все это продолжается, пока вся коллекция не будет отсортирована по степени возрастания значений, от наименьшего к наибольшему.
Сортировка вставками
Сортировка вставками это упорядочивание коллекции путем вставки каждого встреченного значения на правильную позицию.
В этом случае мы не проходим всю коллекцию при каждой итерации (как в сортировке пузырьком и выбором). Вместо этого мы начинаем со сравнения значений элементов с индексами 0 и 1. Если последнее значение меньше первого, они меняются местами. После этого мы перемещаемся к элементу с индексом 2 и сравниваем его значение со значениями двух предыдущих элементов (сначала с индексом 1, потом с индексом 0).
Каждый раз, находя более высокое значение, вы размещаете его правее. Найдя правильную позицию, вы вставляете содержимое ячейки с индексом 2 в ячейку на нужной позиции.
Это как будто вы вынимаете содержимое следующей ячейки и возвращаетесь с ним к предыдущей. Если содержимое предыдущей ячейки имеет больше значение, что то, которое вы «держите», вы перемещаете содержимое предыдущей ячейки в следующую. Это продолжается, пока вы не найдете подходящую ячейку, куда можно поместить значение, находящееся у вас «в руках».
Еще одна простая структура данных
Ассоциативный массив
Ассоциативный массив (объект с парами «ключ/значение») подобен непронумерованному набору депозитных ячеек. Каждый уникальный ключ открывает определенные данные. В отличие от массива, данные располагаются не по порядку, а доступ к ним возможен только с применением уникальных ключей.
Таким образом, вы получаете доступ к депозитной ячейке, используя ключ от нее (objectName[‘s’]), изменяете ее содержимое или создаете ключ, открывающий специфический контент (objectName[‘s’] = “Sherlock Holmes”). У вас есть доступ ко всем ключам для всего содержимого во всех депозитных ячейках (Object.keys(objectName) или Object.values(objectName)).
Заключение
Использование базовых алгоритмов (линейный и бинарный поиск, сортировка пузырьком,выбором и вставками) и структур данных (массивы и ассоциативные массивы) подводит нас к вопросам времени и пространства относительно управления данными.
Если при создании программ мы учитываем время, необходимое для поиска, сортировки или доступа к данным, а также объем памяти, необходимый для этих процессов, то в результате мы переходим от простой действенности наших программ к эффективности.
[customscript]techrocks_custom_after_post_html[/customscript]
[customscript]techrocks_custom_script[/customscript]