Как сопоставить записи 2D-матрицы с массивом 1D с помощью косвенного массива указателей?

Примечание. Я отредактировал этот вопрос с учетом полезных отзывов Кита Рэндалла и Чию.

У меня есть идея использовать 1D-массив для кэширования наиболее часто используемых элементов 2D-матрицы NxM в конкретном контексте обработки. Вопрос в том, существует ли уже масса работ, откуда можно получить представление, или есть просто люди, осведомленные. Сначала я расскажу о работе ног, а потом тоже задам вопрос. В качестве дополнительного примечания: Chiyou уже предложил кривые заполнения пробелов, которые концептуально выглядят как то, что мне нужно, но не дают быстрого ответа на мой конкретный вопрос (т.е. я не могу найти кривую, которая чего я добиваюсь).

Легкая работа. В настоящее время наиболее часто используемые записи определяются как комбинация циклов и специального pointer_array (см. код ниже), которые в комбинации создают индексы для наиболее используемые матричные элементы. Массив указателей содержит числа в диапазоне [0, max( N, M)] (см. выше размеры матрицы, определенные как NxM).

Цель кода — создать подходящую (в контексте программы) комбинацию индексов для обработки некоторых элементов матрицы. Возможно N = M, то есть квадратная матрица. Код (C++), проходящий через матрицу, будет выглядеть следующим образом.

for(int i = 0; i < N; i++)
{        
    for(int j = i + 1; j < M; j++)
    {
        auto pointer1 = pointer_array[i];
        auto pointer2 = pointer_array[i + 1];
        auto pointer3 = pointer_array[j];
        auto pointer4 = pointer_array[j + 1];

        auto entry1 = some_matrix[pointer1][pointer3];
        auto entry2 = some_matrix[pointer2][pointer4];
        auto entry3 = some_matrix[pointer3][pointer4];
        auto entry4 = some_matrix[pointer1][pointer2];

        //Computing with the entries...
    }
}

Некоторые вещи, заслуживающие отдельного внимания:

1. Я думаю, что для того, чтобы это кэширование было целесообразным, оно должно быть плотным. То есть что-то, к чему можно получить доступ случайным образом и что оно расположено в памяти непрерывно. т.е. пространство не «тратится впустую» (за исключением, может быть, если есть много отдельных фрагментов), а сложность находится в O (1). Это означало бы, что кеш не может быть такой же двумерной матрицей, упорядоченной полностью, как одномерный упорядоченный массив строк/столбцов. Я чувствую, что он должен вписываться в массив, имеющий длину max(N, M) (см. выше определение размера матрицы).

2. Многие записи в some_matrix будут игнорироваться во время циклов.

3. Порядок pointer_array записывает маршрут по матрице, поэтому он используется и в других местах.

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

5. Нестандартным мышлением было бы создание аналогичной комбинации индексов для чего-то, что концептуально похоже на доступ к 2D-матрице, но только более разумно. Одним из вариантов может быть кэширование строк/столбцов матрицы во время цикла.

6. Поскольку записи будут использоваться много, было бы более идеально заменить косвенность pointer_array кэшированием вызовов some_matrix, чтобы получение значений entry* в циклах было бы быстрее, т.е. из предварительно загруженного кеша вместо, возможно, довольно большого матрица. Другой момент здесь заключается в том, что он будет сохраняться в хранилище, что, в свою очередь, означает, что часто используемые значения могут очень хорошо соответствовать более быстрому кешу.

Вопрос: Можно ли устроить схему индексации так, чтобы матричная индексация по сути стала

//Load the 2D matrix entries to some_1d_cache using the pointer_array
//so that the loop indices can be used directly...

for (int i = 0; i < N; i++)
{        
    for (int j = i + 1; j < M; j++)
    {           
        //The some_1d_cache((x, y) call will calculate an index to the 1D cache array...
        auto entry1 = some_1d_cache(i, j);
        auto entry2 = some_1d_cache(i + 1, j + 1);
        auto entry3 = some_1d_cache(j, j + 1);
        auto entry4 = some_1d_cache(i, i + 1);

        //Computing with the entries...
    }
}

Или, может быть, что-то вроде следующего тоже подойдет

for (int i = 0; i < N; i++)
{        
    for (int j = i + 1; j < M; j++)
    {            
        auto pointer1 = pointer_array[i];
        auto pointer2 = pointer_array[i + 1];
        auto pointer3 = pointer_array[j];
        auto pointer4 = pointer_array[j + 1];

        //The some_1d_cache((x, y) call will calculate an index to the 1D cache array...
        auto entry1 = some_1d_cache(pointer1, pointer3);
        auto entry2 = some_1d_cache(pointer2, pointer4);
        auto entry3 = some_1d_cache(pointer3, pointer4);
        auto entry4 = some_1d_cache(pointer1, pointer2);

        //Computing with the entries...
    }
}