Есть ли структура данных с этими характеристиками?

Question

Я ищу структуру данных, которая позволила бы мне хранить в памяти двумерную матрицу значений M -by- N непрерывно в памяти, чтобы расстояние в памяти между любыми двумя точками приближалось к евклидову расстоянию междуэти точки в матрице.То есть в типичном основном представлении строки в виде одномерного массива M * N элементов расстояние в памяти отличается между соседними ячейками в одной строке (1) и соседними ячейками в соседних строках (N).

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

У меня есть приложение, которое должно выполнять быстрые свертки изображений без оборудованияускорение, и хотя мне известны обычные методы оптимизации для такого рода вещей, я чувствую, что специализированная структура данных или упорядочение данных могут повысить производительность.

Answer 1

Учитывая требование, что вы хотите хранить значения непрерывно в памяти, я настоятельно рекомендую вам исследовать кривые заполнения пространства , особенно Кривые Гильберта .

Чтобы дать немного контекста, такие кривые иногда используются в индексах базы данных, чтобы улучшить локальность запросов многомерного диапазона (например, «найти все элементы с координатами x / y в этом прямоугольнике»), таким образом, стремясь уменьшить количество различныхстраницы доступны.Немного похоже на R-деревья, которые уже были предложены здесь.

В любом случае, похоже, что вы связаны с массивом значений M * N в памяти, поэтому весь вопрос в том, какрасположите значения в этом массиве, я полагаю.(Если я неправильно понял вопрос.)

Таким образом, на самом деле, такие упорядочения, вероятно, все еще изменят только характеристики распределения расстояний. Среднее расстояние для любых двух случайно выбранных точек из матрицы не должно измениться, поэтому я имеюдоговориться с Оли там.Я полагаю, что потенциальная выгода во многом зависит от вашего конкретного случая использования.

Answer 2

Я бы предположил "нет"!И если ответ окажется «да», то это почти наверняка настолько нерегулярно, что это будет намного медленнее для операции типа свертки.

РЕДАКТИРОВАТЬ

Чтобы уточнить мое предположение, возьмите пример.Допустим, сначала мы храним a[0][0].Мы хотим, чтобы a[k][0] и a[0][k] были одинаковыми расстояниями и пропорциональны k, поэтому мы можем выбрать чередование хранения первой строки и первого столбца (т. Е. a[0][0], a[1][0], a[0][1], a[2][0], a[0][2] и т. Д.). Но как нам теперь поступить?то же самое, например, для a[1][0]?Все места рядом с ним в памяти теперь заняты вещами, которые близки к a[0][0].

Хотя есть и другие возможности, кроме моего примера, я бы держал пари, что вы всегда сталкиваетесь с такой проблемой.

РЕДАКТИРОВАТЬ

Если ваши данные немногочисленны, то может быть возможность сделать что-то умное (по предложению Кубби о R-деревьях).Тем не менее, это все равно потребует нерегулярного доступа и отслеживания указателя, поэтому будет значительно медленнее, чем простая свертка для любого заданного числа точек.

Answer 3

Вы можете посмотреть на кривые заполнения пространства, в частности на кривую Z-порядка, которая (в основном) сохраняет пространственную локальность. Однако поиск индексов может оказаться дорогостоящим в вычислительном отношении.

Если вы используете это, чтобы попытаться улучшить производительность кеша, вы можете попробовать метод, называемый «bricking», который немного похож на один или два уровня кривой заполнения пространства. По сути, вы подразделяете свою матрицу на плитки nxn (где nxn аккуратно помещается в кэш L1). Вы также можете хранить листы другого уровня, чтобы они помещались в кеш более высокого уровня. Преимущество, которое это имеет перед кривой заполнения пространства, состоит в том, что индексы можно довольно быстро вычислить. Одна ссылка включена в статью здесь: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.30.8959

Answer 4

Невозможно «линеаризовать» 2D-структуру в 1D-структуру и сохранить неизменным соотношение близости в обоих направлениях. Это одно из фундаментальных топологических свойств мира.

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

Кривая Z-порядка популярна для этого приложения: http://en.wikipedia.org/wiki/Z-order_(curve)

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

Answer 5

Это звучит как нечто, чему может помочь R-дерево. или один из его вариантов. Ничего подобного в стандартной библиотеке C ++ нет, но похоже, что в библиотеке кандидатов в бусты есть R-дерево Boost.Geometry (пока не является частью буста). Я бы посмотрел на это, прежде чем писать свой собственный.

Answer 6

Ответ - нет. Подумайте об этом - память 1D. Ваша матрица 2D. Вы хотите раздавить это дополнительное измерение - без потерь? Этого не произойдет.

Что более важно, так это то, что как только вы отойдете на определенное расстояние, загрузка в кеш займет то же самое время. Если у вас отсутствует кэш, не имеет значения, будет ли он 100 или 100000. По сути, вы не можете получить более непрерывную / лучшую производительность, чем простой массив, если вы не хотите получить LRU для вашего массива.

Answer 7

Вы можете думать о своей 2D матрице как о большой спирали, начинающейся в центре и прогрессирующей наружу. Размотайте спираль и сохраните данные в указанном порядке, а расстояние между адресами не менее неопределенно приблизительно соответствует евклидову расстоянию между точками, которые они представляют. Хотя это будет не совсем точно, я уверен, что и вы не сможете добиться большего. В то же время, я думаю, что даже в лучшем случае это будет минимально помочь вашему свёрточному коду.

Answer 8

Это не совсем связано с близостью, но может помочь.Это, безусловно, помогает для минимизации доступа к диску.

Один из способов улучшить "закрытость" - это мозаичное изображение.Если ваше ядро ​​свертки меньше размера плитки, вы обычно касаетесь максимум 4 плиток в худшем случае.Вы можете рекурсивно разбивать тайлы на большие секции, чтобы улучшить локализацию.Подобный Стоксу (по крайней мере, я думаю, его аргумент Стокса) (или некоторое вариационное исчисление) может показать, что для прямоугольников наилучшая (то есть для проверки произвольных под прямоугольников) форма - это меньший прямоугольник с тем же соотношением сторон.

Быстрая интуиция - подумайте о квадрате - если вы разбиваете квадрат большего размера на квадраты меньшего размера, тот факт, что квадрат охватывает максимальную площадь для данного периметра, означает, что квадратные плитки имеют минимальную длину границы.Когда вы трансформируете большой квадрат, я думаю, вы можете показать, что вы должны трансформировать плитку таким же образом.(может также быть в состоянии сделать простую многомерную дифференциацию)

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

Это также действительно того стоит для различных схем сжатия, таких как косинусные преобразования.(Вот почему, когда вы загружаете изображение, оно часто появляется так же, как и в меньших и меньших квадратах, пока не будет достигнуто окончательное разрешение.

В этой области много книг, и они полезны.

Answer 9

Вам нужно преобразовать адреса из пространства памяти в исходное пространство массива, чтобы выполнить это.Кроме того, вы указали только расстояние, которое может вызвать некоторые проблемы (без направления)

Если у меня есть массив R x C и две ячейки в местоположениях [r, c] и [c,r], расстояние от некоторой произвольной точки, скажем, [0,0], идентично.И вы никак не сможете заставить один адрес памяти содержать две вещи, если только у вас нет одной из этих модных новых машин с кубитами.

Однако вы можете принять во внимание, что в главном массиве подрядR x C, что каждая строка имеет размер C * sizeof (yourdata) в байтах.И наоборот, вы можете сказать, что исходные координаты любого адреса памяти в пределах массива:

r = (адрес / C) c = (адрес% C)

, поэтому

r1 = (адрес1 / C)

r2 = (адрес2 / C)

c1 = (адрес1% C)

c2 = (адрес2% C)

dx = r1 - r2

dy = c1 - c2

dist = sqrt (dx ^ 2 + dy ^ 2)

(предполагается, что вывы используете массивы, основанные на нуле) (сократите все это вместе, чтобы сделать его более оптимальным)

Для гораздо большего количества идей здесь, посмотрите на любой код манипуляции 2D-изображения, который использует вычисленное значение, называемое "шаг",что в основном указывает на то, что они перемещаются назад и вперед между адресами памяти и адресами массивов

Answer 10

Я думаю, вы забыли, что расстояние в памяти компьютера не доступно для компьютера, работающего пешком :), поэтому расстояние в значительной степени не имеет значения.

Это оперативная память, поэтому на самом деле вам нужно выяснить, какие операции вам нужно выполнить, и оптимизировать доступ для этого.