Неупорядоченная карта для наивного решения C ++
У меня есть задание на C ++, где я должен придумать наивное решение проблемы Кнута с выбранным контейнером и изучить сгенерированные данные о производительности. Смотрите проблему ниже:
Три миллиона человек с разными именами были проложены из конца в конец, из Нью-Йорка в Калифорнию. Каждому участнику дали листок бумаги, на котором он записал свое имя и имя человека, находящегося непосредственно к западу от него в строке. Человек на крайнем западном конце линии не понимал, что делать, поэтому он выбросил свою газету; оставшиеся 2999999 листов бумаги были помещены в огромную корзину и доставлены в Национальный архив в Вашингтоне, округ Колумбия. Здесь содержимое корзины было полностью перемешано и передано на магнитные ленты.
В этот момент ученый-информатор заметил, что на лентах было достаточно информации, чтобы восстановить список людей в их первоначальном порядке. И ученый-компьютерщик нашел способ выполнить реконструкцию с менее чем 1000 проходов через ленты данных, используя только последовательный доступ к лентам и небольшой объем оперативной памяти. Как это было возможно?
[Другими словами, учитывая пары (xi, xi + 1) для 1 ≤ i < N, в случайном порядке, где xi различны, как можно получить последовательность x1 x2… .xN, ограничивая все операции последовательными методами, подходящими для использования на магнитных лентах. Это проблема сортировки по порядку, когда нет простого способа определить, какой из двух заданных ключей предшествует другому;
Исходя из моих исследований, я решил использовать unordered_map вместо списка или карты нормалей. Что я не понимаю, так это наивное решение, которое было предоставлено нам для реализации в виде кода:
Рассмотрим документы как набор кортежей (имя, имя), и из этих кортежей можно установить как преемника (западного соседа), так и предшественника (восточного соседа).
- identify an individual xc
- append xc to empty list
- while xc has westerly neighbour
- xc < westerly neighbour of xc
- append xc to list
- xc < head of list
- while xc has easterly neighbour
- xc < easterly neighbour of xc
- prepend xc to list
Мой первый вопрос — является ли xc случайным элементом, так как порядок не может быть определен из-за характера контейнера?
Мой второй вопрос — имена, которые нам дали, находятся в файле примерно так:
Hazbgaei,Ckwkkkxa
Hrunmkoc,Usjgmunt
Cmkcwncb,Ycrnwzjl
Oygvmrhf,Hylmukiw
Jursaual,Gzrddsbg
Так наивное решение говорит, что я должен взять имя и поместить его в один список, затем фамилию и поместить его в другой список?
Извиняюсь, если я полностью выключен, но я действительно пытался понять это!
Решение
Я считаю, что решение говорит использовать один список. Выберите первый кортеж и укажите его имя в качестве заголовка списка, а западного соседа — в качестве следующего элемента. Затем найдите кортеж с западным соседом в качестве имени (которое, конечно, является трудной частью), возьмите западного соседа из этого кортежа и добавьте его в список. Повторяйте до тех пор, пока не найдете кортеж с именем последнего добавленного человека. Тогда вы знаете, что достигли западного побережья.
Итак, первый xc по сути случайный. После этого xc является детерминированным. Строка, которая говорит
- while xc has westerly neighbour
по сути говоря, «найдите тот кортеж, у которого в качестве имени есть текущий западный сосед».
Последняя часть, конечно, просто применяет ту же логику в обратном порядке, чтобы заполнить цепь, идущую на восток.
Другие решения
Я делаю это как ответ, потому что невозможно спросить это как комментарий. Также уточняю это ИМХО хотя бы половина ответа
Это подразумевается следующим образом?
identify an individual xc
append xc to empty list
while( xc has westerly neighbour )
{
if( xc < westerly neighbour of xc )
{
append xc to list
}
// Do not understand this:
// - xc < head of list
}
while( while xc has easterly neighbour )
{
if( xc < easterly neighbour of xc )
{
prepend xc to list
}
}
(Это просто попытка приблизиться к решению — я даже не думал об алгоритме …)
identify an individual xc
append xc to empty list
while( xc has westerly neighbour )
{
xc := westerly neighbour of xc
append xc to list
xc := head of list
while( xc has easterly neighbour )
{
xc := easterly neighbour of xc
prepend xc to list
}
}
Кажется, что в этом есть какой-то смысл: так что вы пробежитесь по списку, соберете всех западных соседей, насколько это возможно, и сделаете это со всеми восточными после этого. Таким образом, при каждом запуске исходного списка отсортированный список становится длиннее и длиннее.
ИМХО чего-то не хватает: если я интерпретирую всю имеющуюся информацию, я прихожу к следующему решению. Но для этого нужно намного больше отсканировать оригинальную ленту: вместо заданных 10000 раз она сканирует ее около 750 000 раз. Есть идеи?
#include <vector>
#include <algorithm>
#include <iostream>
#include <list>
size_t constexpr max_men { 3000000 };
typedef std::tuple< int, int > neighbors_t;
typedef std::vector< neighbors_t > pool_t;
int main() {
// Need a vector here for random_shuffle - but using it further down
// just with sequencial methods.
pool_t pool_list;
for( size_t i { 0 }; i < max_men - 1; ++i ) {
pool_list.push_back( std::make_tuple( i, i + 1) );
}
std::random_shuffle( pool_list.begin(), pool_list.end() );// Use the algorithm to get it sorted again
// identify an individual xc:
// Pick first from first tuple
// append xc to empty list
std::list<int> sorted_list;
sorted_list.push_back( std::get<0>( pool_list.front() ) );
// Count the number of tape scans
size_t tape_scans { 0 };
do {
// Scan through the pool_list
for( neighbors_t n : pool_list ) {
#if 0
std::cout << "n [" << std::get<0>( n )
<< "] sorted_list [";
for( int i : sorted_list ) {
std::cout << i << " ";
}
std::cout << "]" << std::endl;
#endif
// while( xc has westerly neighbour )
// Found westerly neighbour
if( std::get< 1 >( n ) == sorted_list.front() ) {
// append xc to list
sorted_list.push_front( std::get< 0 >( n ) );
}
if( std::get< 0 >( n ) == sorted_list.back() ) {
// append xc to list
sorted_list.push_back( std::get< 1 >( n ) );
}
}
++tape_scans;
std::cout << "Tape Scans needed [" << tape_scans
<< "] sorted list size [" << sorted_list.size() << "]"<< std::endl;
} while( sorted_list.size() < max_men );
std::cout << "Tape Scans needed [" << tape_scans << "]" << std::endl;
return 0;
}