Предположим, что для заданного массива объектов A фиксированного размера гораздо меньшее подмножество этих объектов соответствует определенному критерию B. Есть три задачи, которые я хочу выполнять примерно с одинаковой частотой:
- Я хочу иметь возможность изменить объект, который в настоящее время не соответствует критериям B, чтобы он соответствовал критериям B в любое время при доступе к объекту в A по индексу.
- Я хочу иметь возможность изменить объект, который в настоящее время соответствует критериям B, чтобы он больше не соответствовал критериям B при доступе к объекту в A по индексу.
- Я также хочу иметь возможность выбирать случайный объект ТОЛЬКО из тех объектов, которые соответствуют критериям B.
Все задачи должны выполняться за постоянное время или как можно ближе к постоянному времени, не зависящее от количества объектов в A и не зависящее от количества объектов, удовлетворяющих критериям. Б. Если постоянное время невозможно, а я подозреваю, что это так, то я хочу завершить оба как можно быстрее, принимая во внимание частоты, о которых я упоминал ранее. Какие структуры данных подходят для этих двух задач, если они повторяются огромное количество раз?
Возьмем, к примеру, реализацию C++, которую я привожу ниже. В то время как временная часть (участок кода, который повторяется огромное количество раз) не зависит от общего размера A (alltiles), временная сложность линейно зависит от B (bluetiles) (независимо от того, увеличивается ли количество alltiles). или нет), серьезно замедляя код.
#include <iostream>
#include <vector>
#include <chrono>
#include <cstdlib>
#include <algorithm>
using namespace std;
enum color {RED, GREEN, BLUE};
const int NUM_ATTEMPTS = 10000;
const int INITIAL_NUM_BLUE_TILES = 1000;
const int TOTAL_TILES = 1000000;
struct tile
{
int color = RED;
};
struct room
{
vector<tile> alltiles;
vector<tile*> bluetiles;
room(vector<tile> v) : alltiles(v) {}
};
int main()
{
srand (time(NULL));
// set up the initial room, time complexity here is irrelevant
room myroom(vector<tile>(1*TOTAL_TILES));
for(int i = 0; i < INITIAL_NUM_BLUE_TILES; i++)
{
myroom.alltiles[i].color = BLUE;
myroom.bluetiles.push_back(&myroom.alltiles[i]);
}
auto begin = std::chrono::high_resolution_clock::now();
for(int attempt_num = 0; attempt_num < NUM_ATTEMPTS; attempt_num++)
{
// access a BLUE tile by index from alltiles to change its color to RED
myroom.alltiles[5].color = RED; // constant time
myroom.bluetiles.erase(std::remove(myroom.bluetiles.begin(), myroom.bluetiles.end(), &myroom.alltiles[5]), myroom.bluetiles.end()); // linear time, oh no!
// access a RED tile by index from alltiles to change its color to BLUE
myroom.alltiles[5].color = BLUE; // constant time
myroom.bluetiles.push_back(&myroom.alltiles[5]); // constant time
// randomly choose from ONLY the blue tiles
int rand_index = rand() % myroom.bluetiles.size(); // constant time
myroom.bluetiles[rand_index]->color = GREEN; // constant time
myroom.bluetiles[rand_index]->color = BLUE; // constant time
// so now I have constant time access to a random blue tile
}
auto end = std::chrono::high_resolution_clock::now();
double runtime = std::chrono::duration_cast<std::chrono::milliseconds>(end-begin).count();
cout << runtime << " ms" << endl;
return 0;
}
Части, которые замеряются по времени, — это операции, которые мне интересно выполнять часто; в реальной программе логика выбора тайлов для изменения отличается. Надеюсь, лучшая структура данных не потребует какого-либо вероятностного анализа, но я боюсь, что он все же может понадобиться.
Я подозреваю, что, возможно, использование двойной косвенности путем сохранения указателя (указывающего на элементы в векторе bluetiles) в классе плитки может позволить мне добиться этого за постоянное время, но я не уверен. Я думаю, это могло бы, по крайней мере, ускорить его в том смысле, что поиск блютайлов больше не был бы необходим, но тогда удаление элемента в блютайлах все еще было бы линейным временем (поскольку я использую вектор), так что я действительно просто не уверен, что делать здесь.
Можете ли вы разработать самую быструю структуру данных для достижения этой цели и предоставить сборку реализации C++ из моего примера? Или то, что у меня есть, так хорошо, как никогда?
myroom.bluetiles.erase(std::remove(myroom.bluetiles.begin(), myroom.bluetiles.end(), &myroom.alltiles[5]), myroom.bluetiles.end());
не очень хороший код. Не указано, будет ли сначала выполнятьсяstd::remove
или последнийmyroom.bluetiles.end()
. Таким образом, эта функция может вести себя двумя разными способами. Он указан в C++17, но не в C++11. - person mch   schedule 22.08.2018