Comments 12
Чтобы подсчитывать быстро сумму на отрезке за O(log N) нужен простой советский дерево отрезков.
В функции Cheer используется поиск в std::map, который выполняется за логарифмическое время. Плюс не более 99 итераций для поиска в users_by_pages , это константа и при расчете сложности она не учитывается. Получаем тот же O(log N).
Ага, а N у нас - тысяча, ура, получили O(1)
Вы правы, мой алгоритм работает дольше, чем дерево отрезков. @xxxphilinxxx подробно пояснил, в чем была моя ошибка при подсчетах.
А можно было бы просто из "неограниченного числа читателей" вычесть число пользователей, прочитавших столько же страниц, сколько и заданный, но тогда бы не родилась статья :)
По условиям задачи мы не знаем, сколько пользователей прочитало столько же страниц, что и искомый пользователь. Этот параметр постоянно меняется. И нужно реализовать быстрый подсчет с минимальным использованием дополнительной памяти. При количестве читателей, скажем, 1млн, создавать массив на 1 млн ячеек не рационально. Хотя, Вы правы, это самый простой способ, наивный алгоритм.
Промежуточные суммы вижу, а где хеширование из заголовка? В вычислении ключа этих сумм?
Тут выше упомянули дерево отрезков - вы его фактически и реализовали, просто зафиксировали кол-во уровней на трех (книга/сотни/страницы) и зафиксировали кол-во потомков на третьем уровне на сотне элементов.
А можно было бы просто из "неограниченного числа читателей" вычесть число пользователей, прочитавших столько же страниц, сколько и заданный, но тогда бы не родилась статья :)
По условиям задачи мы не знаем, сколько пользователей прочитало столько же страниц, что и искомый пользователь.
Если хранить счетчик пользователей, не читающих страницу, а уже прочитавших ее, то все как раз становится тривиально: 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], а не вектор, хотя книги ооочень длинными бывают - не встречали, например, "Червя" Джона Маккрея?
Можно пользователей на странице учитывать вот так:
Создаём обратное дерево номера страницы и в последнем листочке храним количество пользователей. Поиск любой страницы занимает не боее количества десятичных разрядов номера страницы:
#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;
}
*извиняюсь за размер картинки
Наивным решением было бы хранить в 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)). Хешированием тут и не пахнет.
Алгоритм быстрого поиска при помощи хэширования