Конспект: префиксные суммы, слияние, сортирующие сети

Понятия

Скан (префиксная сумма) ассоциативной операции: включающий y[i] = x[0] ⊕ … ⊕ x[i], исключающий - без x[i]. Ассоциативность - единственное требование: дерево переставляет скобки.

Упаковка - оставить элементы по условию; устойчивое разбиение - нули вперёд, единицы назад, порядок внутри групп сохранён. Ранг элемента в массиве - сколько там элементов меньше него.

Сортирующая сеть - фиксированные слои компараторов; глубина - число слоёв. Принцип нулей и единиц - сеть, сортирующая все 2ⁿ 0-1 входов, сортирует всё.

Что унести

ДВА СКАНА                 шагов           работа
Хиллис - Стил             ⌈log₂ n⌉        n · log₂ n − (n − 1)
Блеллох (подъём+спуск)    2 log₂ n        2(n − 1)
1024 числа: ХС - 10 шагов, 9217 сложений; Блеллох - 20 и 2046
Блеллох даёт исключающий скан; включающий = + x[i]
шаг читает старые значения: новый массив или ход справа налево

ЧТО СТРОЯТ ИЗ СКАНА
упаковка:      адрес = исключающий скан флагов, размер = сумма
разбиение:     нули - скан (1 − bit), единицы - нулей + скан bit
поразрядная:   разбиение по битам от младшего; каждое устойчиво
ранг в списке: rang += rang[sled]; sled = sled[sled]
               ⌈log₂ n⌉ раундов, работа n log n; 1000 эл. - 10

СЛИЯНИЕ И СОРТИРОВКА
место A[i] = i + (в B строго меньших)
место B[j] = j + (в A меньших или равных)  - равные не сталкиваются
рангами: глубина log n, работа n log n
сортировка слиянием рангами: глубина ~log² n / 2, работа ~n log² n / 2
    65 536: параллелизм 65 536, но работы в 8,5 раза больше
работоэффективно: p кусков, двоичный поиск только границ
выборка: s · p образцов, границы - образцы номер s, 2s, …
    4000 чисел, 8 корзин: s = 1 - перекос 3,65; s = 64 - 1,13

СОРТИРУЮЩИЕ СЕТИ
битонная (Бэтчер, 1968):
    глубина log₂ n (log₂ n + 1) / 2
    компараторов n/4 · log₂ n (log₂ n + 1)
    8 входов: 6 слоёв, 24 компаратора; 16: 10 и 80
    слияние блока k: зеркальный слой i ↔ k − 1 − i, потом k/4, …, 1
чёт-нечет перестановки: n слоёв, n(n − 1)/2 компараторов
    7 слоёв на 8 входах: 3 плохих входа из 256, ловят 8% случайных
минимум для 8 входов: 19 компараторов (чётно-нечётное слияние)
AKS (1983): глубина O(log n), константы - тысячи
n не степень двойки: достроить до N, лишние провода - +∞,
    компараторы с ними выбросить

Ловушки джокера

Сложение на месте. Шаг Хиллиса - Стила, пишущий в тот же массив слева направо, читает уже обновлённые ячейки.

Неассоциативная операция. Вычитание и «среднее двух» сканом не считаются; сложение float ассоциативно лишь приближённо - ответ чуть отличается от цикла.

Включающий вместо исключающего. Адреса при упаковке сдвигаются на единицу.

Общий счётчик вместо скана. Адреса раздаются в порядке прихода: упаковка теряет устойчивость, а поразрядная сортировка - правильность.

Одинаковое правило для равных при слиянии. Две записи в одну ячейку или пустая ячейка.

Слияние рангами на малом числе ядер. Логарифмическая глубина не окупает n log n работы на уровне.

Границы выборки без запаса. Одна корзина втрое больше остальных.

Проверка сети случайными тестами. Это выборка, а не доказательство; полный перебор 0-1 входов при n ≤ 20 - секунды.

Слой с общим проводом. Два компаратора на одном проводе - два слоя, а не один.

Ранжирование списка: удвоение указателей даёт O(n log n) работы; случайное независимое множество удаляет в среднем четверть внутренних вершин. Рекурсивное сжатие даёт ожидаемую линейную работу, не детерминированный худший случай.

Понятия

Что унести

Ловушки джокера

Комментарии

Оставить комментарий