В математическом анализе и информатике функции , которые являются Z-порядком , кривой Лебега , кривой заполнения пространства Мортона , [1] порядком Мортона или кодом Мортона отображают многомерные данные в одно измерение , сохраняя локальность точек данных. Он назван во Франции в честь Анри Лебега , который изучал его в 1904 году, [2] и назван в Соединенных Штатах в честь Гая Макдональда Мортона, который впервые применил порядок к упорядочению файлов в 1966 году. [3] Значение z точки в многомерном пространстве просто вычисляется путем чередования двоичных представлений ее значений координат. После сортировки данных в этом порядке может использоваться любая одномерная структура данных, такая как простые одномерные массивы , двоичные деревья поиска , B-деревья , списки пропусков или (с усечением младших значащих битов) хэш-таблицы . Полученный порядок можно эквивалентно описать как порядок, который можно было бы получить при обходе в глубину квадродерева или октодерева .
На рисунке ниже показаны значения Z для двумерного случая с целочисленными координатами 0 ≤ x ≤ 7, 0 ≤ y ≤ 7 (показаны как в десятичном, так и в двоичном виде). Чередование двоичных значений координат (начиная справа с бита x (синего цвета) и чередуясь слева с битом y (красного цвета)) дает двоичные значения z (наклоненные на 45°, как показано). Соединение значений z в их числовом порядке дает рекурсивно Z-образную кривую. Двумерные значения Z также известны как значения quadkey.
Значения Z координат x описываются как двоичные числа из последовательности Мозера–де Брейна , имеющие ненулевые биты только на четных позициях:
x[] = {0b000000, 0b000001, 0b000100, 0b000101, 0b010000, 0b010001, 0b010100, 0b010101}Сумма и разность двух значений x вычисляются с помощью побитовых операций :
x[i+j] = ((x[i] | 0b10101010) + x[j]) & 0b01010101x[i−j] = ((x[i] & 0b01010101) − x[j]) & 0b01010101 если i ≥ j
Это свойство можно использовать для смещения значения Z, например, в двух измерениях координаты вверх (уменьшение y), вниз (увеличение y), влево (уменьшение x) и вправо (увеличение x) от текущего значения Z z следующие :
верх = (((z & 0b10101010) − 1) & 0b10101010) | (з и 0b01010101)низ = (((z | 0b01010101) + 1) & 0b10101010) | (z & 0b01010101)слева = (((z & 0b01010101) − 1) & 0b01010101) | (z & 0b10101010)вправо = (((z | 0b10101010) + 1) & 0b01010101) | (з и 0b10101010)
И вообще, чтобы сложить два двумерных Z-значения w и z :
сумма = ((z | 0b10101010) + (w & 0b01010101) & 0b01010101) | ((z | 0b01010101) + (w & 0b10101010) & 0b10101010)
Z-упорядочение может быть использовано для эффективного построения квадродерева (2D) или октодерева (3D) для набора точек. [4] [5] Основная идея заключается в сортировке входного набора в соответствии с Z-порядком. После сортировки точки могут быть либо сохранены в бинарном дереве поиска и использованы напрямую, что называется линейным квадродеревом, [6] либо они могут быть использованы для построения квадродерева на основе указателя.
Входные точки обычно масштабируются в каждом измерении, чтобы быть положительными целыми числами, либо как представление с фиксированной точкой в единичном диапазоне [0, 1], либо соответствующее размеру машинного слова. Оба представления эквивалентны и позволяют найти ненулевой бит наивысшего порядка за постоянное время. Каждый квадрат в квадродереве имеет длину стороны, которая является степенью двойки, и угловые координаты, которые кратны длине стороны. При наличии любых двух точек производный квадрат для двух точек является наименьшим квадратом, покрывающим обе точки. Чередование битов из компонентов x и y каждой точки называется перетасовкой x и y и может быть расширено до более высоких измерений. [4]
Точки можно сортировать в соответствии с их перетасовкой без явного чередования битов. Для этого для каждого измерения проверяется самый значимый бит исключающего или координат двух точек для этого измерения. Измерение, для которого самый значимый бит является наибольшим, затем используется для сравнения двух точек с целью определения порядка их перетасовки.
Операция «исключающее или» маскирует биты более высокого порядка, для которых две координаты идентичны. Поскольку перетасовка чередует биты от более высокого порядка к более низкому, идентификация координаты с самым большим наиболее значимым битом идентифицирует первый бит в порядке перетасовки, который отличается, и эту координату можно использовать для сравнения двух точек. [7] Это показано в следующем коде Python:
def cmp_zorder ( lhs , rhs ) -> bool : """Сравнить z-упорядочение.""" # Предположим, что lhs и rhs — это объекты индексов, подобные массивам. assert len ( lhs ) == len ( rhs ) # Будет содержать наиболее значимое измерение. msd = 0 # Цикл по остальным измерениям. for dim in range ( 1 , len ( lhs )): # Проверяем, является ли текущее измерение более значимым , # сравнивая наиболее значимые биты. if less_msb ( lhs [ msd ] ^ rhs [ msd ], lhs [ dim ] ^ rhs [ dim ]): msd = dim return lhs [ msd ] < rhs [ msd ] Один из способов определить, меньше ли самый значимый бит, — сравнить пол логарифма по основанию 2 каждой точки. Оказывается, следующая операция эквивалентна и требует только операций исключающего или: [7]
def less_msb ( x : int , y : int ) -> bool : возвращает x < y и x < ( x ^ y )Также возможно сравнивать числа с плавающей точкой, используя ту же технику. Функция less_msbмодифицирована, чтобы сначала сравнить показатели. Только когда они равны, стандартная less_msbфункция используется для мантисс. [8]
После того, как точки отсортированы, два свойства упрощают построение квадродерева: первое заключается в том, что точки, содержащиеся в квадрате квадродерева, образуют непрерывный интервал в отсортированном порядке. Второе заключается в том, что если более одного дочернего элемента квадрата содержат входную точку, квадрат является производным квадратом для двух соседних точек в отсортированном порядке.
Для каждой смежной пары точек вычисляется производный квадрат и определяется длина его стороны. Для каждого производного квадрата интервал, содержащий его, ограничивается первым большим квадратом справа и слева в отсортированном порядке. [4] Каждый такой интервал соответствует квадрату в квадродереве. Результатом этого является сжатое квадродерево, в котором присутствуют только узлы, содержащие входные точки или два или более потомков. Несжатое квадродерево может быть построено путем восстановления отсутствующих узлов, если это необходимо.
Вместо того, чтобы строить квадродерево на основе указателей, точки можно поддерживать в отсортированном порядке в структуре данных, такой как двоичное дерево поиска. Это позволяет добавлять и удалять точки за время O (log n ) . Два квадродерева можно объединить, объединив два отсортированных набора точек и удалив дубликаты. Местоположение точки можно определить, выполнив поиск точек, предшествующих и следующих за точкой запроса в отсортированном порядке. Если квадродерево сжато, найденный узел-предшественник может быть произвольным листом внутри интересующего сжатого узла. В этом случае необходимо найти предшественника наименее общего предка точки запроса и найденного листа. [9]
С помощью чередования бит записи базы данных преобразуются в (возможно, очень длинную) последовательность битов. Последовательности битов интерпретируются как двоичные числа, а данные сортируются или индексируются по двоичным значениям с использованием любой одномерной структуры данных, как упоминалось во введении. Однако при запросе многомерного диапазона поиска в этих данных использование двоичного поиска не очень эффективно. Хотя Z-порядок хорошо сохраняет локальность, для эффективного поиска по диапазону необходим алгоритм для вычисления из точки, обнаруженной в структуре данных, следующего возможного значения Z, которое находится в многомерном диапазоне поиска:
В этом примере запрашиваемый диапазон ( x = 2, ..., 3, y = 2, ..., 6) обозначен пунктирным прямоугольником. Его наибольшее значение Z (MAX) равно 45. В этом примере значение F = 19 встречается при поиске структуры данных в направлении возрастания значения Z, поэтому нам придется искать в интервале между F и MAX (заштрихованная область). Чтобы ускорить поиск, можно вычислить следующее значение Z, которое находится в диапазоне поиска, называемом BIGMIN (36 в примере), и искать только в интервале между BIGMIN и MAX (жирные значения), таким образом пропуская большую часть заштрихованной области. Поиск в направлении убывания аналогичен LITMAX, которое является наибольшим значением Z в диапазоне запроса ниже F. Проблема BIGMIN впервые была сформулирована и ее решение показано в работе Тропфа и Герцога. [10]
Подробное объяснение алгоритма расчета LITMAX/BIGMIN вместе с исходным кодом Pascal (3D, легко адаптируется к nD) и подсказками о том, как обрабатывать данные с плавающей точкой и, возможно, отрицательные данные, предоставлено в 2021 году Tropf: Здесь чередование битов не выполняется явно; структура данных имеет только указатели на исходные (несортированные) записи базы данных. С общей функцией сравнения записей (больше-меньше-равно, в смысле z-значения) избегаются осложнения с длиной битовых последовательностей, превышающей длину компьютерного слова, и код можно легко адаптировать к любому количеству измерений и любой длине ключевого слова записи.
Поскольку подход не зависит от выбранной одномерной структуры данных, по-прежнему существует свобода выбора структурирования данных, поэтому для работы с динамическими данными можно использовать такие известные методы, как сбалансированные деревья, а поддержание баланса дерева при вставке или удалении занимает O(log n) времени. Этот метод также используется в UB-деревьях (сбалансированных), [11] .
Свободный выбор упрощает включение метода в существующие базы данных. Это отличается, например, от R-деревьев , где необходимы специальные соображения.
Применение метода иерархически (в соответствии со структурой данных), опционально как в направлении увеличения, так и в направлении убывания, дает высокоэффективный многомерный поиск по диапазону, который важен как в коммерческих, так и в технических приложениях, например, как процедура, лежащая в основе поиска ближайшего соседа. Z-порядок — один из немногих многомерных методов доступа, который нашел свое применение в коммерческих системах баз данных. [12] Метод используется в различных технических приложениях разных областей [13] и в коммерческих системах баз данных. [14]
Еще в 1966 году GM Morton предложил Z-порядок для упорядочивания файлов статической двухмерной географической базы данных. Ареальные единицы данных содержатся в одном или нескольких квадратичных кадрах, представленных их размерами и Z-значениями нижнего правого угла, размеры соответствуют иерархии Z-порядка в угловой позиции. С высокой вероятностью переход к соседнему кадру осуществляется одним или несколькими относительно небольшими шагами сканирования. [3]
В качестве альтернативы была предложена кривая Гильберта , поскольку она лучше сохраняет порядок [5] и, по сути, использовалась в оптимизированном индексе, S2-геометрии [15] .
Алгоритм Штрассена для умножения матриц основан на разбиении матриц на четыре блока, а затем рекурсивном разбиении каждого из этих блоков на четыре меньших блока, пока блоки не станут отдельными элементами (или, что более практично: пока матрицы не станут настолько маленькими, что тривиальный алгоритм последовательности Мозера–де Брейна будет быстрее). Расположение элементов матрицы в Z-порядке затем улучшает локальность и имеет дополнительное преимущество (по сравнению с упорядочением по строкам или столбцам), что подпрограмме для умножения двух блоков не нужно знать общий размер матрицы, а только размер блоков и их расположение в памяти. Было продемонстрировано эффективное использование умножения Штрассена с Z-порядком, см. статью Валсалама и Скьеллума 2002 года. [16]
Булуч и др. представляют разреженную матричную структуру данных, которая Z-упорядочивает свои ненулевые элементы, чтобы обеспечить параллельное умножение матрицы на вектор. [17]
Матрицы в линейной алгебре также можно обходить с помощью заполняющей пространство кривой. [18] Обычные циклы обходят матрицу строка за строкой. Обход с помощью Z-кривой обеспечивает эффективный доступ к иерархии памяти . [19]
Некоторые графические процессоры хранят текстурные карты в Z-порядке для увеличения пространственной локальности ссылок во время растеризации с текстурным отображением . Это позволяет строкам кэша представлять прямоугольные плитки, увеличивая вероятность того, что близлежащие обращения находятся в кэше. В большем масштабе это также снижает вероятность дорогостоящих, так называемых, «разрывов страниц» (т. е. стоимость изменения строк ) в SDRAM/DDRAM. Это важно, поскольку 3D-рендеринг включает в себя произвольные преобразования (повороты, масштабирование, перспективу и искажение анимированными поверхностями).
Эти форматы часто называют swizzled textures или twiddle textures . Могут также использоваться другие форматы плиток.
Алгоритм Барнса-Хата требует построения октодерева. Хранение данных в виде дерева на основе указателей требует множества последовательных разыменований указателей для итерации по октодереву в порядке глубины (дорого на машине с распределенной памятью). Вместо этого, если сохранить данные в хэш-таблице , используя хэширование октодерева, кривая Z-порядка естественным образом итерирует октодерево в порядке глубины. [5]