Слияние отсортированных списков, удаление дубликатов


Я хочу объединить два отсортированных списков целых чисел, но это не в общем случае, сортировка слиянием, потому что такое же количество может появляются в обоих списках. (Однако, каждое число может появляться только один раз в определенный список.)

Самый простой способ я нашел, чтобы сделать это (способ mergeWithSet):

  • Добавить все числа из списка в treeSet
  • Добавить все числа из списка два в treeSet
  • Создать новый список из treeSet

Это работает, но я думаю, что эффективность будет примерно за o(Н+м+(п+м)журнал(N+М)), т. е. за o(Nlog(N)), а я думаю, что эта проблема может быть решена за o(Н+м) воспользовавшись тем, что списки уже отсортированы. Быстрое изменение в общем случае работает слиянием (метод mergeWithGet), но для того, чтобы практика использования итераторов, я написал способ mergeWithIterator, который использует только итераторы.

Вопрос:

  • mergeWithGet аккуратный способ. Почему mergeWithIterator так сложно? Я что-то пропустила?
  • Я вижу большой разницы в эффективности для огромных списков или в этот сценарий Три алгоритмы ведут себя более или менее одинаково?
  • Любое решение на Java 8 поток? Просто чтобы проверить, если параллелизм работает в этом случае

Спасибо заранее, и любое предложение будет очень кстати. Три метода работают. Код:

import java.util.*;


public class MergeLists {
    public static List<Integer> mergeWithIterator(List<Integer> list1, List<Integer> list2) {
        List<Integer> sorted = new ArrayList<>();
        Iterator<Integer> itList1 = list1.iterator();
        Iterator<Integer> itList2 = list2.iterator();

        Integer currentList1 = itList1.next();
        Integer currentList2 = itList2.next();
        while (itList1.hasNext() && itList2.hasNext()) {
            if (currentList1 > currentList2) {
                sorted.add(currentList2);
                currentList2 = itList2.next();
            } else if (currentList1 < currentList2) {
                sorted.add(currentList1);
                currentList1 = itList1.next();
            } else {
                sorted.add(currentList1);
                currentList1 = itList1.next();
                currentList2 = itList2.next();
            }

        }
        //one (or both) of the currents have the last number of their list
        //Special Case: Both lists have the same size
        if (!itList1.hasNext() && !itList2.hasNext()) {
            if (currentList1 > currentList2) {
                sorted.add(currentList2);
                sorted.add(currentList1);
            } else if (currentList1 < currentList2) {
                sorted.add(currentList1);
                sorted.add(currentList2);
            } else {
                sorted.add(currentList1);
            }
            return sorted;
        }
        //General case:One list is longer than the other: we add from the longer till the number is
        //greater than the one that is last in the other list, then the last and the rest of the longer list
        Iterator<Integer> itLongestList;
        Integer lastFromShortest;
        Integer lastFromLongest;
        if (itList1.hasNext()) {
            itLongestList = itList1;
            lastFromShortest = currentList2;
            lastFromLongest = currentList1;
        } else {
            itLongestList = itList2;
            lastFromShortest = currentList1;
            lastFromLongest = currentList2;
        }
        while (lastFromLongest < lastFromShortest && itLongestList.hasNext()) {
            sorted.add(lastFromLongest);
            lastFromLongest = itLongestList.next();
        }
        if (lastFromShortest < lastFromLongest) {
            sorted.add(lastFromShortest);
            sorted.add(lastFromLongest);
        } else if (lastFromShortest > lastFromLongest) {
            sorted.add(lastFromLongest);
            sorted.add(lastFromShortest);
        } else {
            sorted.add(lastFromShortest);
        }
        while (itLongestList.hasNext()) {
            sorted.add(itLongestList.next());

        }
        return sorted;
    }

    public static List<Integer> mergeWithGet(List<Integer> list1, List<Integer> list2) {
        List<Integer> sorted = new ArrayList<>();
        int i = 0;
        int j = 0;
        while (i < list1.size() && j < list2.size()) {
            if (list1.get(i) < list2.get(j))
                sorted.add(list1.get(i++));
            else if (list1.get(i) > list2.get(j)) {
                sorted.add(list2.get(j++));
            } else {
                sorted.add(list1.get(i));
                i++;
                j++;
            }
        }

        // Store remaining elements of first list
        while (i < list1.size())
            sorted.add(list1.get(i++));
        // Store remaining elements of second list
        while (j < list2.size())
            sorted.add(list2.get(j++));
        return sorted;
    }

    public static List<Integer> mergeWithSet(List<Integer> list1, List<Integer> list2) {
        Set<Integer> sortedSet = new TreeSet<>();
        sortedSet.addAll(list1);
        sortedSet.addAll(list2);
        return new ArrayList<>(sortedSet);
    }


    public static void main(String[] args) {
        List<Integer> list1 = Arrays.asList(-30, 0, 10, 20, 40, 50);
        List<Integer> list2 = Arrays.asList(0, 5, 15, 20, 40);
        //0, 20 and 40 should appear only once in the result
        System.out.println(mergeWithGet(list1, list2));
        System.out.println(mergeWithIterator(list1, list2));
        System.out.println(mergeWithSet(list1, list2));
    }
}

я



Комментарии
3 ответа

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

public static List<Integer> mergeWithIterator(List<Integer> list1, List<Integer> list2) {
List<Integer> sorted = new ArrayList<>();

Iterator<Integer> iterator1 = list1.iterator();
Iterator<Integer> iterator2 = list2.iterator();
Integer element1 = null;
Integer element2 = null;

while (iterator1.hasNext() && iterator2.hasNext()) {
if (element1 == null) {
element1 = iterator1.next();
}
if (element2 == null) {
element2 = iterator2.next();
}
if (element1 < element2) {
sorted.add(element1);
element1 = null;
} else if (element1 > element2) {
sorted.add(element2);
element2 = null;
} else {
sorted.add(element1);
element1 = null;
element2 = null;
}
}

if (element1 != null) {
sorted.add(element1);
}
if (element2 != null) {
sorted.add(element2);
}

while (iterator1.hasNext()) {
sorted.add(iterator1.next());
}
while (iterator2.hasNext()) {
sorted.add(iterator2.next());
}

return sorted;
}

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

public static List<Integer> mergeWithIterator(List<Integer> list1, List<Integer> list2) {
List<Integer> sorted = new ArrayList<>();

Iterator<Integer> iterator1 = list1.iterator();
Iterator<Integer> iterator2 = list2.iterator();
Integer element1 = iterator1.hasNext() ? iterator1.next() : null;
Integer element2 = iterator2.hasNext() ? iterator2.next() : null;

while (!(element1 == null && element2 == null)) {
if (element2 == null || (element1 != null && element1 < element2)) {
sorted.add(element1);
element1 = iterator1.hasNext() ? iterator1.next() : null;
} else if (element1 == null || (element2 != null && element2 < element1)) {
sorted.add(element2);
element2 = iterator2.hasNext() ? iterator2.next() : null;
} else {
sorted.add(element1);
element1 = iterator1.hasNext() ? iterator1.next() : null;
element2 = iterator2.hasNext() ? iterator2.next() : null;
}
}
return sorted;
}

Простой (но, возможно, наивно) потоков выполнения могут быть:

public static List<Integer> mergeWithStreams(List<Integer> list1, List<Integer> list2) {
return Stream.concat(list1.stream(), list2.stream())
.sorted()
.distinct()
.collect(toList());
}

К слову, вы могли бы сделать методы более универсальны по определению типов элементов как реализация Comparable интерфейс. Это конечно может сделать итератор реализации с использованием null.

По поводу эффективности, я думаю, вы должны измерить. Для достаточно больших списков итератора реализация может действительно вам, что дополнительный бит скорости, а это сложности действительно линейная Вт.Р.Т. входы.

Для потоковой передачи и параллельно, я не думаю, что у меня достаточно знаний, чтобы ответить. Я думаю, что это напрямую зависит от формата ввода, но в целом не улучшит производительность мудрым. Мера, мера, мера! Это, безусловно, является readeability улучшение хоть и мудрый.

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

1
ответ дан 3 марта 2018 в 05:03 Источник Поделиться

Вот замечательное решение бедных на Java итераторы позволило мне:

import java.util.*;
import java.util.function.BiFunction;

public class SortedListMerger<T> {
public static void main(String[] args) {
Integer[] l1 = new Integer[] {1, 3, 5};
Integer[] l2 = new Integer[] {1, 3, 4};
SortedListMerger<Integer> m = new SortedListMerger<>((a, b)-> a * b, Comparator.comparingInt(a -> a));
ArrayList<Integer> d = new ArrayList<>();
m.merge(Arrays.asList(l1), Arrays.asList(l2), d);
for (int i : d)
System.out.println(i);
}

private BiFunction<T, T, T> ifEqual;
private Comparator<T> cmp;

public SortedListMerger(BiFunction<T, T, T> ifEqual, Comparator<T> cmp) {
this.ifEqual = ifEqual;
this.cmp = cmp;
}

public void merge(Iterable<T> src1, Iterable<T> src2, List<T> dest) {
Iterator<T> src1i = src1.iterator();
Iterator<T> src2i = src2.iterator();
T elem1 = src1i.hasNext() ? src1i.next() : null;
T elem2 = src2i.hasNext() ? src2i.next() : null;
T prev = null;
T curr;

while (elem1 != null || elem2 != null) {
if (elem1 != null && elem2 != null) {
curr = cmp.compare(elem1, elem2) <= 0 ? elem1 : elem2;
if (curr == elem1) {
elem1 = src1i.hasNext() ? src1i.next() : null;
} else {
elem2 = src2i.hasNext() ? src2i.next() : null;
}
} else if (elem1 != null) {
curr = elem1;
elem1 = src1i.hasNext() ? src1i.next() : null;
} else {
curr = elem2;
elem2 = src2i.hasNext() ? src2i.next() : null;
}

if (prev != null && cmp.compare(prev, curr) == 0) {
prev = ifEqual.apply(prev, curr);
} else {
dest.add(curr);
prev = curr;
}
}
}
}

основным методом, слияния, только 30 строк

0
ответ дан 3 марта 2018 в 05:03 Источник Поделиться

В качестве альтернативы Санер обработки Iterator имея next()но нет current() способ, рассмотреть процессуальные разложения:

    /** @return as accurate an approximation of the number of elements
* as can be expected to be near zero cost. */
static int cheapSize(@SuppressWarnings("rawtypes")
java.util.Collection c) {
return c instanceof java.util.RandomAccess ? c.size()
: c.isEmpty() ? 0 : 1;
}
/** Merges elements of ordered lists <code>list1
и
* lista сохранение только одного из каждой пары сравнения равных.
* @возвращает объединенный список,
* или одним из оригинальных списков, если другой был пуст */
публичный статический > Список
mergeWithIterator(список список1, список листа) {
окончательный инт Н1, Н;
если ((Н1 = cheapSize(список1)) <= 0)
возврат листа;
если ((на = cheapSize(листа)) <= 0)
возвращение список1;
возвращение слияния(список1.итератор(), листа.итератор(),
новый Java.утиль.Класса ArrayList<>(П1+НС) / / математика.мин(Н1, Н)
);
}
/** Добавляет next и всех элементов, повторяемых по
* tail для head.
* @возвращения head*/
статический > Список
методы addall(список голову, т далее итератора хвост) {
голову.добавить(следующий);
вернуться методы addall(голова, хвост);
}
/** Добавляет все элементы повторяются по tail для head.
* @возвращения head*/
статический > Список
методы addall(список голову, итератор хвост) {
а (хвост.hasNext())
голову.добавить(хвост.следующий());
возвращение головы;
}
/** Сливает элементов, повторяемых по it1и
* ita сохранение только одного из каждой пары сравнения равных.
* @возвращение Объединенного списка */

статический > Список
слияния(итератор Ита итератора подача it-1, Списокотсортированный//, инт Н
) {
Т итема = МТА.следующий(),
элемент1 = подача it-1.следующий();
в то время как (правда) {
инт СМР = итема.метод compareto(пункт 1);
если (0 < ЦМП) {
отсортированный.добавить(пункт 1);
если (!подача it-1.hasNext())
вернуться методы addall(отсортированный, итема итд);
элемент1 = подача it-1.следующий();
} еще {
отсортированный.добавить(итема);
если (!МТА.hasNext())
возврат 0 == СМР ? методы addall(сортировка, подача it-1)
: методы addall(сортировка, элемент1, подача it-1);
итема = МТА.следующий();
если (0 = = / СС) {
если (!подача it-1.hasNext())
вернуться методы addall(отсортированный, итема итд);
элемент1 = подача it-1.следующий();
}
}
}
}

0
ответ дан 3 марта 2018 в 09:03 Источник Поделиться