Автор немного затрагивал тему ленивых вычислений. В этой заметке разберём поподробнее.
Ленивые последовательности (также известные как потоки (aka streams)) представляют собой интересную функциональную структуру данных. В основном, ленивая последовательность – это список, который не полностью известен / вычислен, пока вы его не используете. В этом отличительная особенность ленивых вычислений в отличие от “жадных” (eager). Давайте посмотрим на примере.
Представим, что существует неупорядоченный массив arr из 10000 неуникальных элементов, являющихся целыми числами в диапазоне [-100, 100] ([2,-8, 46, -1, 42, -1 , ..., 0, -5]). И поставим задачу:
Найти среди уникальных удвоенных значений положительных нечётных чисел 10 наибольших.
function task_chaning(arr) {
let r =
arr
.filter(x => x > 0) // оставляем положительные
.filter(x => x % 2 != 0) // оставляем нечётные
.reduce((acc, e) => { // оставляем уникальные
if (!acc.includes(e)) {
acc.push(e)
}
return acc
}, [])
.map(x => x * 2) // удваиваем
.sort((a, b) => a - b) // сортируем от меньшего к большему
// берём 10 наибольших
return r.slice(r.length < 10 ? 0 : r.length - 10)
}
Как вы можете заметить после каждого вызова из методов map, filter, reduce и slice создаётся новый массив (вспоминаем о том, что исходный массив из 10000 элементов). Даже если мы объединим первые два фильтра в один - это не сильно поможет.
Выглядит красиво, но не очень здорово из-за создания массивов на этапе промежуточных вычислений.
for-loopfunction task_loops(arr) {
let r = []
for (const element of arr) {
if (element < 0) continue // оставляем положительные
if (element % 2 == 0) continue // оставляем нечётные
if (!r.includes(element)) { // оставляем уникальные
r.push(element)
}
}
for (let i = 0; i < r.length; i++) {
r[i] = r[i] * 2; // удваиваем
}
r.sort((a, b) => a - b) // сортируем
// берём 10 наибольших
return r.slice(r.length < 10 ? 0 : r.length - 10);
}
Здесь получилось избежать ненужных созданий массивов в промежуточных этапах, где это возможно.
Однако, это решение слабо параметризуется - если в первом случае была возможность при необходимости передавать функции фильтрации или трансформации в качестве аргументов, то здесь это не очень простая задача.
Могут ли помочь с задачей ленивые последовательности? Выясним это чуть позже, а пока что реализуем несколько вариантов ленивых последовательностей.
В javaScript есть функции-генераторы, но автор намеренно не использует их… как впрочем и классы, стараясь обойтись только старыми добрыми функциями.
Одна из простейших реализаций ленивой последовательности может быть выражена примерно так:
function sequence_gen(seed, next_f) {
let next = seed
return () => {
let current = next
next = next_f(next)
return current
}
}
Да - и это всё. sequence_gen принимает в качестве аргументов seed - первый элемент последовательности и next_f - функцию создания следующего элемента на основании текущего элемента. Тело возвращаемой функции замыкает переменную next и обновляет её при каждом своём вызове.
const seq = sequence_gen(0, i => i + 1)
seq() // 0
seq() // 1
seq() // 2
//...
И так далее. Ещё раз - обратите внимание, что следующий элемент генерируется только в момент вызова.
Ранее функция range уже была реализована, но её можно немного модифицировать и расширить её возможности
// вспомогательная функция
function orElse(a, f) {
return a != undefined ? a : f()
}
function range({ from, to, step } = {}) {
const _from = orElse(from, () => 0)
const _step = orElse(step, () => 1)
const _to = orElse(to, () => _step > 0 ? Number.MAX_SAFE_INTEGER : Number.MIN_SAFE_INTEGER)
let next = _from
return () => {
let current = next
if (Math.abs(_to - current) < Math.abs(_step)) return null
next = next + _step
return current;
}
}
Или мы можем использовать функцию ранее написанную функцию sequence_gen:
function range({ from, to, step } = {}) {
const _from = orElse(from, () => 0)
const _step = orElse(step, () => 1)
const _to = orElse(to, () => _step > 0 ? Number.MAX_SAFE_INTEGER : Number.MIN_SAFE_INTEGER)
return sequence_gen(_from, (curr) => Math.abs(_to - curr) < Math.abs(_step)? null : curr + _step)
}
Теперь функция range может учитывать шаг движения по последовательности.
Для простоты, сделаем допущение, что
null- признак конца последовательности. Так же можно для этого использовать какую-либо специальную константу или символ.
let r = range({from: 1, to: 10, step: 3})
r() // 1
r() // 4
r() // 7
r() // null
Как вы можете заметить двигаться можно как с положительным шагом, так и с отрицательным. А так же можно сгенерировать “бесконечную” последовательность опустив to
seq_array превращает массив в ленивую последовательность (сразу же воспользуемся sequence_gen, но с некоторым трюком):
function seq_array(arr) {
if (arr.length == 0) return () => null
let idx = 0
return sequence_gen(arr[idx], () => idx < arr.length - 1 ? arr[++idx] : null)
}
или же в js мы можем воспользоваться итератором у массива:
function seq_array(arr) {
if (arr.length == 0) return () => null
const iter = arr[Symbol.iterator]();
return () => {
let n = iter.next()
if (n.done) return null
return n.value
}
let sa = seq_array([1,2,3])
sa() // 1
sa() // 2
sa() // 3
sa() // null
Так же можно реализовать интересный вариант зацикленной последовательности на основе массива:
function circle(arr) {
if (arr.length == 0) return () => null
let idx = 0
return () => {
idx = idx != arr.length? idx : 0
return arr[idx++]
}
}
let ca = circle([1,2,3])
ca() // 1
ca() // 2
ca() // 3
ca() // 1
// ...
Реализуем несколько функций, которые продемонстрируют работу с ленивыми последовательностями, а также помогут справиться с поставленной задачей. Функции работы с ленивыми последовательностями можно условно разделить на два типа - они отличаются по поведению:
map, skip, filtertake, count, reduce, sum и т.д. - особенно внимательно при использовании этих функций нужно отнестись во время работы с потенциально бесконечными последовательностями.skip, как можно понять из названия, пропускает одно или несколько значений последовательности.
function skip(number, lazy_seq) {
if (number <= 0) return lazy_seq
lazy_seq()
return skip(number - 1, lazy_seq)
}
Чтобы впустую не вызывать
lazy_seq()в случае, если последовательность закончилась можно сделать замену:lazy_seq()=>if (lazy_seq() == null) return lazy_seq
Для демонстрации подойдёт любая из функций генераторов последовательности, возьмём например range
let r = range({from: 3})
r() // 3
r() // 4
let skip3 = skip(3, r)
skip3() // 8
skip3() // 9
...
Обратите внимание: из-за ленивости вычислений, происходит вычисление и пропуск только заданного числа элементов (3).
Если skip отрабатывает лишь один раз, то map “накладывает эффект” трансформации на каждый элемент последовательности, но только при запросе этого элемента
function map(f, lazy_seq) {
return () => {
let item = lazy_seq()
return (item == null) ? item : f(item)
}
}
мы так же можем скомбинировать map и skip :
let r = range({from: 3})
r() // 3
r() // 4
let sm = map(x => x * 3, skip(3, r)) // пропускаем 5,6,7
sm() // 24
sm() // 27
В случае с filter - элемент последовательности проверяется на соответствие некоторому условию (pred), если возвращается true - элемент возвращается в качестве результата; если false - берётся следующий элемент, пока не найдётся подходящий или последовательность не закончится.
function filter(pred, lazy_seq) {
return () => {
let r = lazy_seq()
if (r == null) return r
return pred(r) ? r : filter(pred, lazy_seq)()
}
}
const is_odd = x => x % 2 != 0
let fr = filter(is_odd, range())
fr() // 1
fr() // 3
fr() // 5
// ...
reduce как и ожидается - собирает всю последовательность в аккумулятор
не использовать с бесконечными последовательностями
function reduce(reducer, acc, lazy_seq) {
let next = lazy_seq()
if (next == null) return acc
return reduce(reducer, reducer(acc, next), lazy_seq)
}
reduce((acc, item) => [...acc, item], [], range({from: 2 to: 20}))
// [2,3,4,5,..., 19]
Автор предлагает читателю самостоятельно реализовать функции
sumиcount
take “забирает” из последовательности указанное число элементов.
function take(number, lazy_seq) {
let take_f = range({ from: number, to: 0, step: -1 })
return reduce((acc) => {
let r = lazy_seq()
return r == null ? acc : [...acc, r]
}, [], take_f)
}
Разумеется, есть больше, чем один способ реализации функции
take. Автор не претендует на единственно верное решение.
take(5, range({from: 2 to: 20})) // [2,3,4,5,6]
- Реализовать функцию
take_while, принимающую в качестве первого аргумента не число, а функцию-условие для элементов последовательности:- пока оно истинно - элементы забираются из последовательности;
- когда условие не выполняется - сразу же возвращается аккумулированный результат из предыдущих элементов последовательности
Кажется, что реализованных функций работы с ленивыми последовательностями более чем достаточно для решения поставленной ранее задачи. Напомним в чём она заключается:
Найти среди уникальных удвоенных значений положительных нечётных чисел 10 наибольших.
function task_lazy(arr) {
let seq = seq_array(arr)
let filtered = filter(x => x % 2 != 0, filter((i) => i >= 0, seq))
let uniq = reduce((acc, e) => {
if (!acc.includes(e)) { acc.push(e) }
return acc},[], filtered)
let r = uniq
.map(x => x * 2)
.sort((a, b) => a - b)
return r.slice(r.length < 10 ? 0 : r.length - 10);
}
Выглядит достаточно страшно, однако на протяжении первой части (до удвоения, сортировки и выборки 10 наибольших элементов) новый массив создаётся только, на моменте вызова reduce.
Улучшить удобство при работе с ленивыми последовательностями автор попытается в следующей секции
Надеюсь читателю что-то говорит слово piping (в контексте Unix систем или конкретных языков программирования). Автор реализовал три небольшие функции, которые позволят сделать работу с ленивыми последовательностями (и не только) более приятной:
function $pipe$(value) {
return (...ffs) => ffs.reduce((v, f) => f(v), value)
}
function $pipe(f) {
return (...args) => (pipable) => f(pipable, ...args)
}
function pipe$(f) {
return (...args) => (pipable) => f(...args, pipable)
}
Суть данных функций “инжектировать” некоторый элемент в качестве первого ($pipe) или последнего (pipe$) аргумента для некоторой функции помимо остальных её аргументов.
Пример:
const subs = (x,y) => x - y
$pipe$(5)(
$pipe(subs)(2),
$pipe(subs)(1)
) // 2
$pipe$(5)(
pipe$(subs)(2),
pipe$(subs)(1)
) // -2
Нечто похожее автор реализовывал, когда пытался “познакомить” pattern matching и js
И применительно к задаче с ленивыми последовательностями получится примерно так:
function task_lazy_piping(arr) {
return $pipe$(seq_array(arr))(
pipe$(filter)(i => i >= 0),
pipe$(filter)(x => x % 2 != 0),
pipe$(reduce)((acc, e) => {
if (!acc.includes(e)) { acc.push(e) }
return acc},[]),
// БОЛЕЕ ТОГО !
$pipe((uniq, f) => uniq.map(f))(x=>x*2),
$pipe((doubled, sort_f) => doubled.sort(sort_f))((a, b) => a - b),
$pipe((s, n) => s.slice(s.length < n ? 0 : s.length - n))(10)
)
}
Читатель может убедиться, что результат выполнения всех вариантов решения одной и той же задачи - одинаковый.
Подводя итоги, автор хотел бы подчеркнуть основную идею ленивых вычислений: do it later. При работе с данными далеко не всегда нужно вычислять всё сразу - бывает, что, исходя из логики, можно избежать долгих или тяжеловесных вычислений, просто отложив их и выполнить их лишь в тот момент когда и если они понадобятся.
Те простые функции и механизмы продемонстрированные в рамках этой заметки при работе с ленивыми вычислениями даже при “поддержке” piping, по мнению автора, по своим возможностям находятся на несколько ступеней ниже, чем transdusers, которые позволяют легко многократно использовать и переиспользовать логику по обработке данных.