1. Danil Eremeev
  2. erl_prime

Overview

HTTPS SSH

Генерация простых чисел

Комментарии к выполнению задания

Для проверки простого числа на простоту использован метод Миллера-Рабина, использовались следующие ресурсы:

так же был найден реализованный алгоритм на эрланге:

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

Не использовал OTP т.к. хотелось написать именно на чистом языке, посмотреть какими "внутренностями" оперирует сам OTP.

Структура:
Главный супервизор - управляет всем, раздает задачи
Супервизор задачи - получает задачи - отдает на выполнение, возвращает назад
Воркер - проверяет на простоту числа из своего диапазона

Принцип работы:

Сначала запускается "супервизор", который по умолчанию, на той же ноде запускает супервизора воркера. Так же к главному супервизору можно присоеденить дополнительных воркер супервизоров, которые создаются отдельной коммандой на указанной ноде.

При подаче комманды рассчета создается record задачи, где указывается

  • с какого числа считаем
  • до какого числа считаем

далее по очереди выбираются свободные воркеры супервизоры (главный супервизор следит за их состоянием), и им назначается часть работ (от какого то числа, и столько то чисел подряд). Если какой то из воркеров падает - задача этого воркера возвращается назад в record основной задачи (как недоделанная), и будет подхвачена первой, при следующей раздаче. (При этом хочется пояснить - существует только список "возвращенных" задач, новые задачи берутся на основе чисел "с какого и по какое считаем").

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

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

Тестирование

В основном все проверяется на юниттестах - от отдельных методов, до ситуации с умиранием отдельного воркера.

Тест проверки числа на простоту тестируется след. способом:

самым простейшим алгоритмом генерируются простые числа до достаточно большого числа.

Затем каждое число тестируется алгоритмом Миллера-Рабина, при этом после каждого простого числа делается 1 раз +1 - и проверяется что алгоритм выдает составное число.

Запуск

Основные проверки делаются коммандой

make

если хочется поиграться вживую

erl -pa ebin primerator:start()

% добавит воркера на той же ноде (или на другой если указать) primerator:create_worker(node())

%посчитать все простые до указанного числа primerator:go(11)

% или get_result - через небольшую затычку получить данные от процесса primerator:async_receive(get_percents)

start.sh не очень удачная попытка тестирования, в процессе работы перешел полностью на тестирование make'ом

Условие задачи

В одной волшебной стране живет король, очень любящий коллекционировать чугунные тазики. От остальных таких коллекций его коллекция отличается тем, что каждый тазик имеет уникальный диаметр. Уникальность означает, что, во первых, в коллекции нет тазиков одинакового диаметра, а во вторых, что значение диаметра каждого тазика не делится без остатка на значения диаметров всех остальных тазиков из коллекции. К сожалению, король болен некой ментальной болезнью, которая вынуждает его каждый год полностью обновлять свою коллекцию, заказывая заново изготовление всех тазиков артели расторопных гномов. При этом из года в год он увеличивает количество экспонатов в коллекции. В связи с тем, что короли в волшебной стране живут долго, сейчас диаметр самого большого тазика в коллекции составляет триллиарды вершков. У любящих подданных короля есть проблема: всю эту коллекцию нужно где- то хранить. Маги волшебной страны умеют локально сворачивать пространство-время так, что вся коллекция занимает не очень много места. Для того чтобы провести такую операцию им нужно подготовиться. Подготовка требует времени, а король не любит ждать и желает получить коллекцию сразу же, как только она будет готова. Чтобы успеть подготовиться к моменту изготовления коллекции, магам необходимо знать диаметры всех тазиков в коллекции. Необходимо помочь подданным короля. Для этого следует сообщить им диаметры всех тазиков в коллекции. Вам нужно разработать распределенное приложение на Эрланге, выдающее в файл список диаметров, разделенных запятыми. Все диаметры - натуральные числа. Минимальный диаметр - два вершка. Входной параметр - число, про которое известно, что диаметр самого большого тазика не превышает его. Объем вычислений велик настолько, что отдельный компьютер за приемлемое время с ним не справится, их будет больше. Система должна автоматически распараллеливать задачу в зависимости от доступных ресурсов. Кроме того, надежность каждого отдельного ресурса невысока и нужно быть готовыми к тому, что в процессе работы некоторые вычислительные узлы будут отказывать. Так же нужно уметь сообщать стороннему наблюдателю о текущем прогрессе в решении вычислительной задачи. Алгоритмы, архитектура, форматы данных и способы взаимодействия с внешним наблюдателем остаются на ваше усмотрение, нужно уметь аргументировать ваш выбор. Так же мы рассчитываем, что ваше решение будет хорошо покрыто автоматическими тестами.