Разделение списка в подсписках по элементам

У меня есть этот список ( List ):

 ["a", "b", null, "c", null, "d", "e"] 

И мне хотелось бы что-то вроде этого:

 [["a", "b"], ["c"], ["d", "e"]] 

Другими словами, я хочу разбить мой список в подсписках, используя значение null качестве разделителя, чтобы получить список списков ( List<List> ). Я ищу решение Java 8. Я пробовал с Collectors.partitioningBy но я не уверен, что это то, что я ищу. Благодаря!

Единственное решение, которое я придумал на данный момент, – это реализовать свой собственный сборщик.

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

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

Это не является желательным поведением, и его следует избегать . Вот почему я делаю исключение в части комбайнера (вместо (l1, l2) -> {l1.addAll(l2); return l1;} ), поскольку он используется параллельно при объединении двух списков, так что у вас есть исключение вместо неправильного результата.

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

Итак, вот реализация коллектора:

 private static Collector>, List>> splitBySeparator(Predicate sep) { final List current = new ArrayList<>(); return Collector.of(() -> new ArrayList>(), (l, elem) -> { if (sep.test(elem)) { l.add(new ArrayList<>(current)); current.clear(); } else { current.add(elem); } }, (l1, l2) -> { throw new RuntimeException("Should not run this in parallel"); }, l -> { if (current.size() != 0) { l.add(current); return l; } ); } 

и как его использовать:

 List> ll = list.stream().collect(splitBySeparator(Objects::isNull)); 

Вывод:

 [[a, b], [c], [d, e]] 

Поскольку ответ Юопа Эггена отсутствует , похоже, что это можно сделать параллельно (дайте ему за это честь!). При этом он уменьшает реализацию пользовательского коллектора до:

 private static Collector>, List>> splitBySeparator(Predicate sep) { return Collector.of(() -> new ArrayList>(Arrays.asList(new ArrayList<>())), (l, elem) -> {if(sep.test(elem)){l.add(new ArrayList<>());} else l.get(l.size()-1).add(elem);}, (l1, l2) -> {l1.get(l1.size() - 1).addAll(l2.remove(0)); l1.addAll(l2); return l1;}); } 

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


Обратите внимание, что Stream API не всегда является заменой. Есть задачи, которые проще и удобнее использовать streamи, и есть задачи, которые нет. В вашем случае вы также можете создать для этого метод утилиты:

 private static  List> splitBySeparator(List list, Predicate predicate) { final List> finalList = new ArrayList<>(); int fromIndex = 0; int toIndex = 0; for(T elem : list) { if(predicate.test(elem)) { finalList.add(list.subList(fromIndex, toIndex)); fromIndex = toIndex + 1; } toIndex++; } if(fromIndex != toIndex) { finalList.add(list.subList(fromIndex, toIndex)); } return finalList; } 

и назовите его как List> list = splitBySeparator(originalList, Objects::isNull); ,

Его можно улучшить для проверки крайних случаев.

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

Во-первых, это обычное решение для обсуждения и анализа:

 static List> splitConventional(List input) { List> result = new ArrayList<>(); int prev = 0; for (int cur = 0; cur < input.size(); cur++) { if (input.get(cur) == null) { result.add(input.subList(prev, cur)); prev = cur + 1; } } result.add(input.subList(prev, input.size())); return result; } 

Это в основном просто, но есть немного тонкости. Один момент состоит в том, что ожидающий подсписок от prev до cur всегда открыт. Когда мы сталкиваемся с null мы закрываем его, добавляем в список результатов и продвигаем вперед. После цикла мы закрываем подсписку безоговорочно.

Другое наблюдение заключается в том, что это цикл по индексам, а не по самим значениям, поэтому мы используем арифметику for-loop вместо расширенного цикла «для каждого». Но это предполагает, что мы можем использовать индексы для генерации поддиапазонов вместо streamовой передачи значений и ввода логики в коллекционер (как это было сделано с помощью предлагаемого решения Joop Eggen ).

Как только мы это осознали, мы можем видеть, что каждая позиция null во вводе является разделителем для подсписчика: это правый конец подслова слева, и он (плюс один) является левым концом подсписчика право. Если мы сможем обрабатывать случаи краев, это приводит к подходу, в котором мы находим индексы, в которых встречаются null элементы, сопоставляем их с подсписками и собираем подсписки.

Итоговый код выглядит следующим образом:

 static List> splitStream(List input) { int[] indexes = Stream.of(IntStream.of(-1), IntStream.range(0, input.size()) .filter(i -> input.get(i) == null), IntStream.of(input.size())) .flatMapToInt(s -> s) .toArray(); return IntStream.range(0, indexes.length-1) .mapToObj(i -> input.subList(indexes[i]+1, indexes[i+1])) .collect(toList()); } 

Получение индексов, при которых происходит null довольно просто. Блок преткновения добавляет -1 слева и size на правом конце. Я решил использовать Stream.of для добавления, а затем flatMapToInt чтобы сгладить их. (Я попробовал несколько других подходов, но этот казался самым чистым).

Здесь гораздо удобнее использовать массивы для индексов. Во-первых, нотация для доступа к массиву лучше, чем для List: indexes[i] vs. indexes.get(i) . Во-вторых, использование массива позволяет избежать бокса.

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

обсуждение

Подход streamов немного короче, чем версия for-loop, но она более плотная. Версия for-loop знакома, потому что мы все время делаем это в Java, но если вы еще не знаете, что этот цикл должен делать, это не очевидно. Возможно, вам придется моделировать несколько циклов, прежде чем вы выясните, что делает, и почему открытый подписок должен быть закрыт после окончания цикла. (Я изначально забыл его, но я это испытал в тестировании).

По-видимому, подход к streamам легче осмыслить, что происходит: получить список (или массив), который указывает границы между подсписками. Это простой stream с двумя слоями. Трудность, как я уже упоминал выше, заключается в нахождении способа привязать значения края к концам. Если бы был лучший синтаксис для этого, например,

  // Java plus pidgin Scala int[] indexes = [-1] ++ IntStream.range(0, input.size()) .filter(i -> input.get(i) == null) ++ [input.size()]; 

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

И, конечно, это безопасно при параллельном запуске.

ОБНОВЛЕНИЕ 2016-02-06

Вот более удобный способ создания массива подсписных индексов. Он основан на тех же принципах, но он корректирует диапазон индексов и добавляет некоторые условия фильтру, чтобы избежать необходимости конкатенации и выравнивания индексов.

 static List> splitStream(List input) { int sz = input.size(); int[] indexes = IntStream.rangeClosed(-1, sz) .filter(i -> i == -1 || i == sz || input.get(i) == null) .toArray(); return IntStream.range(0, indexes.length-1) .mapToObj(i -> input.subList(indexes[i]+1, indexes[i+1])) .collect(toList()); } 

ОБНОВЛЕНИЕ 2016-11-23

Я выступил с сообщением с Брайаном Гетцем в Devoxx Antwerp 2016, «Думая в параллель» ( видео ), в котором была представлена ​​эта проблема и мои решения. Представленная проблема представляет собой небольшую вариацию, которая разбивается на «#» вместо нуля, но в остальном это одно и то же. В разговоре я упомянул, что у меня была куча модульных тестов для этой проблемы. Я добавил их ниже, как отдельную программу, вместе с реализацией цикла и streamов. Интересным упражнением для читателей является запуск решений, предложенных в других ответах на тестовые примеры, которые я здесь привел, и посмотреть, какие из них терпят неудачу и почему. (Другие решения должны быть адаптированы для разделения на основе предиката вместо разделения на нуль.)

 import java.util.*; import java.util.function.*; import java.util.stream.*; import static java.util.Arrays.asList; public class ListSplitting { static final Map, List>> TESTCASES = new LinkedHashMap<>(); static { TESTCASES.put(asList(), asList(asList())); TESTCASES.put(asList("a", "b", "c"), asList(asList("a", "b", "c"))); TESTCASES.put(asList("a", "b", "#", "c", "#", "d", "e"), asList(asList("a", "b"), asList("c"), asList("d", "e"))); TESTCASES.put(asList("#"), asList(asList(), asList())); TESTCASES.put(asList("#", "a", "b"), asList(asList(), asList("a", "b"))); TESTCASES.put(asList("a", "b", "#"), asList(asList("a", "b"), asList())); TESTCASES.put(asList("#"), asList(asList(), asList())); TESTCASES.put(asList("a", "#", "b"), asList(asList("a"), asList("b"))); TESTCASES.put(asList("a", "#", "#", "b"), asList(asList("a"), asList(), asList("b"))); TESTCASES.put(asList("a", "#", "#", "#", "b"), asList(asList("a"), asList(), asList(), asList("b"))); } static final Predicate TESTPRED = "#"::equals; static void testAll(BiFunction, Predicate, List>> f) { TESTCASES.forEach((input, expected) -> { List> actual = f.apply(input, TESTPRED); System.out.println(input + " => " + expected); if (!expected.equals(actual)) { System.out.println(" ERROR: actual was " + actual); } }); } static  List> splitStream(List input, Predicate pred) { int[] edges = IntStream.range(-1, input.size()+1) .filter(i -> i == -1 || i == input.size() || pred.test(input.get(i))) .toArray(); return IntStream.range(0, edges.length-1) .mapToObj(k -> input.subList(edges[k]+1, edges[k+1])) .collect(Collectors.toList()); } static  List> splitLoop(List input, Predicate pred) { List> result = new ArrayList<>(); int start = 0; for (int cur = 0; cur < input.size(); cur++) { if (pred.test(input.get(cur))) { result.add(input.subList(start, cur)); start = cur + 1; } } result.add(input.subList(start, input.size())); return result; } public static void main(String[] args) { System.out.println("===== Loop ====="); testAll(ListSplitting::splitLoop); System.out.println("===== Stream ====="); testAll(ListSplitting::splitStream); } } 

Решением является использование Stream.collect . Создание коллектора с использованием его шаблона построителя уже задано как решение. Альтернативой является другой перегруженный collect являющийся немного более примитивным.

  List strings = Arrays.asList("a", "b", null, "c", null, "d", "e"); List> groups = strings.stream() .collect(() -> { List> list = new ArrayList<>(); list.add(new ArrayList<>()); return list; }, (list, s) -> { if (s == null) { list.add(new ArrayList<>()); } else { list.get(list.size() - 1).add(s); } }, (list1, list2) -> { // Simple merging of partial sublists would // introduce a false level-break at the beginning. list1.get(list1.size() - 1).addAll(list2.remove(0)); list1.addAll(list2); }); 

Как я вижу, я составляю список строковых списков, где всегда есть хотя бы один последний (пустой) список строк.

  • Первая функция создает начальный список строковых списков. Он определяет результат (типизированный) объект.
  • Вторая функция вызывается для обработки каждого элемента. Это действие на частичный результат и элемент.
  • Третий не используется, он играет роль в параллелизации обработки, когда частичные результаты должны быть объединены.

Решение с аккумулятором:

Как отмечает @StuartMarks, объединитель не заполняет контракт на параллелизм.

Из-за комментария @ArnaudDenoyelle версия с использованием reduce .

  List> groups = strings.stream() .reduce(new ArrayList>(), (list, s) -> { if (list.isEmpty()) { list.add(new ArrayList<>()); } if (s == null) { list.add(new ArrayList<>()); } else { list.get(list.size() - 1).add(s); } return list; }, (list1, list2) -> { list1.addAll(list2); return list1; }); 
  • Первым параметром является накопленный объект.
  • Вторая функция накапливается.
  • Третий – вышеупомянутый объединитель.

Пожалуйста, не голосуйте. Мне не хватает места, чтобы объяснить это в комментариях .

Это решение с Stream и foreach но это строго эквивалентно решению Alexis или циклу foreach (и менее понятно, и я не мог избавиться от конструктора копирования):

 List> result = new ArrayList<>(); final List current = new ArrayList<>(); list.stream().forEach(s -> { if (s == null) { result.add(new ArrayList<>(current)); current.clear(); } else { current.add(s); } } ); result.add(current); System.out.println(result); 

Я понимаю, что вы хотите найти более элегантное решение с Java 8, но я действительно думаю, что он не был разработан для этого случая. И, как сказал г-н Ложка, очень предпочитают наивный путь в этом случае.

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

Здесь я группирую элемент по первому индексу после этого элемента со значением null . Итак, в вашем примере "a" и "b" будут отображены на 2 . Кроме того, я сопоставляю значение null с индексом -1 , которое следует удалить позже.

 List list = Arrays.asList("a", "b", null, "c", null, "d", "e"); Function indexGroupingFunc = (str) -> { if (str == null) { return -1; } int index = list.indexOf(str) + 1; while (index < list.size() && list.get(index) != null) { index++; } return index; }; Map> grouped = list.stream() .collect(Collectors.groupingBy(indexGroupingFunc)); grouped.remove(-1); // Remove null elements grouped under -1 System.out.println(grouped.values()); // [[a, b], [c], [d, e]] 

Вы также можете избежать получения первого индекса null элемента каждый раз, путем кэширования текущего индекса min в AtomicInteger . Обновленная Function будет выглядеть так:

 AtomicInteger currentMinIndex = new AtomicInteger(-1); Function indexGroupingFunc = (str) -> { if (str == null) { return -1; } int index = names.indexOf(str) + 1; if (currentMinIndex.get() > index) { return currentMinIndex.get(); } else { while (index < names.size() && names.get(index) != null) { index++; } currentMinIndex.set(index); return index; } }; 

Хотя ответ Маркса Стюарта является кратким, интуитивным и параллельным (и лучшим) , я хочу поделиться другим интересным решением, которое не нуждается в трюке начала и конца.

Если мы посмотрим на проблемную область и подумаем о параллелизме, мы сможем легко решить эту проблему с помощью страtagsи разделения и покорения. Вместо того, чтобы думать о проблеме как о серийном списке, нам нужно пройти, мы можем рассматривать проблему как состав одной и той же основной проблемы: разбиение списка на null значение. Мы можем легко увидеть, что мы можем рекурсивно разбить проблему на следующую рекурсивную страtagsю:

 split(L) : - if (no null value found) -> return just the simple list - else -> cut L around 'null' naming the resulting sublists L1 and L2 return split(L1) + split(L2) 

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

Одна картинка стоит тысячи слов:

введите описание изображения здесь

Алгоритм прост и полный: нам не нужны специальные трюки для обработки крайних случаев начала / конца списка. Нам не нужны специальные трюки для обработки крайних случаев, таких как пустые списки или списки с null значениями. Или списки, заканчивающиеся на null или начинающиеся с null .

Простая наивная реализация этой страtagsи выглядит следующим образом:

 public List> split(List input) { OptionalInt index = IntStream.range(0, input.size()) .filter(i -> input.get(i) == null) .findAny(); if (!index.isPresent()) return asList(input); List firstHalf = input.subList(0, index.getAsInt()); List secondHalf = input.subList(index.getAsInt()+1, input.size()); return asList(firstHalf, secondHalf).stream() .map(this::split) .flatMap(List::stream) .collect(toList()); } 

Сначала мы ищем индекс любого null значения в списке. Если мы его не найдем, мы вернем список. Если мы найдем один, мы разделим список в 2 подсписках, перейдем через них и рекурсивно снова назовем метод split . Полученные списки подзадачи затем извлекаются и объединяются для возвращаемого значения.

Заметим, что 2 streamа можно легко сделать параллельными (), и алгоритм по-прежнему будет работать из-за функционального разложения проблемы.

Хотя код уже довольно краткий, его всегда можно адаптировать по-разному. Для примера, вместо проверки необязательного значения в базовом случае, мы могли бы воспользоваться методом orElse на orElse чтобы вернуть конец индекса этого списка, что позволяет нам повторно использовать второй stream и дополнительно отфильтровать пустые списки:

 public List> split(List input) { int index = IntStream.range(0, input.size()) .filter(i -> input.get(i) == null) .findAny().orElse(input.size()); return asList(input.subList(0, index), input.subList(index+1, input.size())).stream() .map(this::split) .flatMap(List::stream) .filter(list -> !list.isEmpty()) .collect(toList()); } 

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

В этом случае recursion, вероятно, не может быть лучшим решением (алгоритм Stuart Marks для поиска индексов – это только O (N), а списки отображения / расщепления имеют значительную стоимость), но он выражает решение простым, интуитивно-параллелизуемым алгоритмом без каких-либо побочные эффекты.

Я не буду углубляться в сложность, преимущества / недостатки или варианты использования с критериями остановки и / или частичной доступности результата. Я просто почувствовал необходимость разделить эту страtagsю решения, поскольку другие подходы были просто итеративными или использовали слишком сложный алгоритм решения, который не был параллелизирован.

Это очень интересная проблема. Я придумал однострочное решение. Это может не очень показательно, но оно работает.

 List list = Arrays.asList("a", "b", null, "c", null, "d", "e"); Collection> cl = IntStream.range(0, list.size()) .filter(i -> list.get(i) != null).boxed() .collect(Collectors.groupingBy( i -> IntStream.range(0, i).filter(j -> list.get(j) == null).count(), Collectors.mapping(i -> list.get(i), Collectors.toList())) ).values(); 

Это похоже на то, что @Rohit Jain придумал. Я группирую пробел между нулевыми значениями. Если вам действительно нужен List> вы можете добавить:

 List> ll = cl.stream().collect(Collectors.toList()); 

Ну, после небольшой работы U придумал однострочное streamовое решение. В конечном итоге он использует функцию reduce() для группировки, которая казалась естественным выбором, но это было немного уродливо, получая строки в List> необходимые для сокращения:

 List> result = list.stream() .map(Arrays::asList) .map(x -> new LinkedList(x)) .map(Arrays::asList) .map(x -> new LinkedList>(x)) .reduce( (a, b) -> { if (b.getFirst().get(0) == null) a.add(new LinkedList()); else a.getLast().addAll(b.getFirst()); return a;}).get(); 

Это , однако, 1 линия!

Когда вы запускаете вход с вопросом,

 System.out.println(result); 

Производит:

 [[a, b], [c], [d, e]] 

Вот код от AbacusUtil

 List list = N.asList(null, null, "a", "b", null, "c", null, null, "d", "e"); Stream.of(list).splitIntoList(null, (e, any) -> e == null, null).filter(e -> e.get(0) != null).forEach(N::println); 

Декларация: Я разработчик AbacusUtil.

В моей библиотеке StreamEx есть метод groupRuns который поможет вам решить эту проблему:

 List input = Arrays.asList("a", "b", null, "c", null, "d", "e"); List> result = StreamEx.of(input) .groupRuns((a, b) -> a != null && b != null) .remove(list -> list.get(0) == null).toList(); 

Метод groupRuns берет BiPredicate который для пары смежных элементов возвращает true, если они должны быть сгруппированы. После этого мы удаляем группы, содержащие нули, и собираем остальные в список.

Это решение совместимо с параллелью: вы можете использовать его и для параллельного streamа. Кроме того, он отлично работает с любым источником streamа (не только списками произвольного доступа, как и в некоторых других решениях), и он несколько лучше, чем коллекционные решения, так как здесь вы можете использовать любую операцию терминала, которую вы хотите, без промежуточных потерь памяти.

С помощью String можно делать:

 String s = ....; String[] parts = s.split("sth"); 

Если все последовательные коллекции (поскольку String – последовательность символов) имели эту абстракцию, это тоже можно было бы сделать для них:

 List l = ... List> parts = l.split(condition) (possibly with several overloaded variants) 

Если мы ограничиваем исходную задачу списком строк (и накладываем некоторые ограничения на ее содержимое элементов), мы могли бы взломать ее так:

 String als = Arrays.toString(new String[]{"a", "b", null, "c", null, "d", "e"}); String[] sa = als.substring(1, als.length() - 1).split("null, "); List> res = Stream.of(sa).map(s -> Arrays.asList(s.split(", "))).collect(Collectors.toList()); 

(пожалуйста, не воспринимайте это всерьез хотя :))

В противном случае также работает обычная старая recursion:

 List> part(List input, List> acc, List cur, int i) { if (i == input.size()) return acc; if (input.get(i) != null) { cur.add(input.get(i)); } else if (!cur.isEmpty()) { acc.add(cur); cur = new ArrayList<>(); } return part(input, acc, cur, i + 1); } 

(обратите внимание, что в этом случае нуль должен быть добавлен к списку ввода)

 part(input, new ArrayList<>(), new ArrayList<>(), 0) 

Группируйте по другому токену, когда вы найдете нуль (или разделитель). Я использовал здесь другое целое число (использовал атом, как держатель)

Затем переназначьте сгенерированную карту, чтобы преобразовать ее в список списков.

 AtomicInteger i = new AtomicInteger(); List> x = Stream.of("A", "B", null, "C", "D", "E", null, "H", "K") .collect(Collectors.groupingBy(s -> s == null ? i.incrementAndGet() : i.get())) .entrySet().stream().map(e -> e.getValue().stream().filter(v -> v != null).collect(Collectors.toList())) .collect(Collectors.toList()); System.out.println(x); 

Я смотрел видео на «Думая параллельно» Стюарта. Поэтому решил решить его, прежде чем увидеть его ответ в видео. Обновит решение со временем. на данный момент

 Arrays.asList(IntStream.range(0, abc.size()-1). filter(index -> abc.get(index).equals("#") ). map(index -> (index)).toArray()). stream().forEach( index -> {for (int i = 0; i < index.length; i++) { if(sublist.size()==0){ sublist.add(new ArrayList(abc.subList(0, index[i]))); }else{ sublist.add(new ArrayList(abc.subList(index[i]-1, index[i]))); } } sublist.add(new ArrayList(abc.subList(index[index.length-1]+1, abc.size()))); }); 
  • Работа со списком списков в Java
  • Как удалить дубликаты из списка при сохранении порядка?
  • Добавить объект в список в R в амортизированном постоянном времени, O (1)?
  • Как легко инициализировать список кортежей?
  • Производительность массивов против списков
  • Удалить дубликаты из списка объектов на основе свойства в Java 8
  • Prolog - подсчет числа в списке
  • Интеллектуальный способ удаления элементов из списка при перечислении в C #
  • Каковы различия между векторными и списковыми типами данных в R?
  • список по сравнению с lambda + filter
  • C #: Как преобразовать список объектов в список одного свойства этого объекта?
  • Давайте будем гением компьютера.