Оцените решение задачи - C/C++

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

EP>А что Hana даёт по сравнению с Boost.Fusion? Только скорость компиляции?

Не знаю

, хотел просто посмотреть на Hana. Мне нужно было compile-time reflection для структур с наследованием, с Boost.Fusion не получилось: BOOST_FUSION_ADAPT_STRUCT для базового класса, решил посмотреть что еще есть.

PM>>Кстати недавно Eric победил проблему с производительностью counted ranges

EP>Спасибо за ссылку.
EP>Но ведь не побелил же! Его концепция CountedRange выглядит как хак, который к тому же жертвует производительностью. Если бы не было потерь производительности, то можно было бы и пережить, а с потерями — ну уж нет.
EP>ИМХО, не нужно боятся вводить новые концепции Range'ей — если эти концепции чётко улавливают суть, позволяя писать эффективный код (в абсолютном смысле, а не "в этом вот примере всего 5%" разница). Не хаки-адапторы к старым алгоритмам, а полноценные range со своими оптимизированными алгоритмами, как раз наподобие partition_point_n.

Да не победил, но сильно не ухудшил, что уже хорошо. Вообще, насколько я помню, основной трудностью у него было то, что в перспективе маячили параллельные иерархии bounded, counted and infinite ranges и для каждой иерархии нужно было реализовывать весь набор алгоритмов из стандартной библиотеки.

А с такими адаптерами можно использовать библиотечные реализации, что гораздо надежнее. И оптимизированные реализации для разных типов ranges со временем будут добавляться.

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

_>Здравствуйте, Evgeny.Panasyuk, Вы писали:

EP>>Линейный обход связного списка в общем случае на порядок(и) дороже чем соответствующий обход вектора. Если в задаче не указанно что нужен именно связный список, то по-умолчанию нужно брать vector.

_>Намекаешь на то, что элементы вектора помещаются в памяти последовательно и компактно, а элементы списка — как повезет?
Даже если разместить узлы списка в памяти последовательно, то всё равно его обход будет в разы медленнее вектора. Неприятно, но не катастрофа.
Но вот если действительно узлы списка раскидать по памяти, то одних кеш-промахов уже вполне будет достаточно для той самой просадки на порядки.
Ещё тут стоит учесть, что элементы списка расходуют память менее экономно чем вектор. Что опять же не лучшим образом сказывается на использовании кеша.

_>:???: Откуда порядки? Обход вектора — грубо говоря — выкомпилируется в инкремент адреса на константу. Обход связного списка — в чтение адреса следующего элемента.
Чтение адреса следующего элемента — это плохо. Плохо потому что это ещё одно чтение из памяти, и плохо потому что программа как правило не может продвинутся дальше до завершения чтения из-за зависимости по данным. Ведь в типичной итерации по списку сначала читается адрес следующего элемента, а затем он обрабатывается. Суперскалярный процессор может делать эти операции почти параллельно для вектора, но лишь последовательно для списка.

Ну и прочие эффекты, вроде автоматической векторизации и распараллеливания алгоритмов могут играть свою роль. Для вектора компилятор во многих случаях умеет делать это автоматически, для списка же шансов практически нет.

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

Есть ещё одно решение, лежащее в стороне.
Это использование приоритетной очереди.

по-быстрому накидал

#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
#include <iterator>

// исходные данные
typedef int Value;
typedef std::vector<Value> Source;

typedef std::vector<Source> Sources;
Sources sources;

// состояние вектора можно представить как диапазон итераторов
typedef Source::iterator SourceIter;
typedef std::pair<SourceIter,SourceIter> SourceRange;

SourceRange full_range(Source& s) { return SourceRange(s.begin(), s.end()); }
bool is_empty(SourceRange const& sr) { return sr.first == sr.second; }
Value peek(SourceRange const& sr) { return *sr.first; }
Value shift(SourceRange& sr) { return *sr.first++; }

std::ostream& operator<< (std::ostream& ost, SourceRange const& sr)
{
    ost << "[";
    std::copy(sr.first, sr.second, std::ostream_iterator<Value>(ost,","));
    ost << "]";
    return ost;
}

// очередь

struct Comparator // над непустыми диапазонами
{
    bool operator()(SourceRange const& l, SourceRange const& r) const
    {
        std::cout << "   -- comparing " << l << " to " << r << std::endl;
        return peek(l) > peek(r);
    }
};

typedef std::priority_queue<SourceRange, std::vector<SourceRange>, Comparator> Queue; // очередь из непустых диапазонов
Queue queue;

void add_to_queue(SourceRange const& sr)
{
    std::cout << " -- adding " << sr << std::endl;
    if(!is_empty(sr))
        queue.push(sr);
    std::cout << std::endl;
}

void add_to_queue_full_range(Source& s)
{
    add_to_queue(full_range(s));
}

// собственно, наша задача

void setup()
{
    for(Source& s : sources)
        add_to_queue_full_range(s);
}

bool done()
{
    return queue.empty();
}

Value next()
{
    SourceRange sr = queue.top();
    std::cout << " -- taking " << sr << std::endl;

    queue.pop();
    std::cout << std::endl;

    Value v = shift(sr);
    add_to_queue(sr);
    return v;
}

// проверяем

int main()
{
    sources = Sources {
        Source { 1, 5, 12, 28, 31 },
        Source { 6, 9, 13 },
        Source { 3, 7, 10, 15 },
    };

    setup();

    std::cout << "--------" << std::endl;
    while(!done())
    {
        Value v = next();
        std::cout << v << std::endl;
    }
}

Здравствуйте, Andrew.W Worobow, Вы писали:

O>>Даны 3 списка с числами. Числа в списках не повторяются. Сами списки отсортированы. Необходимо реализовать метод GetNext, который бы обходил все 3 списка и выдавал числа в порядке возрастания. Объединять списки нельзя!

AWW>Что значит нельзя объединят?
Очевидно же: нельзя создавать копию данных.

AWW>Тут вообще просится дерево, единное дерево. И все. То есть все просто, дерево с узлами элементами этих списков.
AWW>Всего на вскидку строчек 20-30. Если использовать готовую реализацию дерева.

Дерево — это читерство, потому что это копия данных. Только, если сделаешь ленивое дерево. Но на С++ ленивость в 20 строчек не уложится.

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

O>>>Даны 3 списка с числами. Числа в списках не повторяются. Сами списки отсортированы. Необходимо реализовать метод GetNext, который бы обходил все 3 списка и выдавал числа в порядке возрастания. Объединять списки нельзя!

AWW>>Что значит нельзя объединят?
К>Очевидно же: нельзя создавать копию данных.

Надо тогда в задаче четко написать — стоимость копирования данных равна 100*О.

AWW>>Тут вообще просится дерево, единное дерево. И все. То есть все просто, дерево с узлами элементами этих списков.
AWW>>Всего на вскидку строчек 20-30. Если использовать готовую реализацию дерева.

К>Дерево — это читерство, потому что это копия данных. Только, если сделаешь ленивое дерево. Но на С++ ленивость в 20 строчек не уложится.

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

Вообще дерево можно сделать и без копирования, ну ссылки там, указатели.
Тут то еще вопрос — "А где написано что копировать нельзя?"

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

_>>

Откуда порядки? Обход вектора — грубо говоря — выкомпилируется в инкремент адреса на константу. Обход связного списка — в чтение адреса следующего элемента.

Переход по списку p=p->next;

  4006fc:       48 8b 45 f8             mov    -0x8(%rbp),%rax
  400700:       48 8b 00                mov    (%rax),%rax
  400703:       48 89 45 f8             mov    %rax,-0x8(%rbp)

Переход по массиву ++i; d=mas[i]


  
  4006f9:       8b 45 fc                mov    -0x4(%rbp),%eax
  4006fc:       8d 50 01                lea    0x1(%rax),%edx
  4006ff:       89 55 fc                mov    %edx,-0x4(%rbp)
  400702:       48 98                   cltq   
  400704:       8b 84 85 60 fe ff ff    mov    -0x1a0(%rbp,%rax,4),%eax
  40070b:       89 45 f8                mov    %eax,-0x8(%rbp)

[/code]

Объясните на этом примере где тут итерация по массиву обходится дешевле чем по списку.
Более того, итерация по списку-дешевле.
Что до промахов в кеше из-за раскиданности нод списка, во всех нормальных
системах, ноды для списков выделяются из некоторого непрерывного массива,
кеша специализированного аллокатора. Так что никакой раскиданности.

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

А так?


template <typename T, int N, template <typename...> class U, template <typename...> class P >
 struct iter {
  typedef U<T> value_array;
  typedef P<value_array*> pointer_array;
  iter(const pointer_array& u): mas(u), msz(mas.size()),
                sz(0), current(0)
  {  size_t n=msz, m=0, tmp;
    max_sz=0;
      while(m<n)
       {
        tmp=mas[m]->size();
        index[m]=0;
        max_sz+=tmp;
        sz1[m++]=tmp;
       
       };
     
     };

  bool allow(size_t n){ return sz1[n] > index[n]; };
  const pointer_array& mas;
  size_t sz;
  size_t msz;
  size_t sz1[N];
  size_t index[N];
  size_t max_sz;
  size_t current;
 };
 

template <typename T, int N, template <typename...> class U, template <typename...>  class P>
T* GetNext(iter<T, N, U, P>& m){
  typedef typename iter<T, N, U, P>::value_array value_array;
  T* p=NULL;
  size_t  lim=m.msz, cnt=0, tmp=m.sz;
  if(tmp == m.max_sz) return NULL;
  tmp=m.current;
  if(!m.allow(tmp))
   {
     while(cnt< lim)
       {
    if(m.allow(cnt))
         {  
       tmp=cnt; m.current=tmp; break;
         };
    ++cnt;
       };
       if(cnt==lim) return NULL;
     }; 
  
  value_array& ref=*m.mas[tmp];
   p=const_cast<T*>(std::addressof(ref[m.index[tmp]]));
   cnt=0;
   while(cnt < lim){
     if(!m.allow(cnt)){ ++cnt; continue; }
     tmp=m.index[cnt];
     value_array& ref=*m.mas[cnt];
     if(p)
       {
     if(ref[tmp] < *p)
            {
             p=const_cast<T*>(std::addressof(ref[tmp]));
             m.current=cnt;         
        }
       };
     ++cnt;
       };
  ++m.sz;
  ++m.index[m.current];
  return p;
 };

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

O>Решение:

Ужос.

Коду машинного нагенерируется раз в 20 больше, чем если не заворачивать все подряд в STL'ные контейнеры.

Не говоря уж о том, что нет никакой надобности проходиться по vectors два раза.

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

А вот ещё одно решение. Его идея в том, чтобы учитывать сравнения, сделанные на предыдущих шагах.
Для простоты, сделал на мутабельных списках, из которых изымаются головные значения. Переделать на неизменяемые векторы — дело нехитрое, просто потребуется ещё и индексы/итераторы хранить.

Скрытый текст

#include <vector>
#include <list>
#include <iostream>

using namespace std;

typedef int Value;
std::vector< std::list<Value> > sources; // ровно 3 элемента

// конечный автомат
typedef Value (*TakeFun)();
TakeFun taker = nullptr;

// такт конечного автомата:
template<int A, int B, int C> // номера источников, в порядке возрастания голов
Value take()
{
    cout << "take " << A << "," << B << "," << C << endl;

    // взять самый маленький из самого маленького
    Value v = sources[A].front();
    sources[A].pop_front();

    // действие для следующего такта
    if(sources[A].empty()) // источник кончился - выпихнем его в хвост
        taker = take<B,C,-1>;
    else if(B < 0 || sources[A].front() <= sources[B].front()) // первый источник по-прежнему лучший (или второго уже нет)
        taker = take<A,B,C>;
    else if(C < 0 || sources[A].front() <= sources[C].front()) // первый источник - между вторым и третьим (или третьего нет)
        taker = take<B,A,C>;
    else // первый источник - позади третьего
        taker = take<B,C,A>;

    return v;
}

// инициализируем конечный автомат, сортировка пузырьком
template<int A, int B, int C> void setup()
{
    cout << "setup " << A << "," << B << "," << C << endl;
    if(A < 0)
        taker = take<-1,-1,-1>;
    else if(B < 0)
        taker = take<A,-1,-1>;
    else if(sources[A].front() > sources[B].front())
        setup<B,A,C>();
    else if(C < 0)
        taker = take<A,B,-1>;
    else if(sources[B].front() > sources[C].front())
        setup<A,C,B>();
    else
        taker = take<A,B,C>;
}

int main()
{
    sources = vector< list<int> > {
        list<int> { 1, 5, 12, 28, 31 },
        list<int> { 6, 9, 13 },
        list<int> { 3, 7, 10, 15 },
    };

    setup<0,1,2>();
    cout << "------" << endl;
    while(taker != &take<-1,-1,-1>)
    {
        Value v = taker();
        cout << v << endl;
    }
}

Здравствуйте, Andrew.W Worobow, Вы писали:

AWW>>>Что значит нельзя объединят?
К>>Очевидно же: нельзя создавать копию данных.
AWW>Надо тогда в задаче четко написать — стоимость копирования данных равна 100*О.

У меня телепалка лучше работает

AWW>>>Тут вообще просится дерево, единное дерево. И все. То есть все просто, дерево с узлами элементами этих списков.
AWW>>>Всего на вскидку строчек 20-30. Если использовать готовую реализацию дерева.

К>>Дерево — это читерство, потому что это копия данных. Только, если сделаешь ленивое дерево. Но на С++ ленивость в 20 строчек не уложится.

AWW>

AWW>Вообще дерево можно сделать и без копирования, ну ссылки там, указатели.
AWW>Тут то еще вопрос — "А где написано что копировать нельзя?"

Включаю телепалку: ты хочешь сделать не просто "единое дерево", а "непросто" — а именно, приоритетную очередь.
Дерево — это потроха реализации приоритетной очереди. Причём обычная, std::priority_queue, вообще лишь подразумевает деревянную структуру, а размещается в обычном векторе.
Я тут для прикола наколбасил очередь на конечном автомате с шаблонной функцией перехода. Можно ведь и так.

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

#include <vector>
#include <list>
#include <set>
#include <iostream>
#include <stdint.h>

std::set<int32_t> GetNext(const std::vector<std::list<int32_t>> &source)
{
    if (source.empty()) return std::set<int32_t>();

    std::set<int32_t> result;
    for (uint32_t sourceIndex = 0; sourceIndex < source.size(); ++sourceIndex) {
        result.insert(source[sourceIndex].begin(), source[sourceIndex].end());
    }
    return result;
}
int main()
{
    std::list<int32_t> source1 = { 1, 5, 12, 28, 31 };
    std::list<int32_t> source2 = { 6, 9, 13 };
    std::list<int32_t> source3 = { 3, 7, 10, 15 };

    std::vector<std::list<int32_t>> sources;
    sources.push_back(source1);
    sources.push_back(source2);
    sources.push_back(source3);

    auto result = GetNext(sources);
    for (auto value : result) {
        std::cout << value << std::endl;
    }

    return 0;
}

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

S>Что до промахов в кеше из-за раскиданности нод списка, во всех нормальных
S>системах, ноды для списков выделяются из некоторого непрерывного массива,
S>кеша специализированного аллокатора. Так что никакой раскиданности.

Вот мне тоже так думается, но у wathcmaker-а был еще один козырь — зависимость по данным. Компилятор может (хотя и не должен) развернуть цикл обхода массива и (в суперскалярной арх-ре) практически параллельно выполнять операции над группой элементов массива. Отдельные коллеги, (напр. Касперски в одной из своих книг) уверяют, что это дает существенную разницу.

P.S. Кроме того, для связного списка нет никакой гарантии, что последовательные элементы списка располагаются в памяти последовательно, что как бы снижает эффект выделения памяти для узлов списка из одного пула.

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

Ну так ты энергично объединил списки в set.
А в условиях задачи было сказано этого не делать.

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

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

К>Ну так ты энергично объединил списки в set.
К>А в условиях задачи было сказано этого не делать.

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

P.S. Если уж точно следовать условию задачи, то записи вида std::vector<std::list<int32_t>> (и похожее) даже в виде входных параметров для функции GetNext не допустимы.

Здравствуйте, Кодт, Вы писали:
К>int main()
К>{
К> sources = vector< list<int> > {
К> list<int> { 1, 5, 12, 28, 31 },
К> list<int> { 6, 9, 13 },
К> list<int> { 3, 7, 10, 15 },
К> };
К>}
К>[/c]
К>[/cut]
Это не объединение ?)

Условие:
Даны 3 списка с числами. Числа в списках не повторяются. Сами списки отсортированы.
Необходимо реализовать метод GetNext, который бы обходил все 3 списка и выдавал числа в порядке возрастания. Объединять списки нельзя!

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

O>Условие:
O>Даны 3 списка с числами. Числа в списках не повторяются. Сами списки отсортированы. Необходимо реализовать метод GetNext, который бы обходил все 3 списка и выдавал числа в порядке возрастания. Объединять списки нельзя!
O>Примеры списков:
O>[List]: 1, 5, 12, 28, 31
O>[List]: 6, 9, 13
O>[List]: 3, 7, 10, 15
O>Вывод в этом случае должен быть таким:
O>GetNext << 1;
O>GetNext << 3;
O>GetNext << 5;
O>GetNext << 6;
O>GetNext << 7;
O>GetNext << 9;
O>и т.д.

O>Шутка!:

#include <iostream>
#include <vector>
#include <thread>
#include <chrono>

void GetNext(int n)
{
  std::this_thread::sleep_for(std::chrono::milliseconds(n*500));
  std::cout << "GetNext << " << n << std::endl;
}


void Start(int* p, size_t sz)
{
    for(size_t i = 0; i < sz; i++)
      std::thread(GetNext, p[i]);
}


int main(int argc, char * argv[])
{
    int vec1[] = {1, 5, 12, 28, 31};
    int vec2[] = {6, 9, 13};
    int vec3[] = {3, 7, 10, 15};

    Start(vec1, sizeof(vec1)/sizeof(int));
    Start(vec2, sizeof(vec2)/sizeof(int));
    Start(vec3, sizeof(vec3)/sizeof(int));
  
    std::this_thread::sleep_for(std::chrono::seconds(30));
    return 0;
}

И отсортированность списков не нужна!

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

S>Объясните на этом примере где тут итерация по массиву обходится дешевле чем по списку.
Какой-то странный пример. Такое ощущение, что выключена оптимизация. Приведи исходный код, настройки компилятора. И нужно больше контекста. И лучше сравнивать более-менее ясные задачи, а не совсем уж абстрактные строчки кода вроде d=mas[i].
Ведь можно написать одну функцию из одной строки:

template<T> inc(T::iterator& i) { ++i; }

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

В общем, я на твоём примере пока объяснять не буду. Лучше приведу свой:

template <typename C> traverse_test(const C& c) {
    volatile auto x = accumulate(c.begin(), c.end(), 0);
}

Компилируем на x86-64 c g++ 4.8.2 с выключенной векторизацией и с выключенным распараллеливанием.
Если в качестве контейнера C взять std::list<int> или std::forward_list<int>, то внутренний цикл будет выглядеть так:

.L5:
        addl    8(%rax), %edx  // сложили в аккумулятор
        movq    (%rax), %rax   // взяли адрес следующего элемента
        testq   %rax, %rax     // проверили, что список не закончился
        jne     .L5            // и начали обрабатывать следующий элемент

Если качестве контейнера C взять std::vector<int>, то цикл получится таким:

.L5:
        addl    (%rax), %edx   // сложили в аккумулятор
        addq    $4, %rax       // взяли адрес следующего элемента
        cmpq    %rax, %rcx     // проверили, что список не закончился
        jne     .L5            // и начали обрабатывать следующий элемент

Если разрешить автоматическую векторизацию (точнее не запрещать, так как она включена по умолчанию), то код для std::list<int> или std::forward_list<int> не изменится, а для std::vector<int> основный цикл будет таким:

.L15:
        addq    $1, %rdx       // обновили счётчик
        paddd   (%rsi), %xmm0  // сложили в аккумулятор 
        addq    $16, %rsi      // взяли адрес следующего элемента
        cmpq    %rdx, %r9      // проверили счётчик
        ja      .L15           // и начали обрабатывать следующий элементы

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

Но, разумеется, скорость работы меряется не числом инструкций. Поэтому тест нужно ещё запустить. Возьмём миллион чисел, положим их в контейнер. Убедимся что все элементы идут в памяти плотно и по порядку (в реальной программе, такие гарантии получить можно не всегда для списков, но пусть будет так). И запустим traverse_test раз 200. У меня не видно существенных отличий между std::list<int> и std::forward_list<int> в этом тесте, а в остальном время работы получается таким:

list    590 ms // c и без автовекторизации
vector  103 ms // без автовекторизации
vector  43  ms // c автовекторизацией

С тестированием forward_list возникла правда сложность, так как там есть только push_front, но не push_back, то есть элементы идут как бы в обратном порядке. И если это не исправлять, то скорость работы :forward_list оказывается даже ниже list и тест завершается за 650 ms. Если аналогично "ухудшить" ситуацию и для вектора, использовав rbegin вместо begin, то замедление также заметно ухудшает автовекторизированный вариант на 4-5 мс, не изменяя, впрочем, существенно вариант без векторизации.

В общем, из этого теста вполне можно заключить, что фраза «vector на порядок быстрее list в задаче пробега по всем элементам (и подсчёта их суммы)» не так уж далека от истины.

S>Что до промахов в кеше из-за раскиданности нод списка, во всех нормальных
S>системах, ноды для списков выделяются из некоторого непрерывного массива,
S>кеша специализированного аллокатора. Так что никакой раскиданности.
Это верно разве что только после первичного заполнения списка. Как только начинаются его модификации, то сразу всё идёт кувырком.
Да вот, например, тут предложено собрать один список из трёх, видимо переставляя только указатели, не перенося сами элементы. Но после этого многие связи между элементами будут совсем нелокальными, даже если изначально все элемента каждого списка шли подряд. Конечно, в данной задаче с тремя списками это не так критично — отслеживать три потока prefetch современные x86 процессоры умеют, — но в чуть-чуть более сложной задаче всё будет куда печальнее. Удали, например, из списка элемент, потом добавь к нему новый в начало. Либо просто вставь новый элемент в середину. Где будет для него память выделена? Будет ли она в той же или в соседней кеш-линии, что и память его соседей по списку? Да совсем не обязательно. И никакой специализированный аллокатор это не поборет.
А если вставки или удаления в середине не нужны, то зачем тем более выбирать список, а не массив?

От:	Andrew.W Worobow	https://github.com/Worobow
Дата:	16.10.14 07:04
Оценка:	-1

От:	Andrew.W Worobow	https://github.com/Worobow
Дата:	16.10.14 07:14
Оценка:

	От:	slava_phirsov
	Дата:	16.10.14 08:12
	Оценка:

	От:	PM
	Дата:	16.10.14 09:11
	Оценка:

	От:	watchmaker
	Дата:	16.10.14 09:36
	Оценка:	+1

От:	Pzz	https://github.com/alexpevzner
Дата:	16.10.14 13:00
Оценка:

	От:	Кодт
	Дата:	16.10.14 13:03
	Оценка:	39 (3) +1