12 лучших алгоритмов структуры данных для реализации в практических приложениях в 2021 году
Новый год… Новое начало… !!!
Какой у тебя план на этот год ??? (Быть программистом)
Конечно, если вы программист, то в этом году вы также напишете код, создадите проекты и решите множество вопросов по кодированию.
Давайте поговорим о структурах данных и алгоритмах ...
Сердце информатики и дыхание программиста жить в мире программирования ...
Многие новички начинают изучать программирование, овладевая этими двумя важными инструментами информатики. Возможно, вы много практиковались, но пытались ли вы когда-нибудь узнать, насколько эти алгоритмы полезны в реальных приложениях. Наверняка есть какие-то причины для их изучения. Большинство начинающих программистов изучают его ради работы, но разве это не интересно, если мы узнаем о практической реализации этих алгоритмов в реальном мире.
Наступает новый год, и в этом новом году мы рекомендуем вам проверить практические сценарии известных алгоритмов вместо того, чтобы изучать их просто ради работы. В этом блоге мы обсудим некоторые практические реализации этих алгоритмов в реальном мире.
Неважно, новичок вы или опытный человек, вам будет интересно читать. Эта статья освежит воспоминания опытных программистов.
1. Последовательность Фибоначчи.
Наверняка вам доводилось хоть раз в жизни реализовывать программу для ряда Фибоначчи. Вы, будучи студентом, могли просить реализовать программу для ряда Фибоначчи или задавали этот вопрос во время интервью в компаниях XYZ.
Да!!! Речь идет о той же серии, где применяется математическая формула a n = a n −2 + a n −1, чтобы получить ряд в нашей программе. Мы реализуем код, чтобы довести серии 0, 1, 1, 2, 3, 5, 8, 13 и 21 до бесконечности. В этой серии мы получаем следующее по величине число, добавляя последовательные серии.
Вы пишете программу, сдаете экзамены или очищаете собеседования, но пробовали ли вы когда-нибудь искать то, где эта серия используется в реальных приложениях? Что может быть возможным сценарием , чтобы использовать этот алгоритм в реальном мире?
Красоту этой последовательности можно использовать для вычисления миль в километры и наоборот . Вы получите почти точный результат (не точный, но достаточно точный). В последовательности Фибоначчи вы можете рассматривать любое число как мили, а следующее число будет в километрах.
Consider the sequence 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …
In the above example, you can take two consecutive numbers 8 and 13. The smaller number is in miles i.e 8 and the bigger one is in kilometers i.e. 13.
8 in miles = 13 in kilometers.
2. Алгоритмы палиндрома
Это еще один популярный алгоритм среди программистов. Число или строка палиндрома читаются в обратном порядке. Например… уровень, мадам, 12021. Реализация этого алгоритма также является частым вопросом процесса собеседования во многих компаниях.
Вы проверяете свои логические способности при реализации программы для чисел-палиндромов, но можете ли вы просто подумать о практическом сценарии этого знаменитого алгоритма? Где это можно использовать?
Палиндромы используются при обработке последовательностей ДНК . Но как его использовать в этой обработке?
Становится доступным множество последовательностей ДНК. Для хранения информации об этих последовательностях ДНК мы используем базу данных молекулярной биологии. Емкость этих баз данных будет больше в будущем, поэтому важно эффективно передавать и хранить данные в базе данных.
Для повышения производительности важно сжать эти последовательности ДНК. Для сжатия этих последовательностей можно использовать CTW (метод взвешивания контекстного дерева). Этот метод сжимает последовательности ДНК менее чем с двумя битами на символ.
Известны в основном две характерные структуры последовательностей ДНК. Один - палиндром или обратные комплименты, а другой - приблизительные повторения. Используя хэш и динамическое программирование, алгоритм ищет приблизительный повтор и палиндром, прежде чем кодирует следующий символ. Если он находит палиндром или приблизительный повтор с достаточной длиной, алгоритм представляет его с длиной и расстоянием.
3. Массив
Первая структура данных, которую нужно изучить в программировании ...
Наиболее распространенная и широко используемая структура данных во многих приложениях…
Путешествие каждого новичка в программировании начинается с решения вопросов Array. Будучи программистом, вы наверняка часто использовали эту структуру данных в своем приложении. Эта структура данных используется во всех возможных ситуациях, когда вам нужно собрать объект в одном месте. От простого к сложному программному обеспечению или массиву веб-приложений в основном используется для динамического хранения и отображения данных на веб-страницах. Давайте возьмем один из хороших примеров использования массива в реальном приложении…
Все мы, должно быть, хотя бы раз использовали систему онлайн-бронирования билетов. Это может быть бронирование билетов на поезд, автобус, самолет, фильмы или другие шоу. Если мы хотим забронировать любое место, достаточно щелкнуть квадрат, и оно будет забронировано.
Вы когда-нибудь задумывались, что место, которое вы бронируете онлайн в любой системе, представляет собой двумерный массив?
Когда вы бронируете место, оно находится где-то в определенной строке и столбце. Это может быть представлено двумерным массивом, например, сиденьем [4] [5]. Таким образом, массив применим во всех системах онлайн-бронирования. Надеюсь, вы поняли суть и поняли реальное применение Array.
4. Стеки
Как новичок, вы наверняка читали о типичном примере структуры данных стека ... стопка тарелок или книг в шкафу, но можете ли вы просто подумать о другом примере стека, помимо этого базового?
Есть ли какое-нибудь реальное приложение, построенное и работающее на концепции структуры данных Stack?
Да!!! Там есть…
Текстовый редактор, такой как блокнот или Microsoft Word, использует структуру данных стека для выполнения задач отмены в своем редакторе. Еще один хороший пример стека - это браузер, работающий на вашем ноутбуке или в системе.
Каждый раз, когда вы выполняете действие в текстовом редакторе, создается стек. Используя операцию push, вы сохраняете действие, его метаданные, такие как тип действия, характер действия, его данные и т. Д. Используя действие pop, вы выполняете операцию отмены и последнее действие (хранящееся в верхней части стека) удаляется или отменяется из стека.
Еще один хороший пример структуры данных стека - это браузер, работающий на вашем ноутбуке или системе. Предположим, вы посещаете www.google.com, а затем посещаете www.geeksforgeeks.org. После этого вы заходите на сайт www.youtube.com. Эта информация сохраняется в структуре данных стека с помощью операции push. Когда вы нажимаете кнопку «Назад» в браузере, вы переходите на предыдущую страницу, которая представляет собой операцию всплывающего окна, выполняемую в стеке.
Итак, если вы находитесь на странице www.youtube.com и нажимаете кнопку «Назад», вы переходите на предыдущую страницу www.geeksforgeeks.org. При повторном нажатии кнопки «Назад» выполняется всплывающая операция, и вы возвращаетесь на страницу www.google.com.
5. Связанный список
Еще одна популярная и распространенная среди программистов структура данных - это связанный список. Теперь подумайте о назначении этой структуры данных в реальном приложении.
У всех нас есть музыкальный проигрыватель на наших телефонах, и у нас есть песни. Предположим, у вас в списке 5-6 песен. Когда вы создаете плейлист для этих песен, он работает по концепции связанного списка. Эти песни воспроизводятся одна за другой, и это один из лучших примеров односвязного списка. Песни связаны, и вы можете перейти от песни три к песне четыре, но вы не можете вернуться (поведение односвязного списка).
Когда вы реализуете функцию воспроизведения песни в обоих направлениях, она следует поведению двусвязного списка. В двусвязном списке узлы связаны в обоих направлениях. Таким образом, в списке воспроизведения вы можете переходить от песни 3 к песне 4, а также от песни 3 к песне 2. У вас будут кнопки как предыдущая, так и следующая. Таким образом, возможна двунаправленная навигация.
Когда вы воспроизводите песни в режиме повтора, он следует поведению кругового связанного списка. В круговом связном списке последний узел связан с первым узлом. Таким образом, как только последняя песня будет завершена, первая песня будет воспроизводиться снова, и она будет воспроизводиться в циклическом режиме, и она никогда не остановится.
6. Алгоритм двоичного поиска
Как программист, вы могли знать алгоритм двоичного поиска. Этот алгоритм также известен как поиск половинного интервала, логарифмический поиск или двоичное чередование. В этом алгоритме мы ищем целевое значение в отсортированном массиве.
Этот алгоритм упрощает процесс поиска, поскольку вам не нужно сравнивать каждый элемент в списке чисел. Двоичный поиск - это быстрый способ поиска целевого значения в упорядоченном списке данных. Это дает вам возможность выполнять этот процесс эффективно. Вы можете найти множество примеров алгоритмов двоичного поиска, таких как поиск значения слова в словаре, но знаете ли вы кого-нибудь из реальных приложений, использующих метод двоичного поиска?
Один из реальных сценариев этого алгоритма - проверка учетных данных пользователя в приложении . Используя двоичный поиск, вы можете проверить миллионы учетных данных пользователей за доли секунды.
Этот алгоритм также используется во многих библиотеках языков программирования, таких как Java, .NET, C ++ STL и т. Д. Метод Python list.sort () использует Timsort, который (AFAIK) использует двоичный поиск для определения позиций элементов. Двоичный поиск также используется в 99% 3D-игр и приложений.
7. Алгоритм сортировки слиянием
Сортировка слиянием работает с концепцией техники «разделяй и властвуй». Мы делим список на несколько подсписок, пока подсписок не будет содержать ни одного элемента. После этого мы объединяем эти подсписки, чтобы получить отсортированный список элементов. Это простое и краткое введение в этот алгоритм, но знаете ли вы, где он используется в реальных приложениях.
Многие люди любят делать покупки в Интернете через любой веб-сайт электронной коммерции . Вы знаете, что эти сайты электронной коммерции используют этот алгоритм? На большинстве сайтов электронной коммерции есть раздел « Вам может понравиться». В этом разделе хранится массив всех учетных записей пользователей, а затем, в зависимости от того, какая из них имеет наименьшее количество инверсий с вашим набором вариантов, начните рекомендовать то, что они купили, или что им нравится. (В следующий раз этот раздел напомнит вам об использовании бинарного поиска при совершении покупок на этих сайтах)
8. Числа Армстронга.
Еще одна популярная среди программистов программа - проверка номера Армстронг или нет. В числах Армстронга сумма кубиков цифр числа равна самому числу. Например, 153 и 371 - это числа Армстронга. Числа Армстронга в основном используются в приложениях для защиты данных для шифрования и дешифрования данных.
Посетите ссылку IJITEE. Приведены числа Армстронга для беспроводных сенсорных сетей . Они использовали алгоритмы безопасности на основе Армстронга, где 128-битный ключ генерируется с использованием числа Армстронга. Он используется в алгоритме AES для шифрования и дешифрования данных.
9. Кодирование Хаффмана.
Кодирование Хаффмана используется вместе с криптографией и сжатием данных. Он используется для сжатия данных без потерь. В зависимости от вероятности это реализовано таким образом, что вам не нужно хранить несколько копий одного и того же.
Кодирование Хаффмана используется в форматах сжатия , таких как GZIP, PKZIP (WinZip, и т.д.), и BZIP2. Все коммуникации с Интернетом и из него используют кодировку Хаффмана. Большинство файлов изображений, таких как JPEG и PNG, закодированы по Хаффману. Кроме того, музыкальные файлы, такие как MP3, кодируются по Хаффману.
Код Хаффмана преобразует коды фиксированной длины в коды переменной длины. Это дополнительно сжимается с использованием методов JPEG и MPEG, которые генерируют желаемую степень сжатия.
10. Динамическое программирование.
Еще одна любимая тема студентов-информатиков и программистов - динамическое программирование. 0-1 Задача о рюкзаке, проблемы с разбивкой по словам, самая длинная общая подпоследовательность - все эти проблемы являются наиболее популярными и распространенными проблемами динамического программирования. Вы решаете это, вы используете свои логические способности, но где на самом деле в реальном мире используется эта концепция ...
Динамическое программирование широко используется в биоинформатике, математике и экономике . В биоинформатики задач , таких как выравнивание последовательности, сворачивания белка, предсказания структуры РНК и связывания белок-ДНК использует динамическое программирование.
В математике DP используется в матричном умножении, которое широко используется в ракетной технике. Путь ракет определяется путем решения многих параметров. Все проблемы принятия решений можно оптимально решить с помощью динамического программирования.
11. График
Если вы куда-то путешествуете, выходите на улицу или пытаетесь найти маршрут к конкретному пункту назначения. Вы используете своего лучшего друга в телефоне Google Map. Вы знаете, что Google Map использует структуру данных Graph?
Структура данных графа - это очень мощная структура данных. Не только Земля, но и вся Вселенная может быть представлена на графике. С помощью Graph вы можете представить все, от крошечных субатомных частиц до гигантской вселенной.
Когда вы используете карту Google, все города и штаты связаны как график с информацией о расстоянии. Есть много способов добраться из одного города в другой, но чтобы найти кратчайший путь между двумя городами, вам нужно использовать некоторые алгоритмы. Алгоритмы Дейкстры, которые являются очень мощным алгоритмом, могут быть реализованы для поиска кратчайшего пути между двумя городами.
Чтобы определить кратчайший путь к месту назначения, алгоритм Дейкстры включает вашу навигационную систему / GPS в вашем телефоне. Uber использует венгерский алгоритм, чтобы назначить каждую машину людям, которые ищут поездку.
Facebook также использует структуру данных графика для реализации ленты новостей или подписчиков . Он использует Graph API для реализации большинства вещей в своем приложении. Все может быть представлено вершинами или узлами, такими как страницы, места, группы, комментарии, фотографии, фотоальбомы, истории, видео, заметки и т. Д. Каждое соединение или взаимосвязь является преимуществом на Facebook. Graph API хранит данные в виде вершин и ребер.
12. Структура данных Trie
Это тема расширенной структуры данных для программистов. Вы узнаете, что это может быть ради работы, вам также нравится решать вопросы, основанные на этом, но какая польза от этой расширенной темы в реальном приложении. Где это реализовано в нашей повседневной жизни? Давайте подойдем к этому интересному ответу ...
Вы используете свой мобильный телефон каждый день, вы также используете в нем функции смахивания. Эта функция смахивания на клавиатуре вашего мобильного устройства и автокоррекция при написании документа использует структуру данных Trie. Структура данных Trie содержит значения символов в вашем телефоне.
История сетевого браузера также использует структуру данных Trie. URL-адреса посещенного вами сайта организованы структурой данных Trie. Когда пользователь вводит префикс ранее использованного URL-адреса, браузер завершает URL-адрес, используя эту мощную структуру данных.
Последняя мысль
Теперь вы знаете о практических примерах использования известных структур данных и алгоритмов. Разве не интересно знать, как эти известные алгоритмы реализуются в нашей повседневной жизни?
Многие из нас не знали об интересных случаях использования этих структур данных и алгоритмов. Мы где-то его использовали, но не знали об этом. Всегда полезно знать преимущества чего-либо, прежде чем вы начнете чему-то учиться. Это всего лишь набор структур данных и алгоритмов, которые мы ввели, но есть несколько алгоритмов, которые мы используем в нашей повседневной жизни.
Теперь, в этом новом году, мы думаем о практических примерах использования других алгоритмов ...
Кроме того, в этом новом году не просто изучите эти алгоритмы ради их изучения, но и изучите эти алгоритмы, чтобы самостоятельно реализовать какое-нибудь интересное реальное приложение.
Вниманию читателя! Не переставай учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .
Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.