Обзор Кода Java: Объедините отсортированные списки в единственный отсортированный [закрытый] список
Почему нет?
public static Logger getLogger(Object o) {
final Logger logger = Logger.getLogger(o.getClass());
logger.setLevel(ResourceManager.LOGLEVEL);
return logger;
}
И затем когда Вам нужен регистратор для класса:
getLogger(this).debug("Some log message")
4 ответа
Ваше решение, вероятно, самое быстрое. Для SortedLists стоимость вставки равна log (n), поэтому вы получите M log (M) (где M - общий размер списков).
Добавление их в один список и сортировка, при этом их легче читать , по-прежнему M log (M).
Ваше решение - просто 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), и вы можете пропустить проверку на null.
Эффективность будет отстой, если lists содержит список ArrayList, поскольку lower.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 может предоставить реализацию кучи.
Поскольку Балус и Меритон вместе дали отличный ответ на ваш вопрос об алгоритме, я отвечу на вашу сторону о "первой" идиоме.
Определенно есть и другие подходы (например, установка минимального значения «магического»), но я чувствую, что «первый» (которому я бы, вероятно, дал более длинное название, но это педантично) является лучшим, потому что это очень ясно. Наличие логического значения, такого как «first», является явным сигналом того, что ваш цикл сделает что-то особенное с первого раза. Это помогает читателю.
Конечно, вам это не понадобится, если вы воспользуетесь подходом Балуса / Меритона, но такая ситуация возникает.