как решить более эффективно задачу на С++ (неэффективное, но правильно работающее решение имеется):

typedef std::vector<uint8_t> Fragment;
std::vector< Fragment > buff_of_fragments;
std::array<uint8_t, 64>  byte_buff;
std::array<uint16_t, 32> word_buff;

buff_of_fragments занимает 80% памяти и дефрагментировать его нет возможности. Фрагменты в общем случае могут иметь разную длину. Требуется копировать последовательно по частям для быстрой обработки
1. из buff_of_fragments в byte_byff
2. из buff_of_fragments в word_byff

задача усложняется тем, что данные в buff_of_fragments начинаются не с нулевого байта buff_of_fragments[0][0], а со смещения offset, т.е. с buff_of_fragments[0][offset].
операция

reinterpret_cast<uint16_t*>(&buff_of_fragments[0][offset]);

небезопасна для нечетных offset из-за архитектурных особенностей процессора (MIPS).

На данный момент на ум приходит побайтное копирование из buff_of_fragments в byte_byff с поиском позиции байта в buff_of_fragments. Например, мне надо скопировать байты с позиции дефрагментированного вектора:

std::copy(defrag_buff.begin() + 1280, defrag_buff.begin() + 1280 + 64, byte_buff.begin());

но, поскольку дефрагментация невозможна, я должен найти каким-то образом (последовательным или методом дихотометрии) номер фрагмента и смещение в buff_of_fragments[fr_nr][offset1] для позиции 1280. Последняя, копируемая в byte_buff, позиция 1280 + 64 может находиться в другом фрагменте buff_of_fragments[fr_nr + n][offset2].
Для начала, хотя бы, как быстро найти fr_nr?

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

_>как решить более эффективно задачу на С++ (неэффективное, но правильно работающее решение имеется):
Компилятор gcc-4.6.4, поддерживаются опции -std=c++0x

Я так и не понял, какая исходная задача? Найти байт? Зачем тогда копировать?

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

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


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

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

S>Я так и не понял, какая исходная задача? Найти байт? Зачем тогда копировать?

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

исходная задача разбить фрагментированный вектор на отрезки равной длины для быстрой обработки и последующего сохранения этих отрезков. случайный (рандомный) доступ к элементу фрагментированного вектора -- сопутствующая, но не обязательная задача. Чтобы использовать stl алгоритмы был разработан соответствующий итератор:

//----------------------------------------------------------------------------
#include <iterator>
#include <type_traits>
#include <stdexcept>
//----------------------------------------------------------------------------
namespace xxx
{
//----------------------------------------------------------------------------

template<typename _Container>
class fragmented_array_iterator
{
    typedef typename _Container::value_type* _Iterator;
protected:
    _Container* m_buffer;
    size_t      m_current;

    typedef std::iterator_traits<_Iterator> traits_type;

public:
    typedef _Iterator                    iterator_type;
    typedef typename traits_type::iterator_category    iterator_category;
    typedef typename traits_type::value_type          value_type;
    typedef typename traits_type::difference_type     difference_type;
    typedef typename traits_type::reference         reference;
    typedef typename traits_type::pointer           pointer;

    explicit fragmented_array_iterator(_Container& data) : m_buffer(&data), m_current(0) { }

    template <typename _Int>
    explicit fragmented_array_iterator(_Container& data, _Int current) : m_buffer(&data), m_current(current) { }

...
    fragmented_array_iterator
    operator--(int)
    { return fragmented_array_iterator(m_current--); }

    // Random access iterator requirements
    reference
    operator[](const difference_type& __n) const
    { return m_buffer[m_current+__n]; }//m_current[__n]; }

    fragmented_array_iterator&
    operator+=(const difference_type& __n)
    { m_current += __n; return *this; }
...
};
//----------------------------------------------------------------------------

По большому счету для последовательного копирования кусков фрагментированного вектора в буфер фиксированный длины Random access iterator и Random access к элементам массива не нужен, но решение задачи является "бонусом" к удобству работы с фрагментированным вектором. Алгоритмы перестают замечать фрагментированность, облегчает отладку.

Здравствуйте, 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-х минут. Этого оказалось достаточно.

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


_>Поиск выглядит так:

_>            {return (value.data_offset_pos + value.fragment_length) <= ref.data_offset_pos;});

И не боишься передавать в lower_bound компаратор нарушающий strict weak ordering?

_>Предварительно создал вектор индексов, каждый элемент индекса имеет три параметра: номер фрагмента, длина фрагмента и номер байта полезных данных, с которого начинается фрагмент.
Считаю, проще будет если использовать только последний параметр из трёх. Тогда выполнение функции сразу начинается с вызова lower_bound, а все проверки уже делаются для возвращённого итератора. Сейчас же есть как минимум несколько избыточных проверок на частные случаи, часть из которых к тому же маскирует проблему с плохим компаратором.

Уж лучше вместо них кеширование последнего ответа добавить, чтобы поиск не делать, если ожидается последовательный доступ к содержимому.

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

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


_>>Поиск выглядит так:
W>

_>>            {return (value.data_offset_pos + value.fragment_length) <= ref.data_offset_pos;});
W>

W>И не боишься передавать в lower_bound компаратор нарушающий strict weak ordering?

_>>Предварительно создал вектор индексов, каждый элемент индекса имеет три параметра: номер фрагмента, длина фрагмента и номер байта полезных данных, с которого начинается фрагмент.
W>Считаю, проще будет если использовать только последний параметр из трёх. Тогда выполнение функции сразу начинается с вызова lower_bound, а все проверки уже делаются для возвращённого итератора. Сейчас же есть как минимум несколько избыточных проверок на частные случаи, часть из которых к тому же маскирует проблему с плохим компаратором.

W>Уж лучше вместо них кеширование последнего ответа добавить, чтобы поиск не делать, если ожидается последовательный доступ к содержимому.

С избыточностью проверок и кешированием последнего ответа согласен, поправлю. на счет лямбды было бы хорошо, если бы был unary_lower_bound, но -std=c++0x его не поддерживает. Как лучше компаратор реализовать, чтобы не нарушать strict weak ordering? (признаться про существование strict weak ordering только сейчас узнал).

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

_>Как лучше компаратор реализовать, чтобы не нарушать strict weak ordering?
Не <=, а просто < (или std::less, если угодно).

_> на счет лямбды было бы хорошо, если бы был unary_lower_bound, но -std=c++0x его не поддерживает.

Ну вот сейчас в m_index_list находится массив троек. Хотя достаточно было бы хранить лишь поле .data_offset_pos, то есть использовать обычный массив целых чисел. Тогда вся работа сведётся к единственному вызову

const auto it = lower_bound(m_index_list.begin(), m_index_list.end(), data_pos);

тут проверка, что fragment_index существует (т.е. it != end(m_index_list)) 

const size_t fragment_index = it - m_index_list.begin();

тут проверка, что data_pos принадлежит границам найденного фрагмента (это и так уже делается в функции Packet::at)

Всё, других проверок и условий не нужно.

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

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

_>>Как лучше компаратор реализовать, чтобы не нарушать strict weak ordering?
W>Не <=, а просто < (или std::less, если угодно).

возможно я не прав, но так нельзя. Например если фрагмент нулевой длины, то at(0) укажет на нулевой номер фрагмента, а должен указывать на следующий фрагмент. то же самое будет, если фрагмент имеет длину n, на запрос at(n) вернется не следующий, а текущий номер фрагмента. "равно" появилось именно после тестов.
С остальным согласен, подумаю, т.к. фрагменты содержат не только полезные данные, но и служебную информацию в которой поле длины фрагмента два байта, но на первый взгляд всё легко вычислимо без дополнительных полей индекса.

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

_>"равно" появилось именно после тестов.

Ну ок. Да, <= в lower_bound можно оставить. Просто нужно обязательно помнить, что этот предикат задаёт лишь разбиение, но не strict weak ordering. То есть, если его подставить в очень похожие алгоритмы вроде std::equal_range, или std::binary_search, или как параметр std::map/set, то это приведёт к UB. Из-за таких потенциальных, но довольно вероятных проблем я бы поостерёгся так писать.

_>Например если фрагмент нулевой длины, то at(0) укажет на нулевой номер фрагмента,
Хм... А зачем тебе вообще нужно хранить фрагменты нулевой длины в этом алгоритме?
Кажется, куда лучше будет просто отфильтровать их заранее. Если же у тебя с пустыми фрагментами связана какая-то дополнительная информация, которую нельзя потерять, то всё равно стоит подумать как бы передать в конкретно эту структуру данных лишь срез исходного массива.
Но, если есть желание, то такую фигню можно обойти через upper_bound — 1, либо, что чуть лучше, изменив компаратор на такой, который ещё и вернёт true при попытке сравнения с фрагментом нулевой длины даже при совпадении начала (разумеется, не сломав при этом требования упорядоченности). Ну либо, да, оставить как есть.

_>то же самое будет, если фрагмент имеет длину n, на запрос at(n) вернется не следующий, а текущий номер фрагмента.
Что?
Например, если у тебя файл состоит из трёх фрагментов длиной соответственно n, m и k. То в массиве m_index_list будет три элемента: {0, n, m + n}. Разумеется, lower_bound от n вернёт итератор на средний элемент массива, то есть как раз на фрагмент длиной m, который и содержит в себе все байты с индексами от n до n + m — 1 включительно. Всё как надо.

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

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

_>>"равно" появилось именно после тестов.

W>Ну ок. Да, <= в lower_bound можно оставить. Просто нужно обязательно помнить, что этот предикат задаёт лишь разбиение, но не strict weak ordering. То есть, если его подставить в очень похожие алгоритмы вроде std::equal_range, или std::binary_search, или как параметр std::map/set, то это приведёт к UB. Из-за таких потенциальных, но довольно вероятных проблем я бы поостерёгся так писать.

Согласен!

_>>то же самое будет, если фрагмент имеет длину n, на запрос at(n) вернется не следующий, а текущий номер фрагмента.
W>Что?
W>Например, если у тебя файл состоит из трёх фрагментов длиной соответственно n, m и k. То в массиве m_index_list будет три элемента: {0, n, m + n}. Разумеется, lower_bound от n вернёт итератор на средний элемент массива, то есть как раз на фрагмент длиной m, который и содержит в себе все байты с индексами от n до n + m — 1 включительно. Всё как надо.

Я вот о чем: http://ideone.com/onlLWh

#include <iostream>
#include <algorithm>
#include <vector>
//#include <cstddef>

int main() 
{
    std::vector<size_t> m_index_list;
    m_index_list.push_back(0);
    m_index_list.push_back(5);
    m_index_list.push_back(9);

    for (size_t data_pos = 4; data_pos < 12; ++data_pos)
    {
        // your code goes here
        auto it = lower_bound(m_index_list.begin(), m_index_list.end(), data_pos);

        //тут проверка, что fragment_index существует (т.е. it != end(m_index_list)) 

        size_t fragment_index = it - m_index_list.begin();

        std::cout << "data_pos " << data_pos << ": fragment_index = " << fragment_index << std::endl;
    }
 
    return 0;
}

data_pos 4: fragment_index = 1
data_pos 5: fragment_index = 1 <--- ошибка
data_pos 6: fragment_index = 2
data_pos 7: fragment_index = 2
data_pos 8: fragment_index = 2
data_pos 9: fragment_index = 2 <--- ошибка
data_pos 10: fragment_index = 3
data_pos 11: fragment_index = 3

получается, чтобы избежать ошибки надо добавлять на 1 меньше, что тоже решение:

...
    m_index_list.push_back(0);
    m_index_list.push_back(5 - 1);
    m_index_list.push_back(9 - 1);
...

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

__>Я вот о чем: http://ideone.com/onlLWh
Теперь понял. Да, я ошибся. Очередная off-by-one error.

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

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

__>>Я вот о чем: http://ideone.com/onlLWh
W>Теперь понял. Да, я ошибся. Очередная off-by-one error.

Спасибо за дискуссию. Замена на upper_bound дает желаемый результат: http://ideone.com/EDZMUr