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

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

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

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

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

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

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

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

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

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

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

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

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

r = (address / 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-изображений, который использует вычисленное значение, называемое «шаг», которое, по сути, является индикатором того, что они прыгают. вперед и назад между адресами памяти и адресами массива

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

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

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

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

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

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

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

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

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

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

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

Чтобы уточнить мою догадку, возьмем пример. Допустим, сначала мы сохраняем 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] и т. д.) Но как теперь сделать то же самое, например, для а[1][0]? Все места рядом с ним в памяти теперь заняты тем, что находится рядом с a[0][0].

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

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

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