| 2. Приведенные ниже функции позволяют установить, проверить и сбросить значение бита. |
#def1пе ВITSPERW0RD 32 #def1ne SHIFT 5 #deTine MASK OxlF
#define N 10000000 int a[l+N/BITSPERWORD],
void set (i nt i) { a[i>>SHIFT] |= (l«(i & MASK)), } void cl г (i n t i) { a[i>>SHIFT] &= -(l«(i & MASK)); } int test(int i) {return a[i>>SHIFT] & (l<<(i & MASK)), }
3. Программа на языке С, приведенная ниже, реализует алгоритм сортировки, используя функции, определенные в решении задачи 2.
int та 1п(void)
{ int i ,
for (i = 0, i < N, i++) clr(i ) .
while (scanf("Јd" , &i) != EOF) set(i ) , for (i = 0, i < N, i++) i f (test(i ))
printf("%d\n", i ) ; return 0;}
Я воспользовался программой из решения задачи 4, чтобы сформировать файл из миллиона различных целых чисел, каждое из которых не превышало десяти миллионов. В табл. 1 приведена стоимость сортировки такого файла с помощью системной утилиты sort, программ на С и C++ из решения задачи 1 и программы с битовым вектором.
Таблица 1. Время сортировки файла
Системная сортировка C++/STL С/qsort C/bitmap
Полное время, с 89 38 12,6 10,7
Время вычисления, с 79 28 2,4 0,5
Занимаемая память, Мбайт 0,8 70 4 1,25
В первой строке приведено полное время работы программы, а во второй строке из этого времени вычитается время ввода и вывода данных (10,2 с). Хотя программа на C+ + использует в 50 раз больше памяти и времени на вычисления, чем специализированная программа на С, сам текст программы оказывается вдвое короче и его гораздо проще расширить для решения других задач. |
Опубликовал vovan666
April 17 2013 00:06:13 ·
0 Комментариев ·
4035 Прочтений ·
|
|
Главная
Каталог файлов
