Ускорить добавление матрицы в C #

Я согласен с ответом от zacherates.

Но вы можете сделать вызов intern () в ваших нелиберальных строках.

Из примера zacherates:

// ... but they are not the same object
new String("test") == "test" ==> false 

Если вы ставите нелитеральное равенство строки, это правда

new String("test").intern() == "test" ==> true 
11
задан Jean Azzopardi 8 December 2009 в 17:42
поделиться

15 ответов

Несмотря на использование небезопасного кода, GetPixel вполне может оказаться здесь узким местом. Вы искали способы получить все пиксели изображения в за один вызов , а не один раз на пиксель? Например, Bitmap.LockBits может быть вашим другом ...

На моем нетбуке очень простой цикл, повторяющий 640 * 480 * 200 раз, занимает всего около 100 миллисекунд, поэтому если вы обнаружите, что все идет медленно, вам следует еще раз взглянуть на бит внутри цикла.

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

В частности, вы можете иметь одномерный массив размером Ширина * Высота и просто сохранять индекс:

int index = 0;
for (int x = 0; x < Width; x++)
{
    for (int y = 0; y < Height; y++)
    {
        Byte pixelValue = image.GetPixel(x, y).B;
        this.sumOfPixelValues[index] += pixelValue;
        this.sumOfPixelValuesSquared[index] += pixelValue * pixelValue;
        index++;
    }
}

Используя тот же простой тест жгут, добавление записи в двумерный прямоугольный массив заняло общее время цикла от 200 * 640 * 480 примерно до 850 мс; использование одномерного прямоугольного массива вернуло его примерно к 340 мс - так что это довольно важно, и в настоящее время у вас есть два таких массива на итерацию цикла.

они значительно медленнее, чем одномерные массивы.

В частности, вы можете иметь одномерный массив размером Ширина * Высота и просто сохранять индекс:

int index = 0;
for (int x = 0; x < Width; x++)
{
    for (int y = 0; y < Height; y++)
    {
        Byte pixelValue = image.GetPixel(x, y).B;
        this.sumOfPixelValues[index] += pixelValue;
        this.sumOfPixelValuesSquared[index] += pixelValue * pixelValue;
        index++;
    }
}

Используя ту же простую тестовую программу, добавление записи в двумерный прямоугольный массив заняло общее время цикла от 200 * 640 * 480 до примерно 850 мс; использование одномерного прямоугольного массива вернуло его примерно к 340 мс - так что это довольно важно, и в настоящее время у вас есть два таких массива на итерацию цикла.

они значительно медленнее, чем одномерные массивы.

В частности, вы можете иметь одномерный массив размером Ширина * Высота и просто сохранять индекс:

int index = 0;
for (int x = 0; x < Width; x++)
{
    for (int y = 0; y < Height; y++)
    {
        Byte pixelValue = image.GetPixel(x, y).B;
        this.sumOfPixelValues[index] += pixelValue;
        this.sumOfPixelValuesSquared[index] += pixelValue * pixelValue;
        index++;
    }
}

Используя ту же простую тестовую программу, добавление записи в двумерный прямоугольный массив заняло общее время цикла от 200 * 640 * 480 до примерно 850 мс; использование одномерного прямоугольного массива вернуло его примерно к 340 мс - так что это довольно важно, и в настоящее время у вас есть два таких массива на итерацию цикла.

18
ответ дан 3 December 2019 в 02:10
поделиться

Это классический случай ужасного сбоя микрооптимизации. Вы ничего не получите, глядя на этот цикл. Чтобы получить реальный выигрыш в скорости, вам нужно начать с общей картины: -

  • Можно ли предварительно загрузить изображение [n + 1] асинхронно при обработке изображения [n]?
  • Можно ли загрузить только канал B из изображения? Это уменьшит пропускную способность памяти?
  • Можете ли вы загрузить значение B и обновить массивы sumOfPixelValues ​​(Squared) напрямую, то есть читать файл и обновлять вместо того, чтобы читать файл, хранить, читать, обновлять? Опять же, это снижает пропускную способность памяти.
  • Можно ли использовать одномерные массивы вместо двухмерных? Может быть, создать свой собственный класс массива, который будет работать в любом случае.
  • Возможно, вы могли бы изучить использование Mono и расширений SIMD?
  • Можете ли вы обрабатывать изображение по частям и назначать их простаивающим процессорам в среде с несколькими процессорами?

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

Попробуйте использовать специальные средства доступа к изображениям, чтобы не тратить впустую пропускную способность памяти:

public Color GetBPixel (int x, int y)
{
    int offsetFromOrigin = (y * this.stride) + (x * 3);
    unsafe
    {
        return this.imagePtr [offsetFromOrigin + 1];
    }
}

или, еще лучше:

public Color GetBPixel (int offset)
{
    unsafe
    {
        return this.imagePtr [offset + 1];
    }
}

, и используйте указанное выше в цикле, например:

for (int start_offset = 0, y = 0 ; y < Height ; start_offset += stride, ++y)
{
   for (int x = 0, offset = start_offset ; x < Width ; offset += 3, ++x)
   {
      pixel = GetBPixel (offset);
      // do stuff
   }
}
0
ответ дан 3 December 2019 в 02:10
поделиться

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

Byte  pixelValue = image.GetPixel(x, y).B;

Очевидно, если pixelValue = 0, то нет причина для суммирования, чтобы ваша процедура могла стать

public void PopulatePixelValueMatrices(GenericImage image,int Width, int Height)
  {
  for (int x = 0; x < Width; x++)
    {
    for (int y = 0; y < Height; y++)
      {
       Byte  pixelValue = image.GetPixel(x, y).B;

       if(pixelValue != 0)
         {
         this.sumOfPixelValues[x, y] += pixelValue;
         this.sumOfPixelValuesSquared[x, y] += pixelValue * pixelValue;
         }}}}

Однако вопрос в том, как часто вы будете видеть pixelValue = 0, и компенсирует ли экономия на вычислении и сохранении стоимость теста.

0
ответ дан 3 December 2019 в 02:10
поделиться

Иногда выполнение задач на собственном C #, даже небезопасных вызовов, просто медленнее, чем использование уже оптимизированных методов.

Результатов не гарантировано, но вы можете изучить System.Windows.Media.Imaging и взгляните на свою проблему с другой стороны.

0
ответ дан 3 December 2019 в 02:10
поделиться

System.Drawing.Color - это структура, которая в текущих версиях. NET убивает большинство оптимизаций. Поскольку вы внутренний цикл может проходить через массив image.imagePtr с шагом 3 вместо того, чтобы постоянно пересчитывать смещение. Теперь небезопасная версия для хорошей меры, выполняющая оптимизацию, для которой, я думаю, .NET должна быть достаточно умной, но, вероятно, нет:

unsafe public void PopulatePixelValueMatrices(GenericImage image,int Width, int Height)
{          
    byte* scanline = image.imagePtr;
    fixed (uint* sums = &this.sumOfPixelValues[0,0])
    fixed (uint* squared = &this.sumOfPixelValuesSquared[0,0])
    for (int y = 0; y < Height; y++)
    {
        byte* blue = scanline;
        for (int x = 0; x < Width; x++)
        {
            byte pixelValue = *blue;
            *sums += pixelValue;
            *squares += pixelValue * pixelValue;
            blue += 3;
            sums++;
            squares++;
        }
        scanline += image.stride;
    }
}
3
ответ дан 3 December 2019 в 02:10
поделиться

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

Если вы хотите выполнять более сложные операции, вам нужно использовать высокооптимизированную математическую библиотеку, такую ​​как NMath.Net, которая использует собственный код, а не .net.

0
ответ дан 3 December 2019 в 02:10
поделиться

Прочтите эту статью, в которой также есть код и упоминается о медлительности GetPixel

текст ссылки

Из статьи это код для простого инвертирования битов. Это также показывает использование LockBits.

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

public static bool Invert(Bitmap b)
{

BitmapData bmData = b.LockBits(new Rectangle(0, 0, b.Width, b.Height), 
                               ImageLockMode.ReadWrite, PixelFormat.Format24bppRgb); 

int stride = bmData.Stride; 
System.IntPtr Scan0 = bmData.Scan0; 
unsafe 
{ 
    byte * p = (byte *)(void *)Scan0;
    int nOffset = stride - b.Width*3; 
    int nWidth = b.Width * 3;
    for(int y=0;y < b.Height;++y)
    {
        for(int x=0; x < nWidth; ++x )
        {
            p[0] = (byte)(255-p[0]);
            ++p;
        }
        p += nOffset;
    }
}

b.UnlockBits(bmData);

return true;

}

6
ответ дан 3 December 2019 в 02:10
поделиться

сложность сложения матрицы составляет O (n ^ 2) по количеству сложений.

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

  1. легко доказать, что результирующий алгоритм будет без блокировок
  2. вы можете настроить оптимальное количество потоков для использования
-1
ответ дан 3 December 2019 в 02:10
поделиться

Единственный способ эффективно ускорить умножение матриц - это использовать правильный алгоритм. Существуют более эффективные способы ускорить умножение матриц. Взгляните на алгоритмы Стрессена и Куперсмита Винограда . Также отмечено [с предыдущими ответами], что вы можете распараллелить код, что немного помогает.

0
ответ дан 3 December 2019 в 02:10
поделиться

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

1
ответ дан 3 December 2019 в 02:10
поделиться

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

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

1
ответ дан 3 December 2019 в 02:10
поделиться

Лучшее место для начала - профилирование кода.

Добавление матриц - это очень параллельная операция, и ее можно ускорить, распараллеливая операцию с несколькими потоками.

Я бы рекомендовал использовать Библиотека Intel IPP , которая содержит многопоточный высокооптимизированный API для такого рода операций. Возможно, удивительно, что это всего около 100 долларов, но это значительно усложнит ваш проект.

Если вы не хотите утруждать себя программированием на смешанных языках и IPP, вы можете попробовать библиотеки C # math centerpace. NMath API содержит простые в использовании матричные операции прямого масштабирования.

Paul

3
ответ дан 3 December 2019 в 02:10
поделиться

Я не уверен, что это быстрее, но вы можете написать что-нибудь вроде:

public void PopulatePixelValueMatrices(GenericImage image,int Width, int Height)
{            
        Byte pixelValue;
        for (int x = 0; x < Width; x++)
        {
            for (int y = 0; y < Height; y++)
            {
                pixelValue = image.GetPixel(x, y).B;
                this.sumOfPixelValues[x, y] += pixelValue;
                this.sumOfPixelValuesSquared[x, y] += pixelValue * pixelValue;
            }
        }
}
0
ответ дан 3 December 2019 в 02:10
поделиться

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

0
ответ дан 3 December 2019 в 02:10
поделиться

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

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

long sumOfPixelValues[n,m];
long sumOfPixelValuesSquared[n,m];

-

struct Sums
{
    long sumOfPixelValues;
    long sumOfPixelValuesSquared;
}

Sums sums[n,m];

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

3
ответ дан 3 December 2019 в 02:10
поделиться
Другие вопросы по тегам:

Похожие вопросы: