Разделение списка в подсписках по элементам
У меня есть этот список (List<String>):
["a", "b", null, "c", null, "d", "e"]
И мне бы хотелось что-то вроде этого:
[["a", "b"], ["c"], ["d", "e"]]
Другими словами, я хочу разбить мой список в подсписках, используя значение null как разделитель, чтобы получить список списков (List<List<String>>). Я ищу решение Java 8. Я пробовал с Collectors.partitioningBy, но я не уверен, что это то, что я ищу. Спасибо!
Ответы
Ответ 1
Единственное решение, которое я придумал на данный момент, - это реализовать свой собственный сборщик.
Прежде чем читать решение, я хочу добавить несколько заметок об этом. Я принял этот вопрос больше как упражнение по программированию, я не уверен, что это можно сделать с параллельным потоком.
Значит, вы должны знать, что он будет молча разбивать, если конвейер выполняется в параллельно.
Это не желаемое поведение и избегать. Вот почему я делаю исключение в части комбайнера (вместо (l1, l2) -> {l1.addAll(l2); return l1;}), поскольку он используется параллельно при объединении двух списков, так что у вас есть исключение вместо неправильного результата.
Также это не очень эффективно из-за копирования списка (хотя он использует собственный метод для копирования базового массива).
Итак, вот реализация коллектора:
private static Collector<String, List<List<String>>, List<List<String>>> splitBySeparator(Predicate<String> sep) {
final List<String> current = new ArrayList<>();
return Collector.of(() -> new ArrayList<List<String>>(),
(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<List<String>> ll = list.stream().collect(splitBySeparator(Objects::isNull));
Вывод:
[[a, b], [c], [d, e]]
<ч/" > Поскольку ответ Joop Eggen отсутствует, похоже, что это можно сделать параллельно (дайте ему кредит за это!). При этом он уменьшает реализацию пользовательского коллектора до:
private static Collector<String, List<List<String>>, List<List<String>>> splitBySeparator(Predicate<String> sep) {
return Collector.of(() -> new ArrayList<List<String>>(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;});
}
которые позволяют абзацу о parallelism немного устаревать, однако я позволяю ему, поскольку это может быть хорошим напоминанием.
Обратите внимание, что Stream API не всегда является заменой. Есть задачи, которые проще и удобнее использовать потоки, и есть задачи, которые нет. В вашем случае вы также можете создать для этого метод утилиты:
private static <T> List<List<T>> splitBySeparator(List<T> list, Predicate<? super T> predicate) {
final List<List<T>> 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<String>> list = splitBySeparator(originalList, Objects::isNull);.
Его можно улучшить для проверки крайних случаев.
Ответ 2
Хотя уже есть несколько ответов и принятый ответ, в этой теме все еще есть пара вопросов. Во-первых, консенсус, похоже, заключается в том, что решение этой проблемы с использованием потоков является просто упражнением и что традиционный подход к петле предпочтительнее. Во-вторых, ответы, данные до сих пор, не учитывали подход с использованием методов массива или векторного стиля, которые, как я думаю, значительно улучшают решение потоков.
Во-первых, здесь обычное решение для обсуждения и анализа:
static List<List<String>> splitConventional(List<String> input) {
List<List<String>> 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, мы закрываем его, добавляем в список результатов и продвигаем prev. После цикла мы закроем подсписку безоговорочно.
Другое наблюдение заключается в том, что это цикл по индексам, а не по самим значениям, поэтому мы используем арифметику for-loop вместо расширенного цикла "для каждого". Но это предполагает, что мы можем использовать индексы для генерации поддиапазонов вместо потоковой передачи значений и ввода логики в коллекционер (как это было сделано предлагаемым решением Joop Eggen).
Как только мы это осознали, мы можем видеть, что каждая позиция null на входе является разделителем для подписок: это правый конец подслова слева, а он (плюс один) - левый конец подвыражения вправо. Если мы можем обрабатывать случаи краев, это приводит к подходу, в котором мы находим индексы, в которых встречаются элементы null, сопоставляем их с подсписками и собирают подсписки.
Полученный код выглядит следующим образом:
static List<List<String>> splitStream(List<String> 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, чтобы сгладить их. (Я попробовал несколько других подходов, но это казалось самым чистым.)
Это немного удобнее использовать массивы для индексов здесь. Во-первых, нотация для доступа к массиву лучше, чем для списка: indexes[i] vs. indexes.get(i). Во-вторых, использование массива позволяет избежать бокса.
В этот момент каждое значение индекса в массиве (кроме последнего) меньше, чем начальная позиция подсписчика. Индекс к его непосредственному праву - это конец подписок. Мы просто обтекаем массив и сопоставляем каждую пару индексов в подсписку и собираем вывод.
Обсуждение
Подход потоков немного короче, чем версия for-loop, но он более плотный. Версия for-loop знакома, потому что мы все время делаем это в Java, но если вы еще не знаете, что этот цикл должен делать, это не очевидно. Возможно, вам придется моделировать несколько циклов, прежде чем вы выясните, что делает prev, и почему открытый подписок должен быть закрыт после окончания цикла. (Я изначально забыл его, но я поймал это при тестировании.)
Поток, по-моему, проще концептуализировать, что происходит: получить список (или массив), который указывает границы между подсписками. Это легкий поток двухслойных. Трудность, как я уже упоминал выше, заключается в нахождении способа привязать значения края к концам. Если для этого был лучший синтаксис, например,
// 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<List<String>> splitStream(List<String> 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, "Думая параллельно" (видео), который показал эту проблему и мои решения. Представленная проблема представляет собой небольшую вариацию, которая разбивается на "#" вместо нулевого, но в остальном это одно и то же. В разговоре я упомянул, что у меня была куча модульных тестов для этой проблемы. Я добавил их ниже, как отдельную программу, вместе с реализацией цикла и потоков. Интересным упражнением для читателей является запуск решений, предложенных в других ответах на тестовые примеры, которые я здесь привел, и посмотреть, какие из них терпят неудачу и почему. (Другие решения должны быть адаптированы для разделения на основе предиката вместо разделения на нуль.)
import java.util.*;
import java.util.function.*;
import java.util.stream.*;
import static java.util.Arrays.asList;
public class ListSplitting {
static final Map<List<String>, List<List<String>>> 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<String> TESTPRED = "#"::equals;
static void testAll(BiFunction<List<String>, Predicate<String>, List<List<String>>> f) {
TESTCASES.forEach((input, expected) -> {
List<List<String>> actual = f.apply(input, TESTPRED);
System.out.println(input + " => " + expected);
if (!expected.equals(actual)) {
System.out.println(" ERROR: actual was " + actual);
}
});
}
static <T> List<List<T>> splitStream(List<T> input, Predicate<? super T> 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 <T> List<List<T>> splitLoop(List<T> input, Predicate<? super T> pred) {
List<List<T>> 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);
}
}
Ответ 3
Решение состоит в использовании Stream.collect. Создание коллектора с использованием его шаблона построителя уже задано как решение. Альтернативой является другой перегруженный collect, являющийся чуть более примитивным.
List<String> strings = Arrays.asList("a", "b", null, "c", null, "d", "e");
List<List<String>> groups = strings.stream()
.collect(() -> {
List<List<String>> 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, комбайнер не заполняет контракт для parallelism.
Из-за комментария @ArnaudDenoyelle версии с использованием reduce.
List<List<String>> groups = strings.stream()
.reduce(new ArrayList<List<String>>(),
(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;
});
- Первым параметром является накопленный объект.
- Вторая функция накапливается.
- Третий - вышеупомянутый объединитель.
Ответ 4
Пожалуйста, не голосуйте. Мне не хватает места, чтобы объяснить это в комментариях.
Это решение с Stream и a foreach, но это строго эквивалентно решению Alexis или циклу foreach (и менее понятно, и я не мог избавиться от конструктора копирования):
List<List<String>> result = new ArrayList<>();
final List<String> 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, но я действительно думаю, что он не был разработан для этого случая. И, как сказал г-н Ложка, в этом случае предпочитают наивный путь.
Ответ 5
Здесь другой подход, в котором используется функция группировки, которая использует индексы списка для группировки.
Здесь я группирую элемент по первому индексу после этого элемента со значением null. Итак, в вашем примере "a" и "b" будут отображаться на 2. Кроме того, я сопоставляю значение null с индексом -1, которое следует удалить позже.
List<String> list = Arrays.asList("a", "b", null, "c", null, "d", "e");
Function<String, Integer> 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<Integer, List<String>> 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<String, Integer> 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;
}
};
Ответ 6
Хотя ответ Marks Stuart является кратким, интуитивно понятным и безопасным (и лучшим), я хочу поделиться другим интересным решением, которое не требует начала/конец границ.
Если мы рассмотрим проблемную область и подумаем о parallelism, мы сможем легко решить эту проблему с помощью стратегии разделения и покорения. Вместо того, чтобы думать о проблеме как о серийном списке, нам нужно пройти, мы можем рассматривать проблему как состав одной и той же основной проблемы: разбиение списка на значение null. Мы можем легко увидеть, что мы можем рекурсивно разбить проблему на следующую рекурсивную стратегию:
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.
Простая наивная реализация этой стратегии выглядит следующим образом:
public List<List<String>> split(List<String> input) {
OptionalInt index = IntStream.range(0, input.size())
.filter(i -> input.get(i) == null)
.findAny();
if (!index.isPresent())
return asList(input);
List<String> firstHalf = input.subList(0, index.getAsInt());
List<String> 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 потока можно легко сделать параллельными(), и алгоритм по-прежнему будет работать из-за функционального разложения проблемы.
Хотя код уже довольно краткий, его всегда можно адаптировать по-разному. Для примера вместо проверки необязательного значения в базовом случае мы могли бы воспользоваться методом orElse на OptionalInt, чтобы вернуть конечный индекс списка, что позволяет нам повторно использовать второй поток и дополнительно отфильтровать пустые списки:
public List<List<String>> split(List<String> 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());
}
Пример приводится только для указания простой простоты, приспособляемости и элегантности рекурсивного подхода. В самом деле, эта версия представила бы небольшое ограничение производительности и потерпит неудачу, если вход был пуст (и, как таковой, может потребоваться дополнительная пустая проверка).
В этом случае рекурсия может быть не лучшим решением (алгоритм Stuart Marks для поиска индексов - это только O (N), а списки отображения/расщепления имеют значительный стоимость), но он выражает решение простым, интуитивно понятным параллелизуемым алгоритмом без каких-либо побочных эффектов.
Я не буду углубляться в сложность, преимущества/недостатки или варианты использования с критериями остановки и/или частичной доступности результата. Я просто почувствовал необходимость разделить эту стратегию решения, поскольку другие подходы были просто итеративными или использовали слишком сложный алгоритм решения, который не был параллелизирован.
Ответ 7
Это очень интересная проблема. Я придумал однострочное решение. Это может не очень показательно, но оно работает.
List<String> list = Arrays.asList("a", "b", null, "c", null, "d", "e");
Collection<List<String>> 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<String>>, вы можете добавить:
List<List<String>> ll = cl.stream().collect(Collectors.toList());
Ответ 8
Хорошо, после небольшой работы U разработал однострочное потоковое решение. В конечном итоге он использует reduce() для группировки, которая казалась естественным выбором, но это было немного уродливо, получая строки в List<List<String>>, необходимые для сокращения:
List<List<String>> result = list.stream()
.map(Arrays::asList)
.map(x -> new LinkedList<String>(x))
.map(Arrays::asList)
.map(x -> new LinkedList<List<String>>(x))
.reduce( (a, b) -> {
if (b.getFirst().get(0) == null)
a.add(new LinkedList<String>());
else
a.getLast().addAll(b.getFirst());
return a;}).get();
Это, однако, 1 строка!
При запуске с заданием вопроса,
System.out.println(result);
Выдает:
[[a, b], [c], [d, e]]
Ответ 9
Вот код от AbacusUtil
List<String> 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.
Ответ 10
В моей библиотеке StreamEx есть groupRuns, который поможет вам решить эту проблему:
List<String> input = Arrays.asList("a", "b", null, "c", null, "d", "e");
List<List<String>> result = StreamEx.of(input)
.groupRuns((a, b) -> a != null && b != null)
.remove(list -> list.get(0) == null).toList();
Метод groupRuns принимает значение BiPredicate, которое для пары смежных элементов возвращает true, если они должны быть сгруппированы. После этого мы удаляем группы, содержащие нули, и собираем остальные в список.
Это решение совместимо с параллелью: вы можете использовать его и для параллельного потока. Также он отлично работает с любым источником потока (не только списками произвольного доступа, как и в некоторых других решениях), и он несколько лучше, чем коллекционные решения, так как здесь вы можете использовать любую операцию терминала, которая вам нужна, без промежуточных потерь памяти.
Ответ 11
С помощью String можно сделать:
String s = ....;
String[] parts = s.split("sth");
Если все последовательные коллекции (поскольку String является последовательностью символов) имели эту абстракцию, это тоже можно было бы сделать для них:
List<T> l = ...
List<List<T>> 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<List<String>> res = Stream.of(sa).map(s -> Arrays.asList(s.split(", "))).collect(Collectors.toList());
(пожалуйста, не воспринимайте это всерьез, хотя:))
В противном случае также работает обычная старая рекурсия:
List<List<String>> part(List<String> input, List<List<String>> acc, List<String> 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)
Ответ 12
Группируйте по другому токену, когда вы найдете нуль (или разделитель). Я использовал здесь другое целое число (использовал атом, как держатель)
Затем переделайте сгенерированную карту, чтобы преобразовать ее в список списков.
AtomicInteger i = new AtomicInteger();
List<List<String>> 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);
Ответ 13
Я смотрел видео на "Думая параллельно" Стюарта. Поэтому решил решить его, прежде чем увидеть его ответ в видео. Обновит решение со временем. пока
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<String>(abc.subList(0, index[i])));
}else{
sublist.add(new ArrayList<String>(abc.subList(index[i]-1, index[i])));
}
}
sublist.add(new ArrayList<String>(abc.subList(index[index.length-1]+1, abc.size())));
});
