Обзор кода Java: объединить отсортированные списки в один отсортированный список
Я хочу объединить отсортированные списки в один список. Как это решение? Я считаю, что это работает в O(N) время. Какие-то явные недостатки, неэффективность или стилистические проблемы?
Мне не очень нравится идиома установки флага для "это первая итерация" и использования его, чтобы убедиться, что "наименьшее" имеет значение по умолчанию. Есть ли лучший способ обойти это?
public static <T extends Comparable<? super T>> List<T> merge(Set<List<T>> lists) {
List<T> result = new ArrayList<T>();
int totalSize = 0; // every element in the set
for (List<T> l : lists) {
totalSize += l.size();
}
boolean first; //awkward
List<T> lowest = lists.iterator().next(); // the list with the lowest item to add
while (result.size() < totalSize) { // while we still have something to add
first = true;
for (List<T> l : lists) {
if (! l.isEmpty()) {
if (first) {
lowest = l;
first = false;
}
else if (l.get(0).compareTo(lowest.get(0)) <= 0) {
lowest = l;
}
}
}
result.add(lowest.get(0));
lowest.remove(0);
}
return result;
}
Примечание: это не домашняя работа, но и не для производственного кода.
5 ответов
Ваше решение, вероятно, самое быстрое. SortedLists имеют стоимость вставки log(n), так что в итоге вы получите M log (M) (где M - общий размер списков).
Добавление их в один список и сортировка, хотя и проще для чтения, все равно M log(M).
Ваше решение просто М.
Вы можете немного очистить свой код, изменив размер списка результатов и используя ссылку на самый низкий список вместо логического.
public static <T extends Comparable<? super T>> List<T> merge(Set<List<T>> lists) {
int totalSize = 0; // every element in the set
for (List<T> l : lists) {
totalSize += l.size();
}
List<T> result = new ArrayList<T>(totalSize);
List<T> lowest;
while (result.size() < totalSize) { // while we still have something to add
lowest = null;
for (List<T> l : lists) {
if (! l.isEmpty()) {
if (lowest == null) {
lowest = l;
} else if (l.get(0).compareTo(lowest.get(0)) <= 0) {
lowest = l;
}
}
}
result.add(lowest.get(0));
lowest.remove(0);
}
return result;
}
Если вы действительно конкретны, используйте объект List в качестве входных данных, и младший может быть инициализирован как lists.get(0), и вы можете пропустить проверку нуля.
Эффективность будет сосать, если lists содержит ArrayList, так как lowest.remove(0) будет занимать линейное время в длине списка, делая ваш алгоритм O(n^2).
Я бы сделал:
List<T> result = new ArrayList<T>();
for (List<T> list : lists) {
result.addAll(list);
}
Collections.sort(result);
который находится в O(n log n) и оставляет гораздо менее утомительный код для тестирования, отладки и сопровождения.
Чтобы расширить комментарий Антона:
Поместив последний результат из каждого Списка вместе с указателем того списка, в котором он находится, в кучу, затем постоянно извлекайте верхнюю часть из кучи и помещайте новый элемент в кучу из списка, принадлежащего только что выбранному элементу. выкл.
Java PriorityQueue может обеспечить реализацию кучи.
Это действительно старый вопрос, но мне не нравятся какие-либо из представленных ответов, поэтому я в итоге и сделал.
Решение просто добавить их все в один список и сортировать плохо из-за линейной сложности журнала. Если это не важно для вас, то это, безусловно, самый простой и простой ответ. Ваше первоначальное решение неплохое, но оно немного грязное, и @Dathan отметил, что сложность O(m n) для m списков и n итоговых элементов. Вы можете уменьшить это значение до O(n log(m)), используя кучу, поэтому уменьшите количество сравнений для каждого элемента. Я использую вспомогательный класс, который позволяет мне сравнивать итерации. Таким образом, я не уничтожаю исходные списки, и он должен работать с разумной сложностью независимо от того, какой тип списков вводится. Единственный недостаток, который я вижу в реализации ниже, заключается в том, что она не поддерживает списки с null элементы, однако это может быть исправлено при желании.
public static <E extends Comparable<? super E>> List<E> merge(Collection<? extends List<? extends E>> lists) {
PriorityQueue<CompIterator<E>> queue = new PriorityQueue<CompIterator<E>>();
for (List<? extends E> list : lists)
if (!list.isEmpty())
queue.add(new CompIterator<E>(list.iterator()));
List<E> merged = new ArrayList<E>();
while (!queue.isEmpty()) {
CompIterator<E> next = queue.remove();
merged.add(next.next());
if (next.hasNext())
queue.add(next);
}
return merged;
}
private static class CompIterator<E extends Comparable<? super E>> implements Iterator<E>, Comparable<CompIterator<E>> {
E peekElem;
Iterator<? extends E> it;
public CompIterator(Iterator<? extends E> it) {
this.it = it;
if (it.hasNext()) peekElem = it.next();
else peekElem = null;
}
@Override
public boolean hasNext() {
return peekElem != null;
}
@Override
public E next() {
E ret = peekElem;
if (it.hasNext()) peekElem = it.next();
else peekElem = null;
return ret;
}
@Override
public void remove() {
throw new UnsupportedOperationException();
}
@Override
public int compareTo(CompIterator<E> o) {
if (peekElem == null) return 1;
else return peekElem.compareTo(o.peekElem);
}
}
Каждый элемент возвращаемого списка включает в себя две операции кучи O(log(m)), также есть начальная итерация по всем спискам. Следовательно, общая сложность составляет O(n log(m) + m) для n полных элементов и m списков. делая это всегда быстрее, чем объединять и сортировать.
Так как Балус и Меритон вместе дали отличный ответ на ваш вопрос об алгоритме, я поговорю с вами о "первой" идиоме.
Определенно есть и другие подходы (например, установка минимального значения "магического"), но мне кажется, что "первое" (которому я, вероятно, назвал бы более длинное имя, но это педантично) лучше, потому что оно очень Чисто. Присутствие логического типа "first" является четким сигналом того, что ваш цикл будет делать что-то особенное с первого раза. Это помогает читателю.
Конечно, вам это не нужно, если вы используете подход Балус / Меритон, но это ситуация, которая возникает.