Алгоритм быстрого поиска при помощи хэширования

В этой статье я хочу представить алгоритм оптимизации хранения данных для быстрого поиска (на примере контейнера 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 всех, кто прочитал меньше. 

Алгоритм позволяет значительно ускорить поиск, при этом использует минимум дополнительной памяти.

Спасибо за внимание.