В этой статье я хочу представить алгоритм оптимизации хранения данных для быстрого поиска (на примере контейнера map).
Итак, задание
Есть некая электронная книга, которую одновременно читает неограниченное количество читателей. Нужно сделать так, чтобы заданный читатель в любой момент мог проверить, какая доля пользователей прочитала меньшую часть книги, чем он . Наивным решением было бы хранить в std::map<int,int> в качестве ключа номера страниц, в качестве значения- количество прочитавших их пользователей. Конечно, при таком подходе программа медленно работает с большими тестами потому, что количество итераций по контейнеру map равняется числу прочитанных пользователем страниц. То есть, если пользователь прочел 1000 страниц из 1000 возможных, то в цикле нужно будет сделать 1000 итераций, и это сильно замедляет программу.
Чтобы уменьшить время работы программы, нужно упростить алгоритм подсчета пользователей. В этом алгоритме отдельно подсчитывается, сколько пользователей читают каждую из предшествующих сотен страниц, и затем уже постранично суммируются все, кто прочел меньшее количество страниц из той сотни, на которой сейчас находится читатель. Как вы уже, наверное, догадались, для такого алгоритма понадобится завести отдельный контейнер, в котором для каждой сотни страниц будет хранится количество читающих ее пользователей. Такой алгоритм позволяет вместо 998 итераций (если пользователь читает 999-ю страницу) сделать всего 107 (9 итераций сотням и 98 по единичным страницам).
Это вкратце, теперь перейдем к подробному описанию и для начала приведу код.
#include <iomanip>
#include <iostream>
#include <vector>
#include <utility>
#include <map>
using namespace std;
class ReadingManager {
public:
//ф-я отмечает, какую страницу читает пользователь
void Read(int user_id, int page_count)
{
if (pages_by_users.find(user_id)!= pages_by_users.end())
{
//уменьшаем количество читателей в той сотне страниц, на которой ранее был пользователь
hundreds_of_users[((pages_by_users[user_id] - (pages_by_users[user_id] % 100)) + 100)/100]--;
//уменьшаем ко-во читателей на уже прочитанной странице
users_by_pages[pages_by_users[user_id]]--;
}
pages_by_users[user_id] = page_count;
users_by_pages[page_count]++;
// увеличиваем на 1 число пользователей, дочитавших до данной сотни страниц.
hundreds_of_users[((pages_by_users[user_id] - (pages_by_users[user_id] % 100)) + 100) / 100]++;
}
//ф-я сообщает пользователю, сколько читателей прочли меньше, чем он
float Cheer(int user_id)
{
//пользователь пока не прочел ни одной страницы
if (!pages_by_users.count(user_id))
{ return 0; }
//пользователь - единственный читатель
if (pages_by_users.size() == 1)
{ return 1; }
//номер страницы, которую читает пользователь
int read_by_user = pages_by_users.at(user_id);
int total_users_less = 0;
// с какого числа начинать постраничный подсчет пользователей
int bottom_border = (read_by_user>99)?(read_by_user - (read_by_user % 100)):1;
// пока никто, кроме читателя, не дочитал до этой страницы
if (users_by_pages.find(bottom_border) == users_by_pages.end())
{ users_by_pages [bottom_border]=0; }
map<int, int >::const_iterator it;
for (it = users_by_pages.find(bottom_border); it != users_by_pages.end();++it)
{
//пока не дойдем до страницы читателя
if (it->first == read_by_user)
{ break; }
//постранично суммируем всех читателей в данной сотне
total_users_less += it->second;
}
// подсчет читателей по сотням страниц
if (read_by_user > 99)
{
int hundreds = 1, x = (read_by_user - (read_by_user % 100)) / 100;
while (hundreds <= x)
{
total_users_less += hundreds_of_users[hundreds];
hundreds++;
}
}
return float(total_users_less) / (pages_by_users.size() - 1);
}
private:
map<int, int> pages_by_users; //читатели - страницы
map<int,int> users_by_pages; // страницы - читатели
int hundreds_of_users[10] = { 0 }; // массив для поделенных на сотни страниц
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
ReadingManager manager;
unsigned long int query_count;
cin >> query_count;
unsigned long int query_id = 0;
string query_type;
int user_id;
while (query_id < query_count)
{
cin >> query_type;
cin >> user_id;
if (query_type == "READ")
{
int page_count;
cin >> page_count;
manager.Read(user_id, page_count);
}
else if (query_type == "CHEER")
{
cout << setprecision(6) << manager.Cheer(user_id) << "\n";
}
++query_id;
}
return 0;
} Во-первых, в отдельном массиве нужно для каждой сотни страниц хранить, сколько пользователей в данный момент читают одну из страниц в этой сотне. Для этого нужно разбить страницы на сотни и при каждом вызове функции Read учитывать, сколько пользователей перешли на чтение новой сотни страниц (сколько пользователей читают страницы с 1-99, с 100-199 и тд). Страницы округляются вверх до ближайшей сотни ((pages_by_users[user_id] - (pages_by_users[user_id] % 100)) + 100). Так, страницу 135 округляем до 200, 765 до 800, 38 до 100.
Предварительно находим в pages_by_users до какой станицы пользователь, если это не новый пользователь, дочитал в прошлый раз, вычисляем по той же формуле, до какой сотни была округлена страница, и уменьшаем число пользователей, читающих эту сотню, на единицу. Затем вычисляем новую сотню и увеличиваем число читателей в ней на единицу. Эти данные удобно хранить в массиве из 11 элементов (для 1000 страниц), при создании все элементы инициализируются нулями. Чтобы соотнести сотни страниц с индексами массива, полученная сотня делится на 100. В ячейке массива с индексом 1 хранится, сколько пользователей читают страницы с 1 по 99, с индексом 2- сколько читают страницы с 100 по 199 и тд.
hundreds_of_users[((pages_by_users[user_id] - (pages_by_users[user_id] % 100)) + 100) / 100]++; // увеличиваем на 1 число пользователей, дочитавших до данной сотни страниц. Скажем, страницы с 301-400 читают 98 человек.
Теперь не нужно проходить по всем страницам в цикле, достаточно округлить page_count вниз до ближайшей сотни( с 567 до 500, например), чтобы выяснить, до какой страницы можно считать пользователей по сотням страниц. Эти данные мы возьмем из массива:
if (read_by_user > 99)
{
int hundreds = 1, x = (read_by_user - (read_by_user % 100)) / 100;
while (hundreds <= x)
{
total_users_less += hundreds_of_users[hundreds];
hundreds++;
}
} Для учета пользователей, которые прочли 500 страниц, понадобится всего 5 итераций.
2) Итоговое число пользователей, которые прочли меньше, чем искомый пользователь, найдем из users_by_pages. Нам понадобится сделать уже не 567, а всего 66 итераций. Если page_count меньше 100, то есть, пользователь не дочитал полную сотню страниц, нельзя учитывать всех, кто читает эту же сотню страниц. В таком случае за количество итераций, равное (read_by_user -1), суммируем в map всех, кто прочитал меньше.
Алгоритм позволяет значительно ускорить поиск, при этом использует минимум дополнительной памяти.
Спасибо за внимание.
Комментарии (12)
lyagushkaa
21.07.2023 14:11+2А можно было бы просто из "неограниченного числа читателей" вычесть число пользователей, прочитавших столько же страниц, сколько и заданный, но тогда бы не родилась статья :)
Amina_Zubairova Автор
21.07.2023 14:11По условиям задачи мы не знаем, сколько пользователей прочитало столько же страниц, что и искомый пользователь. Этот параметр постоянно меняется. И нужно реализовать быстрый подсчет с минимальным использованием дополнительной памяти. При количестве читателей, скажем, 1млн, создавать массив на 1 млн ячеек не рационально. Хотя, Вы правы, это самый простой способ, наивный алгоритм.
xxxphilinxxx
21.07.2023 14:11+2Промежуточные суммы вижу, а где хеширование из заголовка? В вычислении ключа этих сумм?
Тут выше упомянули дерево отрезков - вы его фактически и реализовали, просто зафиксировали кол-во уровней на трех (книга/сотни/страницы) и зафиксировали кол-во потомков на третьем уровне на сотне элементов.
А можно было бы просто из "неограниченного числа читателей" вычесть число пользователей, прочитавших столько же страниц, сколько и заданный, но тогда бы не родилась статья :)
По условиям задачи мы не знаем, сколько пользователей прочитало столько же страниц, что и искомый пользователь.Если хранить счетчик пользователей, не читающих страницу, а уже прочитавших ее, то все как раз становится тривиально:
total_book_readers - pages_read_count[current_pages[user_id]-1]. Даже Read станет проще, не нужно будет декрементить предыдущую страницу.Плюс не более 99 итераций для поиска в users_by_pages , это константа и при расчете сложности она не учитывается.
99 итераций помимо остальных действий для вас несущественны, а в статье 1000 называете уже сильно замедляющими программу, хотя тут всего один порядок разницы.
Получаем тот же O(log N).
Логарифм у вас там в поиске по пользователям, а не по страницам; его, кстати, еще приплюсовать надо. К тому же у меня немного другая математика: если N - кол-во страниц, то кол-во чтений будет (N/100 + 99). Константы убираем и получаем вполне линейную из-за фиксации только на сотнях сложность O(N) безо всяких логарифмов. Вместе с пользователями O(N) + O(log U).
Еще в глаза бросилось, что в функции Read чтение из map "pages_by_users[user_id]" пять раз фигурирует в пределах одной функции, причем дважды по дважды в пределах одной строки. И сотни почему-то int[10], а не вектор, хотя книги ооочень длинными бывают - не встречали, например, "Червя" Джона Маккрея?
Amina_Zubairova Автор
21.07.2023 14:11+1Спасибо за такой подробный разбор и за реальные советы, как улучшить этот алгоритм. Действительно, как оказалось, его можно значительно упростить. Хэширование да, в вычислении ключа.
Kotofay
21.07.2023 14:11Можно пользователей на странице учитывать вот так:
Создаём обратное дерево номера страницы и в последнем листочке храним количество пользователей. Поиск любой страницы занимает не боее количества десятичных разрядов номера страницы:#include <iostream> #include <iomanip> #include <string> #include <cstdlib> struct node { node * nodes[ 10 ] = { nullptr, }; unsigned users = { 0U }; void addUser() { users++; }; void removeUser() { if( users > 0U ) users--; }; }; struct book { node nodes[ 10 ]; int l{ 0 }; void usersPages( int page, node * n ) { if( n == nullptr ) return; std::cout << std::setw(l++) << page << ":" << n->users << std::endl; for( int i = 0; i < 10; i++ ) { usersPages( i, n->nodes[ i ] ); } l--; } void printUsersPages() { for( int i = 0; i < 10; i++ ) { usersPages( i, &nodes[ i ] ); } } node * findPage( int page ) { std::string strPage = std::to_string( page ); if( strPage.empty() ) return nullptr; auto it = strPage.rbegin(); int num = *it - '0'; node * nodePage{ &nodes[ num ] }; for( ; it != strPage.rend(); ++it ) { num = *it - '0'; if( nodePage->nodes[ num ] == nullptr ) nodePage->nodes[ num ] = new node; nodePage = nodePage->nodes[ num ]; } return nodePage; } void addUser( int page ) { if( auto nodePage = findPage( page ) ) { nodePage->addUser(); } } void removeUser( int page ) { if( auto nodePage = findPage( page ) ) { nodePage->removeUser(); } } }; int main() { book foo; int page = 7641063; if( auto nodePage = foo.findPage( page ) ) { nodePage->addUser(); nodePage->addUser(); nodePage->removeUser(); nodePage->addUser(); std::cout << page << ":" << nodePage->users << std::endl << std::endl; } page = 1001; if( auto nodePage = foo.findPage( page ) ) { nodePage->addUser(); nodePage->removeUser(); nodePage->addUser(); std::cout << page << ":" << nodePage->users << std::endl << std::endl; } page = 1111; if( auto nodePage = foo.findPage( page ) ) { nodePage->addUser(); nodePage->removeUser(); nodePage->addUser(); std::cout << page << ":" << nodePage->users << std::endl << std::endl; } foo.printUsersPages(); return 0; }
*извиняюсь за размер картинки
wataru
21.07.2023 14:11+1Наивным решением было бы хранить в
std::map<int,int>в качестве ключа номера страниц, в качестве значения- количество прочитавших их пользователейЕсли все равно есть актуальная информация о том, какие страницы прочитал каждый пользователь, то наивное решение —
multiset<int>— хранить, сколько страниц прочитал каждый пользователь и просто считать, сколько там чисел не больше заданного. Хоть бы и черезstd::distance. Будет за линию от количества пользователей, но зато очень просто в реализации и концептуально.Стандартная реализация балансированых деревьев в set'ах в С++, к сожалению, не умеет считать количество ключей меньше заданного за логарифм, но в балансированых деревьях поиска это можно сделать. Можно или написать свое дерево или воспользоваться чуть другой структурой — дервевом отрезков.
И еще, очень глаз режет вот этот код:
((pages_by_users[user_id] - (pages_by_users[user_id] % 100)) + 100)/100его можно заменить на
pages_by_users[user_id] / 100 + 1И еще неясно, зачем там +100 (+1 в сокращенном коде) вообще нужно.
У вас там несоклько раз такие излишне сложные конструкции встречаются.А еще, где у вас там хеширование из заголовка? Вот такое вот разделение данных на группы (по сотням) — это скорее шардирование или аггрегирование. Или что-то типа Sqrt-декомпозиции (по уму, надо делить не на сотни, а на куски длиной sqrt(n)). Хешированием тут и не пахнет.
dzhidzhoev
21.07.2023 14:11+1Деление на группы по сотням - скорее смахивает на корневую оптимизацию.
wataru
21.07.2023 14:11корневую оптимизацию.
По-моему, мы об одном и том же говорим. Это может быть то, что я назвал "sqrt-декомпозицией"? Разбиваем N элементов на K=sqrt(N) групп. При запросе обходим группы за O(k) и возможно элементы в одной или двух группах за O(N/k)?
kogemrka
Чтобы подсчитывать быстро сумму на отрезке за O(log N) нужен простой советский дерево отрезков.
Amina_Zubairova Автор
В функции Cheer используется поиск в std::map, который выполняется за логарифмическое время. Плюс не более 99 итераций для поиска в users_by_pages , это константа и при расчете сложности она не учитывается. Получаем тот же O(log N).
kogemrka
Ага, а N у нас - тысяча, ура, получили O(1)
Amina_Zubairova Автор
Вы правы, мой алгоритм работает дольше, чем дерево отрезков. @xxxphilinxxx подробно пояснил, в чем была моя ошибка при подсчетах.