Russian Language English Language

6.Информационные системы

6.1 ИСПОЛЬЗОВАНИЕ СХЕМЫ ТУРНИРА С ВЫБЫВАНИЕМ ПРИ СЛИЯНИИ УПОРЯДОЧЕННЫХ ЧАСТЕЙ МАССИВА

6.2 РЕАЛИЗАЦИЯ ПРЕЦЕДЕНТНОГО МОДУЛЯ С ИСПОЛЬЗОВАНИЕМ МЕХАНИЗМА СТРУКТУРНОГО ОТОБРАЖЕНИЯ

6.3 ВЕБ-СЕРВИС ДЛЯ ОРГАНИЗАЦИИ ВЫЧИСЛЕНИЙ

6.4 МЕТОДИКА ОПРЕДЕЛЕНИЯ НОВОСТНЫХ ЗАПРОСОВ К ПОИСКОВОЙ СИСТЕМЕ

6.5 ОБ ОДНОМ ПОДХОДЕ К РЕШЕНИЮ ЗАДАЧИ ПОИСКА ОПТИМАЛЬНЫХ МАРШРУТОВ НА ТРАНСПОРТНЫХ СХЕМАХ


Экспресс информация

Редколлегия журнала

Подписка на новости

Гостевая книга

Предоставление материалов

Письмо в редакцию

На начало


2015, Номер 1 ( 26)



Place for sale
BC/NW 2015 № 1 (26) 6:1

BC/NW 2015  1 (26) 6:1

ИСПОЛЬЗОВАНИЕ СХЕМЫ ТУРНИРА С ВЫБЫВАНИЕМ ПРИ СЛИЯНИИ УПОРЯДОЧЕННЫХ ЧАСТЕЙ МАССИВА

 

Белякова Е.М., Зубов В.С.

 

Схема турнира явилась прообразом широко используемой пирамидальной сортировки [1], предлагаем применять ее также для рациональной организации слияния t частей массива (t-арное слияние). Здесь главной проблемой является минимизация числа M сравнений при выборе каждой записи в результат слияния, теоретический минимум ≈ log 2 t, а всего за слияние ≈ n log 2 t, где n – общее число записей (ключей), участвующих в слиянии.

Пусть части массива упорядочены по возрастанию ключей. В схему выбора, являющуюся бинарным деревом, сначала загружаются t ссылок на первые записи частей. Это листья дерева. В результате сравнений по принципу турнира с выбыванием в корень дерева поднимается ссылка на минимальную запись, передаваемую в результат. Эта ссылка увеличивается на 1, что означает переход к следующей записи той части, из которой извлекли минимальную запись. «Турнир» повторяется, в корень поднимается ссылка на вторую по величине запись и т.д.

Если выбранная запись последняя в своей части, ссылка на нее в дереве заменяется ссылкой на , тем самым блокируется выбор в опустевшей части. После рассмотрения всех n записей все узлы дерева станут ссылками на . Примечательно, что даже в случае исчерпания всех частей, кроме одной, выбор записи по-прежнему требует прохождения трассы от листа до корня дерева. При больших частях это не приводит к заметным издержкам времени, зато упрощает алгоритм и оценку среднего числа M сравнений.

Значение M, очевидно, равно log 2 t при t = 2k . При других k схема турнира отличается от «классической». Дерево ссылок размещается в памяти наподобие дерева в пирамидальной сортировке и является полным деревом [2]. Для него значение M может быть найдено по методике получения длины внешнего пути, изложенной в [2].

Применение схемы турнира в t-арном слиянии минимизирует общее число сравнений и выдвигает метод t-арного слияния в лидеры при сортировке больших массивов данных.

Литература

1. Кнут Д.Э. Искусство программирования. Т. 3. Сортировка и поиск: пер. сангл. – 2-е изд. М.: Издательский дом «Вильямс», 2000.

2. Кнут Д.Э. Искусство программирования. Т. 1. Основные алгоритмы: пер. с англ. – 3-е изд. М.: Издательский дом «Вильямс», 2001.