Создать базу данных фильмографии актера Кристиана Бейла, произвести анализ информации и её сортировку
Министерство образования и
Федеральное государственное бюджетное образовательное учреждение
высшего профессионального образования
«Тульский государственный университет»
Политехнический институт
Факультет транспортных и технологических систем
Кафедра «Технология полиграфического производства и
Курсовая работа
по дисциплине «Информатика»
на тему:
«Создать базу данных фильмографии актера Кристиана Бейла, произвести анализ информации и её сортировку»
Выполнил студент гр. 622211
Дергачев В.Н.
Проверил доцент
Пальчун Е.Н.
Тула 2012
Содержание
1. |
Теоретическая часть……………………………………………………2 |
|
2. |
Проектная часть………………………………………………………12 |
|
3. |
Вывод………………………………………………………………… |
|
4. |
Библиографический список………………………………………….18 |
|
Приложения…………………………………………………… |
||
Введение
На протяжении последних 10 лет идет планомерное вытеснение карточной системы в библиотеках, архивах на поисковые системы общего доступа, реализованные на основе ЭВМ. При этом в последние годы такие системы выходят за рамки учреждения в общий доступ средствами Интернет технологий.
В данной работе не идет речь о создании подобной системы, а рассматривается вопрос, связанный с дальнейшей обработкой информации, после выполнения поискового запроса, а именно – сортировка данных. При всей, на первый взгляд простоте процесса, это всё еще не до конца отработанная процедура.
Решение данного вопроса является важным этапом в эволюции технологии обработки информации.
Теоретическая часть
Достаточно часто
Решение сортировать данные на стороне сервера вполне оправданно и с точки зрения трудозатрат программиста, так как многие из них имеют встроенные функции сортировки многомерных массивов, и поэтому не требуется вдумываться в алгоритмы сортировки, что-то изобретать или перестраивать алгоритм под свои нужды. Но все-таки такое решение не оправдано, если подходить к этой проблеме с точки зрения удобства использования пользователями.
Вначале посетителю сайта требуется дождаться достаточно длительной загрузки страницы, просмотреть результаты, нажать на кнопку "Отсортировать" и опять дожидаться, пока сервер закончит работу и вернет результат. Такие множественные перезагрузки страницы никак не способствуют популярности сайта у посетителя. В конце-концов, устав дожидаться очередной загрузки страницы, или испугавшись лишнего траффика, он покинет сайт в поисках более лояльного к нему ресурса.
В общем понимании сортировка - это упорядочивание элементов по возрастанию или убыванию. Сортировка очень важная операция во всех сферах программирования.
Во всех обменных сортировках сравниваются два элемента отстоящие друг от друга на расстоянии d. При этом два элемента сравниваются и элемент с большим весом перемещается вправо, а с меньшим влево.
Существует большое количество способов сортировки, разработаны математические приемы обработки данных. Условно эти методы можно разделить на две категории: универсальные и методы, позволяющие обработать конкретные типы данных.
К последним, можно отнести обработку числовых данных на предмет выявления ложных (нулевых или сильно заниженных, завышенных) значений. Это бывает очень важно при решении технических задач, например, никто не может утверждать, что в полученных во время эксперимента данных нет результатов, которые могут привести к потере работоспособности программного продукта в дальнейших расчетах. В этом случае статистическая сортировка позволяет решить данную проблему.
Однако данный метод не применим к текстовым или тем более смешанному типу данных.
Для решения проблемы сортировки смешанных или текстовых типов данных существуют так называемые универсальные методы. В числе наиболее часто применяемых решений выделяют три основных, речь о которых пойдет ниже. Именно эти методы и необходимо реализовывать в нашем случае, так как данные, хранимые в библиотечных каталогах, далеко не всегда являются однородными по типу (могут содержать год, число страниц и другую числовую составляющую, и при этом иметь название, автора и другую текстовую информацию).
Среди наиболее востребованных и проверенных методов выделяют три основных.
Стандартный обмен
Метод стандартного обмена еще называется "Методом Пузырька". В этом методе d=1, т.е. сравниваются рядом стоящие элементы. При первом проходе алгоритм последовательно сравнивает по два элемента и меняет их местами в зависимости от условия сортировки. При этом на последнем месте оказывается самый максимальный (минимальный) элемент. На втором шаге алгоритм сравнивает первые N-1 элементов в ставит предпоследним самый большой. При каждом последующем шаге интервал уменьшается на единицу.
Давайте рассмотрим пример:
Дано множество
{8,3,4,2,5}
1. {3,8,4,2,5} - сравниваются 8 и 3, переставляются т.к. 8>3
2. {3,4,8,2,5} - сравниваем 8 и 4, также переставляем.
3. {3,4,2,8,5}
4. {3,4,2,5,8}
В результате этого первого шага элемент весом в 8, переместился в конец. Далее он не рассматривается и операция сортировки производится с множеством {3,4,2,5}.
В результате всех шагов у нас образуется отсортированное по возрастанию множество {2,3,4,5,8}.
Программная реализация этого алгоритма на языке СИ представлена ниже.
#include <stdio.h>
#include <stdlib.h>
int BubbleSort(int *array,int len)
{
int i,j,c;
int k=0;
for (i=len;i>1;i--)
{
k=0;
for (j=1;j<i;j++)
if (array[j]<array[j-1])
{
c=array[j];
array[j]=array[j-1];
array[j-1]=c;
k=1;
};
if (k==0) return 0;
};
};
Условия Айверсона
На каком-то этапе, может даже на начальном, массив окажется полностью отсортированным, и для того, чтобы зря не тратить время на сортировку существует условие Айверсона.
Условие: Сортировку можно прекратить досрочно, если на каком-то этапе в ходе сравнения не будет сделано ни одной перестановки.
За это условие в процедуре Bub
Метод Шекла
Сортировка по методу Шелла также относится к обменным сортировкам, и даже принцип функционирования очень похож на "метод пузырька".
В этом методе первоначально рассматриваются элементы, отстоящие друг от друга на расстояние d=[n/2], где [ ] - операция взятия целой части, и n - количество элементов исходного массива.
На следующих шагах d меняется по закону d=[d/2], при d=1 метод Шелла вырождается в метод стандартного обмена ("Метод Пузырка").
Для объяснения данного приема, рассмотрим пример:
Дано множество:
{6,3,4,8,2,9}
d=[n/2]=[6/2]=3
{6,3,4,8,2,9} - сравниваем 6 и 8
{6,2,4,8,3,9} - сравниваем 3 и 2, переставляем
{6,3,4,8,2,9} - сравниваем 4 и 9
далее d=[d/2]=[3/2]=1
выродился в метод "Пузырька"
В этом примере не очень видна эффективность этого метода, но представьте, что вы сортируете 1000 элементов. Этот метод обеспечивает более быстрое перебрасывание больших элементов вправо и меньших влево, чем метод "Пузырька" и этим обеспечивает большее быстродействие.
Программная реализация на СИ может быть записана следующим образом:
int BubbleSort(int *array,int len)
{
/* Код сортировки из предыдущего шага */
};
int ShellSort(int *array,int len)
{
long d=len,i,j;
int c;
do
{
d=d/2;
i=0;
while ((j=i+d)<len)
{
if (array[i]>array[j])
{
c=array[i];
array[i]=array[j];
array[j]=c;
};
i++;
};
}
while (d>1);
BubbleSort(array,len);
};
Результат выполнения:
8 -5 1 7 3 -10 6 5 10 9
-10 -5 1 3 5 6 7 8 9 10
Для теста эффективности обычно создают счетчик циклов, и на конкретном примере до вырождения в метод "Пузырька" было выполнено всего 3 прохода. Причем, массив был получен в следующем виде:
-10 -5 1 3 5 6 7 8 9 10
Из него видно, что он уже отсортирован и метод "Пузырька" работал в холостую, но совершил всего один цикл, т.к. в нем выполнилось условие Айверсона.
Очевидно, что метод Шелла обладает большим быстродействием.
При обходе оригинального массива процедура может создавать вспомогательный, или же напрямую работать с оригинальным массивом, при этом она удаляет ненужные элементы. Для того чтобы хранить список данных надо всегда помнить ссылку на один из его компонентов. Обычно хранят ссылку на первый компонент, так как это самый рациональный выбор.
Вся проблема заключается в том, что "ходящая" процедура не в курсе какой элемент она удаляет, и ей все равно будь он первый, средний или последний. И возникает вопрос, что же будет, если она нечаянно удалит первый элемент, адрес которого Вы храните неизвестно в каком количестве переменных. Получается, что весь список пропадет разом.
Так вот как уберечься от удаления первого элемента? Идея, как всегда крайне проста. Обработчик списка надо написать таким образом, чтобы он анализировал положение удаляемого элемента списка, т.е. если удаляемый элемент находится в середине списка, то он удаляется обычным образом, а вот если он был первым, то не удаляет себя, а удаляет следующий по списку элемент, при этом полностью скопировав его содержимое.
Все просто, надо чтобы элемент как бы удалялся, но при этом второй строго занимал бы его прежнее место. Таким образом, помня адрес первого элемента, Вы можете с ним делать, что хотите, так как Вы его никогда не потеряете.
Сортировка Хоара
Сортировка Хоара это третий метод относящийся к обменным сортировкам. Этот метод признан одним из лучших методов сортировки, которые когда-либо изобрели. Он даже носит название "Быстрой сортировки".
В методе Хоара первоначально выделяют
базовый элемент, относительно которого
ключи с большим весом
В качестве базового элемента очень удобно брать крайние элементы.
Для наглядного представления, рассмотрим следующий пример:
Дано множество:
{9,6,3,4,10,8,2,7}
Берем 9 в качестве базового элемента. Сравниваем 9 с противоположностоящим элементом, в данном случае это 7. 7 меньше, чем 9, следовательно элементы меняются местами.
{7,6,3,4,10,8,2,9}
Далее последовательно сравнивают элементы с 9, и меняют их местами в зависимости от сравнения.
{7,6,3,4,10,8,2,9}
{7,6,3,4,10,8,2,9}
{7,6,3,4,10,8,2,9}
{7,6,3,4,9,8,2,10} - 9 и 10 меняем местами.
{7,6,3,4,8,9,2,10} - 9 и 8 меняем местами.
{7,6,3,4,8,2,9,10} - 2 и 9 меняем местами.
После такого перебрасывания элементов весь массив разбивается на два подмножетсва, разделенных элементом 9.
{7,6,3,4,8,2}
{10}
Далее по уже отработанному алгоритму сортируются эти подмножества.
Подмножество из одного элемента естественно можно не сортировать. Выбираем в первом подмножестве базовый элемент 7.
{7,6,3,4,8,2}
{2,6,3,4,8,7} - меняем местами 2 и 7.
{2,6,3,4,8,7}
{2,6,3,4,8,7}
{2,6,3,4,8,7}
{2,6,3,4,7,8}- меняем местами 7 и 8
Получили снова два
{2,6,3,4}
{8}
Скорость работы алгоритма зависит прежде всего от его реализации, поэтому самое главное найти эту правильную реализацию. Единственный путь к ускорению всегда лежит через уменьшение количества сравнений на каждой итерации.
Проектная часть
В нашем задании существует условие, что данные сортируются в среде Интернет. Поэтому задачу необходимо решать, основываясь именно на этом сегменте языков программирования.
В сфере web-программирования, существуют уже готовые решения по сортировке на стороне клиента. В большинстве случаев они основаны на сортировке методом Хоара. Условно их можно разделить на 2 вида: сортировку таблиц, на основе анализа их содержания, и сортировку массивов, а после формирования таблицы, для удобного вывода информации.
К первому способу относятся способы сортировки на основе библиотек jquery. В них уже заложены проверенные методы сортировки, в частности Хоара.
Ко второму – отдельные
У обоих методов есть свои плюсы и минусы, в частности у первого способа, уже должны быть готовые таблицы, оформленные синтаксисом HTML. Конечно, их можно получать методами обхода массивов, однако это потребует большей трудоемкости при написании программы. У второго же способа серьезным недостатком является неотработанность и возможность наличия ошибок в алгоритме, а также сложности при оформлении результатов, так как почти всегда используется способ динамического создания таблиц с применением объектного программирования. Это сложная система получения таблицы результатов, при этом не всегда удобно рассматривать подобный код с точки зрения нахождения ошибки при формировании сложных табличных структур (объединение ячеек, установка размеров, как всей таблицы так и её ячеек, обводки и т.д.).
Мы выбираем первый вариант, так как он является отработанным, понятным и удобным способом записи данных. Кроме того, получить динамически подобную структуру циклом не так сложно, как объектным.
После выбора способа сортировки данных необходимо проанализировать задание и определить, какую информацию необходимо сортировать, а что можно просто указывать так как она не играет роль первостепенной.
В моем задании присутствуют как данные, встречающиеся в каждой записи, так и редко встречающиеся.
ДЛЯ КНИГ
Во всех записях присутствуют следующие данные:
1. Автор произведения;
2. Название произведения;
3. Издательство;
4. Год выпуска.
Присутствует также отрывочная информация по:
1. Количеству страниц в
2. Количеству томов или номеру тома.
ДЛЯ ФИЛЬМОВ
Во всех записях присутствуют следующие данные:
1. Год выпуска;
2. Название произведения.
Присутствует также отрывочная информация по:
1. Попаданию фильма в рейтинги TOP 250 и другие;
2. Объему бюджета;
3. Имени героя, под которым снимался актер.
В связи с этим считаю верным, применять сортировку, только к данным всегда, встречающимся в записях, а другие записи поместить в примечание или описание.
Для реализации поставленной задачи необходимо использовать бесплатный плагин jquery. Его подключение заключается в добавлении текстовой строки в исполняемый блок Интернет страницы:
<script type="text/javascript" src="jquery-latest.js"></
а также, написанного специально для сортировки дополнения tablesorter в минимальной комплектации, для уменьшения объема всего проекта:
<script type="text/javascript" src="jquery.tablesorter.min.
и внешней библиотеки стилей дополнения tablesorter:
<style type="text/css">@import "style.css";</style>.
Далее формируется сама таблица, для упрощения процесса и большей наглядности делаем это вручную. При этом необходимо помнить следующие особенности:
1. Сортировка осуществляется
на основе активации ячеек
верхнего ряда таблицы или,
проще говоря, её заголовков. Так
как в спецификации указано,
что оформление заголовков
2. Чтобы создать заголовок таблицы, необходимо применить особый тег в таблице (<th> … </th>) и, как указанно в спецификации, разбить её на «головную часть» (<thead> … </thead>) и «тело» (<tbody> … </tbody>).
Учитывая данные условия использования и подключения плагина получим следующую примерную конструкцию таблицы:
<table class="tablesorter" id="myTable">
<thead>
<tr>
<th>Автор</th>
<th>Название произведения (фильма)</th>
<th>Год выхода</th>
</tr>
</thead>
<tbody>
<tr>
<td>Иванов Иван Иванович</td>
<td>Моя книга</td>
<td>2010</td>
</tr>
<tr>
<td>Василий Иванович Иванов</td>
<td>Это моя книга</td>
<td>2009</td>
</tr>
</tbody>
</table>
После заполняем таблицу и получаем в итоге код Интернет страницы, представленной в приложении 1.
Далее следует проверка на адекватность работы программы, а именно:
1. Произвольно выбираются 2 параметра,
по которым осуществляется
2. Выполняется сортировка данных, по ранее выбранным параметрам по возрастанию и по убыванию.
3. Выполняется проверка на
Результат 2-го и 3-го пункта приведен в приложении 3.
Вывод
Процедура сортировки крайне важный элемент в обработке данных различных фондов, архивов, библиотек. Она позволяет сократить время нахождения информации, способствует выявлению специфических особенностей и закономерностей в найденном материале.
При существующих методах сортировки необходимо выбирать те, которые являются отработанными и максимально быстрыми. Наиболее подходящим является метод Хоара, как наиболее сбалансированный.
В среде Интернет сортировку лучше производить на стороне клиента, так как данный процесс сильно загружает серверную машину и уменьшает пропускную способность канала связи. Последнее приводит к задержкам в загрузке страниц и постепенно приводит к потере популярности ресурса.
Также стоит отметить, что лучше сортировать данные без перезагрузки страницы средствами JavaScript, так как это не раздражает пользователя и самое главное, нет вероятности потери данных при составлении ответа сервера, так как клиентская машина уже имеет всю необходимую информацию.
Как видно из приложения 3, приведенного ниже, все тесты прошли удачно. А значит данным методом можно пользоваться в дальнейшем.
Библиографический список
1. Андреева, Т.А. Программирование на языке Pascal : учеб. пособие / Т.А. Андреева.— М.: Интернет-ун-т информ. технологий. БИНОМ. Лаборатория знаний, 2006 .— 234 с. — (Основы информационных технологий).— [АУЛ-1 – 14 экз, Шифр(ы) хранения: 1256787, 1256788, 1256789, 1256790, 1256791, 1256792, 1256793, 1256794, 1256795, 1274067, 1274068, 1274069, 1274070, 1274071].
2. Борисенко, В.В. Интернет
3. Марков, А.С. Базы данных. Введение в теорию и методологию : учебник для вузов / А.С.Марков, К.Ю.Лисовский .— М. : Финансы и статистика, 2004.— 512 с. – [АУЛ-1 – 7 экз, Шифр(ы) хранения: 1205178, 1205179, 1223424, 1223425, 1223426, 1223427, 1223428]
4. Хорев, П.Б. Технологии
Приложение 1
Итоговый код Интернет страницы
<html>
<head>
<title>Фильмография актера Кристиана Бейла</title>
<meta http-equiv="Content-type" content="text/html; charset=Windows-1251">
<style type="text/css">@import "style.css";</style>
<script type="text/javascript" src="jquery-latest.js"></
<script type="text/javascript" src="jquery.tablesorter.min.
</head>
<body>
<table class="tablesorter" id="myTable">
<thead>
<tr>
<th>Год выпуска</th>
<th>Название произведения</th>
<th>Оригинальное название</th>
<th>Объем бюджета</th>
<th>Имя героя</th>
</tr>
</thead>
<tbody>
<tr>
<td>2012</td>
<td>Бетмен 3 </td>
<td>Untitled Batman Project </td>
<td>Неизвестен</td>
<td>Bruce Wayne</td>
</tr>
<tr>
<td>2011</td>
<td>Убить Пабло </td>
<td>Killing Pablo </td>
<td>Неизвестен</td>
<td>Major Steve Jacoby</td>
</tr>
<tr>
<td>2010</td>
<td>Боец </td>
<td>Fighter, The </td>
<td>Неизвестен</td>
<td>Dickie Eklund</td>
</tr>
<tr>
<td>2009</td>
<td>Джонни Д. </td>
<td>Public Enemies </td>
<td>Неизвестно</td>
<td>Melvin Purvis</td>
</tr>
<tr>
<td>2009</td>
<td>Терминатор: Да придёт спаситель </td>
<td>Terminator Salvation</td>
<td>Неизвестен</td>
<td>John Connor</td>
</tr>
<tr>
<td>2008</td>
<td>Темный рыцарь </td>
<td>Dark Knight, The </td>
<td>$ 10 000 000</td>
<td>Bruce Wayne </td>
</tr>
<tr>
<td>2007</td>
<td>Меня там нет </td>
<td>I'm Not There</td>
<td>Неизвестен</td>
<td>Jack / Pastor John</td>
</tr>
<tr>
<td>2007</td>
<td>Поезд на Юму</td>
<td>3:10 to Yuma </td>
<td>Неизвестен</td>
<td>Dan Evans</td>
</tr>
<tr>
<td>2006</td>
<td>Престиж</td>
<td>Prestige, The </td>
<td>Неизвестен</td>
<td>Alfred Borden</td>
</tr>
<tr>
<td>2006</td>
<td>Спасительный рассвет </td>
<td>Rescue Dawn </td>
<td>Неизвестен</td>
<td>Dieter </td>
</tr>
<tr>
<td>2005</td>
<td>Новый Свет </td>
<td>New World, The </td>
<td>Неизвестен</td>
<td>John Rolfe</td>
</tr>
<tr>
<td>2005</td>
<td>Крутые времена </td>
<td>Harsh Times </td>
<td>Неизвестен</td>
<td>Jim Luther Davis</td>
</tr>
<tr>
<td>2005</td>
<td>Бэтмен: Начало </td>
<td>Batman Begins</td>
<td>Неизвестен</td>
<td>Bruce Wayne </td>
</tr>
<tr>
<td>2004</td>
<td>Ходячий замок </td>
<td>Hauru no ugoku shiro</td>
<td>Неизвестен</td>
<td>Howl, озвучка, английская версия</
</tr>
<tr>
<td>2004</td>
<td>Машинист</td>
<td>Maquinista, El</td>
<td>Неизвестен</td>
<td>Trevor Reznik</td>
</tr>
<tr>
<td>2002</td>
<td>Эквилибриум</td>
<td>Equilibrium</td>
<td>Неизвестен</td>
<td>John Preston </td>
</tr>
<tr>
<td>2002</td>
<td>Власть огня</td>
<td>Reign of Fire </td>
<td>Неизвестен</td>
<td>Quinn Abercromby</td>
</tr>
<tr>
<td>2002</td>
<td>Лорел Каньон </td>
<td>Laurel Canyon</td>
<td>Неизвестен</td>
<td>Sam</td>
</tr>
<tr>
<td>2001</td>
<td>Выбор капитана Корелли</
<td>Captain Corelli's Mandolin</td>
<td>Неизвестен</td>
<td>Mandras</td>
</tr>
<tr>
<td>2000</td>
<td>Шафт</td>
<td>Shaft</td>
<td>Неизвестен</td>
<td>Walter Wade, Jr</td>
</tr>
<tr>
<td>2000</td>
<td>Американский психопат </td>
<td>American Psycho </td>
<td>Неизвестен</td>
<td>Patrick Bateman</td>
</tr>
<tr>
<td>1999</td>
<td>Иисус (ТВ) </td>
<td>Mary, Mother of Jesus </td>
<td>Неизвестен</td>
<td>Jesus of Nazareth</td>
</tr>
<tr>
<td>1999</td>
<td>Сон в летнюю ночь</td>
<td>A Midsummer Night's Dream</td>
<td>Неизвестен</td>
<td>Demetrius</td>
</tr>
<tr>
<td>1998</td>
<td>Все маленькие животные </td>
<td>All the Little Animals</td>
<td>Неизвестен</td>
<td>Bobby Platt</td>
</tr>
<tr>
<td>1998</td>
<td>Бархатная золотая жила</
<td>Velvet Goldmine</td>
<td>Неизвестен</td>
<td>Arthur Stuart</td>
</tr>
<tr>
<td>1997</td>
<td>Метролэнд</td>
<td>Metroland</td>
<td>Неизвестен</td>
<td>Chris</td>
</tr>
<tr>
<td>1996</td>
<td>Секретный агент</td>
<td>Secret Agent, The</td>
<td>Неизвестен</td>
<td>Stevie</td>
</tr>
<tr>
<td>1996</td>
<td>Портрет леди </td>
<td>Portrait of a Lady, The</td>
<td>Неизвестен</td>
<td>Edward Rosier</td>
</tr>
<tr>
<td>1995</td>
<td>Покахонтас</td>
<td>Pocahontas</td>
<td>Неизвестен</td>
<td>Thomas, озвучка</td>
</tr>
<tr>
<td>1994</td>
<td>Маленькие женщины </td>
