Введение
Функция отображения, сохраняющая локальность точек данных.
В математическом анализе и информатике функции, известные как Z-порядок, кривая Лебега, кривая заполнения пространства Мортона, порядок Мортона или код Мортона, отображают многомерные данные в одно измерение, сохраняя при этом локальность точек данных. Во Франции она названа в честь Анри Лебега, который изучал её в 1904 году, а в Соединенных Штатах – в честь Гая Макдональда Мортона, который впервые применил этот порядок к последовательной организации файлов в 1966 году. Z-значение точки в многомерном пространстве вычисляется простым чередованием бинарных представлений её координатных значений. После сортировки данных в таком порядке можно использовать любую одномерную структуру данных, например, простые одномерные массивы, двоичные деревья поиска, B-деревья, списки пропусков или (с усечением младших значащих битов) хеш-таблицы. Полученный порядок эквивалентен порядку, который получается при обходе квадродерева или октадерева в глубину.
Использование с одномерными структурами данных для поиска диапазона
При битовом переплетении записи базы данных преобразуются в (возможно, очень длинную) последовательность битов. Битовые последовательности интерпретируются как двоичные числа, а данные сортируются или индексируются по двоичным значениям, используя любую одномерную структуру данных, как упоминалось во введении. Однако при запросе многомерного диапазона поиска в этих данных использование бинарного поиска не является эффективным. Хотя 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 была впервые сформулирована и ее решение представлено в работе Tropf и Herzog. Подробное описание алгоритма вычисления LITMAX/BIGMIN, вместе с исходным кодом на Pascal (3D, легко адаптируемым к nD) и рекомендациями по обработке данных с плавающей запятой и, возможно, отрицательных данных, приведено в 2021 году Tropf. Здесь битовое переплетение не выполняется явно; структура данных содержит только указатели на исходные (несортированные) записи базы данных. При использовании общей функции сравнения записей (больше, меньше или равно, в смысле Z-значения) избегаются сложности, связанные с длиной битовых последовательностей, превышающей длину машинного слова, и код может быть легко адаптирован к любому количеству измерений и любой длине ключевого слова записи. Поскольку подход не зависит от выбранной одномерной структуры данных, сохраняется свобода выбора способа структурирования данных, поэтому для работы с динамическими данными можно использовать известные методы, такие как сбалансированные деревья, а поддержание баланса дерева при вставке или удалении занимает O(log n) времени. Метод также используется в UB-деревьях (сбалансированных) под названием "GetNextZ address" для BIGMIN. Свобода выбора упрощает внедрение метода в существующие базы данных. Это отличается, например, от R-деревьев, где требуются специальные соображения. Применение метода иерархически (в соответствии со структурой данных), опционально в направлениях возрастания и убывания, обеспечивает высокоэффективный многомерный поиск диапазона, что важно как в коммерческих, так и в технических приложениях, например, в качестве процедуры, лежащей в основе поиска ближайших соседей. Z-порядок – один из немногих многомерных методов доступа, который нашел применение в коммерческих системах баз данных. Метод используется в различных технических приложениях в разных областях и в коммерческих системах баз данных. Еще в 1966 году Г. М. Мортон предложил Z-порядок для последовательного размещения файлов статической двухмерной географической базы данных. Ареальные данные содержатся в одной или нескольких квадратных рамках, представленных их размерами и Z-значениями в правом нижнем углу, при этом размеры соответствуют иерархии Z-порядка в положении угла. С высокой вероятностью переход к соседней рамке осуществляется с помощью одного или нескольких относительно небольших шагов сканирования.
In this example, the range being queried (x = 2, , 3, y = 2, , 6) is indicated by the dotted rectangle. Its highest Z value (MAX) is 45. In this example, the value F = 19 is encountered when searching a data structure in increasing Z value direction, so we would have to search in the interval between F and MAX (hatched area). To speed up the search, one would calculate the next Z value which is in the search range, called BIGMIN (36 in the example) and only search in the interval between BIGMIN and MAX (bold values), thus skipping most of the hatched area. Searching in decreasing direction is analogous with LITMAX which is the highest Z value in the query range lower than F. The BIGMIN problem has first been stated and its solution shown in Tropf and Herzog. An extensive explanation of the LITMAX/BIGMIN calculation algorithm, together with Pascal Source Code (3D, easy to adapt to nD) and hints on how to handle floating point data and possibly negative data, is provided 2021 by Tropf: Here, bit interleaving is not done explicitly; the data structure has just pointers to the original (unsorted) database records. With a general record comparison function (greater less equal, in the sense of z value), complications with bit sequences length exceeding the computer word length are avoided, and the code can easily be adapted to any number of dimensions and any record key word length. As the approach does not depend on the one dimensional data structure chosen, there is still free choice of structuring the data, so well known methods such as balanced trees can be used to cope with dynamic data, and keeping the tree balance when inserting or deleting takes O(log n) time. The method is also used in UB trees (balanced), with the name "GetNextZ address" for BIGMIN. The Free choice makes it easier to incorporate the method into existing databases. This is in contrast for example to R trees where special considerations are necessary. Applying the method hierarchically (according to the data structure at hand), optionally in both increasing and decreasing direction, yields highly efficient multidimensional range search which is important in both commercial and technical applications, e. g. as a procedure underlying nearest neighbour searches. Z order is one of the few multidimensional access methods that has found its way into commercial database systems. The method is used in various technical applications of different fields and in commercial database systems. As long ago as 1966, G. M. Morton proposed Z order for file sequencing of a static two dimensional geographical database. Areal data units are contained in one or a few quadratic frames represented by their sizes and lower right corner Z values, the sizes complying with the Z order hierarchy at the corner position. With high probability, changing to an adjacent frame is done with one or a few relatively small scanning steps.
Линейная алгебра
Алгоритм Страссена для умножения матриц основан на разделении матриц на четыре блока, а затем рекурсивном разделении каждого из этих блоков на четыре меньших блока, пока блоки не превратятся в отдельные элементы (или, более практично, пока не будут достигнуты матрицы настолько малого размера, что тривиальный алгоритм последовательности Мозера — де Брюйна станет быстрее). Расположение элементов матрицы в Z-порядке повышает локальность и имеет дополнительное преимущество (по сравнению с порядком строк или столбцов) в том, что подпрограмме для умножения двух блоков не требуется знать общий размер матрицы, а только размер блоков и их положение в памяти. Эффективность использования умножения Страссена с Z-порядком была продемонстрирована, см. работу Вальсалама и Скьеллума 2002 года. Булуч и др. представили структуру данных для разреженных матриц, в которой ненулевые элементы упорядочены в Z-порядке для обеспечения параллельного умножения матрицы на вектор. Матрицы в линейной алгебре также можно перебирать с помощью кривой, заполняющей пространство. Традиционные циклы перебирают матрицу построчно. Перебор с использованием Z-кривой обеспечивает эффективный доступ к иерархии памяти.
with Z order has been demonstrated, see Valsalam and Skjellum's 2002 paper. Buluç et al. present a sparse matrix data structure that Z orders its non zero elements to enable parallel matrix vector multiplication. Matrices in linear algebra can also be traversed using a space filling curve. Conventional loops traverse a matrix row by row. Traversing with the Z curve allows efficient access to the memory hierarchy.
Картировка текстуры
Некоторые графические процессоры хранят карты текстур в Z-порядке для повышения пространственной локальности при растрировании с наложением текстур. Это позволяет кеш-линиям представлять прямоугольные блоки, увеличивая вероятность того, что соседние обращения будут находиться в кеше. В большем масштабе это также снижает вероятность дорогостоящих так называемых "разрывов страниц" (то есть затраты на смену строк) в SDRAM/DDRAM. Это важно, поскольку 3D-рендеринг включает произвольные преобразования (вращения, масштабирование, перспективные искажения и деформации анимированными поверхностями). Такие форматы часто называют текстурами с перестановкой или текстурами с чередованием. Также могут использоваться другие форматы с разбиением на блоки.
Проблема n-тела
Алгоритм Барнса-Хата требует построения октадрава. Хранение данных в виде дерева, основанного на указателях, требует множества последовательных обращений по указателям для обхода октадрава в порядке глубины (что неэффективно на машине с распределенной памятью). Вместо этого, если хранить данные в хеш-таблице, используя хеширование октадрава, Z-кривая естественным образом обходит октадрав в порядке глубины.