Самый эффективный способ хранения смешанной коллекции двойных и целых чисел

Мне нужно сохранить набор целых и двойных чисел (представляющих номинальные и реальные данные) в С++. Очевидно, я мог бы хранить их все в std::vector<double> , но это кажется немного неправильным и не дает бонусных баллов за эстетику.

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

Я также нашел boost::variant, который может помочь здесь.

Дополнительная информация: количество элементов в коллекции будет небольшим (‹100) и известно при инициализации коллекции.

Подводя итог: я, очевидно, мог бы решить эту проблему бесчисленным количеством способов, но я не уверен, что было бы хорошим решением, когда (i) действительно важна эффективность и (ii) я также хочу написать несколько приятный код. Каков мой лучший выбор здесь?

Изменить, дополнительная информация. Коллекция представляет собой «строку» в большом наборе данных, ее элементы представляют значения определенных «столбцов». Свойства строк известны, поэтому известно, какие данные хранятся в какой позиции. «Эффективность», о которой я говорю, — это в первую очередь эффективность извлечения значения int/double определенного столбца, хотя быстрая установка значений также важна. У меня есть несколько функций, которые работают с данными, которым необходимо получить их как можно быстрее. Пример:

typedef std::vector<double> Row;

void doubleFun(Row const &row)
{
    // Function knows there's always a double at index 0
    double value = row[0];
    ...
}

void integerFun(Row const &row)
{
    // Function knows there's always an integer at index 1
    int value = row[1];
    ...
}

После некоторых размышлений и прочтения предложений кажется, что простое хранение столбцов int и double в двух отдельных векторах является надежным решением. Тогда коллекция Row может просто определить два разных члена для получения номинальных и реальных данных, которые могут использовать функции.

Я думаю, просто хранить как vector<double> тоже нормально, но это зависит от того, насколько быстро происходит преобразование между double и int (что, вероятно, довольно впечатляет).

Извините за то, что сначала было немного неясно, я надеюсь, что теперь это станет яснее, и я смогу получить больше мыслей по этому вопросу.


c++ collections boost-variant
person TC.    schedule 16.10.2009    source источник
comment
Вы не предоставили нам достаточно информации, чтобы найти лучшее решение. Каковы свойства коллекции? Допускаются ли дубликаты? Порядок важен? Должен ли он быть отсортирован? Требуется ли сохранять тип данных или допустимо вставлять 10.0 (двойное число) и получать 10 (целое число)?   -  person Tom    schedule 16.10.2009
comment
Кроме того, какой показатель эффективности вы пытаетесь оптимизировать? Общая площадь? Время вставки? Время поиска произвольного доступа? Время итерации?   -  person Tom    schedule 16.10.2009
comment
Обновлено с дополнительной информацией, извините за то, что сначала не было слишком ясно. Надеюсь, сейчас лучше.   -  person TC.    schedule 16.10.2009

Ответы (5)


arrow_upward
5
arrow_downward

Является ли заказ важным моментом в вашем контейнере?

Если не так:

class MyContainer
{
    std::vector<double> doubles;
    std::vector<int>    ints;

    push(double value) { doubles.push_back(value); }
    push(int value)    { ints.push_back(value); }

   ....
};

Часть итератора (для просмотра всего контейнера) может быть немного сложнее...

person yves Baumes    schedule 16.10.2009

arrow_upward
5
arrow_downward

Почему бы не использовать напрямую вектор double? Поскольку целые числа можно преобразовать в двойные без потери точности... мне кажется, что это самое простое и эффективное решение.

Что еще предстоит установить (и я не мог понять из вашего вопроса), как вы можете сделать разницу между нормальными и реальными значениями. Проблема остается открытой в любом решении, которое вы можете выбрать.

person Cătălin Pitiș    schedule 16.10.2009
comment
правда, теперь 10.0 - это двойное число или целое число? - person gbjbaanb; 16.10.2009
comment
Реальный вопрос: является ли 10,0 нормальным или реальным значением? Но, как я сказал в своем ответе... у меня недостаточно информации. Тот же вопрос можно задать в случае использования вариантов. - person Cătălin Pitiș; 16.10.2009
comment
@Cătălin Boost::variant - это сохранение типа, вы можете использовать посетителя для получения правильного типа - person TimW; 16.10.2009
comment
@TimW: Это эффективно? Если есть другой способ определить разницу между нормальными и реальными значениями... почему я должен использовать варианты. Опять же... мы ничего не знаем о возможностях изменить ситуацию. - person Cătălin Pitiș; 16.10.2009
comment
Я настороженно отношусь к преобразованиям между int и double, которые, похоже, могут создать проблемы. Например, int (1) переводится в 0,9999 ... Но я не читал Что должен знать каждый ученый-компьютерщик об арифметике с плавающей запятой. Кто-нибудь на ТАК знает, плз? (Интересует ответ!! :-)) - person yves Baumes; 16.10.2009
comment
0 и все степени двойки в двойном диапазоне представлены точно. 0,999 ... вместо этого не представлено точно для любого количества девяток. В диапазоне двойных чисел есть целые числа, которые вообще не могут быть представлены как двойные (см. en.wikipedia. org/wiki/Unit_in_the_last_place), но об этом нужно беспокоиться, только если вы используете 64-битные целые числа. - person Dan Berindei; 09.11.2009

arrow_upward
3
arrow_downward

Вы можете использовать тип объединения и использовать его в своем векторе. Но в этом случае вам нужно было бы каким-то образом узнать, какие элементы вектора следует рассматривать как целые, а какие — как двойные. Чтобы отслеживать, какие из них являются целыми, а какие двойными, вы можете использовать набор битов или что-то в этом роде.

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

#include <vector>
#include <bitset>

union di
{
    double d;
    int i;
};


int main(int argc, char* argv[])
{

    std::bitset<2> bitsetInts;

    std::vector<di> v;
    di e1;
    e1.d = 3.9;
    v.push_back(e1);

    di e2;
    e2.i = 3;
    bitsetInts.set(1);
    v.push_back(e2);

    return 0;
}
person Brian R. Bondy    schedule 16.10.2009
comment
это здорово, если максимальный размер фиксирован, именно то, о чем я думал. - person Tom; 16.10.2009

arrow_upward
3
arrow_downward

Я бы выбрал решение boost::variant, оно идеально соответствует вашим потребностям.

person TimW    schedule 16.10.2009

arrow_upward
1
arrow_downward

Существует кортеж boost, который вы можете использовать, если знаете типы во время компиляции. Но если количество элементов невелико, эффективная трата 100 байт не должна вызывать беспокойства.

person pythonic metaphor    schedule 16.10.2009