выберите набор значений из кортежа с индексом времени выполнения - PullRequest
Новая
       19

выберите набор значений из кортежа с индексом времени выполнения

2 голосов
/ 04 июля 2019

Краткое введение в мои вопросы: я пытаюсь реализовать "своего рода" реляционную базу данных, используя контейнеры stl.Это просто для забавы / в образовательных целях, поэтому не нужно таких ответов, как «использовать эту библиотеку», «это абсолютно бесполезно» и так далее.Я знаю, что заголовок немного запутан на этом этапе, но мы дойдем до этого (предложения по улучшению заголовка действительно приветствуются).

Я продолжил с небольшими шагами:

  1. я могу построить таблицу как вектор карт от имени столбцов до их значений => std::vector<std::map<std::string, some_variant>>.Это просто и представляет то, что мне нужно.
  2. подождите, я могу просто сохранить имена столбцов один раз и получить доступ к значениям по их индексу.=> std::vector<std::vector<some_variant>>. Так же просто, как точка 1, но быстрее, чем это.
  3. wait wait, в базе данных таблица представляет собой буквально последовательность кортежей => std::vector<std::tuple<args...>>.Это круто, оно представляет именно то, что я делаю, правильный тип без варианта и даже быстрее, чем другие.

Примечание: "быстрее чем" было измерено для 1000000 записей с помощью простого цикла, подобногоэто: 

std::random_device dev;
std::mt19937 gen(dev());
std::uniform_int_distribution<long> rand1_1000(1, 1000);
std::uniform_real_distribution<double> rand1_10(1.0, 10.0);

void fill_1()
{
    using my_variant = std::variant<long, long long, double, std::string>;
    using values = std::map<std::string, my_variant>;
    using table = std::vector<values>;

    table t;
    for (int i = 0; i < 1000000; ++i)
        t.push_back({ {"col_1", rand1_1000(gen)}, {"col_2", rand1_1000(gen)}, {"col_3", rand1_10(gen)} });
    std::cout << "size:" << t.size() << "\n";//just to prevent optimization
}

  1. 2234101600нс - ср .: 2234

  2. 446344100нс - ср .: 446

  3. 132075400ns - avg: 132

INSERT: Нет проблем с любым из этих решений, вставить так же просто, как оттолкнуть элементы назад, как в примере.

SELECT: 1 и 2 просты, но 3 сложнее.

Итак, наконец, вопросы:

  1. Памятьиспользование : использование ресурсов 1 и 2 связано с большими затратами ресурсов используемой памяти.Итак, 3, кажется, снова правильный выбор здесь.Для примера с 1 миллионом записей 2 long с и double я ожидал что-то около 4 МБ * 2 для длинных и 8 МБ для двойных, плюс некоторые издержки для векторов, карт и вариантов, где они были использованы.Вместо этого мы имеем (измерено с помощью диспетчера задач Windows, не очень точно, я знаю):

    1,340 МБ

    2,120 МБ

    3,31 МБ

    Я что-то пропустил? Кроме резервирования нужного размера заранее или shrink_to_fit после цикла вставки?

  2. Есть ли способ получения во время выполнениякакое-нибудь поле кортежа, как в случае оператора select? 

using my_tuple = std::tuple<long, long, string,  double>;
std::vector<my_tuple> table;
int to_select;//this could be a vector of columns to select obviosly
std::cin>>to_select;
auto result = select (table, to_select);

Видите ли вы какой-либо шанс реализовать эту последнюю строку каким-либо образом? У нас есть две проблемы для того, что я вижу: тип результата должен взять тип из начального кортежа, а затем фактически выполнить выбор нужных полей.

Я прочитал много ответов об этом, все они говорято смежных индексах с использованием make_index_sequence или известного индекса времени компиляции.Я также нашел эту статью , очень интересную, но не очень полезную для этого случая.

Ответы [ 2 ]

2 голосов
/ 04 июля 2019

Это выполнимо, но странно: 

template<size_t candidate, typename ...T>
constexpr std::variant<T...> helperTupleValueAt(const std::tuple<T...>& t, size_t index)
{
    if constexpr (candidate >= sizeof...(T)) {
        throw std::logic_error("out of bounds");
    } else {
        if (candidate == index) {
            return std::variant<T...>{ std::in_place_index<candidate>, std::get<candidate>(t) };
        } else {
            return helperTupleValueAt<candidate + 1>(t, index);
        }
    }
}

template<typename ...T>
std::variant<T...> tupleValueAt(const std::tuple<T...>& t, size_t index)
{
    return helperTupleValueAt<0>(t, index);
}

https://wandbox.org/permlink/FQJd4chAFVSg5eSy

0 голосов
/ 04 июля 2019

Об использовании памяти.

В решении 1 у вас есть 1 std::vector и 1 миллион std::map: накладные расходы огромны.

В решении 2 у вас есть 1 + 1 миллион std::vector: накладные расходы огромны.
Предполагая, что вектор примерно состоит из 3 указателей (данных, емкости, размера), эти 24 байта почти так же велики, как содержимое (3*(max(sizeof(long),sizeof(double))+sizeof(discriminant))).

В решении 3 у вас есть 1 std::vector, непосредственно содержащий полезные данные: накладные расходы незначительны.

...