Здравствуйте, watchmaker, Вы писали:

W>Здравствуйте, _smit, Вы писали:


_>>но, поскольку дефрагментация невозможна, я должен найти каким-то образом (последовательным или методом дихотометрии) номер фрагмента и смещение в buff_of_fragments[fr_nr][offset1] для позиции 1280.
_>>Для начала, хотя бы, как быстро найти fr_nr?
W>Двоичный поиск, он же std::lower_bound, — хорошее решение.
W>Просто хранишь массив аккумулированных длин фрагментов и ищешь в нем смещение. Вернувшийся индекс и будет соответствовать fr_nr, а разница между искомым значением и найденным элементом — смещению внутри соответствующего фрагмента.
W>А если вдруг сам массив фрагментов меняется очень часто, то вместо массива аккумулированных длин используешь любое сбалансированное дерево поиска, но вроде тебе это пока не нужно.

Да, так и есть, "погуглил" и реализовал с использованием std::lower_bound. Предварительно создал вектор индексов, каждый элемент индекса имеет три параметра: номер фрагмента, длина фрагмента и номер байта полезных данных, с которого начинается вектор. Доступ примерно выглядит так:

IndexList::const_iterator Packet::get_fragment_index(size_t data_pos) const
{
    if (m_index_list.size() != m_buffer.size())
        init_fragments_indicies();

    if (m_index_list.empty())
        throw std::range_error("Packet::find_fragment_index failed, the fragments_length_list is empty");

    if (m_index_list.front().fragment_length > data_pos)
        return m_index_list.begin();

    if (data_pos >= (m_index_list.back().data_offset_pos + m_index_list.back().fragment_length))
        throw std::range_error("Packet::Value::find_fragment_index failed, data_pos is out of range");

    if (data_pos >= m_index_list.back().data_offset_pos)
        return --m_index_list.end();

    FragmentIndex ref_index;
    ref_index.data_offset_pos = data_pos;

    auto fragment = std::lower_bound(m_index_list.begin(), m_index_list.end(), ref_index,
            [](Packet::Value::FragmentIndex const& value, Packet::Value::FragmentIndex const& ref)
            {return (value.data_offset_pos + value.fragment_length) <= ref.data_offset_pos;});

    if (fragment == m_index_list.end())
        throw std::logic_error("Packet::Value::find_fragment_index failed, fragment_index not found.");

    return fragment;
}

дотуп к элементу массива стал выглядеть так:

Packet::value_type const& Packet::at(size_t pos) const
{
    auto fragment_index = get_fragment_index(pos);

    if ((pos < fragment_index->data_offset_pos) || (pos > (fragment_index->data_offset_pos + fragment_index->fragment_length)))
        throw std::logic_error("Packet::Value::at failed, wrong fragment index");

    return m_buffer.at(fragment_index->fragment_nr).at(packet_traits::header_size + pos - fragment_index->data_offset_pos);

}

Скорость обработки 10 МБ фрагментированного массива возросла с 15-ти минут до 2-х минут. Этого оказалось достаточно.

Здравствуйте, watchmaker, Вы писали:

W>Здравствуйте, _smit, Вы писали:


_>>но, поскольку дефрагментация невозможна, я должен найти каким-то образом (последовательным или методом дихотометрии) номер фрагмента и смещение в buff_of_fragments[fr_nr][offset1] для позиции 1280.
_>>Для начала, хотя бы, как быстро найти fr_nr?
W>Двоичный поиск, он же std::lower_bound, — хорошее решение.
W>Просто хранишь массив аккумулированных длин фрагментов и ищешь в нем смещение. Вернувшийся индекс и будет соответствовать fr_nr, а разница между искомым значением и найденным элементом — смещению внутри соответствующего фрагмента.
W>А если вдруг сам массив фрагментов меняется очень часто, то вместо массива аккумулированных длин используешь любое сбалансированное дерево поиска, но вроде тебе это пока не нужно.

Да, так и есть, "погуглил" и реализовал с использованием std::lower_bound. Предварительно создал вектор индексов, каждый элемент индекса имеет три параметра: номер фрагмента, длина фрагмента и номер байта полезных данных, с которого начинается фрагмент. Доступ примерно выглядит так:

IndexList::const_iterator Packet::get_fragment_index(size_t data_pos) const
{
    if (m_index_list.size() != m_buffer.size())
        init_fragments_indicies();

    if (m_index_list.empty())
        throw std::range_error("Packet::find_fragment_index failed, the fragments_length_list is empty");

    if (m_index_list.front().fragment_length > data_pos)
        return m_index_list.begin();

    if (data_pos >= (m_index_list.back().data_offset_pos + m_index_list.back().fragment_length))
        throw std::range_error("Packet::find_fragment_index failed, data_pos is out of range");

    if (data_pos >= m_index_list.back().data_offset_pos)
        return --m_index_list.end();

    FragmentIndex ref_index;
    ref_index.data_offset_pos = data_pos;

    auto fragment = std::lower_bound(m_index_list.begin(), m_index_list.end(), ref_index,
            [](Packet::FragmentIndex const& value, Packet::FragmentIndex const& ref)
            {return (value.data_offset_pos + value.fragment_length) <= ref.data_offset_pos;});

    if (fragment == m_index_list.end())
        throw std::logic_error("Packet::find_fragment_index failed, fragment_index not found.");

    return fragment;
}

дотуп к элементу массива стал выглядеть так:

Packet::value_type const& Packet::at(size_t pos) const
{
    auto fragment_index = get_fragment_index(pos);

    if ((pos < fragment_index->data_offset_pos) || (pos > (fragment_index->data_offset_pos + fragment_index->fragment_length)))
        throw std::logic_error("Packet::at failed, wrong fragment index");

    return m_buffer.at(fragment_index->fragment_nr).at(packet_traits::header_size + pos - fragment_index->data_offset_pos);

}

Скорость обработки 10 МБ фрагментированного массива возросла с 15-ти минут до 2-х минут. Этого оказалось достаточно.