Russian Qt Forum

Добрый день

Делаю интерактивный редактор типа "кисти" которая красит точки на "холсте" (в терминах Верес(а))  :). Возникла такая задачка: даны 2 контейнера структур сортированных по возрастанию

C++ (Qt)
typedef std::pair <int, double> TPair;
typedef std::vector <TPair> TVec;
 

Гарантируется уникальность first (ключа) в обоих исходных. В первом все second (значения) ненулевые. Нужно получить контейнер также сортированный,

C++ (Qt)
TVec Merge( const TVec & src1, const TVec & src2 );
 

правила

- если значение = 0 во втором контейнере, такой эл-т не включается в выходной (хоть и был с таким ключом в первом). Др словами это операция удаления

- если эл-т с одним и тем же ключом есть в обоих - то принимается значение из второго (операция замещения) и эл-т включается в выходной  

- если эл-т с таким ключом (и ненулевым значением) только в первом или только во втором - он включается в выходной со своим значением.

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

------

Edit: еще лучше не возвращать контейнер, а модифицировать первый

C++ (Qt)
void Merge( TVec & src1, const TVec & src2 );

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

Набросал на коленке (немного изменённый std::merge..)

C++ (Qt)
struct my_predicate
{
    template <class T>
    bool operator()(const T & a) const
    {
        return (a.second != 0);
    }
 
    template <class T>
    bool operator()(const T & a, const T & b) const
    {
        return b.first <= a.first;
    }
};
 
 
template <class Iterator, class Container, class Predicate>
void merge_if(Iterator first1, Iterator last1,
              Iterator first2, Iterator last2,
              Container & result, Predicate pred)
{
    while (true)
    {
        if (first1 == last1)
        {
            std::copy_if(first2, last2, std::back_inserter(result), pred);
            return;
        }
 
        if (first2 == last2)
        {
            std::copy(first1, last1, std::back_inserter(result));
            return;
        }
 
        if (!pred(*first2))
        {
            ++first2;
            continue;
        }
 
        if (pred(*first1, *first2))
            result.push_back(*first2++);
        else
            result.push_back(*first1++);
    }
}
 

Не проверял, но идея, думаю, понятна..

Проверяем кончился ли один из контейнеров, если да - копируем хвост второго. Хорошо, а дальше
Пример:
Первый: (1, 0.6) (2, 0.1) ...
Второй: (2, 0.0) ...

В итоге эл-т (2, 0.1) успешно проскочил (а не должен был)

Не страшно) Есть предикат, а его уже можно научить и это проверять)

А можно увидеть процесс его обучения? :) Ведь сейчас до нужного ф-ционала еще далеко

offtop: Объяснив с "моей" терминологией вы четко обрисовали задачу. Однако, это уже прогресс :)

Ой далекоооо)

Ну, например, как то так (не проверял: это уже вопрос десятый, главное идея..):

C++ (Qt)
struct my_stepper
{
    template <class T>
    bool operator()(const T & a) const
    {
        return (a.second != 0);
    }
 
    template <class Iter, class Container>
    bool operator()(Iter & in1, Iter & in2, Container & c) const
    {
        if (in2->second == 0) {
            key = in2->first;
            ++in2;
            return false;
        }
 
        if (key)
        {
            if (in1->first == *key) {
                ++in1;
                return false;
            }
        }
 
        auto it = std::back_inserter(c);
 
        *it++ = (in2.first <= in1.first) ? *in2++ : *in1++;
 
        return true;
    }
 
private:
    boost::optional<int> key;
};
 
 
template <class Iterator, class Container, class Stepper>
void merge_if(Iterator first1, Iterator last1,
              Iterator first2, Iterator last2,
              Container & result, Stepper stepper)
{
    while (true)
    {
        if (first1 == last1)
        {
            std::copy_if(first2, last2, std::back_inserter(result), stepper);
            return;
        }
 
        if (first2 == last2)
        {
            std::copy_if(first1, last1, std::back_inserter(result), stepper);
            return;
        }
 
        stepper(first1, first2, result);
    }
}
 

Вот картинка чтобы оживить обсуждение. Точки (узлы сетки) хранятся как пары *индекс + значение" которое показано цветом. Черные точки не хранятся (background). Юзер тыкает "кистью" которая может быть достаточно большой. Если кисть "жесткая" то все точки попавшие в радиус захвата получают цвет кисти (или удаляются из контейнера если кисть черная). Если кисть "мягкая" то результат размазывается/интерполируется от центра к краю. Формализуя это приходим к правилам поста #1  

Пример: второй контейнер  (1, 0) (2, 0)... эл-т с индексом 1 не будет удален (из первого)

Пфф.. Если нужна предыстория по всем нулевым ключам, то можно заменить boost::optional на обычный set, например.

C++ (Qt)
struct my_stepper
{
    template <class T>
    bool operator()(const T & a) const
    {
        return (a.second != 0) && (keys.find(a.first) == keys.end());
    }
 
    template <class Iter, class Container>
    bool operator()(Iter & in1, Iter & in2, Container & c) const
    {
        if (in2->second == 0) {
            keys.insert(in2->first);
            ++in2;
            return false;
        }
 
        if (keys.find(in1->first) != keys.end())
        {
            ++in1;
            return false;
        }
 
        auto it = std::back_inserter(c);
 
        if (in2->first == in1->first)
        {
            *it++ = *in2++;
            ++in1;
            return true;
        }
 
        *it++ = (in2->first < in1->first) ? *in2++ : *in1++;
 
        return true;
    }
 
private:
    mutable std::set<int> keys;
};
 
 
template <class Iterator, class Container, class Stepper>
void merge_if(Iterator first1, Iterator last1,
              Iterator first2, Iterator last2,
              Container & result, Stepper stepper)
{
    while (true)
    {
        if (first1 == last1)
        {
            std::copy_if(first2, last2, std::back_inserter(result), stepper);
            return;
        }
 
        if (first2 == last2)
        {
            std::copy_if(first1, last1, std::back_inserter(result), stepper);
            return;
        }
 
        stepper(first1, first2, result);
    }
}
 

Но это всё детали конкретной реализации Вашего steppera.  

Основная здесь мысль в том, что этот подход сейчас достаточно гибок. Если завтра Вам придёт в голову написать ещё десяток правил для слияния, то достаточно лишь написать свои пользовательские stepperы при этом ничего не меняя в самой функции merge_if.
Более того, она будет работать с любым контейнером..      

Что значит "Пфф.. если нужна"? Не надо мне одолжений делать, условия знаете - стало быть нужна. И чего вот так, без раздумий, тулить ассоциативный контейнер? Это удовольствие дорогое. Не лучше ли так

C++ (Qt)
template <class Iter, class Container>
void Step(Iter & in1, Iter & in2, Container & c) 
{
  if (in1->first < in2->first)  // ключ в первом меньше
    c.push_back(*in1++);    // добавляем из первого и продвигаем его
 
  else {    // ключ в первом НЕ меньше
    if (in2->second)  c.push_back(*in2);     // добавляем из второго если не ноль
    if (in1->first == in2->first) ++in1;        // двигаем первый если ключи равны
    ++in2;                      // всегда двигаем второй 
  }
} 
 

Но это неоптимально. Пример: юзер выбрал всего одну точку и меняет ее значение напр с 0.1 на 0.5. Чего же перемалывать весь контейнер? Ведь он сортирован, возможно пресловутое log(N). Как это сделать не плодя частных случаев?

Без частных случаев - перемалывать весь контейнер :D

Не понял? Есть два контейнера, нужно слить их в третий.. Это уже как минимум ~ N.. О каком логарифме идёт речь?   

C++ (Qt)
void Merge( TVec & src1, const TVec & src2 );

Хотите быстрый поиск (logN), придётся использовать контейнер с random access доступом.. Но, вот если юзер тыкнет мышью и изменит значение на 0.0, то затраты на "выковыривание" этой точки из первого контейнера (вектора) перекроют затраты на поиск..
Короче, оно того стоит?     

С одной точкой все прекрасно получается в общем виде. Все равно чтобы "выковырять" ее надо сначала найти.

Насколько я помню random access означает просто одинаковое время доступа к эл-ту, массив этому требованию удовлетворяет. Вероятно Вы имели ввиду ассоциативный контейнер, напр std::map/set. С таким конечно думать не надо, все операции очевидны (за что придется заплатить перегонками в др местах кода). И так ли уж это хорошо? Напр при большом кол-ве удаляемых std::set легко может оказаться медленнее. Вообще чем сортированный массив хуже? Тем что накладно вставлять/удалять? Так здесь это в одной интерактивной операции, не страшно. Что тут сложного/военного? Только то что никогда раньше это не делали  :)

random access - это фактически доступ по индексу за константное время (например вектор).
Например в списке, даже сортированном, поиск будет "линейным", а не "логарифмическим", но..
Я хотел сказать, что если подразумевается возможное удаление, вставка элементов, то для вектора, даже с логарифмическим поиском, это будет затратнее в целом, чем, например, с тем же списком, хоть и с линейным поиском.
Вообщем, все эти пляски с частными случаями и оптимизацией сейчас напоминают миф о Сизифе..

Может имеет смысл/правильнее вернуться назад и пересмотреть архитектурно те решения, которые привели к этой задаче?) 

К чему сводится этот "архитектурный пересмотр"? Давайте возьмем более подходящий контейнер (напр std::set). Это понятно, но не всегда удобно/выгодно. Есть др модули для которых текущий формат данных утвержден (кстати он такой же и в др приложениях), а гонять из одного контейнера в другой не есть хорошо. Кроме того, прикинув возможные варианты, легко убедиться что шаблонное решение std::set оптимальным совсем не является. Вот были бы данные не сортированы - тогда да, а так нет.

Меня вполне устраивает слияние в выходной контейнер (как обсуждалось выше), но интересна общая ситуация. Фактически есть сортированный контейнер (первый) и набор команд (типа batch) - второй контейнер. Набор полный: изменить/добавить/удалить. Как его оптимально "процессить"?