C # медленный поиск

Question

Я создал простой массив, который содержит 2 000 000 дюймов для хранения всех RGB, и второй массив, который содержит 2 000 000 дюймов для количества раз, когда был обнаружен rgb. Затем он проходит через все 6 000 000 байтов изображения примерно так:

        uint[] colors = new uint[rawImageBytes.Length / 3];
        int[] hits    = new int[rawImageBytes.Length / 3];

        int colorAmount     = 0;
        int totalRepeats    = 0;
        int lastTime        = Environment.TickCount;
        int lastCount       = 0;
        uint currentColor   = 0;
        bool found;

        for (int i = 0; i < rawImageBytes.Length - 3; i += 3)
        {
            if (Environment.TickCount - lastTime > 10000)
            {
                setStatus(((i - lastCount)/10) + " checks per second");
                lastTime = Environment.TickCount;
                lastCount = i;
            }


            currentColor = (uint)((rawImageBytes[i] << 0) | (rawImageBytes[i + 1] << 8) | (rawImageBytes[i + 2] << 16));

            //set it to false to see if pattern exists
            found = false;

            //check all patterns
            for (int k = 0; k < colorAmount; k++)
            {
                //if pattern exists
                if (colors[k] == currentColor)
                {
                    //dont add it and increase the hit instead
                    found = true;
                    hits[k]++;
                }
            }

            //if pattern does not exist, set it
            if (found == false)
            {
                colors[colorAmount] = currentColor;
                hits[colorAmount] = 0;
                colorAmount++;
            }
        }

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

5724 проверок в секунду

5847 проверок в секунду

5959 проверок в секунду

6044 проверок в секунду

6318 проверок в секунду

7096 проверок в секунду

8530 проверок в секунду

10680 проверок в секунду

16233 проверок в секунду

11469 проверок в секунду

Как сделать поиск более эффективным, чтобы он не занимал 20 минут?

Answer 1

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

Вторая проблема, которую я вижу, заключается в том, что вы не прекращаете итерацию после того, как нашли свой цвет в массиве цветов. Вы должны поместить break; после found = true; выражение.

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

    uint[] colors = new uint[rawImageBytes.Length / 3];
    Dictionary<uint,int> hits    = new Dictionary<uint,int>();

    int colorAmount     = 0;
    int totalRepeats    = 0;
    int lastTime        = Environment.TickCount;
    int lastCount       = 0;
    uint currentColor   = 0;


    for (int i = 0; i < rawImageBytes.Length - 3; i += 3)
    {
        if (Environment.TickCount - lastTime > 10000)
        {
            setStatus(((i - lastCount)/10) + " checks per second");
            lastTime = Environment.TickCount;
            lastCount = i;
        }


        currentColor = (uint)((rawImageBytes[i] << 0) | (rawImageBytes[i + 1] << 8) | (rawImageBytes[i + 2] << 16));


        if (hits.ContainsKey(currentColor))
        {
            hits[currentColor]++;
        }
        else
        {
            hits.Add(currentColor,1);
        }

    }

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

Answer 2

Вы можете попробовать использовать список пар подсчета цветов (вместо двух ваших массивов) и сохранить его отсортированным по индексу цвета.Затем используйте бинарный поиск, чтобы найти повторяющиеся цвета.Я подозреваю, что это будет быстрее, чем использование словаря, но, возможно, стоит попробовать тоже (?).

сортировка и двоичный поиск: http://msdn.microsoft.com/en-us/library/b0zbh7b6.aspx#Y700

словарь: http://msdn.microsoft.com/en-us/library/xfhwa508.aspx

Answer 3

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

Вот несколько вещей для тестирования: - сортировка второго массива (по которому вы выполняете поиск) - Array.find () вместо того, чтобы зацикливаться самостоятельно

Answer 4

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

Во-первых, давайте поместим логику вашего итератора в собственный метод, чтобы вы могли настроить его отдельно:

IEnumerable<uint> GetColors(byte[] rawImageBytes) 
{ 
    int lastTime        = Environment.TickCount;
    for (int i = 0; i < rawImageBytes.Length - 3; i += 3)
    {
        if (Environment.TickCount - lastTime > 10000)
        {
           setStatus(((i - lastCount)/10) + " checks per second");
           lastTime = Environment.TickCount;
           lastCount = i;
        }


        currentColor = (uint)((rawImageBytes[i] << 0) | (rawImageBytes[i + 1] << 8) | (rawImageBytes[i + 2] << 16));

        yield return currentColor; 
   }
} 

Теперь давайте немного переписаем ваш метод, используя PLINQ:

var results = (from color in GetColors(rawImageBytes).AsParallel()
              group by color into g
              select new { Color = g.Key,  Count = g.Count()}).ToList(); 

var uniqueColours = results.Count(); 
var totalHits = results.Select(r=>r.Count()).Sum(); 

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

Посмотрите, как это происходит.