Помогите определить какую структуру данных реализовать? С++
У меня есть задача, в которой ежедневно обновляется рекомендуемая цена бумаги (бумага - слово длиной 1-4 символа, заглавные буквы латинского языка, каждый тикер(бумага) уникальный) - пусть это происходит до открытия торговли на бирже. Далее в течение дня, когда идет торговля акциями, происходит частое изменение их цен - программе просто подается тикер и цена. От меня требуется выбрать и реализовать такую структуру данных, чтобы самым быстрым способом находить для поданной бумаги рекомендуемою цену и сравнивать её с переданным значением. Я так понимаю здесь нужна hash-table, так как там поиск O(1) чаще всего, но и хотелось бы избежать ситуаций с О(n). Но не хочется изначально задавать размер таблицы равным всевозможным перестановкам букв в словах длиной 1-4(Тем более если я не знаю сколько акций подадут в начале дня, чтобы добавить). Прочитал про идеальное хэширование, но говорят что с динамической сменой размера плохо работает.Как альтернативную структуру данных вижу только бинарные деревья поиска, но там поиск О(logn). Хотелось бы узнать ваше мнение, как гарантировать очень быстрый поиск и какой структурой. Если что (Использование готовых библиотек запрещено и всякие словари и т.д и т.п.).
Ответы (2 шт):
Структура данных -- массив указателей.
В латинском алфавите 26 заглавных букв. Если использовать по 5 бит на букву, то это 1048576 значений.
Т.о. вы можете получить 20-битный идентификатор бумаги из ее символьного имени и использовать его в качестве индекса для массива. Если это будет массив указателей, то он займет всего 8 Мбайт и вы гарантировано получите прямой доступ к этой бумаге
Прямой ответ:
Суммируя сказанное в комментариях: Самым быстрым по времени вариантом будет хранение вектора всех перестановок. Это обеспечит гарантированно О(1), но требует O(k^m) памяти. Причем О(1) для вектора перестановок, это не тоже самое, что О(1) для "идеальной" хэш-таблицы. Поскольку использование хэш-таблицы неизбежно связано с бOльшими промежуточными вычислениями и с бOльшим числом обращения к памяти.
Тем не менее, если асимптотика О(1) в принципе нас устраивает, то можно попробовать поискать подходящую хэш-функцию. К сожалению, если исходить их предпосылки случайного распределения символов, то, буквально по определению, без знаний о законах распределения символов (если таковые имеются), выбрать "идеальную" хэш-функцию не удастся.
Идея:
Есть ещё идея использовать сочетание последовательного хранения и алгоритмов архивирования. Суть идеи заключается в том, чтобы получив набор строк, найти такую трансформацию полного вектора перестановок, чтобы заданные строки оказались в его начале. Вот простой пример (не дающий окончательного решения, но демонстрирующий идею):
(для удобства вместо символов, я сразу буду использовать числа) Пусть мы получаем 4 строки-ключа, значения для которых нам нужно проверять в дальнейшем. Пусть мы получили вот такие строки:
Мы хотим найти функцию вида N(a1, a2, a3, a4) такую, что при подстановке значений из строки, каждой из строк соответствовало бы минимальное уникальное натуральное число: 0, 1, 2 или 3. Пусть N - это линейная функция. Тогда для нахождения её коэффициентов можно решить СЛАУ
Имеем
Теперь можно хранить не все перестановки и даже не хэш-таблицу значений, а только последовательный вектор 4-х пар ключ-значение.
Если результат round(N(S)) < 0 или > 3 или ключ в векторе с номером round(N(S)) не равен S (v[round(N(S))].key != S), то входная строка не имеем заданного значения. Иначе, v[round(N(S))].value - это искомое значение.
Еще раз - Это не решение, а только идея для возможного решения.
Добавлено Идея 2:
задача показалась интересной с точки зрения спортивного интереса. к тому же ранее попадалась похожая задача, и были кое-какие мысли, но тогда до реализации не дошло
Суть идеи заключается в том, чтобы сжать количество хранимой информации не сильно теряя в производительности. Это достигается тем, что при вводе строк:
- производится подсчет, сколько разных символов встречаются на каждой из позиций;
- каждому символу присваивается его номер на каждой из позиции
Как показали тесты относительно алгоритма на полном перечислении перестановок памяти может экономится в разы, а производительность в среднем ниже буквально на несколько процентов. Это происходит из-за того, что таблица для подсчета номера строки мала, и всегда находится в самом верхнем кэше данных процессора. К тому же это решение еще можно "допилить". (боюсь, что подробное описание этого алгоритма займёт слишком много времени)
Добавлено 2 Идея 3:
Как верно заметил в комментариях @tym32167 здесь можно использовать префиксное дерево. Я почему-то на это решение в последнюю очередь думал. Подумал, что 4 уровня косвенности - это слишком. Но нет. Не вылазит за пределы как минимум L2. Работает даже быстрее чем через прямой доступ к элементам вектора перестановок. Ну и по памяти не сильно больше HashMap.
Изменено
Вот мой последний на данный момент вариант с решениями:
- Solution1: Самое простое с точки зрения кода решение на хэш-таблице
- Solution2: Решение основанное на хранении вектора всех перестановок
- Solution3: Решение (самое запутанное) основанное на подсчете номера символа для каждой из позиций
- Solution4: Решение похожее на префиксное дерево
https://godbolt.org/z/8P3vhsbhj
#include <iostream>
#include <utility>
#include <random>
#include <chrono>
#include <unordered_map>
#include <string>
#include <vector>
using byte = unsigned char;
constexpr char MIN_CHAR = 'A';
constexpr char MAX_CHAR = 'Z';
constexpr char CHAR_COUNT = MAX_CHAR - MIN_CHAR + 1;
inline char RandChar() {
return std::rand() % (CHAR_COUNT) + MIN_CHAR;
}
inline float RandPrice() {
return static_cast<float>(rand()) / RAND_MAX;
}
// Solution1 ----------------------------------------------------------------------------------
// На хэш-таблице
struct Solution1_HashMap {
std::unordered_map<std::string, float> data{};
void UpdatePrice(std::string const key, float price) {
data[key] = price;
}
float CheckPrice(std::string const key) {
auto it = data.find(key);
if (it != data.end()) return it->second;
return -1;
}
size_t TotalMemory() {
return
(data.size() * (sizeof(decltype(data)::value_type) + sizeof(void*)) + // data list
data.bucket_count() * (sizeof(void*) + sizeof(size_t))) // bucket index
* 3 / 2 + // estimated allocation overheads
sizeof(Solution1_HashMap);
}
};
// Solution2 ----------------------------------------------------------------------------------
// На векторе всех перестановок
struct Solution2_AllPerm {
std::vector<float> data = std::vector<float>(CHAR_COUNT * CHAR_COUNT * CHAR_COUNT * CHAR_COUNT, -1);
void UpdatePrice(std::string const key, float price) {
size_t pos = 0;
for (size_t i = 0; i < 4; ++i)
pos = pos * CHAR_COUNT + (key[i] - MIN_CHAR);
data[pos] = price;
}
float CheckPrice(std::string const key) {
size_t pos = (key[0] - MIN_CHAR);
pos = pos * CHAR_COUNT + (key[1] - MIN_CHAR);
pos = pos * CHAR_COUNT + (key[2] - MIN_CHAR);
pos = pos * CHAR_COUNT + (key[3] - MIN_CHAR);
return data[pos];
}
size_t TotalMemory() {
return data.size() * sizeof(float) + sizeof(Solution2_AllPerm);
}
};
// Solution3 ----------------------------------------------------------------------------------
// На сжатом веткоре
struct Solution3_PreSort {
using Numerator = byte[4];
std::vector<float> data{};
Numerator numerators[CHAR_COUNT];
byte counters[4];
Solution3_PreSort() {
for (size_t i = 0; i < CHAR_COUNT; ++i) {
numerators[i][0] = CHAR_COUNT - 1;
numerators[i][1] = CHAR_COUNT - 1;
numerators[i][2] = CHAR_COUNT - 1;
numerators[i][3] = CHAR_COUNT - 1;
}
counters[0] = 0;
counters[1] = 0;
counters[2] = 0;
counters[3] = 0;
}
void UpdatePrice(std::string const key, float price) {
size_t pos = 0;
for (size_t i = 0; i < 4; ++i) {
byte& numerator = numerators[key[i] - MIN_CHAR][i];
byte& counter = counters[i];
if (numerator > counter) {
numerator = counter;
++counter;
}
pos = pos * CHAR_COUNT + numerator;
}
if (pos + 1 > data.size()) {
size_t old_count = data.size();
data.resize(pos + 1);
for (size_t i = old_count; i < pos; ++i) data[i] = -1;
}
data[pos] = price;
}
float CheckPrice(std::string const key) {
size_t pos = numerators[key[0] - MIN_CHAR][0];
pos = pos * CHAR_COUNT + numerators[key[1] - MIN_CHAR][1];
pos = pos * CHAR_COUNT + numerators[key[2] - MIN_CHAR][2];
pos = pos * CHAR_COUNT + numerators[key[3] - MIN_CHAR][3];
if (pos < data.size()) return data[pos];
return -1;
}
size_t TotalMemory() {
return data.size() * sizeof(float) + sizeof(Solution3_PreSort);
}
};
// Solution4 ----------------------------------------------------------------------------------
// На байт-дереве
using Layer = void* [CHAR_COUNT];
using LowerLayer = float [CHAR_COUNT];
template <size_t N = 0> requires (N < 4)
void** NewLayer() {
auto res = new Layer;
for (size_t i = 0; i < CHAR_COUNT; i++) res[i] = nullptr;
return res;
}
template <>
void** NewLayer<3>() {
auto res = new LowerLayer;
for (size_t i = 0; i < CHAR_COUNT; i++) res[i] = -1;
return static_cast<void**>(static_cast<void*>(res));
}
template <size_t N = 0> requires (N < 4)
size_t LayerSize(void** layer) {
if (layer == nullptr) return 0;
size_t res = CHAR_COUNT * sizeof(void*);
for (size_t i = 0; i < CHAR_COUNT; i++) {
res += LayerSize<N + 1>(static_cast<void**>(layer[i]));
}
return res;
}
template <>
size_t LayerSize<3>(void** layer) {
if (layer == nullptr) return 0;
return CHAR_COUNT * sizeof(float);
}
template <size_t N = 0> requires (N < 4)
void DeleteLayer(void** layer) {
if (layer == nullptr) return;
for (size_t i = 0; i < CHAR_COUNT; i++) {
DeleteLayer<N + 1>(static_cast<void**>(layer[i]));
}
delete[] layer;
}
template <>
void DeleteLayer<3>(void** layer) {
if (layer == nullptr) return;
delete[] static_cast<float*>(static_cast<void*>(layer));
}
struct Solution4_CharTree {
void** layer0;
Solution4_CharTree() : layer0(NewLayer()) {}
~Solution4_CharTree() {
DeleteLayer(layer0);
}
void UpdatePrice(std::string const key, float price) {
if (layer0[key[0] - MIN_CHAR] == nullptr)
layer0[key[0] - MIN_CHAR] = NewLayer<1>();
void** layer1 = static_cast<void**>(layer0[key[0] - MIN_CHAR]);
if (layer1[key[1] - MIN_CHAR] == nullptr)
layer1[key[1] - MIN_CHAR] = NewLayer<2>();
void** layer2 = static_cast<void**>(layer1[key[1] - MIN_CHAR]);
if (layer2[key[2] - MIN_CHAR] == nullptr)
layer2[key[2] - MIN_CHAR] = NewLayer<3>();
float* layer3 = static_cast<float*>(layer2[key[2] - MIN_CHAR]);
layer3[key[3] - MIN_CHAR] = price;
}
float CheckPrice(std::string const key) {
void** layer1 = static_cast<void**>(layer0[key[0] - MIN_CHAR]);
if (layer1 == nullptr) return -1;
void** layer2 = static_cast<void**>(layer1[key[1] - MIN_CHAR]);
if (layer2 == nullptr) return -1;
float* layer3 = static_cast<float*>(layer2[key[2] - MIN_CHAR]);
if (layer3 == nullptr) return -1;
return layer3[key[3] - MIN_CHAR];
}
size_t TotalMemory() {
return LayerSize(layer0) + sizeof(Solution4_CharTree);
}
};
// GLOBAL DATA --------------------------------------------------------------------------------
constexpr size_t KnownPricesCount = 10; // количество строк для которых известна цена
constexpr size_t TestPricesCount = 1000000; // количество строк для теста
std::vector<std::pair<std::string, float>> KnownPrices(KnownPricesCount);
std::vector<std::pair<std::string, float>> TestPrices(TestPricesCount);
// TEST FUNC ----------------------------------------------------------------------------------
#define TEST(solution) \
do { \
solution sol; \
for (auto& pa : KnownPrices) sol.UpdatePrice(pa.first, pa.second); \
size_t ChackCounter1 = 0; \
size_t ChackCounter2 = 0; \
auto b = clock(); \
for (auto& test : TestPrices) { \
float price = sol.CheckPrice(test.first); \
if (price >= 0) { \
++ChackCounter1; \
if (price > test.second) ++ChackCounter2; \
} \
} \
auto e = clock(); \
std::cout << "-----------------------------------------------\n"; \
std::cout << " "#solution"\n\n"; \
std::cout << "Runtime = " << e - b << "\n"; \
std::cout << "ChackCounter1 = " << ChackCounter1 << "\n"; \
std::cout << "ChackCounter2 = " << ChackCounter2 << "\n"; \
std::cout << "Total memory = " << sol.TotalMemory() << "\n"; \
std::cout << "\n" << std::endl; \
} while(0) \
// MAIN ---------------------------------------------------------------------------------------
int main()
{
// Инициализация ИД для тестов
std::srand(static_cast<unsigned int>(std::time(0)));
// Список известных бумаг
for (auto& pa : KnownPrices) {
pa.first = std::string{ RandChar(), RandChar(), RandChar(), RandChar() };
pa.second = RandPrice();
}
// Список бумаг для тестов
for (auto& pa : TestPrices) {
pa.first = { RandChar(), RandChar(), RandChar(), RandChar() };
pa.second = RandPrice();
}
// Тестирование
// Здесь можно менять решения местами для сравнения
// при равных условиях относительно "прогрева кэшей"
TEST(Solution1_HashMap);
TEST(Solution2_AllPerm);
TEST(Solution3_PreSort);
TEST(Solution4_CharTree);
std::cin.get();
return 0;
}
//Solution4 считаю лидером, хотя опять же, всё зависит от исходных данных. Ну и от железа. Ну и от компилятора. Результаты на godbolt.org и на моей машине несколько отличаются. Ну и от разрядности зависит (32 vs 64)