Я заполняю стек / вектор (контейнер динамического размера с быстрым произвольным доступом по индексу с вставкой только в конце) составными данными (структура, класс, кортеж…). Для специфицированного c атрибута с небольшим набором возможных значений я хочу получить доступ к n-му из всех элементов в стеке, где этот атрибут удовлетворяет условию. Для достижения этого дополнительная информация может храниться вдоль каждой составной или в отдельной структуре данных.
Обратите внимание, что вектор велик и что сравниваемый атрибут имеет небольшой диапазон значений, но сравнивается с набором допустимых значений , Также атрибуты не распределены равномерно по композитам в векторе.
Псевдокод O (n) наивного подхода. Как я могу улучшить это:
enum Fruit { apple, orange, banana, potato };
struct c {
Fruit a;
Data d;
}
// Let's assume v has a length of many thousand and that the distribution of fruits is *not* completely random e.g. that maybe potato only rarely occurs or that bananas tend to come in packs
c getFruit(vector<c> v, set<Fruit> s, int n) {
int counter=0;
// iterate over all of v's indices
for(int i=0 ; i<v.length; i+=1) {
if(v[i].a in s) {
if(n==counter) {
return v[i];
}
counter+=1;
}
}
}
// note: The attribute is compared to a set (arbitrary combination of fruits)!
getFruit(largeVector, set{apple, orange, potato}, 15234)
Другой подход заключается в создании вектора для каждого возможного набора фруктов, который был бы очень быстрым O (1), но не настолько эффективным для памяти.
(Хотя я должен реализовать это сейчас, я просто спрашиваю из любопытства, потому что мои данные достаточно малы, чтобы просто go при наивном подходе.)
Любой аргумент, почему не кажется более эффективный способ также очень одобрен.
Редактировать: Следует отметить, что новые элементы могут добавляться между запросами для индексов с использованием рассматриваемого алгоритма, поэтому любые кэши должны расти с вектором, и оба растущий вектор и этот отфильтрованный доступ должен быть быстрым.