Практическое занятие 1Тема 1. Подход к оптимизации сортировки в файлах. Тема 2. Применение поразрядных операций

1. Пример процесса разработки программы с выбором структуры представления данных для оптимизациисортировки

Рассмотрим пример, демонстрирующий выбор структуры данных, для обеспечения всех требований предъявляемых к разрабатываемой программе.¹.

1. Понимание предложеннойзадачи

Программист (назовем его Первым программистом) должен был разработать программу сортировки большого объема данных, хранящихся в файле. Программа нужна через сутки. При выборе алгоритма сортировки он решил посоветоваться с более опытным программистом (назовем его Вторым программистом). И у них состоялся диалог, в котором Второй программист уточнял особенности решениязадачи.

Первое предложение Второго программиста – это использовать алгоритм сортировки слиянием, который применяется для сортировки данных в файлах.

Но Первому программисту не хотелось углубляться в теорию алгоритмов.

Тогда Второй программист предложил использовать готовую программу, опубликованную в литературе по программированию, эта программа имеет 200 строк кода, разбитого на 12 функций. На написание и отладку такой программы Первый программист потратил бы не больше недели. Но первый программист сомневался, что проблема будетрешена.

Тогда Второй программист понял, что существуют какие-то требования к программе и он стал расспрашивать второго программиста о его задаче.

В результате Второй программист выяснил следующее:

Разрабатываемая программа будет встроена в большую программу, поэтому она не может использовать системныесредства.

Файл содержит 10⁷записей. Записи – это целые положительные семизначные числа. Узнав размер файла, Второй программист сразу предложил отсортировать записи в оперативной памяти, так как их не так много. Но, Первый программист ответил, что хотя на компьютер оснащен большим объемом памяти, программа сортировки является лишь малой частью большой программы. К моменту ее выполнения будет свободным лишь 1Мбпамяти.

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

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

1. Точная постановказадачи

Входные данные: файл, содержащий не более n (n=10⁷) целых положительных чисел, каждое из которых семизначное число, т.е. принадлежит диапазону [1000000..9999999] и среди них нетповторяющихся.

Результат:упорядоченный по возрастанию список чисел.

Ограничения:

Оперативной памяти – приблизительно 1Мб Дисковая память неограниченна

Время выполнения программы – 10 секунд

¹Жемчужина программирования

2. Исследование пространстваразработки

2. Рассмотрение возможных вариантов решения Первый вариант– Однопроходный алгоритм.

Использовать программу сортировки слиянием из 200 строк кода, оптимизировав ее с учетом того, что сортируются семизначные числа. Это сократит размер кода до нескольких десятков строк. Но на кодирование и отладку потребуется несколько дней. Сортировка слиянием для файлов требует использование двух временных файлов. Сортировка слиянием считывает входной файл один раз и разливает его по нескольким временным файлам (два файла), сортирует его с использованием временных файлов, которые считываются и записываются много раз. Выполнение операций чтения и записи во временные файлы осуществляется за длительное время, так как внешняя память имеет низкое быстродействие выполненияопераций.

Схемаоднопроходного алгоритма

Второй вариант– Сорока пароходный алгоритм.

Данный подход опирается на использование деталей конкретной задачи.

а) Если представить числа как последовательности символов, то на каждое число потребуется семь байт. Тогда в доступном 1Мб памяти поместится всего 143 000 чисел.

б) Если для представления чисел использовать ячейки из 32 бит, то в 1Мб поместится уже 250 000 номеров. Тогда программа может сортировать записи файла в оперативной памяти, считывая его за 40 раз (40*250 000=10⁷): т.е. за первое считывание считываются записи с номерами с 0 по 249 999, которые затем сортируются и записываются в выходной файл. За второй проход сортируются записи с номерами 250 000 по 499 999 и т.д. Для сортировки записей можно использовать алгоритм быстрой сортировки (алгоритм Хоара), который занимает всего 20 строк кода. Вся программа тогда будет содержать около 50 строк кода.

СхемаСорока проходного алгоритма

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

Третий вариант

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

Схема оптимального алгоритма.

Такую схему можно реализовать, когда все данные при сортировке будут размещены в 1Мб оперативной памяти. Т.о. задача сводится к отображению10⁷целых семизначных чисел приблизительно в восемь миллионов доступных бит (1Мб=1024*1024*8 бит=8 388 608 бит а для надо 10 000 000 битов, т.е. недостает еще около 2 000 000битов).

2. Неформальныйалгоритм

Использование последовательности бит для представления чисел напрашивается само собой. Суть такого представления в следующем. Пусть имеется 20 целых чисел и их можно значения в диапазоне от 1 до 20 и их надо представить 20 битами. Последовательность чисел, вставляемая в битовую последовательность из 20 бит будет такой {1, 2, 5, 9, 12, 8}. Сначала вся последовательность бит заполнена нулями. Биты в последовательности нумеруются с нуля.

Теперь создадим отображение, которое вставляет 1 в бит с номером, равным значению вставляемого числа, , тогда получим следующую битовую последовательность: 011001001100100000000.

В решаемой задаче файл представим как строку из десяти миллионов битов (программист нашел недостающие 2 000 000 битов), в которой i-ый бит равен 1, если в файле присутствует число со значением i.

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

программу можно представить как последовательность из трех задач:

1. Инициализация массива нулевымизначениями.

2. Считывание целых чисел из файла и установка в 1 соответствующих бит.

3. Формирование упорядоченного выходного файла путем последовательнойпроверки бит массива и вывод в файл номеров тех бит, которые установлены в1.

2. Определение алгоритмов выбранного решения

n – количество битов в массиве. bit[n] – битовый массив

Абстрактное описание алгоритмаАлгоритм на псевдокоде

//Часть 1: инициализация массива битов нулями for i←0 t n

bit[i]:=0;

//Часть 2: Заполнение битового массива значениями Чтение числа из файла в переменную i bit[i]:=1

//Часть 3: Формирование упорядоченного выходного файла for i←0 t n

if bit[i]=1 then записать i в файл;

Этого набросок программы оказалось достаточно, чтобы программист решил задачу. Как видно из данного материала, что представление данных в виде последовательности бит позволило выполнить все ограничения поставленной задачи.

3. Выводы.

Внимательное изучение задачи позволило программистам найти правильный подход к решению.

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

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

Программа получилась достаточно простой. Простота влечет надежность и эффективность программы, их проще создавать и сопровождать.

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

1. Понимание предложеннойзадачи

2. Постановка абстрактнойзадачи

3. Неформальное описаниепрограммы

«Некоторые программисты размышляют несколько минут, а потом программируют целый день, вместо того, чтобы подумать час, а потом час программировать»²

Неформальное описание программы – это исследование пространства разработки (самой задачи). Неформальные языки высокого уровня помогают описывать проекты программ: псевдокод определяет последовательность выполнения программы, а абстрактные типы данных представляют основные структуры. Решение одной задачи может иметь несколько вариантов, которые неформально описаны.

4. Реализация одногорешения

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

²Жемчужина программирования

«Задача инженерии программного обеспечения в том, чтобы регулировать сложность, а не увеличивать ее»³

3. Операции надбитами

Пример. Инвертирование маски перед умножением. Установить пятый бит в 0

int_tmain(intargc, _TCHAR* argv[])

{

unsigned charx=255;

unsigned charmaska=0x01; //1=00000001

x=x&(~ (maska<<4));

cout<<(int)x; //результат239cin.get();

return0;

}

3. Задания

   1. Напишите выражение, которое решаетзадачу

- Установить 7 бит в 1.

• Установить 5 и 3 биты в0.

• Инвертировать 5 бит переменнойх.

3 Памелу Зейв

• Вывести все биты значения переменной Х. Размер переменной неизвестен.

2. Какую задачу реализует код функции?voidcoutp(unsigned intx)

{

intn=sizeof(int)*8;unsignedmaska=(1<<n-1);

for(inti=1; i<=n;i++)

{

cout<<((x&maska)>>(n-i)); maska=maska>>1;

}}

3. Определите задачи, которые решают функции: set, clr, test #define BITSPERWORD32

#define SHIFT 5

#define maska 0x1F #define N 10000000

int a[1+N/ BITSPERWORD];

void set(int i){ a[i>> SHIFT] |=(1<<(I & MASK));} void clr (int i){ a[i>> SHIFT] &=(1<<(I & MASK));}

int test (int i) { return a[i>> SHIFT] &(1<<(I & MASK));}

3. Реализацияалгоритма