Бойтесь коэффициентов, скрытых за "О-болышш": операции над массивами обычно "дешевле" по сравнению с некоторыми вариантами реализации доступа к битовому вектору, с операциями для работы с указателями в двоичном дереве, с операциями деления, используемыми при работе с "карманами". Чтобы разобраться в вопросах, связанных с эффективностью, давайте рассмотрим случай с N - 1 000 000 и b - 32. При М = 4000 "карманы" являются, вероятно, самой эффективной структурой; когда М = 50 000, побитовое предствление осуществляется быстрее и занимает меньше места; при М = 400 000 программа 1 использует намного меньше места и также работает быстрее. Однако при М = 309 305 лучше отметить пять невыбранных элементов. Любой вариант легко запрограммировать и получить быстроработающую программу.
Еще один подход к получению упорядоченного подмножества случайных целых чисел состоит в "перетасовке" N-элементного массива, в котором содержатся числа от 1 до N, а затем в упорядочении первых М элементов, которые и являются выходными данными. Алгоритм Кнута в разд. 3.4.2 перетасовывает массив X [1 . . . N].
for I := 1 to M do
Swap(XL I], XCRandInt(I,N)3)
Э. Шеперд и А. Воронов из Хьюстонского университета отметили, что в этой программе нам требуется перетасовать только первые М элементов массива, что приводит к программе 3.
for I := 1 to M do XtI3 := I for I := l to M do
Swap(Xm, XCRandlntU.N)]) Sortd, M)
Упорядоченный список находится в массиве X [1 ... М]. В этом алгоритме используется N слов ОЗУ и время О (N + MlogM), но методика, применяемая в задаче 8 гл. 1, сокращает это время до О (MlogM). Этот алгоритм мы можем рассматривать как альтернативу программе 2, множеству выбранных элементов в нем соответствует массив X [1 ... I], а множеству невыбранных элементов - массив X [I + 1 . . . N]. Явно задавая невыбранные элементы, мы устраняем проверку того, был ли очередной элемент выбран ранее.
153
