найти максимум в 3d матрице - PullRequest
Новая
       16

найти максимум в 3d матрице

1 голос
/ 14 января 2012

У меня есть матрица с 3 измерениями (n * m * k). Я пытаюсь оштрафовать максимальное число для каждого n и m путем поиска в измерении k ((я пытаюсь найти максимальное число в измерении k для каждого n и m)) и, наконец, у меня есть 2d матрица (n * m ). У меня есть следующий код, но он такой медленный. Есть ли новый код или какие-либо изменения в текущем коде, которые делают это быстрее.

спасибо.

мой код c #: примечание: li - это 3-мерная матрица, и они больше или равны нулю. 

int[,] array2 = new int[n, m];   
int[,] array = new int[n, m];
 List<Array> li = new List<Array>();             
for(int k = 0; k <'not a specific value, change each time' ; k++)
   { 
     li.Add(array);
     %% changing array
   } %% so li will became a (n*m*k) matrix   

for (int i = 0; i < n; i++)
                for (int j = 0; j < m; j++)
                {
                    int ma = -2;
                    int d = 0;
                    while (d <= k)
                    {
                        ma = Math.Max(ma, Convert.ToInt32(li[d].GetValue(i, j)));
                        d++;
                    }
                    array2[i, j] = ma;
                }

Ответы [ 4 ]

1 голос
/ 14 января 2012

Самой большой проблемой производительности является то, что вы используете Array объекты в качестве элементов вашего списка.Это делает так, чтобы каждый элемент обращался с использованием GetValue, упаковывая значение, т.е. выделяя новый крошечный объект для хранения значения элемента.

Ваш код будет работать намного быстрее, если вы замените 

List<Array> li = new List<Array>();

с 

List<int[,]> li = new List<int[,]>();

и 

ma = Math.Max(ma, Convert.ToInt32(li[d].GetValue(i, j)));

с 

ma = Math.Max(ma, li[d][i, j];

Поскольку вы не знаете 3-е измерение заранее, использовать его сложнее3D-массивы.

Совершенно другой подход заключается в вычислении максимума при построении списка li.Это поможет двумя способами: 1. Вы избегаете индексации в списке массивов и 2. Пока m и n не слишком велики, вы улучшаете локальность.То есть: значения, с которыми вы работаете, находятся ближе друг к другу в памяти и, скорее всего, будут в кеше процессора.

0 голосов
/ 14 января 2012

С точки зрения алгоритма, нет более эффективного способа оценить максимальное значение для фиксированных n, m для всех k.Это займет O (n * m * k) операций.

Теперь единственный способ повысить производительность - это найти улучшения в вашей реализации, особенно в хранилище трехмерной матрицы.

Использование List<Array> является основной областью для улучшения.Вы склонны к проблемам с боксом (преобразование примитивных типов в объекты) и делаете больше вызовов функций, чем необходимо.

Сократите вашу трехмерную матрицу до массива примитивов: 

int[] my3DArray = new int[n * m * l]; // Note I'm using l where you use k

Теперь внесите индекс в ваш массив в [i, j, k], используя следующее смещение: 

int elementAtIJK = my3DArray[i + (n * j) + (m * n * k)];

Если вы просто используете массивы примитивов, вы должны увидеть определенное улучшение.

Редактировать:

На самом деле, в C # (и некоторых других языках) это очень легкодля реализации трехмерных массивов напрямую , например: 

   int[,,] my3DArray = new int[n,m,l];
   int elementAtIJK = my3DArray[i,j,k];

Что гораздо проще, чем я описал вначале (но в конце дня внутренне переводится в одномерную форму).

Что делать, если 3-е измерение имеет разный размер ...

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

Однако, если 3-е измерение может быть очень большим, все эти дополнительные сохраненные нули могут потратить много ценного пространства, а вам нужна Разреженная матрица представление.

Существуют разные механизмы хранения для разреженных матриц.Для ваших целей вы можете рассматривать ваш 3D-массив как 2D-матрицу с (n * m) строками и max (k) столбцами.Поскольку третье измерение различается по длине, в ваших столбцах много пустых мест.Это называется разреженной строкой, и стандартное хранилище данных для этого - «Сжатый разреженный ряд».Опять же, для производительности это может быть представлено только тремя примитивными массивами, массивом данных, массивом индексов строк и массивом указателей столбцов.В Интернете есть ресурсы, которые описывают реализацию КСО лучше, чем я, но, надеюсь, это укажет вам правильное направление.

0 голосов
/ 14 января 2012

Вы можете использовать трехмерный массив следующим образом: 

int xRange = 10;
int yRange = 10;
int zRange = 10;

int[, ,] matrix = new int[xRange, yRange, zRange];

// set up some dummy values
for (int x = 0; x < xRange; x++)
    for (int y = 0; y < yRange; y++)
        for (int z = 0; z < zRange; z++)
            matrix[x, y, z] = x * y * z;

// calculate maximum values
int[,] maxValues = new int[xRange, yRange];

/* LINQ version of maximum calculation
for (int x = 0; x < xRange; x++)
    for (int y = 0; y < yRange; y++)
        maxValues[x, y] = Enumerable.Range(0, zRange).Select(z => matrix[x, y, z]).Max();
*/

// longhand version of maximum calculation
for (int x = 0; x < xRange; x++)
    for (int y = 0; y < yRange; y++)
        for (int z = 0; z < zRange; z++)
            maxValues[x, y] = Math.Max(maxValues[x, y], matrix[x, y, z]);

// display results
for (int x = 0; x < xRange; x++)
{
    for (int y = 0; y < yRange; y++)
        Console.Write("{0}\t", maxValues[x, y]);
    Console.WriteLine();
}
0 голосов
/ 14 января 2012

Это должно сработать (хотя это может быть немного медленнее, чем ваш подход): 

// put this at the top of your source file
using System.Linq;

// put this where you calculate the maxima
for(int i = 0; i < array2.GetLength(0); ++i)
for(int j = 0; j < array2.GetLength(1); ++j)
{
    array2[i, j] = Convert.ToInt32(li.Max(x => x.GetValue(i, j)));
}
...