Необходимо ускорить сопоставление с образцом в зубчатом массиве.

У меня есть зубчатый массив 20 на 20. Я пытаюсь сопоставить 700 различных шаблонов, которые построены как меньшие зубчатые массивы. Значения, которые совпадают (байты ИЛИ: объединены вместе), могут быть «игроком», «оппонентом», «пустым» или «все равно» или их сочетанием. Размер рисунка варьируется от 4х4 до 7х7.

Как я могу ускорить это? Я уверен, что есть лучший способ сделать это. Прямо сейчас проверка всех шаблонов занимает около секунды. Мне нужно знать все совпадения, а не только один раз для каждого шаблона.

// Iterate through all patterns
for( int patNum = 0; patNum < whitePatterns.Length; patNum++)
{
    // Get current pattern
    pat = whitePatterns[patNum];

    col = pat.pattern.Length;
    row = pat.pattern[0].Length;

    for (int x = 0; x < myBoard.Size - col + 1; ++x)
    {
        for (int y = 0; y < myBoard.Size - row + 1; ++y)
        {
            for (int xx = 0; xx < col; ++xx)
                for (int yy = 0; yy < row; ++yy)
                {
                    count++;
                    if ((myBoard.board[x + xx][y + yy] & pat.pattern[xx][yy]) == 0)
                    {
                        goto loopY;
                    }
                }

            // Found a match!

            loopY: ;
        }
    }
}

unity3d c# pattern-matching jagged-arrays
person Andreas    schedule 23.02.2014    source источник
comment
Вы пытались заменить итератор шаблона на Parallel.ForEach()??   -  person Jon Bellamy    schedule 23.02.2014
comment
Нет никакого волшебного способа обойти атаку грубой силы. Но кажется, что он очень хорошо подходит для распараллеливания.   -  person Henk Holterman    schedule 23.02.2014
comment
Вы можете использовать словарь с комбинациями 4x4. Это должно сделать полный или частичный поиск очень быстрым, однако создание такого словаря и предоставление поиска будет дополнительной сложностью и займет некоторое время.   -  person peter    schedule 23.02.2014
comment
Я использую Unity, который использует Mono 2.6 и похоже, что он не поддерживает Parallel.ForEach. Найдет способ попытаться распараллелить цикл шаблона.   -  person Andreas    schedule 23.02.2014

Ответы (2)


arrow_upward
2
arrow_downward

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

Parallel.ForEach(whitePatterns, wp =>
{
int col = wp.pattern.Length;
int row = wp.pattern[0].Length;
for (int x = 0; x < myBoard.Size - col + 1; ++x)
{
    for (int y = 0; y < myBoard.Size - row + 1; ++y)        
    {
        for (int xx = 0; xx < col; ++xx)
            for (int yy = 0; yy < row; ++yy)
        {
            count++;
            if ((myBoard.board[x + xx][y + yy] & wp.pattern[xx][yy]) == 0)
            {
                goto loopY;

            }
        }

        // Found a match!

    loopY: ;
    }       
}
});
person Jon Bellamy    schedule 23.02.2014
comment
В зависимости от объема работы вы можете изменить for, который вы сдаете, на Parallel.ForEach или Parallel.For. Для 700 предметов для проверки уровня в этом ответе может быть правильным. Я настоятельно рекомендую ознакомиться с бесплатной книгой Microsoft Patterns for Parallel Programming. . В частности, посмотрите на антишаблон TOO FINE-GRAINED, TOO COARSE COARSE GRAINED, чтобы узнать больше о распараллеливании вложенных for циклов. - person Scott Chamberlain; 23.02.2014
comment
@ScottChamberlain Спасибо за это. Я такого раньше не встречал. Я действительно собираюсь насладиться чтением. :-) - person Jon Bellamy; 23.02.2014
comment
Использование Unity, не поддерживающего Parallel.ForEach. проверим, как это сделать в Unity. - person Andreas; 23.02.2014
comment
Привет, Джон, не уверен, понял ли ты это, я нашел версию, которая работает с .Net 3.5. Это parallel.for, он работает как шарм, когда просто перебирает длину белых шаблонов и печатает индекс, но я получаю массив за пределами, если я попробую это в приведенном выше коде. Любая подсказка, что может быть причиной этого? Нужен ли мне какой-то замок для любого кода? - person Andreas; 25.02.2014
comment
@Андреас Это здорово. Вам не нужен никакой замок. Когда массив выходит за пределы, где-то генерируется число, выходящее за пределы одного из ваших массивов, но без полного кода я не могу быть уверен, где именно. Я могу только предложить вам поместить некоторые глобальные переменные вне цикла Parallel.For для захвата col, row, x, y, xx и wp. Затем оберните Parallel.For внутри попытки и для каждого цикла, запишите значения текущих переменных в глобальные, установите точку останова в точке исключения, и глобальные переменные должны дать вам некоторое представление о том, почему это не удается. - person Jon Bellamy; 26.02.2014
comment
@Andreas, еще одна мысль, правильно ли вы установили значения в Parallel.For? Я думаю, у вас должно быть Parallel.For(0, whitePatterns.Length, wp => { pat = whitePatterns[wp]; }); по памяти. - person Jon Bellamy; 26.02.2014
comment
Сработало, спасибо :) пропустил объявление col и row внутри цикла. К сожалению, это не ускорило алгоритм, возможно, реализация не так эффективна, как встроенная. Пробовал с foreach, и это было еще медленнее. Я забыл сказать, что причина, по которой это занимает 1,5 секунды, заключается в том, что я делаю это 8 раз, поворачиваю 4 раза, затем отражаю и поворачиваю, чтобы найти все совпадения. Таким образом, большое количество совпадений, лучший вариант выглядит как лучший алгоритм. Спасибо за ответ. - person Andreas; 26.02.2014
comment
@Andreas, это странно, как вы говорите, возможно, это реализация. Тем не менее, добро пожаловать и надеюсь, что вы найдете ответ. - person Jon Bellamy; 26.02.2014

arrow_upward
1
arrow_downward

Итак, у вас есть фиксированный набор паттернов, и вы хотите найти на игровом поле все вхождения этих паттернов.

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

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

На самом деле, вы бы сделали так, чтобы каждая строка каждого шаблона считалась «строкой», и вы строили бы древовидную структуру Ахо-Корасика из этих шаблонов. Затем вы просматриваете все игровое поле, чтобы найти все совпадающие строки. Результатом будет набор строк шаблона с их начальными адресами (строка, столбец) и номерами шаблона.

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

Генерация конечного автомата займет некоторое (небольшое) время, но вам нужно сделать это только один раз. После этого поиски проходят невероятно быстро. Сортировка результатов и выбор совпадений были бы очень быстрыми.

Я создал средство сопоставления с образцом Aho-Corasick на C#, которое может помочь вам начать работу. См. мою статью Возвращение к Aho-Corasick.

person Jim Mischel    schedule 23.02.2014
comment
Спасибо за предложение, посмотрю вашу статью. Это потребует некоторой работы с шаблонами, но, возможно, в конце концов оно того стоит :) - person Andreas; 24.02.2014