Хотя RxJs — отличный инструмент для решения асинхронных событий, легко упустить из виду возможности его операторов и написать, откровенно говоря, вульгарный код. Ярким примером, к которому склонны многие разработчики, плохо знакомые с RxJ, является простое создание пайпа, состоящего из одного оператора map с его «функцией отображения», состоящей из десятков или сотен строк кода. Это НЕ способ решения проблем RxJ, и его следует категорически не поощрять.
Но вместо того, чтобы говорить разработчикам, чего не следует делать, лучше продемонстрировать мощь RxJ и его гибкость для манипулирования данными с помощью конкретных операторов и создателей. Для этого я решил решить некоторые задачи Project Euler, используя почти исключительно RxJ.
Если вы не знакомы с Project Euler, это сайт задач по математическому программированию. В отличие от многих других современных сайтов, он принимает только окончательный ответ, обычно целое число, вместо кода, используемого для его поиска. Хотя время выполнения и использование памяти зависят от решения разработчика, многие проблемы настолько сложны математически, что неэффективным алгоритмам требуется ОЧЕНЬ много времени для решения проблем.
Если вы изо всех сил пытаетесь изучить все операторы, которые может предложить RxJ, я настоятельно рекомендую вам кодировать и бросить вызов себе, чтобы использовать RxJ как можно лучше для решения этих проблем. Архивные задачи можно найти здесь:
Так что зарегистрируйтесь, и давайте ознакомимся с правилами этого испытания перед тем, как закончить!
Правила
Итак, правила, которые я определил для себя, заключались в том, чтобы максимально использовать RxJ. Короче говоря, правила, которые я определил, были следующими:
- У каждой задачи будет создатель потока с именем
taskOne,taskTwoи т. д. Создатель потока будет принимать параметры на основе задачи (поэтому, когда даны тестовые примеры, их можно использовать с параметрами, отличными от решения). - Каждое решение можно найти только с помощью функции custom
solver. Все, что он делает, это подписывается и выводит значение, а также определяет время выполнения, чтобы мы могли сравнивать решения. - Кроме того, допускается объявление функций-создателей и операторов, используемых для нескольких задач! (Нет необходимости снова и снова объявлять одного и того же создателя потока Фибоначчи)
- Все аргументы для операторов должны быть однострочными! Не просто используйте оператор карты и поместите 30 строк кода, делающих все, что требуется внутри! Это именно то, чего мы учимся избегать!
- По возможности рекомендуется использовать малоизвестные операторы и функции-создатели!
Функция solver выглядит так:
Не стесняйтесь копировать его, если хотите. proxjs — это моя собственная библиотека, в которую я помещаю некоторые интересные функции, о которых пишу на Medium. Вы можете сами выбрать, хотите ли вы установить его или нет. Если вы не хотите, весь исходный код (и объяснение того, что он делает) доступен в следующей статье:
Определив эти правила, идите вперед и посмотрите, как у вас дела. Затем вернитесь, чтобы посмотреть, как я их решу! Если вы считаете, что у вас есть лучшее решение, поделитесь им в комментариях ниже!
1: кратное 3 и 5
Начнем с варианта, отдаленно напоминающего FizzBuzz. Мы рассмотрим два разных подхода к этому решению, причем последний использует более экзотические функции RxJs.
Простое решение
Во-первых, мы используем функцию создания RxJs по умолчанию range для составления чисел от 1 до maxNumber. Поскольку мы не включаем заданное максимальное значение, мы вызываем range(1, maxNumber — 1). Это выдаст все числа от 1 до числа перед нашим maxNumber.
Затем мы отфильтровываем все значения, которые не делятся без остатка на 3 или 5. Мы делаем это, помещая filter в наш канал следующим образом: filter(val => val % 3 === 0 || val % 5 === 0).
Наконец, мы хотим просуммировать любые числа, прошедшие наш фильтр. Мы используем reduce, который работает аналогично Array.reduce, например: reduce((acc, val) => acc + val).
Экзотическое решение
Таким образом, проблема с предыдущим решением заключается в следующем: мы создаем кучу чисел, которые нам не нужны, и все они передаются в filter, что означает, что они фактически требуют (минимального количества) вычислительного времени.
В данном случае это не имеет никакого значения. Полное время для тестового примера составляет около 1–2 мс, но, допустим, мы хотим создать что-то более подходящее с точки зрения RxJ.
RxJs имеет функцию создания под названием generate, которая является сокращением для создания наблюдаемых последовательностей, следующих простым правилам. Первый параметр — это начальное значение, второй — когда прекратить излучение, а третий — функция приращения. Другими словами, он работает очень похоже на цикл for. Четвертый параметр, если он задан, представляет собой функцию отображения выходных данных. В нашем случае мы просто хотим вывести значение, поэтому проигнорируем это.
Давайте затем создадим две наблюдаемые последовательности, которые выводят нужные нам числа и ничего больше. Мы начинаем с ряда чисел, делящихся на 3. Мы создаем поток с именем threes$ и определяем, что наше начальное число равно 3, мы хотим закончить, если число равно или больше, чем наш максимум, и мы добавляем 3 к числу для каждую итерацию. Достаточно просто.
Мы повторяем процесс для чисел, которые делятся на 5. В этом случае мы хотим пропустить любое число, которое делится на 3, поэтому в этом случае мы просто сразу добавляем еще 5. Поскольку 5 % 3 = 2, мы всегда можем предположить, что для любого n где n % 3 = 0 и n + 5 % 3 = 2, поэтому всегда будет безопасно просто добавить еще 5.
Наконец, мы хотим объединить эти два потока и добавить все испускаемые значения. При объединении потоков доступен ряд функций, и обычно необходимо тщательно продумать, как следует объединять потоки (особенно это касается асинхронных источников). В нашем случае мы хотим: Все испускаемые значения со всех исходных входов, независимо от порядка. Мы также знаем, что оба наших входных потока синхронны и имеют четко определенное определение завершения.
Учитывая это, и merge, и concat будут работать как положено. Какой из них вы выберете, произволен, но я согласился с merge. Наконец, мы передаем объединенный поток в редуктор, который складывает числа.
В конце я добавил "большой" вариант для обоих решений, чтобы увидеть, что производительность действительно немного увеличилась. Для этого ввода
10 000 000мое простое решение выполняется за 472 мс, а улучшенное решение — за 387 мс. Другими словами, прирост производительности очень незначительный, но, по крайней мере, нам удалось использовать более экзотическую функцию создания.
2: Четные числа Фибоначчи
фибоначчи$
Для этой задачи требуется последовательность чисел Фибоначчи. Давайте сначала создадим наблюдаемую последовательность, которая выводит числа Фибоначчи. Мы хотим сделать это повторно используемым для нескольких задач, поэтому мы создаем отдельный файл и объявляем наш fibonacci$ следующим образом:
Хотя это и не так красиво, как сокращение generate, Observable.create позволяет нам вручную определять нашу наблюдаемую последовательность, используя обычные шаблоны программирования. В этом случае мы начинаем с чисел 0 и 1 и продолжаем синхронно выдавать числа Фибоначчи, пока не увидим, что наблюдатель закрыл свою подписку.
Имейте в виду, что fibonacci$ сам по себе не завершается; при подписке вы должны использовать оператор, который вызывает завершение, например take или takeWhile. Последовательность Фибоначчи никогда не заканчивается, и fibonacci$ отражает это.
Решение
Мы импортируем fibonacci$ и передаем его в takeWhile, что гарантирует, что мы перестанем принимать числа, когда достигнем maxFibonacciValue. В нашем окончательном решении это четыре миллиона. Любые числа, превышающие это значение, будут проигнорированы, и подписка будет немедленно закрыта.
В случае, если вы хотите включить значение разрыва, обратите внимание, что takeWhile принимает второй логический параметр, который определяет, следует ли включать это значение. В нашем случае нас это не интересует, поэтому параметр оставляем неустановленным, так как по умолчанию он равен false.
Затем мы отфильтровываем все нечетные числа, используя filter. Надеюсь, этот шаг не требует дополнительных пояснений.
Затем, как и в предыдущем задании, суммируем числа с помощью reduce.
3: Самый большой простой фактор
простые $
Как и в предыдущей задаче, мы начинаем с создания многоразовой наблюдаемой последовательности, на этот раз той, которая выдает простые числа. Как и в предыдущей задаче, мы хотим продолжать выкачивать значения, пока наблюдатель не закроется.
Логика реализации такова: поскольку все простые числа, кроме 2, являются нечетными, мы начинаем с выдачи 2. Затем мы начинаем нашу процедуру с 3 и увеличиваем на 2 на каждом шаге. Давайте сначала предположим, что мы не заполнили наш список нечетных простых чисел.
Каждый раз, когда мы находим число, которое не делится ни на одно ранее найденное простое число, мы объявляем это число также простым числом, поэтому мы испускаем его и добавляем в наш список ранее увиденных нечетных простых чисел (все числа, найденные с помощью этот метод гарантированно будет нечетным числом). В случае, если оцениваемое число не является простым, мы продолжаем увеличивать значение на 2, пока не найдем число, которое является простым.
С другой стороны, в случае, если мы уже прошли этот шаг, мы просто делаем поиск в нашем списке observedOddPrimes. Обратите внимание, что внутренний outOddIndex для каждого экземпляра primes$ отслеживает только индекс для нечетных чисел. Он игнорирует начальную 2.
Также обратите внимание, что наш список ранее наблюдаемых нечетных простых чисел является внешним по отношению к фактической функции создания. Причина этого в том, что множество экземпляров primes$ может существовать одновременно или последовательно, и если бы мы сохранили массив внутри функции создания, он бы генерировался каждый раз, когда мы создаем primes$.
Предполагая, что в одном вызове может быть несколько подписок на primes$, мы не хотим создавать список каждый раз при создании экземпляра primes$. Однако мы хотим каждый раз создавать новую наблюдаемую последовательность, начинающуюся с 2. Таким образом, выбросы всегда начинаются с 2, увеличиваясь последовательно, но мы гарантируем, что вычисление следующего простого числа происходит только в том случае, если мы еще не вычислили его. Вычисление простых чисел стоит дорого, а поиск уже вычисленных простых чисел — нет.
Поскольку эта процедура является синхронной, мы также должны включить проверку того, закрыл ли наблюдатель свою подписку. Для эмиттеров синхронной последовательности можно с уверенностью предположить, что любой наблюдатель отменит подписку на основе значения предыдущей эмиссии, поэтому мы начинаем наш цикл, проверяя, закрылся ли наблюдатель, и если это так, мы прерываем цикл.
Наивное решение: PrimeFactors()
Теперь, когда у нас есть наблюдаемая последовательность простых чисел, нам нужно создать оператор для нахождения простых множителей числа. Мы собираемся продемонстрировать два способа сделать это. Давайте сначала посмотрим на наивный способ.
Мы начинаем с переключения на поток primes$, чтобы мы могли сравнить число, которое мы оцениваем, с простыми числами. В этом конкретном случае мы предполагаем, что входное число само по себе не является простым числом, так как задача просит нас найти его наибольший простой делитель, поэтому мы можем поставить одно важное ограничение при поиске простых делителей :
Самый большой возможный простой делитель непростого числа - это квадратный корень указанного числа.
Мы ограничиваем наши выбросы от prime$, используя takeWhile(prime => prime ≤ Math.sqrt(product)). Теперь некоторые из вас могут подумать, что этот подход немного сомнительный: не должны ли мы тогда начать с Math.sqrt(product) и постепенно уменьшать значение, пока не найдем простое число?
Мы могли бы… Но все же нам нужно было бы убедиться, что число, которое мы проверяем, действительно является простым числом, а это означает, что нам все еще нужно сгенерировать простые числа до этого числа.
Следующий шаг достаточно прост: мы фильтруем каждую простую эмиссию по кратности произведений на это число. Если оно делится, мы добавляем его к нашему массиву простых множителей, и это наше окончательное излучение.
taskThree затем просто использует этот оператор для произведения, и мы используем map, чтобы получить окончательный простой множитель, который будет самым большим простым множителем этого числа. Обратите внимание, что функция-создатель of создает наблюдаемый поток, состоящий из одного значения; его параметр.
Выполняя это, мы получаем правильный ответ, но время выполнения составляет колоссальные 8 секунд!
Так что мы, очевидно, можем добиться большего успеха, чем это. Как? Вернемся к файлу primeFactors.ts и посмотрим на вторую функцию.
Быстрое решение: PrimeFactorsImproved()
В этом случае мы подходим к проблеме немного по-другому. Предположим, мы начинаем с числа n, которое имеет простые делители p, являясь массивом простых чисел с индексами от 0 до m. Каждый раз, когда мы находим p(i), мы можем предположить, что n % p(i) = 0, но также и forni = n / p(i), ni % p(^i) = 0.
Конкретный пример на простом английском: число 42 имеет три простых делителя: 2, 3 и 7. Деление 42 на любой из них дает нам соответственно 21, 14 и 6. 21, 14, 6, и все они делятся на два других простых числа. факторы (21 по 7 и 3, 14 по 2 и 7, 6 по 2 и 3).
Хотя это не очень полезно для нахождения простых множителей, поскольку мы все равно фильтруем по делимости, это полезно для объявления границ нашего поиска. Как?
Предположим, что вместо того, чтобы объявлять квадратный корень нашего ввода в качестве верхней границы, мы объявляем, что сам ввод является верхней границей. Однако каждый раз, когда мы находим простой множитель, мы делим входные данные на эту верхнюю границу. Мы видим, что наша верхняя граница значительно сужается каждый раз, когда мы находим новый простой множитель, и поэтому наше пространство поиска сильно сужается.
То, как мы это делаем, может показаться не таким элегантным. Мы используем tap, чтобы просто переопределять произведение каждый раз, когда находим новое простое число. В общем, я бы сказал, что использование tap для переопределения значений, используемых в канале, не рекомендуется, но в этом случае это достаточно просто для понимания, и его поведение полностью ограничено этим каналом, поэтому я бы сказал, что это приемлемо.
Мы используем этот новый оператор точно так же, как и предыдущий. Мы видим, что получили правильный ответ, и наше время выполнения составляет 11 мс! Другими словами, это альтернативное решение примерно в 800 раз быстрее, чем предыдущее! Это большое улучшение! Сантехника RxJs для победы!
Сегодняшняя статья была посвящена тому, как более эффективно использовать конвейеры RxJ, демонстрируя их использование в более классическом программировании, связанном с математикой. Надеюсь, вы осознали потенциал многих этих каналов и то, как легко писать даже логически сложные процедуры с использованием RxJ!
