ХОЧУ РАБОТАТЬ В GOOGLE: БОЛЬШОЙ РАЗБОР МАЛЕНЬКОЙ ЗАДАЧИ (PART 2)

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

Теперь давайте допустим, что у нас есть четырехядерный процессор, 4TB оперативной памяти (не спрашивайте, где мы столько взяли…), и задачу требуется решить для строки Unicode размером до 512GB. Понятно, что при таких вводных не использовать многопоточность и оставить три из четырех ядер простаивать было бы потерей ресурсов.

Допустим, речь идет о UTF-16. Тогда в нашей строке будет максимум (512 GB in bits)/16=274877906944 символов. То есть int32 счетчика может не хватить (преставьте, что вся строка состоит из одного символа). А вот int64 (или long или что-там 64-битный тип) вполне (считается как log_2(274877906944)=38, то есть нам надо минимально 38-битное число с учетом того, что символ, встречающийся хотя бы половину раз точно самый частый, и мы можем пректратить считать как только такой найдем).

Дальше есть два подхода:

  1. Использовать общую структуру данных (массив или hash table). Первое, кстати, может быть эффективнее, так как нам достаточно сразу создать массив 65536 элементов, что может существенно помочь в скорости по сравнению с hash table, который будет динамически адаптироваться.
  2. Каждый поток обрабатывает 1/4 часть строки, и в конце мы просто соединяем результаты.

При использовании первого метода важно понимать, что нам понадобится Mutex. Нужно знать что это такое, как он работает в вашем языке программирования. Если вы используете hash, то не забывайте, что для вставления элемента нам надо полностью закрыть таблицу. Для увеличения счетчика достаточно закрыть одно поле, но я не очень представляю как это реализовать, так как когда вы закрываете таблицу, нужно удостовериться, что все поля не закрыты mutex-ом. В общем, получается сложновато – еще один плюс в пользу массивов. Там достаточно закрыть одно поле по отдельности (тогда нам нужен еще массив mutex-ов).

В любом случае, чтобы не париться с mutex-ами (и избежать потенциальных вопросах о деталях многопоточности, если вы не сильный спец в этой области), намного проще будет разделить строку на 4 части, и дать каждому потоку обрабатывать свою часть. В конце нужно объединить все результаты. Это самое простое и эффективное решение. Учтите, что выбирать max(tread1, thread2, thread3, thread4) работать не будет.

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

Продолжение о распределенном варианте этой же задачи следует…