БлогNot. Реализуем параллельные вычисления на Javascript

Реализуем параллельные вычисления на Javascript

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

Мы создаём файл с реализацией исполнителя, который будет содержать логику, используемую каждым вычислительным процессом. Исполнитель может быть основан на готовом интерфейсе Worker, поддерживаемом современными браузерами и обмениваться данными с родительским скриптом через метод postMessage.

Потом исходный скрипт создаёт нужное количество исполнителей и передаёт им данные для обработки, накапливая результаты в некоем контейнере results. Переменная-счётчик worker_count позволяет определить, сколько исполнителей работают в данный момент, а реализованный в интерфейсе метод terminate - удалять завершивших работу исполнителей.

Поскольку происходит обмен данными между файлами, подобный скрипт нужно выполнять на стороне сервера, например, в XAMPP, а не просто кликать по файлу HTML. Кроме того, файл с исполнителем должен находиться в том же домене, что исходный файл, в простом случае как у нас - в одной папке на хосте. В данном случае также следует указать в теге скрипта правильный MIME-тип контента type="text/javascript".

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

Файл parallel.js содержит реализацию кода исполнителя, показывающую пример и для других подобных скриптов:

var onmessage = function (event) { //не let, чтобы не удалялось из контекста!
 postMessage ({
  'n' : event.data.n,
  'factors' : factor (event.data.n),
  'id' : event.data.id
 });
};

function factor (n) { //Факторизация числа n - поиск его делителей
 let fs = [],
     size = Math.floor (Math.sqrt(n));
 for (let p = 2; p <= size; p++) {
  if (n % p == 0) {
   fs[fs.length] = p;
   n = Math.floor (n / p);
  }
 }
 return fs;
}

В реальности можно было искать только первый делитель для каждого числа, здесь организован поиск до обычной в таких случаях границы просто чтобы загрузить процессы работой.

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

<script type="text/javascript">
 let numbers = [13,4541431,45643543534,123421312,1312312,31232131]; //Любые числа
 let workers = [];
 let worker_count = 0;
 let results = [];
 
 for (let i = 0; i < numbers.length; i++) { //Создаём исполнителей
  worker_count++;
  workers[i] = new Worker ('./parallel.js');
  workers[i].onmessage = accumulator;
  workers[i].postMessage ({n: numbers[i], id: i});
 }
 
 function accumulator (event) {
  n = event.data.n;
  factors = event.data.factors;
  id = event.data.id;
  console.log (n + ': ' + factors);
  results[id] = {n:n, factors:factors};
  workers[id].terminate(); //Удаляем отработавших исполнителей
  worker_count--;
  if (worker_count == 0) reducor(); //По завершении подводим итоги
 }
 
 function reducor() {
  let answer = -1;
  for (let i = 0; i < results.length; i++) { //Для каждого числа
   if (results[i].factors.length == 0) results[i].factors = [results[i].n]; 
    //Для простых чисел ответ = самому числу
   let min0 = results[i].factors[0]; //Берём минимальный найденный делитель
   if (answer == -1) answer = i; //Если надо, запоминаем номер нового числа
   else if (min0 > results[answer].factors[0]) answer = i; 
  }
  let n = results[answer].n;
  let factors = results[answer].factors;
  console.log('Число с наибольшим минимальным (простым) делителем = ' + n + ' (' + factors + ')');
 }
</script>

Вот что вышло для показанного в листинге теста (скрин, фрагмент окна браузера):

Вывод скрипта в консоль браузера
Вывод скрипта в консоль браузера

20.08.2021, 13:17 [100 просмотров]


теги: числа javascript программирование