Как реализовать алгоритмы «разделяй и властвуй» в C # с использованием многопоточности?

Question

Я новичок в C # и многопоточности. Как мне написать программы для алгоритмов «разделяй и властвуй», таких как сортировка слиянием или быстрая сортировка в C # с использованием многопоточности?

Answer 1

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

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

Возможно, вы могли бы попросить сообщество предоставить примеры идей приложений для изучения потоков. Мое предложение было бы сканером веб-сайта. Из этого можно извлечь массу полезного!

Answer 2

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

1. Разделить входные данные
2. Запланируйте новое задание для каждой части входных данных, используя методы ThreadPool
3. Барьер-Ожидание завершения всех порожденных нитей
4. Выполнить шаг объединения

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

1. Создайте список из WaitHandle с (например, ManualResetEvent), по одной записи для каждого потока, который вы хотите создать
2. Передать один из дескрипторов ожидания вместе с рабочими данными порожденному потоку (важно: не передавать один дескриптор ожидания двум потокам => Проблемы!)
3. Используйте WaitHandle.WaitAll для ожидания установки всех ручек ожидания
4. В потоке установите дескриптор ожидания в случае успеха или ошибки
5. Проверка на успешность или ошибку отдельных потоков после того, как все потоки вернули

Тем не менее, IIIRC, существует ограничение в 64 дескриптора ожидания в Windows, но я не совсем уверен в этом. Вам придется попробовать.