Я только что опубликовал библиотеку LazySeq на GitHub — результат моих экспериментов на Java 8 недавно. Я надеюсь, вам понравится. Даже если вы не находите это очень полезным, это все же отличный урок функционального программирования в Java 8 (и в целом). Также это, вероятно, первая библиотека сообщества, ориентированная на Java 8!
Вступление
Ленивая последовательность — это структура данных, которая вычисляется только тогда, когда ее элементы действительно необходимы. Все операции над отложенными последовательностями, такими как map() и filter() являются отложенными, откладывая вызов до момента, когда это действительно необходимо. Ленивые последовательности всегда просматриваются с самого начала с использованием очень дешевого first / rest
разложение ( head() и tail() ). Важным свойством ленивых последовательностей является то, что они могут представлять бесконечные потоки данных, например, все натуральные числа или измерения температуры во времени.
Ленивая последовательность запоминает уже вычисленные значения, поэтому, если вы обращаетесь к N-му элементу, все элементы от 1 до N-1 также вычисляются и кэшируются. Несмотря на это, LazySeq (являющийся ядром многих функциональных языков и алгоритмов) является неизменным и поточно-ориентированным.
обоснование
Эта библиотека в значительной степени вдохновлена scala.collection.immutable.Stream и предназначена для обеспечения неизменяемой, поточно-ориентированной и простой в использовании реализации scala.collection.immutable.Stream последовательностей, возможно, бесконечной. Посмотрите ленивые последовательности в Scala и Clojure для некоторых случаев использования.
Имя класса Stream уже используется в Java 8, поэтому был выбран LazySeq , аналогичный lazy-seq в Clojure . Говоря о Stream , поначалу это выглядит как ленивая реализация последовательности, доступная из коробки. Однако, цитируя Javadoc:
Потоки не являются структурами данных
и:
Когда операция выполняется в потоке, она считается использованной и больше не может использоваться для других операций.
Другими словами, java.util.stream.Stream — это просто тонкая оболочка вокруг существующей коллекции, подходящая для одноразового использования. Больше похоже на Iterator чем на Stream в Scala. Эта библиотека пытается заполнить эту нишу.
Конечно, реализация структуры данных с отложенной последовательностью была возможна до Java 8, но отсутствие лямбд делает работу с такой структурой данных утомительной и слишком многословной.
Начиная
Сборка и работа с ленивыми последовательностями за 10 минут.
Бесконечная последовательность всех натуральных чисел
Чтобы создать ленивую последовательность, вы используете фабричный метод LazySeq.cons() который принимает первый элемент ( head ) и функцию, которая позже может быть использована для вычисления rest ( tail ). Например, чтобы получить ленивую последовательность натуральных чисел с заданным начальным элементом, вы просто говорите:
|
1
2
3
|
private LazySeq<Integer> naturals(int from) { return LazySeq.cons(from, () -> naturals(from + 1));} |
Здесь действительно нет рекурсии. Если бы это было так, вызов naturals() быстро привел бы к StackOverflowError поскольку он вызывает себя без условия остановки. Однако выражение () -> naturals(from + 1) определяет функцию, возвращающую LazySeq<Integer> (точнее, Supplier ), которую будет вызывать эта структура данных, но только при необходимости. Посмотрите на код ниже, сколько раз вы думаете, что naturals() функция naturals() (кроме первой строки)?
|
1
2
3
4
5
6
7
8
9
|
final LazySeq<Integer> ints = naturals(2); final LazySeq<String> strings = ints. map(n -> n + 10). filter(n -> n % 2 == 0). take(10). flatMap(n -> Arrays.asList(0x10000 + n, n)). distinct(). map(Integer::toHexString); |
Первый вызов naturals(2) возвращает ленивую последовательность, начинающуюся с 2 но остальные ( 3 , 4 , 5 , …) еще не вычислены. Позже мы map() эту последовательность, filter() ее, take() первые 10 элементов, удалим дубликаты и т. Д. Все эти операции не оценивают последовательность и являются настолько ленивыми, насколько это возможно. Например, take(10) не оценивает первые 10 элементов с нетерпением, чтобы вернуть их. Вместо этого возвращается новая ленивая последовательность, которая помнит, что она должна обрезать оригинальную последовательность на 10-м элементе.
То же относится и к distinct() . Он не оценивает всю последовательность для извлечения всех уникальных значений (в противном случае приведенный выше код быстро взорвется, пройдя бесконечное количество натуральных чисел). Вместо этого он возвращает новую последовательность только с первым элементом. Если вы когда-нибудь попросите второй уникальный элемент, он будет лениво оценивать хвост, но только в максимально возможной степени. Проверять, выписываться
Вывод toString() :
|
1
2
|
System.out.println(strings);//[1000c, ?] |
Знак вопроса ( ? ) Говорит: «В этой коллекции может быть что-то еще, но я пока не знаю» . Вы понимаете, откуда 1000c ? Смотри внимательно:
- Начните с бесконечного потока натуральных чисел, начиная с
2 - Добавьте
10к каждому элементу (таким образом, первый элемент становится12илиCв шестнадцатеричном формате) -
filter()из нечетных чисел (12четных, так что остается) -
take()первые10элементов из последовательности - Каждый элемент заменяется двумя элементами: этот элемент плюс 0x1000 и сам элемент (
flatMap()). Это не дает последовательность пар, но последовательность целых чисел, которая в два раза длиннее - Мы гарантируем, что будут возвращены только
distinct()элементы - В конце мы превращаем целые числа в шестнадцатеричные строки.
Как видите, ни одна из этих операций не требует оценки всего потока. Только голова трансформируется, и это то, что мы видим в конце. Итак, когда эта структура данных действительно оценивается? Когда это абсолютно необходимо, например, во время прохождения побочного эффекта:
|
01
02
03
04
05
06
07
08
09
10
11
12
|
strings.force(); //orstrings.forEach(System.out::println); //orfinal List<String> list = strings.toList(); //orfor (String s : strings) { System.out.println(s);} |
Все приведенные выше утверждения приведут к оценке всей ленивой последовательности. Не очень умно, если наша последовательность была бесконечной, но
strings были ограничены первыми 10 элементами, поэтому они не будут работать бесконечно. Если вы хотите форсировать только часть последовательности, просто вызовите strings.take(5).force() . Кстати, вы заметили, что мы можем LazySeq strings используя стандартный синтаксис Java 5 для каждого? Это потому, что LazySeq реализует интерфейс List , таким образом, прекрасно работает с экосистемой Java Collections Framework :
|
1
2
3
|
import java.util.AbstractList; public abstract class LazySeq<E> extends AbstractList<E> |
Помните, что после вычисления (вычисления) ленивых последовательностей они будут кэшироваться ( запоминаться ) для последующего использования. Это делает ленивые последовательности большими для представления бесконечных или очень длинных потоков данных, которые дороги для вычисления.
iterate ()
Создание бесконечной ленивой последовательности очень часто сводится к предоставлению начального элемента и функции, которая производит следующий элемент на основе предыдущего. Другими словами, второй элемент является функцией первого, третий элемент является функцией второго и так далее. Для таких обстоятельств предусмотрена удобная LazySeq.iterate() . Определение ints теперь может выглядеть так:
|
1
|
final LazySeq<Integer> ints = LazySeq.iterate(2, n -> n + 1); |
Мы начинаем с 2 и каждый последующий элемент представляется как предыдущий элемент + 1.
Больше примеров: последовательность Фибоначчи и гипотеза Коллатца
Ни одна статья о ленивой структуре данных не может быть оставлена без примера чисел Фибоначчи :
|
1
2
3
4
5
6
|
private static LazySeq<Integer> lastTwoFib(int first, int second) { return LazySeq.cons( first, () -> lastTwoFib(second, first + second) );} |
Последовательность Фибоначчи также бесконечна, но мы можем преобразовать ее несколькими способами:
|
01
02
03
04
05
06
07
08
09
10
11
12
13
|
System.out.println( fib. drop(5). take(10). toList());//[5, 8, 13, 21, 34, 55, 89, 144, 233, 377] final int firstAbove1000 = fib. filter(n -> (n > 1000)). head(); fib.get(45); |
Видите, как легко и естественно работать с бесконечным потоком чисел? drop(5).take(10) пропускает первые 5 элементов и отображает следующие 10. В этот момент первые 15 чисел уже вычислены и никогда не будут вычислены снова.
Найти первое число Фибоначчи выше 1000 (бывает 1597 ) очень просто. Метод head() всегда предварительно вычисляется функцией filter() , поэтому дальнейшая оценка не требуется. И последнее, но не менее важное: мы можем просто попросить 45-е число Фибоначчи (на основе 0) и получить
1134903170 . Если вы когда-нибудь попытаетесь получить доступ к любому числу Фибоначчи, вплоть до этого, они будут предварительно рассчитаны и быстро найдены.
Конечные последовательности (гипотеза Коллатца)
Гипотеза Коллатца также является довольно интересной проблемой. Для каждого положительного целого числа n мы вычисляем следующее целое число, используя следующий алгоритм:
-
n/2еслиnчетное -
3n + 1еслиnнечетно
Например, начиная с 10 рядов выглядит следующим образом: 10, 5, 16, 8, 4, 2, 1. Ряд заканчивается, когда он достигает 1. Математики считают, что начиная с любого целого числа, мы в конечном итоге достигнем 1, но это еще не доказано.
Давайте создадим ленивую последовательность, которая генерирует ряды Коллатца для данного n , но только столько, сколько необходимо. Как указано выше, на этот раз наша последовательность будет конечной:
|
1
2
3
4
5
6
7
8
|
private LazySeq<Long> collatz(long from) { if (from > 1) { final long next = from % 2 == 0 ? from / 2 : from * 3 + 1; return LazySeq.cons(from, () -> collatz(next)); } else { return LazySeq.of(1L); }} |
Эта реализация определяется непосредственно определением. Для каждого числа больше 1 верните это число + лениво оцененный ( () -> collatz(next) ) остаток потока. Как вы можете видеть, если дано 1 , мы возвращаем ленивую последовательность of() одного элемента, используя специальный метод фабрики of() . Давайте проверим это с вышеупомянутыми 10 :
|
1
2
3
4
|
final LazySeq<Long> collatz = collatz(10); collatz.filter(n -> (n > 10)).head();collatz.size(); |
filter() позволяет нам найти первое число в последовательности больше 10 . Помните, что ленивая последовательность должна будет проходить содержимое (оценивать себя), но только до точки, где она находит первый соответствующий элемент. Затем он останавливается, гарантируя, что он вычисляет как можно меньше.
Однако size() , чтобы вычислить общее количество элементов, должно пройти всю последовательность. Конечно, это может работать только с конечными ленивыми последовательностями, вызов size() для бесконечной последовательности будет плохо заканчиваться.
Если вы немного поиграете с этой последовательностью, вы быстро поймете, что последовательности для разных чисел имеют один и тот же суффикс (всегда заканчиваются одинаковой последовательностью чисел). Это требует некоторого кеширования / структурного обмена. См. CollatzConjectureTest для подробностей.
Но может ли он быть к чему-то полезен, знаете ли … полезным? Реальная жизнь?
Бесконечные последовательности чисел велики, но не очень практичны в реальной жизни. Может быть, еще несколько простых примеров? Представьте, что у вас есть коллекция, и вам нужно выбрать несколько предметов из этой коллекции случайным образом. Вместо коллекции я буду использовать функцию, возвращающую случайные латинские символы:
|
1
2
3
|
private char randomChar() { return (char) ('A' + (int) (Math.random() * ('Z' - 'A' + 1)));} |
Но есть поворот. Вам нужно N (N <26, количество латинских символов) уникальных значений. Простой вызов randomChar() несколько раз не гарантирует уникальность. Есть несколько подходов к этой проблеме, с LazySeq это довольно просто:
|
1
2
|
LazySeq<Character> charStream = LazySeq.<Character>continually(this::randomChar);LazySeq<Character> uniqueCharStream = charStream.distinct(); |
continually() просто вызывает данную функцию для каждого элемента, когда это необходимо. Таким образом, charStream будет бесконечным потоком случайных символов. Конечно, они не могут быть уникальными. Однако uniqueCharStream гарантирует, что его вывод уникален. Это делается путем изучения следующего элемента базового charStream и отклонения уже появившихся элементов. Теперь мы можем сказать uniqueCharStream.take(4) и быть уверенными, что дубликаты не появятся.
Еще раз обратите внимание, что continually(this::randomChar).distinct().take(4) действительно вызывает randomChar() только один раз! Пока вы не используете эту последовательность, она остается ленивой и откладывает оценку как можно дольше.
Другой пример включает загрузку пакетов (страниц) данных из базы данных. Использование ResultSet или Iterator обременительно, но загрузка всего набора данных в память часто неосуществима. Альтернатива заключается в быстрой загрузке первой партии данных, а затем в предоставлении функции для загрузки следующих партий. Данные загружаются только тогда, когда они действительно необходимы, и мы не испытываем проблем с производительностью или масштабируемостью.
Сначала давайте определим абстрактный API для загрузки пакетов данных из базы данных:
|
1
2
3
|
public List<Record> loadPage(int offset, int max) { //load records from offset to offset + max} |
Я полностью абстрагируюсь от технологии, но вы понимаете суть. Представьте, что теперь мы определяем LazySeq<Record> который начинается со строки 0 и загружает следующие страницы только при необходимости:
|
1
2
3
4
5
6
7
8
|
public static final int PAGE_SIZE = 5; private LazySeq<Record> records(int from) { return LazySeq.concat( loadPage(from, PAGE_SIZE), () -> records(from + PAGE_SIZE) );} |
При создании нового LazySeq<Record> путем вызова records(0) загружается первая страница из 5 элементов. Это означает, что первые 5 элементов последовательности уже вычислены. Если вы когда-нибудь попытаетесь получить доступ к 6-му или более высокому, последовательность автоматически загрузит все отсутствующие записи и кеширует их. Другими словами, вы никогда не вычисляете один и тот же элемент дважды.
Более полезные инструменты при работе с последовательностями — это методы grouped() и sliding() . Первые разделы вводят последовательность в группы одинакового размера. Возьмите это в качестве примера, также доказав, что эти методы как всегда ленивы:
|
1
2
3
4
5
6
7
|
final LazySeq<Character> chars = LazySeq.of('A', 'B', 'C', 'D', 'E', 'F', 'G'); chars.grouped(3);//[[A, B, C], ?] chars.grouped(3).force(); //force evaluation//[[A, B, C], [D, E, F], [G]] |
и аналогично для sliding() :
|
1
2
3
4
5
|
chars.sliding(3);//[[A, B, C], ?] chars.sliding(3).force(); //force evaluation//[[A, B, C], [B, C, D], [C, D, E], [D, E, F], [E, F, G]] |
Эти два метода чрезвычайно полезны. Вы можете просматривать свои данные через скользящее окно (например, для вычисления скользящего среднего ) или разбивать их на сегменты равной длины.
Последний интересный полезный метод, который вы можете найти полезным — это scan() который (конечно, лениво) выполняет входной поток и создает каждый элемент вывода, применяя функцию к предыдущему и текущему элементу ввода. Фрагмент кода стоит тысячи слов:
|
1
2
3
4
5
|
LazySeq<Integer> list = LazySeq. numbers(1). scan(0, (a, x) -> a + x); list.take(10).force(); //[0, 1, 3, 6, 10, 15, 21, 28, 36, 45] |
LazySeq.numbers(1) — это последовательность натуральных чисел (1, 2, 3…). scan() создает новую последовательность, которая начинается с
0 и для каждого элемента ввода (натуральные числа) добавляет его к последнему элементу самого себя. Итак, мы получаем: [ 0 , 0+1 , 0+1+2 , 0+1+2+3 , 0+1+2+3+4 , 0+1+2+3+4+5 …]. Если вы хотите последовательность растущих строк, просто замените несколько типов:
|
1
2
3
4
5
|
LazySeq.continually("*"). scan("", (s, c) -> s + c). map(s -> "|" + s + "\\"). take(10). forEach(System.out::println); |
И наслаждайтесь этим прекрасным треугольником:
|
01
02
03
04
05
06
07
08
09
10
|
|\|*\|**\|***\|****\|*****\|******\|*******\|********\|*********\ |
Альтернативно (тот же вывод):
|
1
2
3
4
|
LazySeq.iterate("", s -> s + "*"). map(s -> "|" + s + "\\"). take(10). forEach(System.out::println); |
Совместимость инфраструктуры коллекций Java
LazySeq реализует интерфейс java.util.List , поэтому его можно использовать в самых разных местах. Кроме того, он также реализует улучшения Java 8 для коллекций, а именно потоков и сборщиков:
|
01
02
03
04
05
06
07
08
09
10
|
lazySeq. stream(). map(n -> n + 1). flatMap(n -> asList(0, n - 1).stream()). filter(n -> n != 0). substream(4, 18). limit(10). sorted(). distinct(). collect(Collectors.toList()); |
Однако потоки в Java 8 были созданы, чтобы обойти функцию, которая является основой LazySeq — ленивая оценка. Приведенный выше пример откладывает все промежуточные шаги до collect() . С LazySeq вы можете безопасно пропустить .stream() и работать непосредственно с последовательностью:
|
1
2
3
4
5
6
7
8
|
lazySeq. map(n -> n + 1). flatMap(n -> asList(0, n - 1)). filter(n -> n != 0). slice(4, 18). limit(10). sorted(). distinct(); |
Более того, LazySeq предоставляет сборщик специального назначения (см. LazySeq.toLazySeq() ), который избегает оценки даже при использовании с collect() что обычно приводит к полному вычислению коллекции.
Детали реализации
Каждая ленивая последовательность построена вокруг идеи жадно вычисленной головы и лениво оцененного хвоста, представленного как функция. Это очень похоже на рекурсивное определение классического односвязного списка:
|
1
2
3
4
5
|
class List<T> { private final T head; private final List<T> tail; //...} |
Однако в случае ленивой последовательности хвост задается как функция, а не как значение. Вызов этой функции откладывается как можно дольше:
|
01
02
03
04
05
06
07
08
09
10
11
12
|
class Cons<E> extends LazySeq<E> { private final E head; private LazySeq<E> tailOrNull; private final Supplier<LazySeq<E>> tailFun; @Override public LazySeq<E> tail() { if (tailOrNull == null) { tailOrNull = tailFun.get(); } return tailOrNull; } |
Для полной реализации см. Cons.java и FixedCons.java используемые, когда tail известен во время создания (например, LazySeq.of(1, 2) в отличие от LazySeq.cons(1, () -> someTailFun() ).
Подводные камни и общие опасности
Ниже описаны общие проблемы и недоразумения.
Оценивая слишком много
Одна из самых больших опасностей работы с бесконечными последовательностями — попытка полностью их оценить, что, очевидно, приводит к бесконечным вычислениям. Идея бесконечной последовательности состоит не в ее полной оценке, а в том, чтобы взять столько, сколько нам нужно, без введения искусственных ограничений и случайной сложности (см. Пример загрузки базы данных).
Однако оценить всю последовательность слишком просто, чтобы ее упустить. Например, вызов LazySeq.size() должен оценить всю последовательность и будет выполняться бесконечно, в конечном итоге заполняя стек или кучу (подробности реализации). Есть другие методы, которые требуют полного обхода, чтобы функционировать должным образом. Например, allMatch() соответствие всех элементов заданному предикату. Некоторые методы еще более опасны, потому что закончится они или нет, зависит от данных в последовательности. Например, anyMatch() может вернуться немедленно, если head соответствует предикату, или никогда.
Иногда мы можем легко избежать дорогостоящих операций, используя более детерминированные методы. Например:
|
1
|
seq.size() <= 10 //BAD |
может не работать или быть очень медленным, если seq бесконечен. Однако мы можем добиться того же с (более) предсказуемым:
|
1
|
seq.drop(10).isEmpty() |
Помните, что ленивые последовательности являются неизменяемыми (поэтому мы не изменяем seq ), drop(n) обычно равен O(n) а isEmpty() — O(1) .
В случае сомнений обратитесь к исходному коду или JavaDoc, чтобы убедиться, что ваша операция не будет слишком охотно оценивать вашу последовательность. Также будьте очень осторожны при использовании LazySeq где LazySeq java.util.Collection или java.util.List .
Проведение ненужной ссылки на голову
Ленивые последовательности по определению запоминают уже вычисленные элементы. Вы должны знать об этом, иначе ваша последовательность (особенно бесконечная) быстро заполнит доступную память. Тем не менее, поскольку LazySeq — просто причудливый связанный список, если вы больше не сохраняете ссылку на LazySeq (а только на некоторый элемент в середине), он становится пригодным для сбора мусора. Например:
|
1
2
|
//LazySeq<Char> first = seq.take(10);seq = seq.drop(10); |
Первые десять элементов отброшены, и мы предполагаем, что ничто не содержит ссылку на то, что ранее было в seq . Это делает первые десять элементов подходящими для сборки мусора. Однако, если мы раскомментируем первую строку и вначале сохраним ссылку на старый заголовок, JVM не освободит память. Давайте рассмотрим это в перспективе. Следующий фрагмент кода в конечном итоге выкинет OutOfMemoryError потому что infinite ссылка продолжает содержать начало последовательности, поэтому все элементы, созданные до сих пор:
|
1
2
3
4
|
LazySeq<Big> infinite = LazySeq.<Big>continually(Big::new);for (Big arr : infinite) { //} |
Тем не менее, путем встраивания вызова continually() или извлечения его в метод этот код работает безупречно (ну, все равно работает вечно, но почти не использует память):
|
1
2
3
4
5
6
7
|
private LazySeq<Big> getContinually() { return LazySeq.<Big>continually(Big::new);} for (Big arr : getContinually()) { //} |
Какая разница? Для каждого цикла используются итераторы внизу. LazySeqIterator внизу не содержит ссылку на старый head() когда он продвигается, поэтому, если ничто больше не ссылается на этот заголовок, он будет иметь право на сборку мусора, смотрите истинный вывод javac при использовании for-each:
|
1
2
3
4
|
for (Iterator<Big> cur = getContinually().iterator(); cur.hasNext(); ) { final Big arr = cur.next(); //...} |
TL; DR
Ваша последовательность растет при прохождении. Если вы продолжаете держать один конец, пока другой растет, он в конечном итоге взорвется. Точно так же, как ваш кэш первого уровня в Hibernate, если вы загружаете слишком много за одну транзакцию. Используйте только столько, сколько необходимо.
Преобразование в простые коллекции Java
Конвертировать просто, но опасно. Это следствие пунктов выше. Вы можете преобразовать ленивую последовательность в java.util.List , вызвав toList() :
|
1
2
|
LazySeq<Integer> even = LazySeq.numbers(0, 2);even.take(5).toList(); //[0, 2, 4, 6, 8] |
или используя Collector из Java 8 с более богатым API:
|
1
2
3
4
|
even. stream(). limit(5). collect(Collectors.toSet()) //[4, 6, 0, 2, 8] |
Но помните, что коллекции Java конечны из определения, поэтому избегайте явного преобразования ленивых последовательностей в коллекции. Обратите внимание, что
LazySeq — это уже List , следовательно, Iterable и Collection . Он также имеет эффективный LazySeq.iterator() . Если вы можете просто передать экземпляр LazySeq напрямую и он может просто работать.
Производительность, временная и пространственная сложность
head() каждой последовательности (кроме пустой) всегда вычисляется с нетерпением, поэтому доступ к ней происходит быстро O(1) . Вычисление tail() может взять все от O(1) (если оно уже было вычислено) до бесконечного времени. В качестве примера возьмем этот допустимый поток:
|
1
2
3
4
5
6
7
8
|
import static com.blogspot.nurkiewicz.lazyseq.LazySeq.cons;import static com.blogspot.nurkiewicz.lazyseq.LazySeq.continually; LazySeq<Integer> oneAndZeros = cons( 1, () -> continually(0)).filter(x -> (x > 0)); |
Он представляет 1 за которым следует бесконечное число 0 с. Отфильтровывая все положительные числа ( x > 0 ), мы получаем последовательность с той же головой, но фильтрация хвоста задерживается (лениво). Однако, если мы теперь небрежно вызовем oneAndZeros.tail() , LazySeq будет продолжать вычислять все больше и больше этой бесконечной последовательности, но, поскольку после начальной 1 нет положительного элемента, эта операция будет выполняться вечно, в конечном итоге выбрасывая StackOverflowError или OutOfMemoryError (это детали реализации).
Однако, если вы когда-нибудь достигнете этого состояния, это, вероятно, программная ошибка или неправильное использование библиотеки. Обычно tail() будет близко к O(1) . С другой стороны, если у вас уже есть много операций, которые уже «сложены», вызов tail() будет запускать их быстро один за другим, поэтому время выполнения tail() сильно зависит от вашей структуры данных.
Большинство операций на LazySeq — O(1) так как они ленивы. Некоторые операции, такие как get(n) или drop(n) являются O(n) ( n представляет параметр, а не длину последовательности). В целом время выполнения будет похоже на обычный связанный список.
Поскольку LazySeq запоминает все уже вычисленные значения в одном связанном списке, потребление памяти всегда равно O(n) , где n n — количество уже вычисленных элементов.
Поиск проблемы
Ошибка invalid target release: 1.8 во время сборки maven
Если вы видите это сообщение об ошибке во время сборки maven:
|
1
2
3
4
|
[INFO] BUILD FAILURE...[ERROR] Failed to execute goal org.apache.maven.plugins:maven-compiler-plugin:3.1:compile (default-compile) on project lazyseq:Fatal error compiling: invalid target release: 1.8 -> [Help 1] |
это означает, что вы не компилируете с использованием Java 8. Загрузите JDK 8 с поддержкой лямбды и позвольте maven использовать его:
|
1
|
$ export JAVA_HOME=/path/to/jdk8 |
Я получаю StackOverflowError или программа зависает бесконечно
При работе с LazySeq вы иногда получаете StackOverflowError или OutOfMemoryError :
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
|
java.lang.StackOverflowError at sun.misc.Unsafe.allocateInstance(Native Method) at java.lang.invoke.DirectMethodHandle.allocateInstance(DirectMethodHandle.java:426) at com.blogspot.nurkiewicz.lazyseq.LazySeq.iterate(LazySeq.java:118) at com.blogspot.nurkiewicz.lazyseq.LazySeq.lambda$0(LazySeq.java:118) at com.blogspot.nurkiewicz.lazyseq.LazySeq$$Lambda$2.get(Unknown Source) at com.blogspot.nurkiewicz.lazyseq.Cons.tail(Cons.java:32) at com.blogspot.nurkiewicz.lazyseq.LazySeq.size(LazySeq.java:325) at com.blogspot.nurkiewicz.lazyseq.LazySeq.size(LazySeq.java:325) at com.blogspot.nurkiewicz.lazyseq.LazySeq.size(LazySeq.java:325) at com.blogspot.nurkiewicz.lazyseq.LazySeq.size(LazySeq.java:325) at com.blogspot.nurkiewicz.lazyseq.LazySeq.size(LazySeq.java:325) at com.blogspot.nurkiewicz.lazyseq.LazySeq.size(LazySeq.java:325) at com.blogspot.nurkiewicz.lazyseq.LazySeq.size(LazySeq.java:325) |
При работе с возможно бесконечными структурами данных необходимо соблюдать осторожность. Избегайте вызова операций, которые должны ( size() , allMatch() , minBy() , forEach() allMatch() , minBy() ,…) или могут ( filter() , distinct() ,…) пройти всю последовательность, чтобы дать правильный полученные результаты. Посмотрите Подводные камни для большего количества примеров и способов избежать.
зрелость
Качество
Этот проект был начат как упражнение и не проверен в бою. Но здоровый набор из 300+ модульных тестов (соотношение тестового кода к производственному коду 3: 1) гарантирует качество и функциональную корректность. Я также удостоверяюсь, что LazySeq настолько ленив, насколько возможно, высмеивая хвостовые функции и проверяя, что они вызываются настолько редко, насколько это возможно.
Вклады и сообщения об ошибках
В случае обнаружения ошибки или отсутствующей функции, не стесняйтесь открыть новый тикет или начать тянуть запрос . Я также хотел бы видеть более интересные использования LazySeq в дикой природе.
Возможные улучшения
- Так же, как
FixedConsиспользуется, когда tail известенFixedCons, рассмотримIterableConsкоторый оборачивает существующиеIterableв один узел, а не строит иерархиюFixedCons. Это может быть использовано для всех методовconcat. - Поддержка параллельной обработки (реализация spliterator?)
Лицензия
Этот проект выпущен под версией 2.0 лицензии Apache .