Есть ли способ сделать это работающим двухъядерным в C #?

Question

Я получил фрагмент кода, который проходит по массиву и ищет похожие и одинаковые строки в нем - помечая его как уникальный или нет.

loop X array for I 
 ( loop X array for Y
   (
     If X is prefix of Y do. else if x is same length as Y and it's prefix do something.
   )
Here is the code to finilize everything for I and corresponding (found/not found) matches in Y.
 )

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

Answer 1

Параллельный алгоритм может выглядеть так:

• Сортировка списка терминов по алфавиту с использованием алгоритма параллельной сортировки
• Разделите отсортированный список терминов на куски, чтобы все интересные термины были в одном кусочке. Если я не ошибаюсь, поскольку каждый чанк начинается с одного и того же символа, у вас никогда не будет интересных совпадений между двумя чанками (совпадения и префиксы всегда будут иметь один и тот же первый символ, верно?)
• Для каждого чанка найдите термины, которые являются префиксами и / или соответствиями, и примите соответствующие меры. Это должно быть легко, так как совпадающие термины будут рядом друг с другом (поскольку большой список отсортирован, каждый блок тоже будет).

Некоторые заметки:

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

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

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

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

В настоящее время алгоритм, описанный в этом вопросе, имеет вид O (n ^ 2) , поскольку он проходит по списку один раз для каждого элемента в списке. Если список отсортирован, то дубликаты могут быть найдены за один проход по списку (дубликаты будут рядом друг с другом) - включая сортировку, это общая стоимость O (n log n) . Для больших наборов данных это будет намного, намного быстрее. Надеюсь, это будет достаточно быстро, чтобы вы могли избежать нескольких потоков, что будет много работы.

Answer 2

Я понимаю ваш вопрос, который вы хотели бы знать, как распараллелить этот код:

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

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

Answer 3

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

Answer 4

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

В конце просто объедините () все темы, вот и все.

Answer 5

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

Answer 6

Я не уверен, что ваш ответ - Parallel Extensions to .net. Вы можете проверить это на странице загрузки и в блоге проекта