Раздел «Образование».FIVTLecturesTerm1Lecture9:
<<Лекции ФИВТ, 1-й семестр

Лекция 9. Структура данных "Множество" (поворение, дописывание, анализ производительности). Структура данных "Двоичная куча"

Структура данных "Множество" (поворение, дописывание, анализ производительности)

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

Работа в командной строке: команды grep и cut.

# насколько раз запускаем  программу с аргументами 500,750, 1000, 1250, 1500, ... 10000
artem@artem-laptop:~/lectures$ for((i=500;$i<=10000; i+=250)); do time (./set $i); done

# запишем оба потока (Stdin & stderr) в файл Set_performance
artem@artem-laptop:~/lectures$ (for((i=500;$i<=10000; i+=250)); do time (./set $i); done) > set_performance.txt 2>&1


# вывести первые 20 строк файла
artem@artem-laptop:~/lectures$ head -20  set_performance.txt 
500

real   0m0.015s
user   0m0.008s
sys   0m0.004s
750

real   0m0.046s
user   0m0.008s
sys   0m0.008s
1000

real   0m0.025s
user   0m0.020s
sys   0m0.008s
1250

real   0m0.040s
user   0m0.028s
sys   0m0.012s


# вывести последние 20 строк файла
artem@artem-laptop:~/lectures$ tail  -20 set_performance.txt
...
# вывести весь файл
artem@artem-laptop:~/lectures$ cat set_performance.txt
...
# вывести первые 5 строк, содержащих user
artem@artem-laptop:~/lectures$ cat set_performance.txt | grep user | head -5
user   0m0.008s
user   0m0.008s
user   0m0.020s
user   0m0.028s
user   0m0.056s


# вывести  строки, содержащие user, значение после буквы m и до буквы s
artem@artem-laptop:~/lectures$ cat set_performance.txt | grep user | cut -dm -f2 | cut -ds -f 1 
0.008
0.008
0.020
0.028
0.056
0.164
0.112
...
# сделать тоже самое, только заменить символ новой строки на запятую, 
# но в конце вывести один символ новой строки
artem@artem-laptop:~/lectures$ cat set_performance.txt | grep user | cut -dm -f2 | cut -ds -f 1 | perl -pe 's/\n/,/g'; echo
0.016,0.012,0.040,0.028,0.072,0.056,0.092,0.200,0.192,0.180,0.324,0.628,0.520,0.584,0.832,0.908,1.000,0.948,1.124,1.180,1.376,
4.020,2.324,2.516,2.728,3.120,3.572,3.480,3.516,3.788,4.088,4.468,4.512,4.992,5.232,5.424,5.728,5.952,6.340,
# эти числа можно отправлять в какой либо мат пакен, чтобы анализировать ассимптотику.

Анализ ассимптотики роста на маленьких значения позволяет примерно оценить время, которое потребуется для решения задачи на входных данных. Важно запуская сложную вычислительную программу примерно представлять время, которое потребуется для вычислений — 10 минут, час, неделя, или 100 лет.

Пример, как это делается в пакете Mathematica.

Структура данных "Двоичная куча"

Ориентированный граф — это множестов элементов, называемых вершинами, некоторые пары из которых помечены как связанные. Связи между элеменами называются рёбрами графа. То есть ориентированный граф есть пара (V,E), где V - множество вершин, а E - подмножество V x V. Ориентированный граф изображается точками, соединенными стрелочками (стрелка направлена от первой вершине в паре ко второй).

Если порядок в паре неважен, то граф называется неориентированным. Можно считать, что неориентированный граф это пара (V,E), где вместе с парой (u,v) в множестве E есть и пара (v,u) (если есть стрелка из u в v, то есть стрелка и из v в u).

Ориентированное дерево — это ориентированный граф, в котором есть вершина, называемая корнем, из которой по рёбрам (то есть двигаясь по стрелкам) можно добраться до любой другой вершины, и при этом нет неориентированных циклов. Неориентированный цикл в ориентированном графе — это последовательность 2 или более разных вершин (u(1),...u(n)), таких что u(1) соединена с u(2), u(2) соединена с u(3), .. u(n) соединена ребром с u(1), при этом направление ребер неважно.

В теории алгоритмов важнейшее место занимают ориентированные деревья, в частности двоичные ориентированные деревья.

Двоичное ориентированное дерево — это дерево, в котором для каждой вершины число исходящих рёбер равно 0, 1 или 2. Вершины, у которых нет исходящих ребер называются листьями.

Множество вершин, до которых можно добраться из некоторой заданной вершины дерева v, вместе с ребрами, их соединяющими, называется поддеревом с корнем v.

Двоичная куча — это структура данных, которая представляет собой двоичное ориентированное дерево, к узлам которого привязаны пары (ключ, значение) и при этом для любой вершины выполнено свойство (свойство двоичной кучи): * ключ любой вершины v не больше чем ключ любой вершины из поддерева с корем в v

Операция добавления элемента в вершину

Читайте в книге "Практика и теория программирования. Часть 2", Винокуров, Ворожцов.

Операция удаления элемента из вершины

Читайте в книге "Практика и теория программирования. Часть 2", Винокуров, Ворожцов.

Задание на семинар