Структура данных для быстрого поиска с последовательной индексацией - PullRequest
Новая
       23

Структура данных для быстрого поиска с последовательной индексацией

0 голосов
/ 28 февраля 2019

Мои data хранятся в векторе пользовательских объектов, и в этом конкретном программном обеспечении меня интересуют те, которые interesting.Таким образом, у меня есть std::vector<size_t> interesting;, где я храню их индексы, так что когда я вызываю data[ interesting[i] ], я получаю i-й интересный объект данных.

Мне нужно указать здесь, что interesting является несортированный вектор индексов, так что на данный момент нет никакого хитрого трюка, который я мог бы использовать с упорядочением элементов в оригинале data ...

Теперь к проблеме:Данные интересны, потому что они имеют либо свойство A, B, либо оба, и мне нужно сохранить значение этого свойства (скажем, простое double) в другом векторе для быстрого поиска.

Интересно, как бы я поступил об этом!Какую структуру я должен использовать для свойств?

Скажите data.size() = 100 и interesting.size() = 90 (намного больше, но проще работать с круглыми числами), и удаление «неинтересных» данных не вариант, потому что онииспользуются другими частями программного обеспечения.В частности, мне нужно иметь возможность выполнять быстрый поиск, ни data, ни interesting не изменятся в размерах при запуске программного обеспечения (будут работать только значения данных), поэтому вставка в структуры является единовременной в начале и выигрываетне влияют на производительность так, как поиск будет.

У меня есть два решения, которые приходят на ум:

  • Я мог бы использовать std::unordered_map<size_t,double> A и аналогичные для B для храненияпары индекс-свойство, поэтому я могу искать, используя A.at(interesting[i]), чтобы получить значение свойства A для i-го интересного элемента.Поскольку на этом этапе больше не будет вставок, могу ли я с уверенностью предположить, что это O (1)?Это был бы мой предпочтительный способ.

  • Я мог бы выделить std::vector<double> A ( data.size() ); для хранения этих значений и просто вызвать A[ interesting[i] ], как я делаю для данных;это обеспечивает быстрый поиск, но я бы:

    1. тратил МНОГО памяти при увеличении размера data ... на самом деле я бы потратил объединенные data.size() элементы, если предположить, что нетперекрытия.На данный момент A и B являются просто double, но если в какой-то момент мне нужно изменить их тип на нечто большее ... Я предполагаю, что разреженного вектора с поиском O (1) не существует, верно?
    2. Здесь нет обязательной проверки, и не дай бог, я пойду и найду A[3], а 3 - неинтересный показатель!Мне нужно было бы добавить мои собственные накладные расходы на проверку, которые, вероятно, приведут к тому, что поиск больше не будет таким быстрым ...

Короче говоря: меня интересуют данныеструктура для свойств A и B, чтобы я мог получить доступ к этим значениям [которые определены только для interesting точки данных] и знать, какому значению data они также соответствуют ...

Кто-нибудь может придумать хорошее решение этой проблемы?Надеюсь, я достаточно ясно дал понять!

Комментатор попросил пример кода, у меня нет работы, так как я не выяснил, какую структуру данных использовать, но в идеале я бы просто хотелделать 

std::vector<MyObject> data;
// ...
// get data and do stuff
// ...

std::vector<size_t> interesting;
// ...
// initialise interesting as a vector of indexes that refer to the data
// ...

// Now initialize the A property DS
std::vector<double> A ( data.size() ); // <--- this is what I'm questioning about
// maybe I'm better off with std::unordered_map<size_t,double> A ?

// so that (once initialised) I can quickly do
size_t i = 5;
std::cout << "Data point " << data[ interesting[i] ] << 
    " has a property A's value of " << A[ interesting[i] ] << std::endl;
// for evey i I want
...