Данные в памяти программ

Наиболее распространенным видом обработки информации является поиск - чаще всего разыскивают детальную информацию в большом множестве данных по каким-либо названиям либо ключевым словам. Современные программные системы сталкиваются с гигантскими объемами данных. В качестве иллюстративного примера можно привести нагрузку на серверы компании Google - исходя из имеющимся в Internet публикаций, в 2013г. Google в среднем обрабатывает до 3.5 миллиардов поисковых запросов в сутки по всему миру. Число сайтов, размещенных в Internet, среди которых и ведется поиск, составляет около 700 миллионов и ежегодно увеличивается примерно на 50 миллионов. Сами сайты содержат большое количество страниц и файлов. Общий объем хранимых данных в Internet оценивается в ~3 зетабайта (10²¹ байт = 10¹² гигабайт) и удваивается каждые 1.5-2 года. Несмотря на эти астрономические объемы данных, поисковые системы выдают результаты за почти незаметное на глаз время для миллионов пользователей одновременно.

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

В целом, проблема эффективности поиска совсем не нова, отличаются лишь объемы обрабатываемых данных. Чтобы прочувствовать аналогию, достаточно представить самую обыкновенную библиотеку. В ней содержатся тысячи или десятки тысяч книг. Читатель обращается за интересующей его книгой к сотруднику библиотеки, и нужный экземпляр обычно обнаруживается за довольно короткое время. Если бы книги размещались на полках произвольно, без какой-либо системы, процесс поиска был бы мучительно долгим. Представьте библиотекаря, перебирающего все книги подряд от полки к полке, ворчание “ну где же она подевалась” и радостный возглас “нашлась!”. Лишь благодаря организации по алфавиту, тематике, годам издания и другим четко соблюдаемым сотрудниками библиотеки принципам, поиск происходит успешно за приемлемое для читателя время и без нервных потрясений для сотрудников. Новые поступления и возвращенные читателями книги размещаются таким же образом, чтобы ни в коем случае не разрушить выработанную эффективную процедуру поиска. Точно также, без особых трудностей обнаруживается и личная карточка, где делаются пометки о выданных конкретному читателю книгах.

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

Основная цель изучения дисциплины “Структуры и алгоритмы обработки данных” состоит в получении четкого представления о типовых методах структурной организации данных для эффективной обработки. Все рассматриваемые в дисциплине методы на сегодняшний день глубоко изучены экспертами, их эффективность проверена и доказана миллионами реальных и учебных компьютерных программ. Это дает право называть их классическим. Более того, все рассматриваемые структуры данных и алгоритмы в той или иной форме давно реализованы на всех существующих языках программирования и встроены в средства разработки в виде библиотек, чаще всего, стандартных, т.е., являющихся неотъемлемыми частями самих языков. Без применения таких стандартных библиотечных средств написание какой-либо нетривиальной программы на сегодняшний день невозможно.

Зачем же изучать то, что уже многократно реализовано и доступно в виде готовых средств? В зависимости от ответа на этот вопрос легко можно отличить настоящего инженера от специалиста-техника. Безусловно, используя готовые средства можно создать работающие программы различной сложности. Использовать готовые средства нужно, поскольку это значительно уменьшает время разработки. Но помимо использования “в слепую”, инженеру необходимо досконально овладеть внутренним устройством классических структур данных и алгоритмов, составляющих основу любых программных систем. Это позволит эффективно применять существующие готовые элементы или базовые идеи решений в конкретном практическом контексте за счет глубокого понимания их свойств. Инженеру также необходимо осознать значимость анализа сложности алгоритмов и эффективности операций конкретных структур данных. Эти факторы непосредственно влияют на эффективность и масштабируемость программных систем, что критически важно в условиях постоянного возрастания сложности вычислительных задач и объемов данных для обработки.

Все примеры, рассматриваемые в материалах дисциплины используют язык С++ в объеме, ограниченным базовым курсом программирования. Конструкции объектно-ориентированного и обобщенного программирования в примерах не используются, несмотря на их уместность в большинстве случаев. В целом, используемое подмножество языка С++ практически не выходит за рамки языка С, за исключением работы с динамической памятью при помощи операторов new/delete, использования ссылок, потокового ввода-вывода, типа bool, перегрузки функций. аргументов по умолчанию, свободного местоположения объявления переменных и других менее значимых языковых средств. Предполагается, что слушатель курса свободно владеет базовыми средствами языка С++ (литералы и переменные, встроенные типы данных, основные инструкции, указатели и работа с памятью, функции, структуры и перечисления, ввод-вывод), а также хотя бы одним средством разработки на языке С++ (например, Microsoft Visual Studio).

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