Claw.ru | Рефераты по информатике, программированию | Создание эффективной реализации сортированного списка с использованием generics Создание эффективной реализации сортированного списка с использованием generics | Категория реферата: Рефераты по информатике, программированию | Теги реферата: реферат мова, изложение язык | Добавил(а) на сайт: Bajdavletov. Предыдущая страница реферата | 7  8  9  10  11  12  13  14  15  16  17 | Следующая страница реферата ...       // Если массив верхнего уровня полностью заполнен просто увеличиваем       // его емкость в 2 раза (в Б+деревьях в этом случае выстраивается       // новый уровень).       if (_pageCount == NodeArray.Length)       {         NodeItem[] NewNodeArray = new NodeItem[2 * _pageCount];         Array.Copy(NodeArray, 0, NewNodeArray, 0, _pageCount);         NodeArray = NewNodeArray;         }       }     }   }

Процедуру удаления элемента из двухуровневого массива я здесь приводить не буду. Ее код можно найти в файле, приложенном к статье. Больший интерес представляет функция поиска индекса в двухуровневом массиве.

Существуют ситуации, когда нужно найти значение, ассоциированное с ключом, и если его нет, то вставить некоторое значение, ассоциированное с этим ключом. Если для решения этой задачи воспользоваться отдельными процедурами поиска и вставки, то общее время удвоится, так как процедура вставки (перед непосредственной вставкой значения) производит поиск места вставки, т.е. имеет место повторное (непродуктивное) выполнение по сути одной и той же операции (поиска). В принципе, если при поиске запоминать найденную позицию, то процедура вставки могла бы воспользоваться результатами функции поиска (при условии, что между поиском и вставкой не было никаких действий). Однако это привело бы к тому, что пользователя класса пришлось допустить в дебри реализации данной коллекции, и надежность работы алгоритмов, построенных по такому принципу, была бы крайне низка. С целью оптимизации я решил создать метод, который пытался бы найти ключ и, если не нашел, вставлял бы некоторое значение «по умолчанию» и позиционировался на него (а если нашел, то просто позиционировался). Это позволяет избавиться от лишней операции поиска в описанных выше случаях, так как после этой операции пользователь получает возможность работать с текущим значением (значением, на которое произошло позиционирование). При этом для чтения или модификации значения не требуется производить повторный поиск. Функцию, производящую позиционирование (или вставку и позиционирование), я решил назвать NavigateOrInsertDefault. Вот ее код: