Дерево/массив мэшап


Я в настоящее время пытается доказать структуру данных, которую я создал, чтобы ускорить поиск интегральных ключей. В конкретном случае я имею в виду, имеет следующий случай использования:

  1. При пуске заполняется из n элементов (где N может быть от 1 до нескольких тысяч), а специфический ключ-это на самом деле беззнаковый инт.
  2. Критический путь в коде требует поиска на основе этого ключа.

Я пробовал следующие:

  1. отсортированный вектор с двоичным поиском
  2. СТД::карта
  3. в Boost::unordered_map

И теперь это дерево. Я нашел с помощью профилирования, что справедливо следующее утверждение

  1. Если каждый элемент взглянул существует, то данная быстрее, чем с std::карта , которая быстрее, чем отсортированный вектор
  2. Если количество успешных запросов на поиск набора невысока, тогда СТД::МАП быстрее, чем данная (я думаю, что хэш-накладные расходы выше за невыполнение случай)

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

/** Copyright: Nim 2011 */
template <typename KeyType, typename ValueType>
class tree
{
public:
  typedef ValueType        value_type;
  typedef ValueType&       reference;
  typedef ValueType const& const_reference;
  typedef KeyType          key_type;
  typedef ValueType*       iterator;
  typedef ValueType const* const_iterator;

private:
  static const size_t MAX_SIZE = 256;

  typedef unsigned char index_type;

  struct node
  {
    node() : _cKey(), _cValue(), _vNodes() {}

    ~node()
    {
      cleanup();
    }

    void add(key_type index, key_type key, const_reference value)
    {
      if (!index)
      {
        _cKey = key;
        _cValue.reset(new value_type(value));
        return;
      }
      // get the lsb
      index_type lsb = index & 0xff;
      if (!_vNodes)
      {
        _vNodes = new node*[MAX_SIZE]();
        _vNodes[lsb] = new node();
      }
      else if (!_vNodes[lsb])
        _vNodes[lsb] = new node();

      _vNodes[lsb]->add(index >> 8, key, value);
    }

    iterator find(key_type index, key_type key)
    {
      if (_cKey == key)
        return _cValue.get();

      if (_vNodes)
      {
        // get the lsb
        index_type lsb = index & 0xff;
        if (_vNodes[lsb])
          return _vNodes[lsb]->find(index >> 8, key);
      }
      return 0;
    }

    const_iterator find(key_type index, key_type key) const
    {
      if (_cKey == key)
        return _cValue.get();

      if (_vNodes)
      {
        // get the lsb
        index_type lsb = index & 0xff;
        if (_vNodes[lsb])
          return _vNodes[lsb]->find(index >> 8, key);
      }
      return 0;
    }

    void optimize()
    {
      if (_vNodes)
      {
        // first see how many nodes we have
        size_t count = 0;
        for(size_t i = 0; i < MAX_SIZE; ++i)
          count += (_vNodes[i] != 0);
        switch(count)
        {
          case 0: return; // nothing to optimize
          case 1: pullup(); break;// we could pull up
          default:
          {
            // means we have more than one node at this level, so optimize each
            for(size_t i = 0; i < MAX_SIZE; ++i)
              if (_vNodes[i])
                _vNodes[i]->optimize();
          }
        }
      }
    }

    void pullup()
    {
      // try to pullup a leaf node
      for(size_t i = 0; i < MAX_SIZE; ++i)
        if (_vNodes[i])
        {
          // if we manage to pullup, then cleanup the nodeset at this level
          if (_vNodes[i]->pullup(_cKey, _cValue))
            cleanup();
          break;
        }
    }

    bool pullup(key_type& key, boost::shared_ptr<value_type>& value)
    {
      if (!_vNodes)
      {
        // this is a leaf node -
        key = _cKey;
        value = _cValue;
        return true;
      }
      // cannot pull up at this level
      // see whether we can pull up from levels below
      size_t count = 0;
      for(size_t i = 0; i < MAX_SIZE; ++i)
        count += (_vNodes[i] != 0);
      switch(count)
      {
        case 0:
        {
          // this is a leaf node -
          key = _cKey;
          value = _cValue;
          return true;
        }
        case 1:
        {
          for(size_t i = 0; i < MAX_SIZE; ++i)
            if (_vNodes[i])
              // if we manage to pullup, then cleanup the nodeset at this level
              return _vNodes[i]->pullup(key, value);
          break;
        }
        default:
        {
          // means we have more than one node at this level so cannot pullup
        }
      }
      return false;
    }

    void print(size_t index, std::ostream& str)
    {
      str << "<node i='" << index << '\'';
      if (_cValue)
        str << " key='" << _cKey << "' value='" << *_cValue << "'";
      str << '>' << std::endl;

      if (_vNodes != 0)
        for(size_t i = 0; i < MAX_SIZE; ++i)
          if (_vNodes[i])
            _vNodes[i]->print(i, str);

      str << "</node>";      
    }

    void cleanup()
    {
      if (_vNodes)
      {
        for(size_t i = 0; i < MAX_SIZE; ++i)
          if (_vNodes[i])
            delete _vNodes[i];
        delete[] _vNodes;
        _vNodes = 0;
      }
    }

    key_type _cKey;
    boost::shared_ptr<value_type> _cValue;
    node** _vNodes;
  };

public:

  tree() : _vNodes() {}

  ~tree()
  {
    if (_vNodes != 0)
    {
      for(size_t i = 0; i < MAX_SIZE; ++i)
        if (_vNodes[i])
          delete _vNodes[i];
      delete[] _vNodes;
      _vNodes = 0;
    }
  }

  iterator end() { return 0; }
  const_iterator end() const { return 0; }

  void add(key_type key, const_reference value)
  {
    // get the lsb
    unsigned char lsb = key & 0xff;
    if (!_vNodes)
    {
      _vNodes = new node*[MAX_SIZE]();
      _vNodes[lsb] = new node();
    }
    else if (!_vNodes[lsb])
      _vNodes[lsb] = new node();

    _vNodes[lsb]->add(key >> 8, key, value);
  }

  iterator find(key_type key)
  {
    if (_vNodes)
    {
      // get the lsb
      index_type lsb = key & 0xff;
      if (_vNodes[lsb])
        return _vNodes[lsb]->find(key >> 8, key);
    }
    return 0;
  }

  const_iterator find(key_type key) const
  {
    if (_vNodes)
    {
      // get the lsb
      index_type lsb = key & 0xff;
      if (_vNodes[lsb])
        return _vNodes[lsb]->find(key >> 8, key);
    }
    return 0;
  }

  void optimize()
  {
    if (_vNodes )
      // optmize each root node
      for(size_t i = 0; i < MAX_SIZE; ++i)
        if (_vNodes[i])
          _vNodes[i]->optimize();
  }

  friend
  std::ostream& operator<<(std::ostream& str, tree const& t)
  {
    str << "<?xml version='1.0'?>" << std::endl;
    if (!t._vNodes)
      return str << "<tree/>" << std::endl;
    str << "<tree> " << std::endl;
    for(size_t i = 0; i < MAX_SIZE; ++i)
      if (t._vNodes[i])
        t._vNodes[i]->print(i, str);
    return str << "</tree> " << std::endl;    
  }

private:
  node** _vNodes;
};

Некоторые основные моменты:

  1. Мне не нужен контейнер должен быть итерируемым - все, что я хочу-быстрый поиск
  2. Я не забочусь о производительности вставки как это начало стоить
  3. Я добавил оптимизировать способ, чтобы "обрезать" дерево и это работает хорошо, однако разница в производительности между подрезают и обычное дерево ничтожна.
  4. Да, я считал использованием Boost::scoped_array.
  5. Я рассматриваю с помощью СТД::вектор а не узел**, я нахожу указатель синтаксис необычайно привлекательным.


386
6
задан 5 июля 2011 в 01:07 Источник Поделиться
Комментарии
1 ответ

Всего лишь несколько пунктов (нюанс: я не эксперт c++).


  1. Сравнение структурированных (т. е. нескалярной ключи) часто является наиболее дорогостоящей частью ведения поиска; это, как правило, стоит поискать сначала на целое число хэш-ключа. Таким образом, вы только должны сделать целое число сравнений, по большей части.

  2. Я невероятно удивлена, что бинарный поиск в отсортированном массиве не бить штаны и все остальное. Бинарный поиск значительно проще, чем все остальное, и имеет оптимальную обрезку. Я серьезно подозреваю, ваши результаты здесь должны делать с проблемой (1) выше.

  3. Вы не скажете, сколько ваш результат отличается в своих экспериментах. Если различия невелики, он, вероятно, не стоит свой собственный код.

2
ответ дан 6 июля 2011 в 11:07 Источник Поделиться