Perl 6 понимание списков

Это медленно, потому что вы пытаетесь материализовать огромное количество предметов. В качестве альтернативы вы можете создать последовательность: (5, 10 … 1000000000).sum, но она по-прежнему материализует и сохраняет массу элементов, поэтому она все еще медленная. Вы можете сделать цикл в стиле C и добавлять к сумме для каждого приращения, но это неинтересно (и все еще медленно для достаточно больших чисел).

Вы можете решить это с помощью математики: числа, делящиеся на N, кратны ему, и если мы вынесем N из этой последовательности, мы обнаружим, что сумма всех искомых чисел равна N * (1 + 2 + ... + floor 1000000000/N). Поскольку это последовательный диапазон вверх, мы можем использовать его Range.sum (который умеет делать это быстро) для вычисления этой части. Таким образом мы получаем:

sub sum-of-stuff (\n, \d) { d * sum 1..n div d; }
say sum-of-stuff 1000000000, 5 # OUTPUT: 100000000500000000

Так что это самый быстрый и разумный способ вычислить вашу задачу, но это не самое веселое!

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

constant N = 10000;
constant DIV = 5;
constant CORES = 32;
constant batch = N div CORES;

(0, batch … N, N).rotor(2 => -1).flat.map({$^a^..$^b})
    .race(:batch :degree(CORES)).map(*.grep(* %% DIV).sum).sum.say;

batch — это размер фрагмента, который необходимо обработать каждому ядру, и вот объяснение однострочного кода, который выполняет всю работу с разбивкой по каждому биту:

Мы используем оператор последовательности для создания последовательности 0, batch, 2*batch, 3*batch и так далее, вплоть до N. Поскольку мы хотим, чтобы N был его частью, мы включаем его во второй раз:

(0, batch … N, N)

Сейчас мы хотим использовать эту последовательность для создания набора объектов Range, мы хотим повторно использовать элементы в последовательности, поэтому мы используем .rotor с пакетом из 2 и обратным шагом 1, затем сгладьте подсписки и используйте .map для создания объектов Range (.map: *^..* выглядит так много приятнее, но, увы, Whatever Stars не хотят карри в такой аранжировке):

.rotor(2 => -1).flat.map({$^a^..$^b})

Теперь самое интересное: мы используем метод .race для создания HyperSeq, чтобы он оценивался с использованием всех наших ядер. Его именованный аргумент :batch позволяет вам указать, сколько элементов обрабатывать в пакете, а его :degree указывает, сколько потоков использовать. Мы уже объединили наши данные, поэтому для :batch мы используем 1. А для :degree используем количество наших ядер. Почему мы не сказали ему собирать наши вещи? Потому что овеществление — наш враг, и мы хотим овеществлять в отдельных потоках. Вместо этого указание на группирование приведет к тому, что все будет реализовано в одном потоке:

.race(:batch :degree(CORES))

Итак, теперь у нас есть HyperSeq, и мы можем нанести его на карту. Помните, что каждый предмет — это наш объект размером Range для партии. Итак, мы вызовем .grep, ищем числа, делящиеся на нужный нам делитель, а затем вызовем .sum:

.map(*.grep(* %% DIV).sum)

Последняя вишенка наверху, мы хотим просуммировать суммы каждого фрагмента и вывести результат, поэтому мы вызываем

.sum.say;

Тада!

Вы также можете переписать забавный фрагмент таким образом и использовать Promises вместо .race:

say sum await (0, batch … N, N).rotor(2 => -1).flat.map:
    { start sum grep * %% DIV, $^a^..$^b }

Аналогично и немного короче. Карта, которая раньше создавала для нас Ranges, теперь также запускает Promise (используя ключевое слово start), который обрабатывает и суммирует фрагмент. В начале строки мы добавили await, чтобы дождаться результата всех обещаний, а затем суммировать результаты этого.

Он по-прежнему чертовски медленный и не поможет вашей первоначальной проблеме, поэтому вместо этого вы должны использовать хороший алгоритм;)

Ваше здоровье.

Как я могу преодолеть это?

Выбрав лучший алгоритм:

Пусть my \N = 1_000_000_000. Вас интересует стоимость

[+] grep * %% 5, 1..N

что то же самое, что

[+] map * * 5, 1..N/5

что в свою очередь

5 * [+] 1..N/5

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

Сколько времени потребуется, если значение меньше 1_000_000_000, скажем, 1_000_000? На моей машине это занимает около 3 секунд. Экстраполируя это, в 1000 раз больше значений для проверки будет означать, что это займет около 3000 секунд.

Чтобы ускорить процесс, вы можете использовать оператор %% (делится на) вместо % (по модулю):

($_ if $_ %% 5 for 1..1000000000).sum

FWIW, я ожидал, что это будет быстрее. Я постараюсь сделать %% быстрее, но я боюсь, что вы все равно будете смотреть на часовую шкалу для своего алгоритма.