Как лучше задать табличную функцию с редкой областью определения?

Question

[Евгений Обыкновенный]

Аргумент функции принимает очень далекие друг от друга значения. Например, x = 2, 10, 100, 2000,...
Нужно задать табличную функцию при этих значениях.

Есть два варианта.

Определить длинный массив

const int func[2001] = {0, 0, f(2), ...., f(100), ....., f(2000)};

или определить функцию

int func(int x)
{
  switch( x )
  {
    case 2: return f(2); break;
    case 100: return f(100); break;
    case 2000: return f(2000); break;
    ...
  }
}

Какой вариант предпочтительнее и быстрее?

upd. Для примера привел числа побольше. На самом деле значения до 100, а всего значений 10-20.

Comments

[Антон Жилин]

Какое максимальное значение, принимаемое функцией? Сколько всего допустимых значений?

[Евгений Обыкновенный]

Для примера привел числа побольше. На самом деле значения до 100, а всего значений 10-20.

Answer 1

[Mercury13]

Если аргументы до 100, функция заранее известна и неизменна — чхайте на всё и делайте простым массивом. Именно так, таблицей переходов, внутри устроен switch. Всё, что я пишу ниже — для общего развития.

Это называется «разреженный массив» (sparse array)

1. Хэш-таблица (std::unordered_map).
Преимущество: есть «в коробке», очень быстра.
Недостаток: ест много памяти.

2. Я также использую вот такой механизм.

template <class T>
class ChunkMap
{
public:
    // Data access
    //------------------------------------------------------------------------//
    /// @return  data at index t, or empty value
    T get(size_t t) const;

    //------------------------------------------------------------------------//
    /// Sets data at index t (empty value to erase)
    void put(size_t t, T x);

    //------------------------------------------------------------------------//
    /// Erases range [0..maxPlus)
    void eraseTo(size_t aMaxPlus);

    // Info
    size_t nChunks() const { return fChunks.size(); }
    bool isEmpty() const { return fChunks.empty(); }

    //------------------------------------------------------------------------//
    /// @return  the number that is beyond all chunks
    size_t ceil() const;

    //------------------------------------------------------------------------//
    /// @return  actual number of records in the map
    size_t size() const;

    //------------------------------------------------------------------------//
    /// @return  lowest value in the map; (0, empty) if empty
    std::pair<size_t, T> lowerValue() const;

    //------------------------------------------------------------------------//
    /// @return  highest value in the map; (0, empty) if empty
    std::pair<size_t, T> upperValue() const;

    //------------------------------------------------------------------------//
    /// @return  (t1, v), t1 <= t;  (0, empty) if none
    std::pair<size_t, T> lowerOrEq(size_t t) const;

    template <class Body> void loop(const Body& r) const;
    template <class Body> void loopFrom(size_t aMin, const Body& r) const;

    //------------------------------------------------------------------------//
    ///  Loops all data. Body is bool-convertible.
    ///  Return true → go on.
    ///  Return false → stop and return false.
    template <class Body> bool loopBool(const Body& r) const;

    void clear() { fChunks.clear(); }

    constexpr static T emptyValue() { return std::numeric_limits<T>::max(); }
    static bool isEmptyValue(const T& x) { return (x == emptyValue()); }

    constexpr static unsigned chunkSize() { return Chunk::SIZE; }

private:
    struct Chunk
    {
        enum { SIZE = 8 };
        Fix1d<T, SIZE> data;   // мой шаблон, массив фиксированного размера с проверкой на выход за границы

        Chunk();
        bool isEmpty() const;
        std::pair<size_t, T> lowerValue(size_t aKey) const;
        std::pair<size_t, T> upperValue(size_t aKey) const;
    };
    typedef std::map<size_t, Chunk> Chunks;
    Chunks fChunks;
};

Можно делать и на unordered_map при желании, но мне нужна lowerOrEq().

Преимущество: экономия памяти, если есть несколько значений рядом.
Недостаток: больше расход памяти (ненамного).

3. Вот ещё есть реализация на Java.
https://android.googlesource.com/platform/framewor...
Преимущество: серьёзная экономия памяти.
Недостатки: когда массив велик (тысячи заполненных элементов), снижается скорость доступа. Большие расходы на чистку мусора.

Answer 2

[Александр Таратин]

всего значений 10-20.

Если функцию f можно сделать constexpr, то я за switch

case 100: return f(100); break;

Для компактности после return ставить break необязательно.

Если нельзя то за длинный массив.