Skip to content

Instantly share code, notes, and snippets.

@jin-x

jin-x/merge_lists0a.cpp

Last active June 18, 2021 13:34
Show Gist options
  • Save jin-x/4d4dd84e0a434630d197ee48c82a2e06 to your computer and use it in GitHub Desktop.
Save jin-x/4d4dd84e0a434630d197ee48c82a2e06 to your computer and use it in GitHub Desktop.
Download ZIP
@jinxonik / UniLecs #271
Raw
merge_lists0a.cpp
/***********************************************************************************************************************
Задача UniLecs №271: https://telegra.ph/Anons-271-Obedinenie-otsortirovannyh-svyazannyh-spiskov-05-27
Алгоритм №0A решения задачи об объединении отсортированных связных списков (самый быстрый и правильный алгоритм) :)
Алгоритм с использованием приоритетной очереди.
________________________________________________________________________________________________________________________
Добавим в приоритетную очередь итераторы, указывающие на начало каждого списка (только для непустых списков).
Запустим цикл, повторяя его, пока приоритетная очередь содержит элементы. В цикле будем извлекать (и удалять) из очереди
наименьший элемент (вернее, итератор, указывающий на наименьший элемент) и записывать его в результирующий список. Затем
будем увеличивать извлечённый итератор, перемещаясь к следующему элементу списка, и если список не закончился, помещать
его обратно в очередь.
По завершении цикла мы получим объединённый отсортированный список, содержащий элементы всех исходных списков.
***********************************************************************************************************************/
#include <vector>
#include <list>
#include <queue>
#include <functional>
// 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;
operator T() {
return value;
}
};
// 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()) {
list_iters.push(ListElement{el.front(), el.begin(), el.end()}); // the 1st value, start and end of list
}
}
// 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.next != top.end) { // increment iterator to the next value in list
top.value = *top.next; // get the next value in list
list_iters.push(top); // add incremented 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& a_list : lists) {
for (const auto& el : a_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;
};
std::vector<ListPosition> list_iters;
for (const auto& el : lists) {
if (el.begin() != el.end()) {
list_iters.push_back(ListPosition{el.begin(), el.end()}); // the 1st value, start and end of list
}
}
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.next < *b.next); });
// Main loop
std::list<T> result;
do {
result.push_back(*list_iters.front().next++);
// 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.next < *b.next)); });
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;
};
std::vector<ListPosition> list_iters;
for (const auto& el : lists) {
if (el.begin() != el.end()) {
list_iters.push_back(ListPosition{el.begin(), el.end()}); // the 1st value and end of list
}
}
// Sort iterators by value
std::sort(list_iters.begin(), list_iters.end(),
[](const ListPosition& a, const ListPosition& b)
{ return (*a.next < *b.next); });
// Main loop
std::list<T> result;
size_t finish_count = 0;
while (finish_count != list_iters.size()) {
result.push_back(*list_iters.front().next++);
// 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.next < *b.next); });
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;
};
std::vector<ListPosition> list_iters;
for (const auto& el : lists) {
if (el.begin() != el.end()) {
list_iters.push_back(ListPosition{el.begin(), el.end()}); // the 1st value and end of list
}
}
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.next < *b.next); });
// Main loop
std::list<T> result;
do {
result.push_back(*list_iters.front().next++);
// 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.next <= *el.next)) { 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;
};
std::vector<ListPosition> list_iters;
for (const auto& el : lists) {
if (el.begin() != el.end()) {
list_iters.push_back(ListPosition{el.begin(), el.end()}); // the 1st value and end of list
}
}
// 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.next) {
min_value = *el.next;
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].next++);
};
// 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;
};
std::vector<ListPosition> list_iters;
for (const auto& el : lists) {
if (el.begin() != el.end()) {
list_iters.push_back(ListPosition{el.begin(), el.end()}); // the 1st value and end of list
}
}
// 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].next;
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.next++);
// 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;
};
std::vector<ListPosition> list_iters;
for (const auto& el : lists) {
if (el.begin() != el.end()) {
list_iters.push_back(ListPosition{el.begin(), el.end()}); // the 1st value and end of list
}
}
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.next < *b.next)); });
if (list_iters.front().next == list_iters.front().end) { break; }
// Add minimal element to list
result.push_back(*list_iters.front().next++);
};
// 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 {}; }
for (size_t i = 1; i < lists.size(); ++i) {
// Merge all lists to the 1st one
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& alist : lists) {
// Merge all lists to result2
std::merge(result.begin(), result.end(), alist.begin(), alist.end(), 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& alist : lists) {
// Append all lists to result
result.insert(result.end(), alist.begin(), alist.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& a_list : lists) {
for (const auto& el : a_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 <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));
// 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;
}
lists.back().sort();
}
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 }
Creating vector of 1000 large lists...
Done (5072361 elements)
Merging lists...
Done! Elapsed time: 0.855275 sec
Checking result... success! ;)
merge_lists0b.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
Creating vector of 1000 large lists...
Done (5072361 elements)
Merging lists...
Done! Elapsed time: 4.67464 sec
Checking result... success! ;)
merge_lists0c.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
Creating vector of 1000 large lists...
Done (5072361 elements)
Merging lists...
Done! Elapsed time: 5.28728 sec
Checking result... success! ;)
merge_lists1a.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
Creating vector of 1000 large lists...
Done (5072361 elements)
Merging lists...
Done! Elapsed time: 1.32364 sec
Checking result... success! ;)
merge_lists1b.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
Creating vector of 1000 large lists...
Done (5072361 elements)
Merging lists...
Done! Elapsed time: 1.3228 sec
Checking result... success! ;)
merge_lists1c.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
Creating vector of 1000 large lists...
Done (5072361 elements)
Merging lists...
Done! Elapsed time: 6.88943 sec
Checking result... success! ;)
merge_lists2a.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
Creating vector of 1000 large lists...
Done (5072361 elements)
Merging lists...
Done! Elapsed time: 33.9143 sec
Checking result... success! ;)
merge_lists2b.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
Creating vector of 1000 large lists...
Done (5072361 elements)
Merging lists...
Done! Elapsed time: 29.368 sec
Checking result... success! ;)
merge_lists3.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
Creating vector of 1000 large lists...
Done (5072361 elements)
Merging lists...
Done! Elapsed time: 95.3676 sec
Checking result... success! ;)
merge_lists4a.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
Creating vector of 1000 large lists...
Done (5072361 elements)
Merging lists...
Done! Elapsed time: 61.79 sec
Checking result... success! ;)
merge_lists4b.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
Creating vector of 1000 large lists...
Done (5072361 elements)
Merging lists...
Done! Elapsed time: 204.083 sec
Checking result... success! ;)
merge_lists5a.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
Creating vector of 1000 large lists...
Done (5072361 elements)
Merging lists...
Done! Elapsed time: 1.25867 sec
Checking result... success! ;)
merge_lists5b.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
Creating vector of 1000 large lists...
Done (5072361 elements)
Merging lists...
Done! Elapsed time: 0.957205 sec
Checking result... success! ;)
merge_lists6a.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
Creating vector of 1000 large lists...
Done (4923020 elements)
Merging lists...
Done! Elapsed time: 0.340481 sec
Checking result... success! ;)
merge_lists6b.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
Creating vector of 1000 large lists...
Done (5072361 elements)
Merging lists...
Done! Elapsed time: 0.423613 sec
Checking result... success! ;)
Raw
results_gcc64.txt
merge_lists0a.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
Creating vector of 1000 large lists...
Done (4996204 elements)
Merging lists...
Done! Elapsed time: 1.06179 sec
Checking result... success! ;)
merge_lists0b.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
Creating vector of 1000 large lists...
Done (4996204 elements)
Merging lists...
Done! Elapsed time: 4.26047 sec
Checking result... success! ;)
merge_lists0c.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
Creating vector of 1000 large lists...
Done (4996204 elements)
Merging lists...
Done! Elapsed time: 4.62432 sec
Checking result... success! ;)
merge_lists1a.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
Creating vector of 1000 large lists...
Done (4996204 elements)
Merging lists...
Done! Elapsed time: 1.54837 sec
Checking result... success! ;)
merge_lists1b.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
Creating vector of 1000 large lists...
Done (4996204 elements)
Merging lists...
Done! Elapsed time: 1.52848 sec
Checking result... success! ;)
merge_lists1c.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
Creating vector of 1000 large lists...
Done (4996204 elements)
Merging lists...
Done! Elapsed time: 6.33579 sec
Checking result... success! ;)
merge_lists2a.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
Creating vector of 1000 large lists...
Done (4996204 elements)
Merging lists...
Done! Elapsed time: 30.864 sec
Checking result... success! ;)
merge_lists2b.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
Creating vector of 1000 large lists...
Done (4996204 elements)
Merging lists...
Done! Elapsed time: 28.8803 sec
Checking result... success! ;)
merge_lists3.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
Creating vector of 1000 large lists...
Done (4996204 elements)
Merging lists...
Done! Elapsed time: 119.42 sec
Checking result... success! ;)
merge_lists4a.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
Creating vector of 1000 large lists...
Done (4996204 elements)
Merging lists...
Done! Elapsed time: 124.981 sec
Checking result... success! ;)
merge_lists4b.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
Creating vector of 1000 large lists...
Done (4996204 elements)
Merging lists...
Done! Elapsed time: 204.656 sec
Checking result... success! ;)
merge_lists5a.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
Creating vector of 1000 large lists...
Done (4996204 elements)
Merging lists...
Done! Elapsed time: 2.48941 sec
Checking result... success! ;)
merge_lists5b.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
Creating vector of 1000 large lists...
Done (4996204 elements)
Merging lists...
Done! Elapsed time: 1.20413 sec
Checking result... success! ;)
merge_lists6a.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
Creating vector of 1000 large lists...
Done (5062182 elements)
Merging lists...
Done! Elapsed time: 0.433972 sec
Checking result... success! ;)
merge_lists6b.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
Creating vector of 1000 large lists...
Done (4996204 elements)
Merging lists...
Done! Elapsed time: 0.473811 sec
Checking result... success! ;)
Raw
results_icc64.txt
merge_lists0a.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
Creating vector of 1000 large lists...
Done (5072361 elements)
Merging lists...
Done! Elapsed time: 1.05706 sec
Checking result... success! ;)
merge_lists0b.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
Creating vector of 1000 large lists...
Done (5072361 elements)
Merging lists...
Done! Elapsed time: 4.44142 sec
Checking result... success! ;)
merge_lists0c.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
Creating vector of 1000 large lists...
Done (5072361 elements)
Merging lists...
Done! Elapsed time: 4.79492 sec
Checking result... success! ;)
merge_lists1a.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
Creating vector of 1000 large lists...
Done (5072361 elements)
Merging lists...
Done! Elapsed time: 1.6693 sec
Checking result... success! ;)
merge_lists1b.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
Creating vector of 1000 large lists...
Done (5072361 elements)
Merging lists...
Done! Elapsed time: 1.61018 sec
Checking result... success! ;)
merge_lists1c.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
Creating vector of 1000 large lists...
Done (5072361 elements)
Merging lists...
Done! Elapsed time: 7.17613 sec
Checking result... success! ;)
merge_lists2a.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
Creating vector of 1000 large lists...
Done (5072361 elements)
Merging lists...
Done! Elapsed time: 33.522 sec
Checking result... success! ;)
merge_lists2b.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
Creating vector of 1000 large lists...
Done (5072361 elements)
Merging lists...
Done! Elapsed time: 29.66 sec
Checking result... success! ;)
merge_lists3.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
Creating vector of 1000 large lists...
Done (5072361 elements)
Merging lists...
Done! Elapsed time: 108.372 sec
Checking result... success! ;)
merge_lists4a.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
Creating vector of 1000 large lists...
Done (5072361 elements)
Merging lists...
Done! Elapsed time: 129.291 sec
Checking result... success! ;)
merge_lists4b.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
Creating vector of 1000 large lists...
Done (5072361 elements)
Merging lists...
Done! Elapsed time: 206.785 sec
Checking result... success! ;)
merge_lists5a.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
Creating vector of 1000 large lists...
Done (5072361 elements)
Merging lists...
Done! Elapsed time: 2.16324 sec
Checking result... success! ;)
merge_lists5b.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
Creating vector of 1000 large lists...
Done (5072361 elements)
Merging lists...
Done! Elapsed time: 1.01737 sec
Checking result... success! ;)
merge_lists6a.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
Creating vector of 1000 large lists...
Done (4923020 elements)
Merging lists...
Done! Elapsed time: 0.415852 sec
Checking result... success! ;)
merge_lists6b.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
Creating vector of 1000 large lists...
Done (5072361 elements)
Merging lists...
Done! Elapsed time: 0.517393 sec
Checking result... success! ;)
Raw
results_vc64.txt
merge_lists0a.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
Creating vector of 1000 large lists...
Done (5072361 elements)
Merging lists...
Done! Elapsed time: 0.830519 sec
Checking result... success! ;)
merge_lists0b.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
Creating vector of 1000 large lists...
Done (5072361 elements)
Merging lists...
Done! Elapsed time: 4.37509 sec
Checking result... success! ;)
merge_lists0c.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
Creating vector of 1000 large lists...
Done (5072361 elements)
Merging lists...
Done! Elapsed time: 4.75224 sec
Checking result... success! ;)
merge_lists1a.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
Creating vector of 1000 large lists...
Done (5072361 elements)
Merging lists...
Done! Elapsed time: 1.36583 sec
Checking result... success! ;)
merge_lists1b.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
Creating vector of 1000 large lists...
Done (5072361 elements)
Merging lists...
Done! Elapsed time: 1.38099 sec
Checking result... success! ;)
merge_lists1c.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
Creating vector of 1000 large lists...
Done (5072361 elements)
Merging lists...
Done! Elapsed time: 6.56724 sec
Checking result... success! ;)
merge_lists2a.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
Creating vector of 1000 large lists...
Done (5072361 elements)
Merging lists...
Done! Elapsed time: 34.7076 sec
Checking result... success! ;)
merge_lists2b.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
Creating vector of 1000 large lists...
Done (5072361 elements)
Merging lists...
Done! Elapsed time: 30.5825 sec
Checking result... success! ;)
merge_lists3.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
Creating vector of 1000 large lists...
Done (5072361 elements)
Merging lists...
Done! Elapsed time: 98.6015 sec
Checking result... success! ;)
merge_lists4a.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
Creating vector of 1000 large lists...
Done (5072361 elements)
Merging lists...
Done! Elapsed time: 61.5054 sec
Checking result... success! ;)
merge_lists4b.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
Creating vector of 1000 large lists...
Done (5072361 elements)
Merging lists...
Done! Elapsed time: 205.942 sec
Checking result... success! ;)
merge_lists5a.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
Creating vector of 1000 large lists...
Done (5072361 elements)
Merging lists...
Done! Elapsed time: 1.27384 sec
Checking result... success! ;)
merge_lists5b.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
Creating vector of 1000 large lists...
Done (5072361 elements)
Merging lists...
Done! Elapsed time: 0.966746 sec
Checking result... success! ;)
merge_lists6a.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
Creating vector of 1000 large lists...
Done (4923020 elements)
Merging lists...
Done! Elapsed time: 0.354751 sec
Checking result... success! ;)
merge_lists6b.exe
{ }
{ }
{ 0, 1, 1, 2, 3, 4, 4, 5, 6 }
Creating vector of 1000 large lists...
Done (5072361 elements)
Merging lists...
Done! Elapsed time: 0.435538 sec
Checking result... success! ;)
@xmichael446
Copy link

Wow!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment