Skip to content

Instantly share code, notes, and snippets.

@jin-x

jin-x/merge_lists0a.cpp

Last active June 8, 2021 19:39
Show Gist options
  • Save jin-x/40894d29b9872473a9b5187bb7660261 to your computer and use it in GitHub Desktop.
Save jin-x/40894d29b9872473a9b5187bb7660261 to your computer and use it in GitHub Desktop.
Download ZIP
@jinxonik / UniLecs #271 (bidirectional order of source lists)
Raw
merge_lists0a.cpp
/***********************************************************************************************************************
Задача UniLecs №271: https://telegra.ph/Anons-271-Obedinenie-otsortirovannyh-svyazannyh-spiskov-05-27
Алгоритм №0A решения задачи об объединении отсортированных связных списков (самый быстрый и правильный алгоритм) :)
Алгоритм с использованием приоритетной очереди.
Модификация с обработкой списков как с восходящими, так и с нисходящими сортировками (определяются автоматически).
________________________________________________________________________________________________________________________
Добавим в приоритетную очередь итераторы, указывающие на начало каждого списка (только для непустых списков).
Запустим цикл, повторяя его, пока приоритетная очередь содержит элементы. В цикле будем извлекать (и удалять) из очереди
наименьший элемент (вернее, итератор, указывающий на наименьший элемент) и записывать его в результирующий список. Затем
будем увеличивать извлечённый итератор, перемещаясь к следующему элементу списка, и если список не закончился, помещать
его обратно в очередь.
По завершении цикла мы получим объединённый отсортированный список, содержащий элементы всех исходных списков.
***********************************************************************************************************************/
#include <vector>
#include <list>
#include <queue>
// Merge vector of sorted lists to a sorted list
template <typename T>
std::list<T> merge_lists(const std::vector<std::list<T>>& lists)
{
// Element structure
struct ListElement {
T value;
typename std::list<T>::const_iterator next, end;
bool descending;
operator T() const {
return value;
}
T get_value() const {
return *std::prev(next, descending);
}
auto move() {
return !descending ? ++next : --next;
}
};
// Create priority queue of list iterators
std::priority_queue<ListElement, std::vector<ListElement>, std::greater<T>> list_iters;
for (const auto& el : lists) {
if (el.begin() != el.end()) {
if (el.front() <= el.back()) {
list_iters.push(ListElement{el.front(), el.begin(), el.end(), false}); // the 1st value, start and end of list (sorted ascending)
} else {
list_iters.push(ListElement{el.back(), el.end(), el.begin(), true}); // the 1st value, end and start of list (sorted descending)
}
}
}
// Main loop
std::list<T> result;
while (!list_iters.empty()) {
auto top = list_iters.top(); // get iterator that points to the least value
result.push_back(top.value); // get the least value
list_iters.pop(); // remove iterator with the least value
if (top.move() != top.end) { // increment/decrement iterator to next value in list
top.value = top.get_value(); // get the next/previous value in list
list_iters.push(top); // add (in/de)cremented iterator if it don't point to the end of list
}
}
// Return result
return result;
} // merge_lists
#include "merge_lists_main.inc"
Raw
merge_lists0b.cpp
/***********************************************************************************************************************
Задача UniLecs №271: https://telegra.ph/Anons-271-Obedinenie-otsortirovannyh-svyazannyh-spiskov-05-27
Алгоритм №0B решения задачи об объединении отсортированных связных списков :)
Алгоритм с использованием упорядоченного multiset.
Модификация с обработкой списков как с восходящими, так и с нисходящими сортировками (определяются автоматически).
________________________________________________________________________________________________________________________
Добавим в упорядоченный multiset все значения изо всех списков. Затем извлечём их по порядку в список.
***********************************************************************************************************************/
#include <vector>
#include <list>
#include <set>
// Merge vector of sorted lists to a sorted list
template <typename T>
std::list<T> merge_lists(const std::vector<std::list<T>>& lists)
{
// Create multiset with all values
std::multiset<T> values;
for (const auto& el : lists) {
values.insert(el.begin(), el.end()); // insert values into set
}
// Extract and return values into list
return {values.begin(), values.end()};
} // merge_lists
#include "merge_lists_main.inc"
Raw
merge_lists0c.cpp
/***********************************************************************************************************************
Задача UniLecs №271: https://telegra.ph/Anons-271-Obedinenie-otsortirovannyh-svyazannyh-spiskov-05-27
Алгоритм №0C решения задачи об объединении отсортированных связных списков :)
Алгоритм с использованием упорядоченной хэш-таблицы.
Модификация с обработкой списков как с восходящими, так и с нисходящими сортировками (определяются автоматически).
________________________________________________________________________________________________________________________
Добавим в упорядоченную хэш-таблицу (map) все значения изо всех списков. В качестве ключа будем использовать значение
элемента списка, а в качестве значения – кол-во таких элементов.
Затем извлечём их по порядку в список, используя каждый ключ столько раз, каково значение с ним ассоциировано.
***********************************************************************************************************************/
#define FIX_RANDOM_SEED // generate always the same lists
#include <vector>
#include <list>
#include <map>
// Merge vector of sorted lists to a sorted list
template <typename T>
std::list<T> merge_lists(const std::vector<std::list<T>>& lists)
{
// Create priority queue of list iterators
std::map<T,size_t> values;
for (const auto& list : lists) {
for (const auto& el : list) {
++values[el]; // insert values into set
}
}
// Main loop
std::list<T> result;
for (const auto& el : values) {
result.insert(result.end(), el.second, el.first); // add values to result list
}
// Return result
return result;
} // merge_lists
#include "merge_lists_main.inc"
Raw
merge_lists1a.cpp
/***********************************************************************************************************************
Задача UniLecs №271: https://telegra.ph/Anons-271-Obedinenie-otsortirovannyh-svyazannyh-spiskov-05-27
Алгоритм №1A решения задачи об объединении отсортированных связных списков (самый быстрый из альтернативных алгоритмов).
Алгоритм сортировки и поддержания сортировки с бинарным поиском.
Модификация с обработкой списков как с восходящими, так и с нисходящими сортировками (определяются автоматически).
________________________________________________________________________________________________________________________
Создадим массив (вектор) итераторов (по сути указателей) list_iters, каждый элемент которого изначально будет указывать
на первый элемент каждого из исходных списков. Для пустых списков добавлять итераторы в list_iters не будем. Отсортируем
этот массив по величине значений, на которые указывают его элементы.
Например, если нам даны списки {3, 5, 8}, {1, 4, 6}, {}, {2, 7}, то после сортировки элементы list_iters будут указывать
на значения в следующем порядке: list_iters[0]: 1 (-> 4 -> 6 -> end), list_iters[1]: 2 (-> 7 -> end), list_iters[2]: 3
(-> 5 -> 8 -> end).
Выходим из функции, возвращая пустой список, если list_iters пуст (все списки оказались пустыми).
Далее начинается основной цикл, который продолжается, пока первый элемент list_iters указывает НЕ на конец списка. Т.е.
если в первом списке больше нет элементов, значит мы обошли все списки (ведь списки, в которых элементы закончились,
будут перемещаться за остальные, см. ниже).
1. Добавим в результирующий список элемент из первого списка (на который указывает первый элемент list_iters). Ведь
list_iters отсортирован таким образом, что первый элемент в нём указывает на наименьшее значение среди всех "следующих"
элементов каждого списка :). Тут же мы сдвинем этот элемент (итератор) вперёд (теперь он будет указывать на следующий
элемент списка либо на конец списка, если в нём больше нет элементов).
2. Далее нам нужно снова отсортировать list_iters, но сделать это нужно максимально быстро. Т.к. у нас изменился только
первый элемент list_iters, нам достаточно "продвинуть" его вверх до тех пор, пока мы не встретим такой же или больший
элемент (речь, разумеется, об элементах, на которые указывают итераторы list_iters). Используем бинарный поиск, чтобы
найти такой элемент максимально быстро. Если первый элемент указывает на конец списка, наш бинарный поиск находит первый
элемент с той же характеристикой (т.е. тоже указывающий на конец списка). После этого сдвинем (скопируем) все элементы,
начиная со второго, до найденного (но не включая его) на 1 позицию назад. А на место последнего скопированного (т.е. на
место элемента перед найденным) запишем самый первый (уже перезаписанный). Таким образом, если первый список закончился,
и первый элемент list_iters указывает на конец списка, мы сдвинем этот элемент в конец, к другим "закончившимся". Такой
алгоритм сортировки похож на сортировку вставками с бинарным поиском.
По завершении цикла мы получим объединённый отсортированный список, содержащий элементы всех исходных списков.
***********************************************************************************************************************/
#define FIX_RANDOM_SEED // generate always the same lists
#include <vector>
#include <list>
#include <algorithm>
// Merge vector of sorted lists to a sorted list
template <typename T>
std::list<T> merge_lists(const std::vector<std::list<T>>& lists)
{
// Create array (vector) of list iterators
struct ListPosition {
typename std::list<T>::const_iterator next, end;
bool descending;
T get_value() const {
return *std::prev(next, descending);
}
void move() {
!descending ? ++next : --next;
}
};
std::vector<ListPosition> list_iters;
for (const auto& el : lists) {
if (el.begin() != el.end()) {
if (el.front() <= el.back()) {
list_iters.push_back(ListPosition{el.begin(), el.end(), false}); // the 1st value, start and end of list (sorted ascending)
} else {
list_iters.push_back(ListPosition{el.end(), el.begin(), true}); // the 1st value, start and end of list (sorted descending)
}
}
}
if (list_iters.empty()) { return {}; } // all lists are empty?
// Sort iterators by value
std::sort(list_iters.begin(), list_iters.end(),
[](const ListPosition& a, const ListPosition& b)
{ return (a.get_value() < b.get_value()); });
// Main loop
std::list<T> result;
do {
result.push_back(list_iters.front().get_value());
list_iters.front().move();
// Float up the 1st element to the neccessary position (to keep 'list_iters' sorted)
const auto key = list_iters.front();
auto position = std::lower_bound(std::next(list_iters.begin()), list_iters.end(), key,
[](const ListPosition& a, const ListPosition& b)
// a at the end -> false; else: b at the end -> true; else: value of a < value of b
{ return (a.next != a.end && (b.next == b.end || a.get_value() < b.get_value())); });
std::copy(std::next(list_iters.begin()), position, list_iters.begin());
*std::prev(position) = key;
} while (list_iters.front().next != list_iters.front().end);
// Return result
return result;
} // merge_lists
#include "merge_lists_main.inc"
Raw
merge_lists1b.cpp
/***********************************************************************************************************************
Задача UniLecs №271: https://telegra.ph/Anons-271-Obedinenie-otsortirovannyh-svyazannyh-spiskov-05-27
Алгоритм №1B решения задачи об объединении отсортированных связных списков (самый быстрый из альтернативных алгоритмов).
Алгоритм сортировки и поддержания сортировки с бинарным поиском и отслеживанием кол-ва закончившихся списков.
Модификация с обработкой списков как с восходящими, так и с нисходящими сортировками (определяются автоматически).
________________________________________________________________________________________________________________________
В сравнении с алгоритмом 1A данный алгоритм содержит некоторые модификации, которые, как я предполагал, должны ускорить
работу. Однако, к сожалению, на практике оказалось, что после компиляции с помощью VC++ и Clang работа даже замедлилась,
буквально на пару процентов, а вот после компиляции с помощью GCC – немного ускорилась, но опять же, примерно на ту же
пару процентов (тестирование производилось на процессоре Intel Core i5-2500K при компиляции для платформы x86-64). Для
выделения модификаций ниже по тексту я буду использовать символы [+].
Создадим массив (вектор) итераторов (по сути указателей) list_iters, каждый элемент которого изначально будет указывать
на первый элемент каждого из исходных списков. Для пустых списков добавлять итераторы в list_iters не будем. Отсортируем
этот массив по величине значений, на которые указывают его элементы.
Например, если нам даны списки {3, 5, 8}, {1, 4, 6}, {}, {2, 7}, то после сортировки элементы list_iters будут указывать
на значения в следующем порядке: list_iters[0]: 1 (-> 4 -> 6 -> end), list_iters[1]: 2 (-> 7 -> end), list_iters[2]: 3
(-> 5 -> 8 -> end).
[+] Создадим переменную finish_count, в которой будем хранить закончившихся списков (находящихся в конце list_iters),
инициализируем её значением 0.
Далее начинается основной цикл, который продолжается, пока...
[+] finish_count не равен размеру list_iters, т.е. кол-ву списков. Это будет означать, что все списки обработаны.
1. Добавим в результирующий список элемент из первого списка (на который указывает первый элемент list_iters). Ведь
list_iters отсортирован таким образом, что первый элемент в нём указывает на наименьшее значение среди всех "следующих"
элементов каждого списка :). Тут же мы сдвинем этот элемент (итератор) вперёд (теперь он будет указывать на следующий
элемент списка либо на конец списка, если в нём больше нет элементов).
[+] 2. Если первый элемент list_iters указывает на конец списка, удалим его, переместив в конец. Для этого сдвинем
(скопируем) все элементы, начиная со второго, но без finish_count последних, на 1 позицию назад, после чего увеличим
finish_count на 1 и продолжим цикл.
3. Иначе нам нужно снова отсортировать list_iters, но сделать это нужно максимально быстро. Т.к. у нас изменился только
первый элемент list_iters, нам достаточно "продвинуть" его вверх до тех пор, пока мы не встретим такой же или больший
элемент (речь, разумеется, об элементах, на которые указывают итераторы list_iters). Используем бинарный поиск, чтобы
найти такой элемент максимально быстро. Если первый элемент указывает на конец списка, наш бинарный поиск находит первый
элемент с той же характеристикой (т.е. тоже указывающий на конец списка). После этого сдвинем (скопируем) все элементы,
начиная со второго, до найденного (но не включая его) на 1 позицию назад. А на место последнего скопированного (т.е. на
место элемента перед найденным) запишем самый первый (уже перезаписанный). Таким образом, если первый список закончился,
и первый элемент list_iters указывает на конец списка, мы сдвинем этот элемент в конец, к другим "закончившимся". Такой
алгоритм сортировки похож на сортировку вставками с бинарным поиском.
[+] Во время бинарного поиска последние finish_count элементы не используются, а в лямбда-функции сравнения при бинарном
поиске отсутствует проверка достижения конца списка.
По завершении цикла мы получим объединённый отсортированный список, содержащий элементы всех исходных списков.
***********************************************************************************************************************/
#define FIX_RANDOM_SEED // generate always the same lists
#include <vector>
#include <list>
#include <algorithm>
// Merge vector of sorted lists to a sorted list
template <typename T>
std::list<T> merge_lists(const std::vector<std::list<T>>& lists)
{
// Create array (vector) of list iterators
struct ListPosition {
typename std::list<T>::const_iterator next, end;
bool descending;
T get_value() const {
return *std::prev(next, descending);
}
void move() {
!descending ? ++next : --next;
}
};
std::vector<ListPosition> list_iters;
for (const auto& el : lists) {
if (el.begin() != el.end()) {
if (el.front() <= el.back()) {
list_iters.push_back(ListPosition{el.begin(), el.end(), false}); // the 1st value, start and end of list (sorted ascending)
} else {
list_iters.push_back(ListPosition{el.end(), el.begin(), true}); // the 1st value, start and end of list (sorted descending)
}
}
}
// Sort iterators by value
std::sort(list_iters.begin(), list_iters.end(),
[](const ListPosition& a, const ListPosition& b)
{ return (a.get_value() < b.get_value()); });
// Main loop
std::list<T> result;
size_t finish_count = 0;
while (finish_count != list_iters.size()) {
result.push_back(list_iters.front().get_value());
list_iters.front().move();
// Float up the 1st element to the neccessary position (to keep 'list_iters' sorted)
if (list_iters.front().next == list_iters.front().end) {
std::copy(std::next(list_iters.begin()), list_iters.end() - finish_count, list_iters.begin());
++finish_count;
} else {
const auto key = list_iters.front();
auto position = std::lower_bound(std::next(list_iters.begin()), list_iters.end() - finish_count, key,
[](const ListPosition& a, const ListPosition& b) { return (a.get_value() < b.get_value()); });
std::copy(std::next(list_iters.begin()), position, list_iters.begin());
*std::prev(position) = key;
}
};
// Return result
return result;
} // merge_lists
#include "merge_lists_main.inc"
Raw
merge_lists1c.cpp
/***********************************************************************************************************************
Задача UniLecs №271: https://telegra.ph/Anons-271-Obedinenie-otsortirovannyh-svyazannyh-spiskov-05-27
Алгоритм №1C решения задачи об объединении отсортированных связных списков.
Алгоритм сортировки и поддержания сортировки с последовательным поиском (работает в разы медленнее алгоритмов 1A и 1B).
Модификация с обработкой списков как с восходящими, так и с нисходящими сортировками (определяются автоматически).
________________________________________________________________________________________________________________________
Данный алгоритм похож на алгоритм 1A с той разницей, что вместо бинарного поиска с последующим копированием производится
поэлементный поиск с постепенным перемещением ("всплыванием") первого элемента.
Создадим массив (вектор) итераторов (по сути указателей) list_iters, каждый элемент которого изначально будет указывать
на первый элемент каждого из исходных списков. Для пустых списков добавлять итераторы в list_iters не будем. Отсортируем
этот массив по величине значений, на которые указывают его элементы.
Например, если нам даны списки {3, 5, 8}, {1, 4, 6}, {}, {2, 7}, то после сортировки элементы list_iters будут указывать
на значения в следующем порядке: list_iters[0]: 1 (-> 4 -> 6 -> end), list_iters[1]: 2 (-> 7 -> end), list_iters[2]: 3
(-> 5 -> 8 -> end).
Выходим из функции, возвращая пустой список, если list_iters пуст (все списки оказались пустыми).
Далее начинается основной цикл, который продолжается, пока первый элемент list_iters указывает НЕ на конец списка. Т.е.
если в первом списке больше нет элементов, значит мы обошли все списки (ведь списки, в которых элементы закончились,
будут перемещаться за остальные, см. ниже).
1. Добавим в результирующий список элемент из первого списка (на который указывает первый элемент list_iters). Ведь
list_iters отсортирован таким образом, что первый элемент в нём указывает на наименьшее значение среди всех "следующих"
элементов каждого списка :). Тут же мы сдвинем этот элемент (итератор) вперёд (теперь он будет указывать на следующий
элемент списка либо на конец списка, если в нём больше нет элементов).
2. Далее нам нужно снова отсортировать list_iters, но сделать это нужно быстро. Поскольку у нас изменился только первый
элемент list_iters, нам достаточно "продвинуть" его вверх до тех пор, пока мы не встретим такой же или больший элемент
(речь, разумеется, об элементах, на которые указывают итераторы list_iters). Для этого мы сравниваем первый элемент с
каждым из последующих и перезаписываем его на место предыдущего, если он не больше. На место последнего (перед тем,
который оказался больше, либо перед концом списка) мы записываем первый элемент. Если первый список закончился, т.е.
первый элемент list_iters указывает на конец списка, мы сдвинем этот элемент в конец, к другим "закончившимся". Такой
алгоритм сортировки похож на сортировку вставками.
По завершении цикла мы получим объединённый отсортированный список, содержащий элементы всех исходных списков.
***********************************************************************************************************************/
#define FIX_RANDOM_SEED // generate always the same lists
#include <vector>
#include <list>
#include <algorithm>
// Merge vector of sorted lists to a sorted list
template <typename T>
std::list<T> merge_lists(const std::vector<std::list<T>>& lists)
{
// Create array (vector) of list iterators
struct ListPosition {
typename std::list<T>::const_iterator next, end;
bool descending;
T get_value() const {
return *std::prev(next, descending);
}
void move() {
!descending ? ++next : --next;
}
};
std::vector<ListPosition> list_iters;
for (const auto& el : lists) {
if (el.begin() != el.end()) {
if (el.front() <= el.back()) {
list_iters.push_back(ListPosition{el.begin(), el.end(), false}); // the 1st value, start and end of list (sorted ascending)
} else {
list_iters.push_back(ListPosition{el.end(), el.begin(), true}); // the 1st value, start and end of list (sorted descending)
}
}
}
if (list_iters.empty()) { return {}; } // all lists are empty?
// Sort iterators by value
std::sort(list_iters.begin(), list_iters.end(),
[](const ListPosition& a, const ListPosition& b)
{ return (a.get_value() < b.get_value()); });
// Main loop
std::list<T> result;
do {
result.push_back(list_iters.front().get_value());
list_iters.front().move();
// Float up the 1st element to the neccessary position (to keep 'list_iters' sorted)
auto position = list_iters.front();
size_t i = 1;
for (; i < list_iters.size(); ++i) {
const auto& el = list_iters[i];
// el at the end -> break; else: position at the end -> continue; else: value of position <= value of el -> break
if (el.next == el.end || (position.next != position.end && position.get_value() <= el.get_value())) { break; }
list_iters[i-1] = el;
}
list_iters[i-1] = position;
} while (list_iters.front().next != list_iters.front().end);
// Return result
return result;
} // merge_lists
#include "merge_lists_main.inc"
Raw
merge_lists2a.cpp
/***********************************************************************************************************************
Задача UniLecs №271: https://telegra.ph/Anons-271-Obedinenie-otsortirovannyh-svyazannyh-spiskov-05-27
Алгоритм №2A решения задачи об объединении отсортированных связных списков.
Алгоритм поиска минимальных элементов (довольно медленный алгоритм, в сравнении с 1A, 1B, 1C).
Модификация с обработкой списков как с восходящими, так и с нисходящими сортировками (определяются автоматически).
________________________________________________________________________________________________________________________
Создадим массив (вектор) итераторов (по сути указателей) list_iters, каждый элемент которого изначально будет указывать
на первый элемент каждого из исходных списков. Для пустых списков добавлять итераторы в list_iters не будем.
Далее начинается основной цикл, выход из которого будет указан ниже.
1. Найдём минимальный элемент из тех, на которые указывают итераторы list_iters.
2. Если все списки были пустыми (ничего не нашли), завершим цикл.
3. Иначе добавим в результирующий список этот найденный элемент. Сдвинем итератор, указывающий на этот элемент вперёд
(теперь он будет указывать на следующий элемент списка либо на конец списка, если в нём больше нет элементов).
По завершении цикла мы получим объединённый отсортированный список, содержащий элементы всех исходных списков.
***********************************************************************************************************************/
#define FIX_RANDOM_SEED // generate always the same lists
#include <vector>
#include <list>
// Merge vector of sorted lists to a sorted list
template <typename T>
std::list<T> merge_lists(const std::vector<std::list<T>>& lists)
{
// Create array (vector) of list iterators
struct ListPosition {
typename std::list<T>::const_iterator next, end;
bool descending;
T get_value() const {
return *std::prev(next, descending);
}
void move() {
!descending ? ++next : --next;
}
};
std::vector<ListPosition> list_iters;
for (const auto& el : lists) {
if (el.begin() != el.end()) {
if (el.front() <= el.back()) {
list_iters.push_back(ListPosition{el.begin(), el.end(), false}); // the 1st value, start and end of list (sorted ascending)
} else {
list_iters.push_back(ListPosition{el.end(), el.begin(), true}); // the 1st value, start and end of list (sorted descending)
}
}
}
// Main loop
std::list<T> result;
for(;;) {
// Find minimal element
bool min_set = false;
T min_value = 0;
size_t min_index = 0;
for (size_t i = 0; i < list_iters.size(); ++i) {
auto& el = list_iters[i];
if (el.next == el.end) { continue; } // is list finished?
if (!min_set || min_value > el.get_value()) {
min_value = el.get_value();
min_index = i;
min_set = true;
}
}
if (!min_set) { break; } // all lists are finished
// Add minimal element to list
result.push_back(list_iters[min_index].get_value());
list_iters[min_index].move();
};
// Return result
return result;
} // merge_lists
#include "merge_lists_main.inc"
Raw
merge_lists2b.cpp
/***********************************************************************************************************************
Задача UniLecs №271: https://telegra.ph/Anons-271-Obedinenie-otsortirovannyh-svyazannyh-spiskov-05-27
Алгоритм №2B решения задачи об объединении отсортированных связных списков.
Алгоритм поиска минимальных элементов с удалением пустых списков (довольно медленный, но до 10% быстрее алгоритма 2A).
Модификация с обработкой списков как с восходящими, так и с нисходящими сортировками (определяются автоматически).
________________________________________________________________________________________________________________________
Создадим массив (вектор) итераторов (по сути указателей) list_iters, каждый элемент которого изначально будет указывать
на первый элемент каждого из исходных списков. Для пустых списков добавлять итераторы в list_iters не будем.
Далее начинается основной цикл, который продолжается, пока список list_iters не пуст.
1. Найдём минимальный элемент из тех, на которые указывают итераторы list_iters.
2. Добавим в результирующий список этот найденный элемент. Сдвинем итератор, указывающий на этот элемент вперёд (теперь
он будет указывать на следующий элемент списка либо на конец списка, если в нём больше нет элементов).
3. Если сдвинутый итератор указывает на конец списка, удаляем его, записывая на его место последний элемент и удаляя
последний элемент.
По завершении цикла мы получим объединённый отсортированный список, содержащий элементы всех исходных списков.
***********************************************************************************************************************/
#define FIX_RANDOM_SEED // generate always the same lists
#include <vector>
#include <list>
// Merge vector of sorted lists to a sorted list
template <typename T>
std::list<T> merge_lists(const std::vector<std::list<T>>& lists)
{
// Create array (vector) of list iterators
struct ListPosition {
typename std::list<T>::const_iterator next, end;
bool descending;
T get_value() const {
return *std::prev(next, descending);
}
void move() {
!descending ? ++next : --next;
}
};
std::vector<ListPosition> list_iters;
for (const auto& el : lists) {
if (el.begin() != el.end()) {
if (el.front() <= el.back()) {
list_iters.push_back(ListPosition{el.begin(), el.end(), false}); // the 1st value, start and end of list (sorted ascending)
} else {
list_iters.push_back(ListPosition{el.end(), el.begin(), true}); // the 1st value, start and end of list (sorted descending)
}
}
}
// Main loop
std::list<T> result;
while (!list_iters.empty()) {
// Find minimal element
bool min_set = false;
T min_value = 0;
size_t min_index = 0;
for (size_t i = 0; i < list_iters.size(); ++i) {
T value = list_iters[i].get_value();
if (!min_set || min_value > value) {
min_value = value;
min_index = i;
min_set = true;
}
}
// Add minimal element to list
auto& el = list_iters[min_index];
result.push_back(el.get_value());
el.move();
// Is list finished?
if (el.next == el.end) {
if (min_index != list_iters.size()-1) { el = list_iters.back(); } // swap it with the last
list_iters.pop_back(); // and remove it
}
};
// Return result
return result;
} // merge_lists
#include "merge_lists_main.inc"
Raw
merge_lists3.cpp
/***********************************************************************************************************************
Задача UniLecs №271: https://telegra.ph/Anons-271-Obedinenie-otsortirovannyh-svyazannyh-spiskov-05-27
Алгоритм №3 решения задачи об объединении отсортированных связных списков (один из самых медленных алгоритмов).
Алгоритм постоянной сортировки.
Модификация с обработкой списков как с восходящими, так и с нисходящими сортировками (определяются автоматически).
________________________________________________________________________________________________________________________
Создадим массив (вектор) итераторов (по сути указателей) list_iters, каждый элемент которого изначально будет указывать
на первый элемент каждого из исходных списков. Для пустых списков добавлять итераторы в list_iters не будем.
Далее начинается основной цикл, выход из которого будет указан ниже.
1. Отсортируем массив list_iters (используя штатную функцию сортировки) по величине значений, на которые указывают его
элементы. Элементы, которые указывают на конец списка переместим в конец массива.
2. Если первый элемент list_iters указывает на конец списка, завершим цикл, т.к. это будет означать, что во всех списках
элементы закончились.
3. Добавим в результирующий список этот найденный элемент. Сдвинем итератор, указывающий на этот элемент вперёд (теперь
он будет указывать на следующий элемент списка либо на конец списка, если в нём больше нет элементов).
По завершении цикла мы получим объединённый отсортированный список, содержащий элементы всех исходных списков.
***********************************************************************************************************************/
#define FIX_RANDOM_SEED // generate always the same arrays
#include <vector>
#include <list>
#include <algorithm>
// Merge vector of sorted lists to a sorted list
template <typename T>
std::list<T> merge_lists(const std::vector<std::list<T>>& lists)
{
// Create array (vector) of list iterators
struct ListPosition {
typename std::list<T>::const_iterator next, end;
bool descending;
T get_value() const {
return *std::prev(next, descending);
}
void move() {
!descending ? ++next : --next;
}
};
std::vector<ListPosition> list_iters;
for (const auto& el : lists) {
if (el.begin() != el.end()) {
if (el.front() <= el.back()) {
list_iters.push_back(ListPosition{el.begin(), el.end(), false}); // the 1st value, start and end of list (sorted ascending)
} else {
list_iters.push_back(ListPosition{el.end(), el.begin(), true}); // the 1st value, start and end of list (sorted descending)
}
}
}
if (list_iters.empty()) { return {}; } // all lists are empty?
// Main loop
std::list<T> result;
for(;;) {
// Resort
std::sort(list_iters.begin(), list_iters.end(), [](const ListPosition& a, const ListPosition& b)
// a.next == a.end -> false; else b.next == b.end -> true; else *a.next < *b.next
{ return (a.next != a.end && (b.next == b.end || a.get_value() < b.get_value())); });
if (list_iters.front().next == list_iters.front().end) { break; }
// Add minimal element to list
result.push_back(list_iters.front().get_value());
list_iters.front().move();
};
// Return result
return result;
} // merge_lists
#include "merge_lists_main.inc"
Raw
merge_lists4a.cpp
/***********************************************************************************************************************
Задача UniLecs №271: https://telegra.ph/Anons-271-Obedinenie-otsortirovannyh-svyazannyh-spiskov-05-27
Алгоритм №4A решения задачи об объединении отсортированных связных списков (один из самых медленных алгоритмов).
Попарное объединение списков встроенной функцией объединения отсортированных списков.
Модификация с обработкой списков как с восходящими, так и с нисходящими сортировками (определяются автоматически).
________________________________________________________________________________________________________________________
Возвращаем пустой список, если кол-во списков равно нулю.
Иначе объединяем с первым списком поочерёдно все последующие списки (штатной функцией объединения пары отсортированных
списков). При данном методе объединения результат помещается в первый список, а остальные списки очищаются. Таким
образом не происходит перераспределения памяти.
По завершении цикла мы получим объединённый отсортированный список, содержащий элементы всех исходных списков.
***********************************************************************************************************************/
#define FIX_RANDOM_SEED // generate always the same lists
#include <vector>
#include <list>
// Merge vector of sorted lists to a sorted list
// Destroys all lists, writes result to the 1st list (lists[0])
template <typename T>
std::list<T> merge_lists(std::vector<std::list<T>>& lists)
{
if (lists.empty()) { return {}; }
if (lists[0].front() > lists[0].back()) { lists[0].reverse(); }
for (size_t i = 1; i < lists.size(); ++i) {
// Merge all lists to the 1st one
if (lists[i].front() > lists[i].back()) { lists[i].reverse(); }
lists[0].merge(lists[i]);
}
// Return result
return lists[0];
} // merge_lists
#include "merge_lists_main.inc"
Raw
merge_lists4b.cpp
/***********************************************************************************************************************
Задача UniLecs №271: https://telegra.ph/Anons-271-Obedinenie-otsortirovannyh-svyazannyh-spiskov-05-27
Алгоритм №4B решения задачи об объединении отсортированных связных списков (самый медленный алгоритм).
Попарное объединение списков встроенной функцией объединения отсортированных списков.
Модификация с обработкой списков как с восходящими, так и с нисходящими сортировками (определяются автоматически).
________________________________________________________________________________________________________________________
Объединяем изначально пустой список (result) поочерёдно с каждым списком (штатной функцией объединения отсортированных
списков в отсортированный список), получая новый список (result2). Полученный список (result2) перекидываем в первый
(result), а тот (result2) очищаем.
По завершении цикла мы получим объединённый отсортированный список, содержащий элементы всех исходных списков.
***********************************************************************************************************************/
#define FIX_RANDOM_SEED // generate always the same lists
#include <vector>
#include <list>
#include <algorithm>
#include <iterator>
// Merge vector of sorted lists to a sorted list
template <typename T>
std::list<T> merge_lists(std::vector<std::list<T>>& lists)
{
std::list<T> result, result2;
for (const auto& list : lists) {
// Merge all lists to result2
if (list.front() <= list.back()) {
std::merge(result.begin(), result.end(), list.begin(), list.end(), std::back_inserter(result2));
} else {
std::merge(result.begin(), result.end(), list.rbegin(), list.rend(), std::back_inserter(result2));
}
result.swap(result2); // write result2 to result
result2.clear(); // clear result2
}
// Return result
return result;
} // merge_lists
#include "merge_lists_main.inc"
Raw
merge_lists5a.cpp
/***********************************************************************************************************************
Задача UniLecs №271: https://telegra.ph/Anons-271-Obedinenie-otsortirovannyh-svyazannyh-spiskov-05-27
Алгоритм №5A решения задачи об объединении отсортированных связных списков (один из самых быстрых банальных алгоритмов).
Последовательное объединение списков в один с последующей сортировкой.
Модификация с обработкой списков как с восходящими, так и с нисходящими сортировками (определяются автоматически).
________________________________________________________________________________________________________________________
Добавляем к первому списку поочерёдно все остальные списки (штатной функцией). При данном методе все добавляемые списки
очищаются. Таким образом не происходит перераспределения памяти.
После добавления сортируем и возвращаем полученный список.
***********************************************************************************************************************/
#define FIX_RANDOM_SEED // generate always the same lists
#include <vector>
#include <list>
// Merge vector of sorted lists to a sorted list
// Destroys all lists, writes result to the 1st list (lists[0])
template <typename T>
std::list<T> merge_lists(std::vector<std::list<T>>& lists)
{
if (lists.empty()) { return {}; }
for (size_t i = 1; i < lists.size(); ++i) {
// Append all lists to the 1st one
lists[0].splice(lists[0].end(), lists[i]);
}
// Sort result
lists[0].sort();
// Return result
return lists[0];
} // merge_lists
#include "merge_lists_main.inc"
Raw
merge_lists5b.cpp
/***********************************************************************************************************************
Задача UniLecs №271: https://telegra.ph/Anons-271-Obedinenie-otsortirovannyh-svyazannyh-spiskov-05-27
Алгоритм №5B решения задачи об объединении отсортированных связных списков (самый быстрый из банальных алгоритмов).
Последовательное объединение списков в один с последующей сортировкой.
Модификация с обработкой списков как с восходящими, так и с нисходящими сортировками (определяются автоматически).
________________________________________________________________________________________________________________________
Добавляем к изначально пустому списку поочерёдно все списки (штатной функцией).
После добавления сортируем и возвращаем полученный список.
Несмотря на необходимость выделения памяти, этот алгоритм почему-то работает быстрее, чем 5A.
***********************************************************************************************************************/
#define FIX_RANDOM_SEED // generate always the same lists
#include <vector>
#include <list>
// Merge vector of sorted lists to a sorted list
template <typename T>
std::list<T> merge_lists(std::vector<std::list<T>>& lists)
{
std::list<T> result;
for (const auto& list : lists) {
// Append all lists to result
result.insert(result.end(), list.begin(), list.end());
}
// Sort result
result.sort();
// Return result
return result;
} // merge_lists
#include "merge_lists_main.inc"
Raw
merge_lists6a.cpp
/***********************************************************************************************************************
Задача UniLecs №271: https://telegra.ph/Anons-271-Obedinenie-otsortirovannyh-svyazannyh-spiskov-05-27
Алгоритм №6A решения задачи об объединении отсортированных связных списков (наиболее быстрый алгоритм, но с нюансом) :)
Алгоритм с использованием сортировки подсчётом (counting sort).
Модификация с обработкой списков как с восходящими, так и с нисходящими сортировками (определяются автоматически).
________________________________________________________________________________________________________________________
Данный алгоритм применим только тогда, когда значения в списках находятся в рамках заранее известного (и не чересчур
большого) диапазона. Обладает линейной сложностью: O(n), где n – общее кол-во элементов всех списков.
Создадим массив (вектор) counts, который будет хранить кол-во каждого из значений в всех списках. Индекс массива будет
соответствовать значениям элементов из списков (уменьшенным на минимальное значение допустимого диапазона), значение –
кол-ву таких элементов во всех списках.
Далее добавим в результирующий список столько каждого из значений, сколько хранится в counts.
***********************************************************************************************************************/
#define MIN_LIST_VALUE -1000 // minimum value in lists
#define MAX_LIST_VALUE 1000000 // maximum value in lists (MAX-MIN shouldn't be too large)
#define CHECK_LIST_VALUE_RANGE // check value range in lists
#include <vector>
#include <list>
#include <type_traits>
#include <stdexcept>
// Merge vector of sorted lists to a sorted list
template <typename T>
std::list<T> merge_lists(const std::vector<std::list<T>>& lists)
{
// Count values
std::vector<size_t> counts(MAX_LIST_VALUE - MIN_LIST_VALUE + 1);
T min_value = MIN_LIST_VALUE, max_value = MAX_LIST_VALUE;
for (const auto& list : lists) {
for (const auto& el : list) {
#ifdef CHECK_LIST_VALUE_RANGE
if (el < MIN_LIST_VALUE || el > MAX_LIST_VALUE) { throw std::range_error("List range error!"); }
#endif
if (el < min_value) { min_value = el; }
if (el > max_value) { max_value = el; }
++counts[el - MIN_LIST_VALUE];
}
}
// Generate the result list
std::list<T> result;
for (T n = min_value; n <= max_value; ++n) {
result.insert(result.end(), counts[n - MIN_LIST_VALUE], n);
}
// Return result
return result;
} // merge_lists
#include "merge_lists_main.inc"
Raw
merge_lists6b.cpp
/***********************************************************************************************************************
Задача UniLecs №271: https://telegra.ph/Anons-271-Obedinenie-otsortirovannyh-svyazannyh-spiskov-05-27
Алгоритм №6B решения задачи об объединении отсортированных связных списков (очень быстрый алгоритм для беззнаковых).
Алгоритм с использованием поразрядной сортировки (radix sort).
Модификация с обработкой списков как с восходящими, так и с нисходящими сортировками (определяются автоматически).
________________________________________________________________________________________________________________________
Данный алгоритм применим только для беззнаковых целых чисел. Обладает линейной сложностью: O(n*k), где n – общее кол-во
элементов всех списков, k - кол-во байтов используемого типа (для типа int обычно равно 4). Работает немного (на 15-20%)
медленнее алгоритма 6A, не имея при этом ограничений на диапазон значений (не считая требования беззнаковости значений,
которое при необходимости можно устранить, немного модифицировав код).
Запишем все элементы списка в массив (вектор) и отсортируем его LSD-поразрядной сортировкой. После чего сформируем из
массива (вектора) список.
***********************************************************************************************************************/
#define FIX_RANDOM_SEED // generate always the same lists
#include <vector>
#include <list>
#include <algorithm>
// Merge vector of sorted lists to a sorted list
template <typename T>
std::list<T> merge_lists(const std::vector<std::list<T>>& lists)
{
// Preparation
constexpr int radix = 8, width = sizeof(T) * CHAR_BIT, mask = (1 << radix) - 1;
std::vector<T> source;
for (const auto& el : lists) {
source.insert(source.end(), el.begin(), el.end());
}
std::vector<T> dest(source.size());
std::vector<size_t> counts(1 << radix);
// Radix sort
for (int shift = 0; shift < width; shift += radix) {
if (shift) { std::fill(counts.begin(), counts.end(), 0); }
// Next three loops implement counting sort
for (const auto& el : source) { ++counts[(el >> shift) & mask]; }
size_t idx = 0;
for (auto& el : counts) { const size_t temp = el; el = idx; idx += temp; }
for (const auto& el : source) { dest[counts[(el >> shift) & mask]++] = el; }
std::swap(source, dest);
}
return {source.begin(), source.end()};
} // merge_lists
#include "merge_lists_main.inc"
Raw
merge_lists_main.inc
/////////////////////////////////////////////////////////////////
// Include file with main function for "merge lists" solutions //
/////////////////////////////////////////////////////////////////
#define LARGE_VECTOR_SIZE 1000
#define MIN_LIST_SIZE 100
#define MAX_LIST_SIZE 10000
#define FIX_RANDOM_SEED // generate always the same lists
#ifndef MIN_LIST_VALUE
#define MIN_LIST_VALUE 0 // minimum value in lists
#endif
#ifndef MAX_LIST_VALUE
#define MAX_LIST_VALUE 1'000'000'000 // maximum value in lists
#endif
#include <iostream>
#include <vector>
#include <list>
#include <algorithm>
#include <functional>
#include <random>
#include <chrono>
using std::cout;
using std::endl;
using std::vector;
using std::list;
// Display list
template <typename T>
void show_list(const list<T>& data)
{
cout << '{';
bool first = true;
for (const auto& el : data) {
if (!first) {
cout << ',';
} else { first = false; }
cout << ' ' << el;
}
cout << " }" << endl;
} // show_list
// Main function
int main()
{
vector<list<int>> lists;
// Predefined vectors of sorted lists
lists = { };
show_list(merge_lists(lists));
lists = { {}, {}, {} };
show_list(merge_lists(lists));
lists = { {1, 4, 5}, {}, {1, 3, 4}, {0}, {2, 6} };
show_list(merge_lists(lists));
lists = { {25, 9, 7}, {1, 2, 10}, {8, 5, 3}, {4, 6}, {10, 20, 30, 40, 50}, {5, 4, 3, 2, 1}};
show_list(merge_lists(lists));
// Generate vector of sorted lists
cout << endl << "Creating vector of " << LARGE_VECTOR_SIZE << " large lists..." << endl;
lists.clear();
size_t count = 0;
#ifdef FIX_RANDOM_SEED
unsigned rnd = 0;
#else
unsigned rnd = std::random_device()();
#endif
std::mt19937 rng(rnd);
std::uniform_int_distribution<int> random;
using rpt = std::uniform_int_distribution<int>::param_type;
for (size_t i = 0; i < LARGE_VECTOR_SIZE; ++i) {
lists.emplace_back();
int max_list_value = random(rng, rpt{MIN_LIST_VALUE + int(sqrt(sqrt(MAX_LIST_VALUE - MIN_LIST_VALUE))), MAX_LIST_VALUE});
for (size_t j = 0, limit = random(rng, rpt{MIN_LIST_SIZE, MAX_LIST_SIZE}); j < limit; ++j) {
lists.back().push_back(random(rng, rpt{MIN_LIST_VALUE, max_list_value}));
++count;
}
if (random(rng, rpt{0, 1}) == 0) { lists.back().sort(); } // ascending order
else { lists.back().sort(std::greater<int>()); } // descending order
}
cout << "Done (" << count << " elements)" << endl;
// Merge lists
cout << "Merging lists..." << endl;
using Clock = std::conditional_t<std::chrono::high_resolution_clock::is_steady, std::chrono::high_resolution_clock, std::chrono::steady_clock>;
auto start_time = Clock::now();
auto result = merge_lists(lists); // just merge it!
auto stop_time = Clock::now();
double duration = std::chrono::duration_cast<std::chrono::duration<double, std::ratio<1>>>(stop_time - start_time).count();
std::cout << "Done! Elapsed time: " << duration << " sec" << std::endl;
// Check result
cout << "Checking result... ";
if (result.size() == count && std::is_sorted(result.begin(), result.end())) {
cout << "success! ;)";
} else {
cout << "EPIC FAIL! :`(";
}
cout << endl;
} // main
Raw
results_clang64.txt
merge_lists0a.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
{ 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 7, 8, 9, 10, 10, 20, 25, 30, 40, 50 }
Creating vector of 1000 large lists...
Done (5097186 elements)
Merging lists...
Done! Elapsed time: 0.927367 sec
Checking result... success! ;)
merge_lists0b.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
{ 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 7, 8, 9, 10, 10, 20, 25, 30, 40, 50 }
Creating vector of 1000 large lists...
Done (5097186 elements)
Merging lists...
Done! Elapsed time: 4.66687 sec
Checking result... success! ;)
merge_lists0c.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
{ 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 7, 8, 9, 10, 10, 20, 25, 30, 40, 50 }
Creating vector of 1000 large lists...
Done (5097186 elements)
Merging lists...
Done! Elapsed time: 5.26758 sec
Checking result... success! ;)
merge_lists1a.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
{ 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 7, 8, 9, 10, 10, 20, 25, 30, 40, 50 }
Creating vector of 1000 large lists...
Done (5097186 elements)
Merging lists...
Done! Elapsed time: 2.16196 sec
Checking result... success! ;)
merge_lists1b.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
{ 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 7, 8, 9, 10, 10, 20, 25, 30, 40, 50 }
Creating vector of 1000 large lists...
Done (5097186 elements)
Merging lists...
Done! Elapsed time: 2.15036 sec
Checking result... success! ;)
merge_lists1c.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
{ 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 7, 8, 9, 10, 10, 20, 25, 30, 40, 50 }
Creating vector of 1000 large lists...
Done (5097186 elements)
Merging lists...
Done! Elapsed time: 11.0926 sec
Checking result... success! ;)
merge_lists2a.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
{ 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 7, 8, 9, 10, 10, 20, 25, 30, 40, 50 }
Creating vector of 1000 large lists...
Done (5097186 elements)
Merging lists...
Done! Elapsed time: 42.6273 sec
Checking result... success! ;)
merge_lists2b.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
{ 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 7, 8, 9, 10, 10, 20, 25, 30, 40, 50 }
Creating vector of 1000 large lists...
Done (5097186 elements)
Merging lists...
Done! Elapsed time: 37.5847 sec
Checking result... success! ;)
merge_lists3.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
{ 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 7, 8, 9, 10, 10, 20, 25, 30, 40, 50 }
Creating vector of 1000 large lists...
Done (5097186 elements)
Merging lists...
Done! Elapsed time: 166.289 sec
Checking result... success! ;)
merge_lists4a.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
{ 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 7, 8, 9, 10, 10, 20, 25, 30, 40, 50 }
Creating vector of 1000 large lists...
Done (5097186 elements)
Merging lists...
Done! Elapsed time: 65.1381 sec
Checking result... success! ;)
merge_lists4b.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
{ 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 7, 8, 9, 10, 10, 20, 25, 30, 40, 50 }
Creating vector of 1000 large lists...
Done (5097186 elements)
Merging lists...
Done! Elapsed time: 204.937 sec
Checking result... success! ;)
merge_lists5a.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
{ 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 7, 8, 9, 10, 10, 20, 25, 30, 40, 50 }
Creating vector of 1000 large lists...
Done (5097186 elements)
Merging lists...
Done! Elapsed time: 1.30321 sec
Checking result... success! ;)
merge_lists5b.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
{ 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 7, 8, 9, 10, 10, 20, 25, 30, 40, 50 }
Creating vector of 1000 large lists...
Done (5097186 elements)
Merging lists...
Done! Elapsed time: 0.993194 sec
Checking result... success! ;)
merge_lists6a.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
{ 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 7, 8, 9, 10, 10, 20, 25, 30, 40, 50 }
Creating vector of 1000 large lists...
Done (4998587 elements)
Merging lists...
Done! Elapsed time: 0.347185 sec
Checking result... success! ;)
merge_lists6b.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
{ 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 7, 8, 9, 10, 10, 20, 25, 30, 40, 50 }
Creating vector of 1000 large lists...
Done (5097186 elements)
Merging lists...
Done! Elapsed time: 0.422865 sec
Checking result... success! ;)
Raw
results_gcc64.txt
merge_lists0a.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
{ 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 7, 8, 9, 10, 10, 20, 25, 30, 40, 50 }
Creating vector of 1000 large lists...
Done (5069610 elements)
Merging lists...
Done! Elapsed time: 1.13719 sec
Checking result... success! ;)
merge_lists0b.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
{ 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 7, 8, 9, 10, 10, 20, 25, 30, 40, 50 }
Creating vector of 1000 large lists...
Done (5069610 elements)
Merging lists...
Done! Elapsed time: 4.30938 sec
Checking result... success! ;)
merge_lists0c.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
{ 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 7, 8, 9, 10, 10, 20, 25, 30, 40, 50 }
Creating vector of 1000 large lists...
Done (5069610 elements)
Merging lists...
Done! Elapsed time: 4.67753 sec
Checking result... success! ;)
merge_lists1a.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
{ 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 7, 8, 9, 10, 10, 20, 25, 30, 40, 50 }
Creating vector of 1000 large lists...
Done (5069610 elements)
Merging lists...
Done! Elapsed time: 2.48074 sec
Checking result... success! ;)
merge_lists1b.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
{ 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 7, 8, 9, 10, 10, 20, 25, 30, 40, 50 }
Creating vector of 1000 large lists...
Done (5069610 elements)
Merging lists...
Done! Elapsed time: 2.42504 sec
Checking result... success! ;)
merge_lists1c.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
{ 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 7, 8, 9, 10, 10, 20, 25, 30, 40, 50 }
Creating vector of 1000 large lists...
Done (5069610 elements)
Merging lists...
Done! Elapsed time: 15.5738 sec
Checking result... success! ;)
merge_lists2a.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
{ 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 7, 8, 9, 10, 10, 20, 25, 30, 40, 50 }
Creating vector of 1000 large lists...
Done (5069610 elements)
Merging lists...
Done! Elapsed time: 68.2797 sec
Checking result... success! ;)
merge_lists2b.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
{ 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 7, 8, 9, 10, 10, 20, 25, 30, 40, 50 }
Creating vector of 1000 large lists...
Done (5069610 elements)
Merging lists...
Done! Elapsed time: 55.2673 sec
Checking result... success! ;)
merge_lists3.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
{ 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 7, 8, 9, 10, 10, 20, 25, 30, 40, 50 }
Creating vector of 1000 large lists...
Done (5069610 elements)
Merging lists...
Done! Elapsed time: 279.653 sec
Checking result... success! ;)
merge_lists4a.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
{ 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 7, 8, 9, 10, 10, 20, 25, 30, 40, 50 }
Creating vector of 1000 large lists...
Done (5069610 elements)
Merging lists...
Done! Elapsed time: 127.108 sec
Checking result... success! ;)
merge_lists4b.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
{ 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 7, 8, 9, 10, 10, 20, 25, 30, 40, 50 }
Creating vector of 1000 large lists...
Done (5069610 elements)
Merging lists...
Done! Elapsed time: 208.837 sec
Checking result... success! ;)
merge_lists5a.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
{ 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 7, 8, 9, 10, 10, 20, 25, 30, 40, 50 }
Creating vector of 1000 large lists...
Done (5069610 elements)
Merging lists...
Done! Elapsed time: 2.54918 sec
Checking result... success! ;)
merge_lists5b.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
{ 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 7, 8, 9, 10, 10, 20, 25, 30, 40, 50 }
Creating vector of 1000 large lists...
Done (5069610 elements)
Merging lists...
Done! Elapsed time: 1.28653 sec
Checking result... success! ;)
merge_lists6a.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
{ 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 7, 8, 9, 10, 10, 20, 25, 30, 40, 50 }
Creating vector of 1000 large lists...
Done (4958792 elements)
Merging lists...
Done! Elapsed time: 0.424758 sec
Checking result... success! ;)
merge_lists6b.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
{ 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 7, 8, 9, 10, 10, 20, 25, 30, 40, 50 }
Creating vector of 1000 large lists...
Done (5069610 elements)
Merging lists...
Done! Elapsed time: 0.480631 sec
Checking result... success! ;)
Raw
results_icc64.txt
merge_lists0a.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
{ 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 7, 8, 9, 10, 10, 20, 25, 30, 40, 50 }
Creating vector of 1000 large lists...
Done (5097186 elements)
Merging lists...
Done! Elapsed time: 1.10661 sec
Checking result... success! ;)
merge_lists0b.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
{ 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 7, 8, 9, 10, 10, 20, 25, 30, 40, 50 }
Creating vector of 1000 large lists...
Done (5097186 elements)
Merging lists...
Done! Elapsed time: 4.40186 sec
Checking result... success! ;)
merge_lists0c.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
{ 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 7, 8, 9, 10, 10, 20, 25, 30, 40, 50 }
Creating vector of 1000 large lists...
Done (5097186 elements)
Merging lists...
Done! Elapsed time: 4.80277 sec
Checking result... success! ;)
merge_lists1a.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
{ 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 7, 8, 9, 10, 10, 20, 25, 30, 40, 50 }
Creating vector of 1000 large lists...
Done (5097186 elements)
Merging lists...
Done! Elapsed time: 2.64207 sec
Checking result... success! ;)
merge_lists1b.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
{ 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 7, 8, 9, 10, 10, 20, 25, 30, 40, 50 }
Creating vector of 1000 large lists...
Done (5097186 elements)
Merging lists...
Done! Elapsed time: 2.59572 sec
Checking result... success! ;)
merge_lists1c.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
{ 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 7, 8, 9, 10, 10, 20, 25, 30, 40, 50 }
Creating vector of 1000 large lists...
Done (5097186 elements)
Merging lists...
Done! Elapsed time: 15.6581 sec
Checking result... success! ;)
merge_lists2a.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
{ 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 7, 8, 9, 10, 10, 20, 25, 30, 40, 50 }
Creating vector of 1000 large lists...
Done (5097186 elements)
Merging lists...
Done! Elapsed time: 55.0799 sec
Checking result... success! ;)
merge_lists2b.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
{ 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 7, 8, 9, 10, 10, 20, 25, 30, 40, 50 }
Creating vector of 1000 large lists...
Done (5097186 elements)
Merging lists...
Done! Elapsed time: 53.1573 sec
Checking result... success! ;)
merge_lists3.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
{ 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 7, 8, 9, 10, 10, 20, 25, 30, 40, 50 }
Creating vector of 1000 large lists...
Done (5097186 elements)
Merging lists...
Done! Elapsed time: 289.074 sec
Checking result... success! ;)
merge_lists4a.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
{ 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 7, 8, 9, 10, 10, 20, 25, 30, 40, 50 }
Creating vector of 1000 large lists...
Done (5097186 elements)
Merging lists...
Done! Elapsed time: 130.564 sec
Checking result... success! ;)
merge_lists4b.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
{ 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 7, 8, 9, 10, 10, 20, 25, 30, 40, 50 }
Creating vector of 1000 large lists...
Done (5097186 elements)
Merging lists...
Done! Elapsed time: 209.664 sec
Checking result... success! ;)
merge_lists5a.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
{ 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 7, 8, 9, 10, 10, 20, 25, 30, 40, 50 }
Creating vector of 1000 large lists...
Done (5097186 elements)
Merging lists...
Done! Elapsed time: 2.17886 sec
Checking result... success! ;)
merge_lists5b.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
{ 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 7, 8, 9, 10, 10, 20, 25, 30, 40, 50 }
Creating vector of 1000 large lists...
Done (5097186 elements)
Merging lists...
Done! Elapsed time: 1.05896 sec
Checking result... success! ;)
merge_lists6a.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
{ 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 7, 8, 9, 10, 10, 20, 25, 30, 40, 50 }
Creating vector of 1000 large lists...
Done (4998587 elements)
Merging lists...
Done! Elapsed time: 0.416111 sec
Checking result... success! ;)
merge_lists6b.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
{ 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 7, 8, 9, 10, 10, 20, 25, 30, 40, 50 }
Creating vector of 1000 large lists...
Done (5097186 elements)
Merging lists...
Done! Elapsed time: 0.528091 sec
Checking result... success! ;)
Raw
results_vc64.txt
merge_lists0a.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
{ 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 7, 8, 9, 10, 10, 20, 25, 30, 40, 50 }
Creating vector of 1000 large lists...
Done (5097186 elements)
Merging lists...
Done! Elapsed time: 0.863297 sec
Checking result... success! ;)
merge_lists0b.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
{ 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 7, 8, 9, 10, 10, 20, 25, 30, 40, 50 }
Creating vector of 1000 large lists...
Done (5097186 elements)
Merging lists...
Done! Elapsed time: 4.34769 sec
Checking result... success! ;)
merge_lists0c.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
{ 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 7, 8, 9, 10, 10, 20, 25, 30, 40, 50 }
Creating vector of 1000 large lists...
Done (5097186 elements)
Merging lists...
Done! Elapsed time: 4.71704 sec
Checking result... success! ;)
merge_lists1a.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
{ 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 7, 8, 9, 10, 10, 20, 25, 30, 40, 50 }
Creating vector of 1000 large lists...
Done (5097186 elements)
Merging lists...
Done! Elapsed time: 2.25888 sec
Checking result... success! ;)
merge_lists1b.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
{ 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 7, 8, 9, 10, 10, 20, 25, 30, 40, 50 }
Creating vector of 1000 large lists...
Done (5097186 elements)
Merging lists...
Done! Elapsed time: 2.23409 sec
Checking result... success! ;)
merge_lists1c.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
{ 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 7, 8, 9, 10, 10, 20, 25, 30, 40, 50 }
Creating vector of 1000 large lists...
Done (5097186 elements)
Merging lists...
Done! Elapsed time: 10.3082 sec
Checking result... success! ;)
merge_lists2a.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
{ 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 7, 8, 9, 10, 10, 20, 25, 30, 40, 50 }
Creating vector of 1000 large lists...
Done (5097186 elements)
Merging lists...
Done! Elapsed time: 42.508 sec
Checking result... success! ;)
merge_lists2b.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
{ 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 7, 8, 9, 10, 10, 20, 25, 30, 40, 50 }
Creating vector of 1000 large lists...
Done (5097186 elements)
Merging lists...
Done! Elapsed time: 37.6744 sec
Checking result... success! ;)
merge_lists3.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
{ 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 7, 8, 9, 10, 10, 20, 25, 30, 40, 50 }
Creating vector of 1000 large lists...
Done (5097186 elements)
Merging lists...
Done! Elapsed time: 175.24 sec
Checking result... success! ;)
merge_lists4a.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
{ 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 7, 8, 9, 10, 10, 20, 25, 30, 40, 50 }
Creating vector of 1000 large lists...
Done (5097186 elements)
Merging lists...
Done! Elapsed time: 64.5252 sec
Checking result... success! ;)
merge_lists4b.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
{ 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 7, 8, 9, 10, 10, 20, 25, 30, 40, 50 }
Creating vector of 1000 large lists...
Done (5097186 elements)
Merging lists...
Done! Elapsed time: 207.028 sec
Checking result... success! ;)
merge_lists5a.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
{ 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 7, 8, 9, 10, 10, 20, 25, 30, 40, 50 }
Creating vector of 1000 large lists...
Done (5097186 elements)
Merging lists...
Done! Elapsed time: 1.33355 sec
Checking result... success! ;)
merge_lists5b.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
{ 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 7, 8, 9, 10, 10, 20, 25, 30, 40, 50 }
Creating vector of 1000 large lists...
Done (5097186 elements)
Merging lists...
Done! Elapsed time: 1.02388 sec
Checking result... success! ;)
merge_lists6a.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
{ 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 7, 8, 9, 10, 10, 20, 25, 30, 40, 50 }
Creating vector of 1000 large lists...
Done (4998587 elements)
Merging lists...
Done! Elapsed time: 0.35109 sec
Checking result... success! ;)
merge_lists6b.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
{ 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 7, 8, 9, 10, 10, 20, 25, 30, 40, 50 }
Creating vector of 1000 large lists...
Done (5097186 elements)
Merging lists...
Done! Elapsed time: 0.440671 sec
Checking result... success! ;)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment