C # Быстрый элемент найти матрицу как Matlab - PullRequest
Новая
       16

C # Быстрый элемент найти матрицу как Matlab

0 голосов
/ 24 сентября 2018

У меня матрица 1000x1000, и я использую Emgu CV. Я пытаюсь найти индекс элемента в этой матрице.

Итак, сначала я пробую это в Matlab 

test_matrix=rand(1000,1000);
tic
[row,col]=find(test_matrix==test_matrix(1,1));
toc;

Это завершается за 9,7 мс.

Затем я использую классический цикл for в C #. 

for (int i = 0; i < element_matrix.Height; i++)
 for (int j = 0; j < element_matrix.Width; j++)
    if (element_matrix[i, j] == finding_element)
       {
         Find_Row_List.Add(i);
         Find_Col_List.Add(j);         
       }

Это завершается за 460 мс.

Затем я делю матрицу на 10малую матрицу и рассчитать каждую деталь в разных потоках. 

             t1= new Thread(() => {
                for(int i = 0; i < 100; i++)
                {
                    for(int j=0;j<element_matrix.Width;j++)
                    {
                        if(element_matrix[i,j]==finding_element)
                        {
                            Find_Row_List.Add(i);
                            Find_Col_List.Add(j);
                        }
                    }
                }
            });
            ...
            t1.Start();
            t2.Start();
            ...
            t10.Start();

            t1.Join();
            t2.Join();
            ...
            t10.Join();

Это завершается за 310 мс.

Я повторяю этот процесс для 20 маленькой матрицы инити .

Завершается за 380 мс.

Затем я использую Parallel.For 

  Parallel.For(0, element_matrix.Height, i =>
    {
        for(int j = 0; j < element_matrix.Width; j++)
        {
            if(element_matrix[i,j]==finding_element)
            {
                Find_Row_List.Add(i);
                Find_Col_List.Add(j);
            }
        }
    });

Завершается за 224 мс.

Я использую два потока и Parallel.For 

      t1 = new Thread(() => {
            Parallel.For(0, 500, i =>
            {
                for (int j = 0; j < element_matrix.Width; j++)
                {
                    if (element_matrix[i, j] == finding_element)
                    {
                        Find_Row_List.Add(i);
                        Find_Col_List.Add(j);
                    }
                }
            });
        });

        t2 = new Thread(() => {
            Parallel.For(500, 1000, i =>
            {
                for (int j = 0; j < element_matrix.Width; j++)
                {
                    if (element_matrix[i, j] == finding_element)
                    {
                        Find_Row_List.Add(i);
                        Find_Col_List.Add(j);
                    }
                }
            });
        });

        t1.Start();
        t2.Start();

        t1.Join();
        t2.Join();

Это завершается за 240 мс.

Резюме 

**Method                       Duration (ms)**
------------------------       ------------
Matlab                         9.7
For Loop (Classic)             460
For Loop (10 threads)          310
For Loop (20 threads)          380
Parallel.For                   224
Parallel.For(2 threads)        250

Все длительности в среднем равны 10. Вычисления.

Я пробую разные методы для расчета так же быстро, как Matlab.Самым быстрым решением является Parallel.For (224 мс).Но это в 25 раз медленнее, чем Matlab.Как я могу улучшить эту продолжительность?

Ответы [ 2 ]

0 голосов
/ 25 сентября 2018

Вы заглянули в библиотеку "Math.Net" для многомерной операции. 

        var sw = new Stopwatch();
        sw.Start();
        var test_matrix = Matrix<double>.Build.Dense(1000, 1000, 0);

        double finding_Element = 1;
        test_matrix[999, 999] = finding_Element;
        test_matrix[998, 999] = finding_Element;

        var result = new List<ValueTuple<int, int>>();

        for (int row = 0; row < 1000; row++)
        {
            for (int column = 0; column < 1000; column++)
            {
                if (test_matrix[row, column] == finding_Element)
                {
                    result.Add(new ValueTuple<int, int>(row, column));
                }
            }
        }

        sw.Stop();
        Console.WriteLine("Find List of Result: " + sw.ElapsedMilliseconds + "ms");

        var sw1 = new Stopwatch();
        sw1.Start();
        var result2 = test_matrix.Find(x => x.Equals(finding_Element)); // First Value
        sw1.Stop();
        Console.WriteLine("Find First Occurence: " + sw.ElapsedMilliseconds + "ms");

        Console.ReadLine();

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

0 голосов
/ 24 сентября 2018

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

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

Однако это должно быть быстрее, чем чтоу вас есть 

var width = Input.GetLength(0);
var height = Input.GetLength(1);
var array = new Point[width * height];
var count = 0;

fixed (Point* r = array)
fixed (double* pInput = Input)
{
   var len = array.Length;

   for (var i = 0; i < len; i++)
      if (*(pInput + i) == someValue)
      {
         var temp = r + count++;
         (*(temp)).X = i;
         (*(temp)).Y = i / width;
      }

   var result = new Point[count];
   Array.Copy(array, 0, result, 0, count);
   return result;
}

Тесты 

----------------------------------------------------------------------------
Mode             : Release (64Bit)
Test Framework   : .NET Framework 4.7.1 (CLR 4.0.30319.42000)
----------------------------------------------------------------------------
Operating System : Microsoft Windows 10 Pro
Version          : 10.0.17134
----------------------------------------------------------------------------
CPU Name         : Intel(R) Core(TM) i7-2600 CPU @ 3.40GHz
Description      : Intel64 Family 6 Model 42 Stepping 7
Cores (Threads)  : 4 (8)      : Architecture  : x64
Clock Speed      : 3401 MHz   : Bus Speed     : 100 MHz
L2Cache          : 1 MB       : L3Cache       : 8 MB
----------------------------------------------------------------------------

Результаты 

--- Standard input ---------------------------------------------------------
| Value   |    Average |    Fastest |    Cycles | Garbage | Test |    Gain |
--- Scale 100 ----------------------------------------------- Time 0.163 ---
| Unsafe2 |  23.472 µs |  21.013 µs |  81.444 K | 0.000 B | N/A  | 80.92 % |
| Index   | 123.034 µs | 114.073 µs | 420.831 K | 0.000 B | Base |  0.00 % |
--- Scale 1,000 -------------------------------------------- Time 16.477 ---
| Unsafe2 |   2.940 ms |   2.324 ms |   9.761 M | 0.000 B | N/A  | 76.77 % |
| Index   |  12.657 ms |  12.021 ms |  43.033 M | 0.000 B | Base |  0.00 % |
----------------------------------------------------------------------------

Вы можете сделать это параллельно, хотя я не уверен, что вы получитевсе это прирост производительности с TPL, хотя вы получите, но это будет немного больше работы

...