В.Д. Валединский - Краткий конспект курса лекций «Работа на ЭВМ и программирование» (1119512), страница 4
Текст из файла (страница 4)
Второй – в точно такой же ситуации, когда нужно удалить k-й элемент, а kй и(k+1)й потомки этой вершины содержат по n элементов. В обоих случаях «сливаем» эти 2вершины по n элементов в одну из 2n элементов (еще у нас было 2 элемента вышележащегоуровня, но один элемент мы удалили, так что снова будет один элемент на верхнем уровне,все свойства B-дерева сохраняются). При этом может понадобиться слить вершинывышележащего уровня и т.д. На каком-то этапе на самом верхнем уровне может не остатьсяэлементов совсем (и у нее будет 1 потомок) – в этом случае удаляем эту пустую вершину иделаем корнем потомка этой вершины.Можно аккуратно посчитать асимптотику добавления и удаления элементов в B –дерево.
В большинстве случаев это происходит за 1-n операций, в среднем n/2 операций илишь в некоторых случаях – существенно больше, вплоть до N/2, где N – число элементов вB-дереве, n – порядок дерева. В среднем в любом случае получается время O(n).Указанные деревья очень широко используются в огромном числе операций с данными,где нельзя заранее указать, каково примерно будет число элементов в оперируемоммножестве данных, либо это число достаточно велико. Сбалансированные деревья имеютлучшую из известных теоретических оценок для трудоемкости операций с деревом,соответствующие оценки для красно-черных деревьев чуть хуже, но операции в нихреализуются несколько проще и поэтому на практике они обычно работают несколькобыстрее (подобное будет в дальнейшем и при сравнении сортировок heapsort с quicksort).
Bдеревья используются для организации хранения и обработки данных на жестком диске, илиином медленном носителе, операции с которым очень медленны и у которого гораздо лучшесчитывать данные последовательно, нежели произвольным образом (вообще-то говоря, этоотносится и к памяти, но там это выражено в меньшей мере и не так критично) и позволяюточень сильно улучшить работу в данном случае.Для организации данных сравнительно небольшого и (или) заранее известного размераприменяются более эффективные методики – множества и хэширование.Лекции по ЭВМ.
Конспект. Лектор В.Д. Валединский.Группа 208, 3 семестр, 2002 год151.4. МножестваМножеством будем считать некий объект, хранящий в себе данные, для которогоопределены операции1. Добавить элемент2. Удалить элемент3. Проверить принадлежность элемента множеству4. Пройти по множеству, выполняя одну и ту же операцию над его элементами(итератор по множеству)4.1. Обычно п.4 определяется в 2 ф-и: инициализировать итератор и получитьследующий элемент множестваОбычно при реализации множества при добавлении элемента в множество добавляетсяне сам элемент, а т.н.
«ключ» - некоторое число, по которому можно получить сам элемент.Например, ключом к данным в памяти может послужить указатель на участок памяти, гдеэти данные начинаются. Это позволяет ограничиться рассмотрением сравнительно простыхмножеств, например, множеств целых чисел. Заметим также, что деревья являются одним изчастных случаев множества (там определены добавление/удаление элемента, проверкапринадлежности – т.е. поиск в дереве, итератор по множеству – процедура обхода подерева). Но мы рассмотрим сейчас более простые и более быстрые реализации.Рассмотрим простейшие реализации множества. Пусть у нас есть множество из pэлементов.
Тогда сопоставим k-му элементу k-й бит некоторого большого числа. Если онравен 1 – элемент лежит в множестве, 0 – не лежит. Таким образом состояние множествабудет целиком описываться p-битным числом (битовое множество). К сожалению, вкомпьютере доступ памяти организуется не побитно, а побайтно или даже по элементамбольшего размера, поэтому для проверки принадлежности приходится вначале выделятьнужную ячейку памяти, а затем проверять в ней наличие того или иного бита.Битовое множество очень эффективно в плане распределения памяти – этопринципиально лучший способ записать произвольное подмножество некоторого множестваиз p элементов.
Однако если p велико и в подмножестве не так много элементов, тоэффективность битового множества резко снижается.Для быстрого поиска в множестве в этом случае вводят понятие хэш-функции. Хэш(hash) – функция, определяющая на множестве M отображение в множество из p элементов{0, … , p-1}.
Очевидно, что хэш-функция h разбивает множество M на классыэквивалентности, на которых хэш-функция дает одинаковые значения.Пусть мы работаем с множеством N M (число элементов в N меньше числаэлементов в M). При проверке x на принадлежность N вычисляем для x хэш-функцию.Затем мы уже можем выполнить проверку x на принадлежность тому классуэквивалентности, в который он попал – он уже меньше N, так что получаем сходящийсяпроцесс к множеству длины 1 (если элемент лежит в N) или 0 (если не лежит). Если хэшфункция «хорошая», то она распределяет классы эквивалентности примерно равномерно ипоиск происходит быстро. В худшем же случае поиск происходит прямым перебором всехэлементов множества и их сравнения с искомым.Методы хэширования могут быть самыми различными. Рассмотрим основныереализации. Простейшей является списочная реализация: запишем некоторую таблицухэширования (hash table) из p элементов.
Каждый элемент этой таблицы – список некоторыхэлементов множества, т.е. как раз k-е подмножество M. Возьмем теперь некоторую хэшфункцию f. Для добавления элемента x в множество – вычислим j = f(x) – хэш для x изапишем x в jй список. При поиске элемента x в множестве опять же вычисляем хэш от x иищем x уже только в этом списке.Другой широко распространенный метод (проверить, он ли описан в лекциях!) – методпроб и ошибок. Он применим только тогда, когда нам заранее известно, что числоразличных элементов в множестве не более N. Снова заводим таблицу хэширования из NЛекции по ЭВМ. Конспект. Лектор В.Д. Валединский.Группа 208, 3 семестр, 2002 год16элементов и берем хэш-функцию f в 0..N-1.
Теперь если надо добавить в множество элементx, то пробуем добавить его на место f(x). Если это место не занято (не занятость можноотслеживать, например, введя специальное число, обозначающее, что место свободно) –записываем в хэш-таблицу на это место x. Если занято – движемся по циклу вправо от f(x)(при достижении правой границы таблицы «перескакиваем» на ее начало), пока не найдемсвободный элемент.
На его место и запишем x. При поиске на наличие элемента вмножестве – встаем вначале на элемент с номером f(x) в хэш-таблице и начинаем двигаться(циклически, снова при достижении правой границы перееходя к левой) вправо, пока ненайдем x или пустой элемент. В первом случае – элемент принадлежит множеству, вовтором – нет. Данная реализация ощутимо быстрее списочной в силу того, что работатьприходится с линейным массивом, а не указателем на список – и операции происходят гдето в 2 раза быстрее.Кроме метода линейных проб и ошибок (описанного выше) используется такженелинейный метод проб и ошибок, когда при невозможности записать данные в iй элементпереходят не к (i+1)%N –му элементу, а к некоторому f(i), где f – некоторая нелинейнаяфункция.
Подобный метод обеспечивает лучшую равномерность распределения элементов вхэш-множестве.В результате же при хорошем подборе хэш-функции получим поиск в множестве всреднем за N/M операций, где N – число элементов в множестве, M – размер хэш-таблицы,т.е. за время O(1) при достаточно большом M и O(N) – в худшем случае, если хэш-функциявсе «покидала» в одну кучу.Примеров «хорошего» подбора можно привести множество.
Для целых чисел можноиспользовать функцию f(x) = x % m, можно – умножать x на какое-нибудь число, например, или e или 5 1 (последнее описано у Кнута) и брать n бит от результата; в строках –2брать первый символ, первые m символов строки, складывать буквы строки по модулюнекоторого; «вращающую» хэш-функцию (hash = (hash<<5)^(hash>>27)^key[i];) и другие.«Мутные теоремы» по К.Ю.Богачеву. В программе курса они, к счастью, неприсутствуют.
Лучше всего их пропустить (по крайней мере мне с ними разобраться неудалось ;-))Посмотрим, чем одни хэш-функции лучше других. «Обобщенной» хэш-функции на входподается последовательность битов – входные ключи V, ее задача – выдать другуюпоследовательность битов K (V и K имеют заранее определенную длину), распределив повозможности ее равномерно.Будем говорить, что бит i из V влияет на бит j из K, если для любых двухпоследовательностей a,b из V и отличающихся только в бите i бит j результатовхэширования h(a), h(b) различается с вероятностью ½ (и соответственно, свероятностью ½ совпадает).Будем говорить, что хэш-функция обладает свойством воронки (funnel), еслисуществует множество t номеров входных битов {i}, которые влияют только нанекоторое множество u битов {j}, причем t u и u k .Легко видеть, что если у нашей хэш-функции имеется воронка из t битов в u битов, тоu из этих t битов «заглушат» остальные t-u битов.
Действительно, согласно определениювлияния, если мы подадим на вход хэш-функции последовательности, различающиесятолько в этих t битах, то они из 2 t исходных элементов сделают не более 2 u элементовиз 2 v возможных – хэш-функция неэффективна.Теорема отсутствия воронки (Nofunnel):1.При фиксированном входном блоке комбинирующий шаг является взаимнооднозначным отображением внутреннего состояния на внутреннее состояние2.При заданном начальном внутреннем состоянии перемешивание являетсявзаимно-однозначным отображением, т.е. каждый новый входной блокприводит к новому внутреннему состояниюЛекции по ЭВМ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
