Разряженные структуры данных. Последовательные и связные формы хранения. Особые случаи хранения.

 

· Матрица NxN элементов называется разреженной, если она содержит небольшой процент ненулевых элементов (число элементов порядка N)

· Коэффициент слабой заполненности матрицы — отношение числа ненулевых элементов к числу нулевых

· Для задач, связанных с разреженными структурами данных, существуют специальные упакованные формы хранения:

1. Последовательная форма

1.1. Хранение в виде последовательных записей

 

Const n= // размерность разр. матрицы

Var a: array [1..n,1..n] of real;

b: array [1..k] of record // k ~ число ненулевых эл-тов (выбирается рандомно)

value: real; // значение ненулевого эл-та

i,j: integer; // позиция ненул. эл-та в строке/столбце

end;

 

Плюсы 1.1: Резкое уменьшение требуемой памяти под хранение

Минусы 1.1: — не известно точное значение k

— необходимо производить упорядочивание по стр/стлбц

— в процессе обработки, ненулевые эл-ты могут стать нул-ми и наоборот

 

 

1.2. Хранение в виде 2х последовательных записей ненулевых элементов.

 

В 1ой – недиагональные, во 2ой – диагональные

 

Const n= // размерность разр. матрицы

Var a: array [1..n,1..n] of real;

b: array [1..k] of record // k ~ число ненулевых эл-тов (выбирается рандомно)

value: real; // значение ненулевого эл-та

i,j: integer; // позиция ненул. эл-та в строке, столбце

end;

 

c: array [1..m] of record

value: real;

ij: integer; // позиция в стр/слбц (неважно, т.к. диагональ)

end;

 

Плюсы 1.2: Ещё меньший объём занимаемой памяти

Минусы 1.2: Вся работа выполняется с 2мя записями => удвоенные минусы 1.1

 

1.3. Хранение в виде последовательности записей(2)

 

Вместо двух значений (I,j) сохраняется одно – позиция элемента (l), где l=i+(j-1)*n, j=trunc(l/n)+1

 

Const n= // размерность разр. матрицы

Var a: array [1..n,1..n] of real;

b: array [1..k] of record // k ~ число ненулевых эл-тов (выбирается рандомно)

value: real; // значение ненулевого эл-та

l: integer; // позиция ненул. эл-та в строке, столбце

end;

 

2. Связные формы

 

Используются динамические структуры

 

2.1. Связное хранение по строкам

— Создаётся массив указателей на списки ненулевых элементов строк

— От каждого элемента массива ссылка на список ненулевых элементов строки, номер которой совпадает соответственно с номером элемента

 

2.2. Связное хранение по столбцам

— Создаётся массив указателей на списки ненулевых элементов столбцов

— От каждого элемента массива ссылка на список ненулевых элементов столбца, номер которого совпадает соответственно с номером элемента

 

2.3. Связное хранение по строкам и столбцам

— Создаётся массив указателей на списки ненулевых элементов столбцов

— Создаётся массив указателей на списки ненулевых элементов строк

— От каждого элемента массива для строк, ссылка на список ненулевых элементов строки, номер которой совпадает соответственно с номером элемента

— От каждого элемента массива для столбцов, ссылка на список ненулевых элементов столбца, номер которого совпадает соответственно с номером элемента

 

3. Особые случаи разреженной матрицы

 

3.1. Треугольная матрица

— Все ненулевые значения находятся в одном из 4х треугольников, образованных диагоналями

— Ненулевые значения заносятся в линейный массив построчно. В качестве отдельной переменной используется переменная, для обозначения ненулевых элементов.

— Позиция в матрице хранится в переменной l,

l=i*(i-1)/2 + j – 1

 

3.2. Ленточная матрица

— с шириной ленты = D, если все её элементы, для которых выполняется |i-j|>D имеют ненулевое значение

— Позиция в матрице хранится в переменной l,

l = (i-1)*(2D+1)+j-I, для D>1

 

 

Если упакованного вида не хватает, матрицу хранят в ОП и на HDD.

 

Сортировки

Понятие сортировки. Параметры оценки алгоритмов сортировки. Классификация сортировок.

 

Сортировка – это процесс изменения порядка в исходной последовательности, с тем что бы для каждой пары соседних элементов выдавало одно из этих значений. Каждый из элементов a_j представляет комбинацию минимума из двух частей. Часть х₁ – ключ элемента, составная часть по которой производиться работа функции F(x, y), у₁ – дополнительные значения, может отсутствовать.

Параметры по которым оцениваются сортировки:

· Время сортировки, за какое время выполняется сортировка.

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

· Устойчивость сортировки, устойчивая сортировка не меняет взаиморасположения одинаковых элементов.

· Естественность поведения, поведение сортировки при работе с уже отсортированной последовательностью.

Сортировки делятся на:

· Внутренние/сортировки массивом – это сортировки у которых данные располагаются во внутренней памяти.

· Внешние сортировки, это сортировки находящиеся во внешней памяти. (Алгоритм Фон-Неймана, сортировка файлов).

Внутренние сортировки так же делятся на:

· Сортировки выбора. Базовый алгоритм, рассматривает последовательность a₁, a₂, …, a_n выбирает минимальный элемент, этот элемент записывается на первое место, а тот элемент который был первым записывается на место выбранного и тд (Алгоритм простого выбора).

· Сортировка вставками. Алгоритм простых вставок a₁ … a_ka_k+1 … a_n считается, что a₁ … a_k – упорядоченная задача: Найти место элемента a_k+1 в упорядоченной последовательности. Место этого элемента ищется последовательным сравнением начиная с a_k до тех пор пока не найдем пару где должен быть a_k, а_i+1. a_k сдвигается в право на 1 элемент, а сам элемент a_k+1 записывается на а_i+1.

· Сортировки обменом. Алгоритм пузырька или простого обмена. Принцип: Каждый элемент последовательности, сравнивается с каждым другим элементом и если в паре условие сортировки нарушено то производится обмен элементов.

· Сортировки подсчетом. Физической перестановки элементов не производится. Они применяются в тех случаях когда не выгодно производить перемещение элементов. Реализация: создается второй массив, который по размерности совпадает с первым массивом – массив счетчик а₁, а₂, …, а_к в₁, в₂, …, в_к – счетчик. Производится сравнение элементов массива со всеми последующими.

Характеристики внутренних методов сортировки. Дополнительные факторы, учитываемые при сортировке.

 

· Линейная – если элементы для сравнения выбираются последовательно, иначе если существуют какие то правила для выбора элементов, то не линейная сортировка.

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

· Сравнительные, распределительные. В сравнительных сортировках ключ рассматривается как единое целое, в распределительных ключ рассматривается по составляющим.

Основной критерий, по которому происходит выбор сортировки: Количество сравнений, кол-во перемещений.

Дополнительные критерии:

· Характеристики выбираемых данных:

· Размер последовательности (внутренний или внешний, сколько памяти потребуется для реализации сортировки).

· Характеристики ключа (Размер ключа, ключ является единым или составным, отдельно вводится является ли ключ машинным словом, ключ так же может состоять из разных частей машинных слов, в какой системе кодировки находятся данные).

· Распределение ключей (есть какое то частичное упорядочивание; имеется ли дублирование значений ключей)

· Какова длина и изменчивость значений в целом, обмен всегда производится только записями фиксированной длины.

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

Программные связи определяют:

· Источник данных, процесс сортировки изолирован, он производится с каким то условием.

· Требуются ли физические перемещения данных

· Характеристики самой машины:

· Кол-во регистров

· Логика операций сравнений

· Временные характеристики операции сравнения

· Какие процессы сравнения реализуются на данной машине

· Объем ОП и внешней памяти, так же вид внешней памяти

· Возможности маскировки данных и т.д.