Файл: Операции, производимые с данными (Операции над данными в общем смысле).pdf

Говоря о формализации данных, имеет смысл ввести понятие модели. Модель — это объект, который отражает существенные особенности и характеристики изучаемого объекта, явления или процесса. При накоплении достаточного количества данных становится возможным составление модели данных при помощи их формализации. В данном случае под формализацией имеет смысл понимать процесс построения моделей при помощи формальных языков. Это могут быть языки программирования, дифференциальное и интегральное исчисление, теория множеств и др. Таким образом, становится возможным описать данные единообразно и привести к одному виду для дальнейшей обработки [4, с. 96].

Операции над формализованными данными

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

• константы — данные, которые программист точно знает и которые не будут меняться во время выполнения программного кода. Такие значение программист может сообщить компилятору заранее;
• переменные — основный тип данных. Такие данные меняются в процессе выполнения программы, а программист может задать только начальные значения. Хотя вполне возможна ситуация, при которой программист задает значения переменных в ходе выполнения программы.

И те, и другие могут быть следующего вида [9, с. 50]:

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

Операции с переменными и константами с точки зрения программиста зависят от возможностей выбранного языка, однако большинство языков программирования поддерживают ряд стандартных операций. Все операции над данными осуществляются посредством операторов. С операторами связаны следующие понятия [9, с. 31]:

• количество операторов. Оператор может совершать действия над:
  • одним операндом (унарный оператор);
  • двумя операндами (бинарный оператор);
  • тремя операндами (тернарный оператор).
• приоритет операторов. Зачастую возможны случаи, когда программистом в одном выражении указаны несколько операторов. В таком случае говорят о приоритете, который разрешается средствами используемого языка;
• ассоциативность операторов — если в выражении содержатся операторы с одинаковы приоритетом, тогда порядок выполнения вычисляется с учетом ассоциативности операторов: справа-налево или слева-направо;
• порядок синтаксического разбора — правила, по которым действует компилятор языка при разборе выражения.

Большинство языков программирования поддерживает стандартный набор арифметических операторов [10, с. 593]:

• Сложение;
• Вычитание;
• Умножение;
• Деление.

В языках высокого уровня также имеют место быть следующие арифметические операции [9, с. 36]:

• Остаток от целочисленного деления;
• Инкремента (увеличение на единицу);
• Декремента (уменьшение на единицу).

При написании любой программы возникает необходимость в написании логических выражений, то есть тех выражений, результат которых может быть равен только «истина» (true) или «ложь» (false). Чаще всего «истина» ассоциируется с 1, ложь с 0. [10, с. 594] Логические операции соответствуют операциям над высказываниями в алгебре логики (табл. 1).

Таблица 1

Операторы отношения сравнивают значение выражений слева и справа от оператора и формируют значения «истина» или «ложь» в зависимости от соотношения выражения, т.е. результатом сравнения является true, если оно удачно, и false в противном случае [10, с. 594].

Побитовые операторы позволяют производить действия непосредственно с битами операндов. Используются эти операторы в языках программирования для [9, с. 39]:

• Установки битов;
• Сброса битов;
• Инверсии отдельных битов.

В таблице 2 приведены правила истинности для основных логических операций: И (AND), ИЛИ (OR) и Исключающее ИЛИ (XOR).

Также в числе побитовых операций существуют операции побитового сдвига и отрицания. Операция сдвига влево и сдвига вправо эквиваленты умножению и делению на 2.

Таблица 2

Ниже приведена таблица основных операторов с соответствующими обозначениями в большинстве современных языков программирования по порядку убывания приоритета выполнения (табл. 3):

Таблица 3

Продолжение таблицы 3

В таблице 3 также указан оператор присваивания. Для компиляторов высокоуровневых языков программирования его использование означает, что значение, полученное в результате вычисления выражения справа от знака равенства, нужно скопировать в область памяти, на которую ссылается выражение слева от знака равенства [9, 38].

Все рассмотренные выше данные и операции над ними являются базовыми. Однако в реальности работать с простыми данными представляется трудоемкой задачей, которая способна произвести большое количество ошибок. Для большей производительности программиста и повышения качества и удобства его работы современные языки программирования поддерживают объявление и использование данных в таком виде, при котором они будут максимально приближены к их реальным аналогам [10, с. 596]. Ключ к эффективному использованию современных языков программирования — это использование типов, определяемых пользователем или программистом [18, с. 201].

Одним из таких сложных типов данных являются массивы. Массивы существуют и поддерживаются в большинстве современных языков программирования. Массив — это совокупность упорядоченных, расположенных в памяти последовательно элементов данных. Все элементы массива имеют один тип, а сам массив занимает в памяти непрерывную линейную область. Каждый элемент массива пронумерован и имеет индекс. Доступ к каждому элементу массива является одинаково эффективным для любого элемента [9, с. 196]. Массивы — это мощный инструмент для работы с одинаковыми типами данных. С помощью массивов разумно организовывать обработку больших объемов данных с постоянным временем доступа к любому элементу. Также стоит отметить, что в современных языках программирования организована поддержка создания и использования многомерных массивов, что позволят работать с различными представлениями данных как с математическими моделями и производить над ними соответствующие математические операции.

При выполнении некоторых задач удобно использовать и управлять данными как некой совокупностью, объединяющей какое-то количество различных разнотипных данных. В современных языках программирования были представлен сложный тип данных — структура. Структура позволяет объединить данные, относящиеся к одному объекту так, чтобы [9, с. 314]:

• хранить совокупность характеристик как единое целое;
• манипулировать этой совокупностью как единым целым;
• иметь возможность обращаться к характеристикам по отдельности.

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

Стоит отметить, что также для эффективной работы с видами данных используются указатели. Указатель — это такая конструкция языка для хранения и использования адресов и ссылок [18, с. 171]. При выполнении программы фрагменты программного кода и элементы данных располагаются в различных участках оперативной памяти, каждый из которых имеет свой уникальный адрес. Обращение к любому элементу программы в современных языках программирования можно осуществить по этому адресу. Для предоставления адреса и существует специальный тип данных — указатель [9, с. 173].

В этой главе были рассмотрены особенности и основные понятия, связанные с операциями, производимыми над данными, с точки зрения разработчика программного обеспечения. Были изложены основы представления данных в ЭВМ и принципы работы с ними с точки зрения разработчика программного обеспечения. Также были рассмотрены основные возможные операции над данными, которые доступны программисту посредствам высокоуровневых языков программирования.

Фильтрация, преобразование и сортировка данных

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

Задача фильтрации неразрывно связана с задачей поиска, так как, по сути, при фильтрации производится поиск данных, которые удовлетворяют какому-либо условию, а остальные данные отсеиваются. Алгоритмов поиска существует великое множество, начиная с самого тривиального и медленного — последовательного поиска, при котором сравнение элементов данных происходит последовательно и упорядоченно [2, с. 426] и заканчивая более сложными алгоритмами, например, бинарным поиском и поиском Фибоначчи.

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

Список является одной из самых основных структур данных. Он может использоваться в качестве альтернативной массиву структуры для хранения упорядоченных данных, а также быть основой для более сложных структур [5, с. 180]. В связанном списке каждый элемент данных встраивается в специальный объект, называемый элементом списка. Каждый элемент содержит ссылку на следующий элемент списка, тогда такой список называется односвязным. Также каждый элемент списка может содержать ссылку на предыдущий элемент, тогда такой список называется двусвязным. Таким образом конкретный элемент можно найти только одним способом: отследив его по цепочке элементов от начала списка [5, с. 182-183]. Важное преимущество связанных списков перед массивами заключается в том, что связанный список всегда использует ровно столько памяти, сколько необходимо, и может расширяться вплоть до всей доступной памяти [5, с. 200].