Перейдем к последним двум структурам, которые построены с учетом того, что нам необходимо хранить именно целые числа, а не данные каких-либо других типов. Битовые векторы знакомы нам с главы 1. В листинге 13.16 приведены внутренние данные и функции класса IntSetBitVec.
Листинг 13.16. Внутренние данные и функции класса IntSetBitVec
enum { ВITSPERWORD = 32. SHIFT = 5, MASK = QxlF }. int n , hi. *x .
void set (i nt i) { x[i»SHIFT] |= (l«(i & MASK)). } void cl r( i nt i) { x[i»SHJFT] &= -(1«M & MASK)). } int test(int i) { return x[i>>SHIFT] & (l«(i & MASK)), }
Конструктор в листинге 13.17 выделяет память под массив и сбрасывает все его биты в 0.
Листинг 13.17. Конструктор класса IntSetBitVec
IntSetBitVec(maxelenents. maxval ) hi = maxval
x = new mt[l + hi/BITSPERW0RD] for i = [0. hi ) cl rd ) n = 0
В задаче 8 вам предлагается ускорить это процесс путем перехода к пословным операциям. Аналогично можно ускорить и функцию report, приведенную в листинге 13.18.
void Veport(v)
J = О
for i = [0. hi) if test(i) v[j++] = i
Наконец, функция insert (листинг 13.19) включает соответствующий бит и увеличивает число п, но только в том случае, если на момент ее вызова бит был сброшен.
Листинг 13.19. Функция insert класса IntSetBitVec
void insert(t) if test(t) return set(t) n + +
Таблица 8.2 показывает, что, если п достаточно мало, чтобы битовый вектор целиком поместился в оперативной памяти, эта структура оказывается весьма эффективной (а задача 8 предлагает вам еще больше увеличить ее производительность). К сожалению, если n = 232, то битовый вектор потребует полгигабайта ОЗУ.
Последняя структура данных объединяет достоинства списков и битовых векторов. Целые числа раскидываются по набору «корзин» (bins). Предположим, что нужно выбрать 4 числа из диапазона 0. .99. Поместим их в четыре корзины. Корзина 0 предназначена для чисел 0..24, корзина 1 — для чисел 25..49, корзина 2 — для чисел 50. .74, а корзина 3 — для чисел 75. .99.
Опубликовал vovan666
April 17 2013 00:03:35 ·
0 Комментариев ·
3526 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
