понедельник, 3 октября 2011 г.

Обратное индексирование или обнуление массива за O(1)

В общем виде задача формулируется так:

Нужно создать структуру данных поддерживающую 3 вида операций на массиве:
1) set(i,value) – инициализация i-ого элемента значением value
2) get(i) – получение значение i-ого элемента
3) clear() – обнуление массива.

Каждая операция должна выполняться за O(1).

Первое, что мне пришло в голову было это:

  1. struct ARRAY {
  2.   vector<int> val;
  3.   vector<int> met;
  4.   int cur;
  5.   int lastClear;
  6.   ARRAY():cur(0), lastClear(0){}
  7.   ARRAY(int size):cur(0), lastClear(0) {
  8.     val.resize(size,0);
  9.     met.resize(size,0);
  10.   }
  11.   void set(int pos, int value) {
  12.     val[pos] = value;
  13.     met[pos] = ++cur;
  14.   }
  15.   int get(int pos) {
  16.     if (met[pos] > lastClear)
  17.       return val[pos];
  18.     return 0;
  19.   }
  20.   void clear() {
  21.     lastClear = ++cur;
  22.   }
  23. };
* This source code was highlighted with Source Code Highlighter.

Но как это все уж больно по-пацаняче. С более изящным решением меня познакомил Кирилл Цыганов. Оно основано на принципе обратного индексирования:

  1. const int MAX_REQ = 1000; // максимальное количество запросов set между вызовами clear
  2. struct ARRAY {
  3.   vector<int> A; // key - индекс; val - значение
  4.   vector<int> S; //key - порядковый номер элемента при добавлении; val - индекс элемента в A
  5.   vector<int> ID;//key - индекс элемента в A; val - порядковый номер элемента при добавлении
  6.   int amount;
  7.   ARRAY():amount(1){}
  8.   ARRAY(int N):amount(1) {
  9.     A.resize(N);
  10.     S.resize(MAX_REQ);
  11.     ID.resize(MAX_REQ);
  12.   }
  13.   void set(int pos, int value) {
  14.     A[pos] = value;
  15.     S[amount] = pos;
  16.     ID[pos] = amount++;
  17.   }
  18.   int get(int pos) {
  19.     if (ID[pos] > amount) // попали в мусор (после clear)
  20.       return 0;
  21.     if (S[ID[pos]] != pos) // обращение к неинициализированному элементу
  22.       return 0;
  23.     return A[S[ID[pos]]];
  24.   }
  25.   void clear() {
  26.     amount = 0;
  27.   }
  28. };
* This source code was highlighted with Source Code Highlighter.

Комментариев нет:

Отправить комментарий