Параллельная программа проверки орфографии

Шаги написания программы ¹

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

if (!File.Exists(wordLookupFile)) // Contains about 150,000 words
new WebClient().DownloadFile("https://csharpcooking.github.io/data/allwords.txt", 
							 wordLookupFile);
var wordLookup = new HashSet<string>(File.ReadAllLines(wordLookupFile),
				     StringComparer.InvariantCultureIgnoreCase);

Затем мы будем применять полученное средство поиска слов для создания тестового “документа”, содержащего массив из миллиона случайных слов. После построения массива мы внесем пару орфографических ошибок:

var random = new Random();
string[] wordList = wordLookup.ToArray();
string[] wordsToTest = Enumerable.Range(0, 1000000)
	.Select(i => wordList[random.Next(0, wordList.Length)])
	.ToArray();
wordsToTest[12345] = "woozsh"; // Introduce a couple
wordsToTest[23456] = "wubsie"; // of spelling mistakes.

Теперь мы можем выполнить параллельную проверку орфографии, сверяя wordsToTest с wordLookup. PLINQ, представляющий собой параллельный вариант языка интегрированных запросов LINQ, позволяет делать это очень просто:

var query = wordsToTest.AsParallel()
.Select((word, index) => new IndexedWord { Word = word, Index = index })
.Where(iword => !wordLookup.Contains(iword.Word))
.OrderBy(iword => iword.Index);
foreach (var mistake in query)
	Console.WriteLine(mistake.Word + " - index = " + mistake.Index);
	
// OUTPUT:
// woozsh - index = 12345
// wubsie - index = 23456

IndexedWord – это специальная структура, которая определена следующим образом:

struct IndexedWord { public string Word; public int Index; }

Метод wordLookup.Contains в предикате придает запросу определенный “вес” и делает уместным его распараллеливание.

Мы могли бы слегка упростить запрос за счет использования анонимного типа вместо структуры IndexedWord. Однако это привело бы к снижению производительности, т.к. анонимные типы (будучи классами, а потому ссылочными типами) привносят накладные расходы на выделение памяти в куче и последующую сборку мусора.

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

Использование ThreadLocal<T> ²

Расширим наш пример, распараллелив само создание случайного тестового списка слов. Мы структурировали его как запрос LINQ, так что все должно быть легко. Вот последовательная версия:

string[] wordsToTest = Enumerable.Range(0, 1000000)
.Select(i => wordList[random.Next(0, wordList.Length)])
.ToArray();

К сожалению, вызов метода random.Next небезопасен в отношении потоков, поэтому работа не сводится к простому добавлению в запрос вызова AsParallel. Потенциальным решением может быть написание функции, помещающей вызов random.Next внутрь блокировки, но это ограничило бы параллелизм. Более удачный вариант предусматривает применение класса ThreadLocal<Random> с целью создания отдельного объекта Random для каждого потока. Тогда распараллелить запрос можно следующим образом:

var localRandom = new ThreadLocal<Random>
(() => new Random(Guid.NewGuid().GetHashCode()));
string[] wordsToTest = Enumerable.Range(0, 1000000).AsParallel()
.Select(i => wordList[localRandom.Value.Next(0, wordList.Length)])
.ToArray();

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

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

Использованные источники

1. Албахари Д., Албахари Б. C# 7.0. Справочник. Полное описание языка.: Пер. с англ. – СпБ.: ООО «Альфа-книга», 2018. – С. 896-897. (См. главу 23. Параллельное программирование, п. Пример: параллельная программа проверки орфографии.) ↩︎

2. Албахари Д., Албахари Б. C# 7.0. Справочник. Полное описание языка.: Пер. с англ. – СпБ.: ООО «Альфа-книга», 2018. – С. 897-898. (См. главу 23. Параллельное программирование, п. Использование ThreadLocal.) ↩︎