Сортировка файлов

Сортировка файлов

Для тестирования четырех вариантов реализации программ сортировки из главы 5 использовался целевой файл, состоящий из 100 000 записей размером 64 байта каждая (всего 6,4 Мбайт). Вывод отсортированного файла во всех случаях подавлялся, чтобы можно было оценивать только время, необходимое для выполнения собственно сортировки. После этого тестировалась многопоточная сортировка (программа 7.2) файла размером 25 Мбайт, состоящего из 400 000 записей размером 64 байта каждая, с использованием одной, двух и четырех потоков. В каждом отдельном запуске использовался отдельный файл, генерируемый программой RandFile, которая находится в каталоге главы 5. Результаты для разных запусков заметно различались между собой.

1. Программа sortBT (программа 5.1) создает бинарное дерево поиска, требующее выделения минимального объема памяти под каждую запись. Эта программа интенсивно использует процессор.

2. Программа sortFL (программа 5.4) создает отображение файла перед тем, как использовать программу qsort. Тестировалась также программа sortFLSR (доступ к куче подвергался сериализации), однако существенных отличий от предыдущего варианта замечено не было.

3. Текст программы sortHP в книге не приводился. Эта программа предварительно распределяет буфер для файла, а затем сортирует файл, считанный в этот буфер, а не его отображение, как программа sortFL.

4. Программа sortMM (программа 5.5) создает постоянно существующий индексный файл.

5. Программа sortMT (программа 7.2) реализует многопоточную сортировку слиянием. Результаты представлены в строках sortMT1, sortMT2 и sortMT4 в соответствии с количеством параллельных потоков. Результаты могут значительно меняться в зависимости от характера сортируемых данных, хотя размер и случайный характер распределения значений данных сглаживают эти различия, что, как правило, характерно для базового алгоритма быстрой сортировки, который использован для реализации функции qsort библиотеки С.

Комментарии

1. Реализация, использующая алгоритм бинарного дерева (программа sortBT), интенсивно использует процессор; кроме того, память в ней распределяется отдельно для каждой записи.

2. Применение отображения файлов и чтение файла в предварительно выделенный буфер обеспечивают примерно одинаковую производительность, но в этих тестах отображение файлов ничем особенным себя не проявило, а в некоторых случаях даже значительно ухудшало результаты. Вместе с тем, в ряде случаев как sortFL, так и sortHP обеспечивали превосходные результаты.

3. Суммарное пользовательское и системное время иногда превышает истекшее время, даже если используется только один поток.

4. Программа sortMT демонстрирует возможности SMP-систем. В некоторых случаях использование дополнительных потоков приводило к повышению производительности и на однопроцессорных системах.

Таблица В.4. Показатели производительности программ сортировки файлов

ЦП Pentium LT Celeron LT Xeon 4?Xeon
ОС W2000  XP W2000 W2000
Файловая система NTFS NTFS NTFS NTFS
sortBT Реальное время - 9,61 - -
Пользовательское время - 1,84 - -
Системное время - 7,44 - -
sortFL Реальное время 11,15 0,78 1,74 5,38
Пользовательское время 4,81 0,41 0,26 5,19
Системное время 0,15 0,09 0,09 0,02
sortHP Реальное время 1,76 0,34 1,52 1,30
Пользовательское время 1,62 0,22 0,15 1,28
Системное время 0,11 0,05 0,03 0,04
sortMM Реальное время 0,99 1,44 1,92 1,39
Пользовательское время 0,31 0,18 0,15 0,38
Системное время 0,68 0,47 0,36 1,03
sortMT1 Реальное время 3,18 3,58 6,80 0,14
Пользовательское время 0,01 0,95 0,01 0,05
Системное время 0,46 0,16 0,16 0,11
sortMT2 Реальное время 2,10 1,22 6,70 0,13
Пользовательское время 0,01 1,05 0,01 0,02
Системное время 0,40 0,16 0,16 0,13
sortMT4 Реальное время 2,20 1,49 6,22 0,13
Пользовательское время 0,01 1,18 0,01 0,12
Системное время 0,16 0,15 0,16 0,09
Поделитесь на страничке

Следующая глава >

Похожие главы из других книг

Сортировка

Из книги Использование ListView в режиме виртуального списка автора Чадов Тимофей

Сортировка Трудности? Это еще что такое? Однако бесплатный сыр сами знаете где. Дело в том, что, так как сами элементы в списке не хранятся, придется самим заботится о сортировке. Не удастся воспользоваться функцией CListCtrl::SortItems, бесполезно писать CompareItems и т.п. Все, что у вас


Сортировка

Из книги Windows Vista автора Вавилов Сергей

Сортировка В отличие от предыдущих версий в Проводнике Windows Vista заголовки столбцов, с помощью которых можно проводить сортировку объектов и другие действия, доступны при любом способе отображения значков.Щелчком кнопки мыши на заголовке любого столбца вы можете


8.1.5. Сортировка массива

Из книги Справочник по PHP автора

8.1.5. Сортировка массива Самый простой способ отсортировать массив — воспользоваться встроенным методом sort:words = %w(the quick brown fox)list = words.sort # ["brown", "fox", "quick", "the"]# Или отсортировать на месте:words.sort!       # ["brown", "fox", "quick", "the"]Здесь предполагается, что все элементы массива сравнимы


8.2.10. Сортировка хэша

Из книги Технология XSLT автора Валиков Алексей Николаевич

8.2.10. Сортировка хэша Хэши по природе своей не упорядочены ни по ключам, ни по значениям. Чтобы отсортировать хэш, Ruby преобразует его в массив, который затем сортирует. Понятно, что и результатом является массив.names = {"Jack"=>"Ruby","Monty"=>"Python",         "Blaise"=>"Pascal", "Minnie"=>"Perl"} list =


Сортировка массивов

Из книги Программирование на языке Пролог для искусственного интеллекта автора Братко Иван

Сортировка массивов array_reverseРасстановка элементов массива в обратном порядке.Синтаксис:array array_reverse(array arr [, bool preserve_keys])Функция array_reverse() возвращает массив, элементы которого следуют в обратном порядке относительно массива, переданного в параметре. При этом связи между


Сортировка

Из книги Фундаментальные алгоритмы и структуры данных в Delphi автора Бакнелл Джулиан М.

Сортировка При преобразовании документа элементами xsl:for-each и xsl:apply-templates, выбранные узлы по умолчанию обрабатываются в порядке просмотра документа, который зависит от выражения, использованного в атрибуте select этих элементов. XSLT позволяет изменять этот порядок


9.1.2. Сортировка списков

Из книги Язык Си - руководство для начинающих автора Прата Стивен

9.1.2. Сортировка списков Сортировка применяется очень часто. Список можно отсортировать (упорядочить), если между его элементами определено отношение порядка. Для удобства изложения мы будем использовать отношение порядкабольше( X, Y)означающее, что X больше, чем Y,


Глава 5. Сортировка

Из книги Linux и UNIX: программирование в shell. Руководство разработчика. автора Тейнсли Дэвид

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


СОРТИРОВКА ЧИСЕЛ

Из книги автора

СОРТИРОВКА ЧИСЕЛ      Одним из наиболее распространенных тестов для машин является сортировка. Мы хотим разработать программу для сортировки целых чисел. Снова применим принцип черного ящика и подумаем в терминах ввода и вывода. Наш общий замысел, показанный на рис. 10.4,


Сортировка данных

Из книги автора

Сортировка данных      Рассмотрим еще раз функцию main( ):  main(  ){int numbers[MAXSIZE]; /* массив для ввода */int size;     /* количество введенных элементов */size = getarray(numbers, MAXSIZE); /* помещает ввод в массив */sort(numbers, size); /* сортировка массива */printf(numbers, size); /* печать отсортированного


11.1. Сортировка файлов с помощью команды sort

Из книги автора

11.1. Сортировка файлов с помощью команды sort Команда sort позволяет выполнять сортировку входного потока по различным полям (ключам сортировки). Это довольно мощная команда, которая весьма полезна при обработке журнальных файлов или реорганизации текстовых столбцов в


11.1.6. Простейшая сортировка

Из книги автора

11.1.6. Простейшая сортировка В простейшем случае, чтобы отсортировать файл, достаточно передать его имя команде sort. Сортировка будет выполнена по строкам:$ sort video.txtA Few Good Men:KL:445:5851A. Iien:HK:119:1982Aliens:HK:532:4892Boys in Company C:HK:192:2]92Star Wars:HK:301:4102The tfili:KL:63:2972Toy Story.