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

EP>>Почему?
E>По разным замерам, насколько я помню...

По каким таким замерам?

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

EP>По каким таким замерам?
Ну читай тот флейм, например
или заведи другую тему.

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

EP>>По каким таким замерам?
E>Ну читай тот флейм, например

Посмотрю.
Но ты же не просто запомнил что "такие-то замеры показали что по-умолчанию лучше брать list -> теперь так и поступаю, и другим советую", а наверное ещё и что там были за замеры, что они примерно измеряли, почему они показали такой реазультат, и в какой задаче

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

EP>Но ты же не просто запомнил что "такие-то замеры показали что по-умолчанию лучше брать list -> теперь так и поступаю, и другим советую", а наверное ещё и что там были за замеры, что они примерно измеряли, почему они показали такой реазультат, и в какой задаче

Ну там какие-о можельные алгоритмы брали работы с коллекцией. Типа пополняли, итерировали сортировали. Что-то такое.
Короче, без мув-семантики вектор вообще сливал, теперь не знаю, если честно.

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

E>C++ таки? Логичнее же у какого-то объекта GetNext звать?
E>Для трёх кучу делать странно, IMHO и min_elenemt'а за глаза:

Да тут не суть важно, главное алгоритм, ведь где три, там и тридцать три. А массивы вообще на диске могут лежать.
Куча все таки наверное не очень хороший вариант. Можно, например, отсортировать и походить по крайнему пока не нарушится сортировка. Потом через lower_bound найти куда переместить крайнего, ну и по новой. log n на один поиск при переходе вместо 3 log n на push-pop в бинарной куче.

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

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

К><>
К>Хороший подход, но энергичный.
К>В случае, если списки длинные (и упорядоченные), то можно запустить столько потоков, сколько есть списков, и засыпать там
К>- либо к заданным моментам времени — sleep_until, естественно, отсчитывая от момента старта программы
К>- либо на время разности между смежными значениями (это хуже, т.к. набежит ошибка)

Нене, это всё излишне усложняет. Преждевременная оптимизация, так можно и до одного потока докатиться...

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

PM>Да не победил, но сильно не ухудшил, что уже хорошо.

Но он же ещё и поменял интерфейс алгоритмов, пусть изменение и незначительное, но нельзя просто взять старый алгоритм (необязательно из STL) и использовать с его итераторами.
И, кстати, не факт что это вообще будет работать для произвольного алгоритма — может он first и last хранит в одной переменной по очереди.

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

Это преувеличение.

В текущем STL плохо поддерживаются signle pass range с предикатом, типа sentinel. Его подход позволяет использовать эти single pass с предикатом, со старым кодом, чуть чуть его изменив.
Но, в STL не так много алгоритмов работающих только с single pass. Причём многие из них, являются всего лишь обвёртками вокруг других алгоритмов. Например [find_if, find, find_if_not, ...]

Другой пример приводил Sean: вот есть partition_point и partition_point_n. Первый работает с Bounded Range, а второй с Counted Range.
Казалось бы, использовав идею Eric'а — можно избавится от реализации одного из них. Но, если посмотреть реализацию partition_point — то она всего лишь делает:

return partition_point_n(first, distance(first, last), p);

То есть опять таки — алгоритм по сути всего лишь один, а partition_point это обвёртка.
И, кстати, это не только partition_point — но и lower_bound_n, lower_bound, upper_bound_n, upper_bound, binary_search_n, binary_search — всё обвёртки.
Да, можно сэкономить на написании нескольких мини-обёрток, но — это достигается 1) за счёт потери производительности 2) изменения интерфейса всех алгоритмов (со старым кодом сразу не заработает) 3) сама концепция выглядит как хак. Стоит ли оно того?

И я думаю что таких примеров много.

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

S>Куча все таки наверное не очень хороший вариант. Можно, например, отсортировать и походить по крайнему пока не нарушится сортировка. Потом через lower_bound найти куда переместить крайнего, ну и по новой. log n на один поиск при переходе вместо 3 log n на push-pop в бинарной куче.

Там можно ещё делать бинарный поиск в самих диапазонах (оправданно или нет — зависит от данных):
https://rsdn.ru/forum/cpp/5688512.1

Автор: Evgeny.Panasyuk
Дата: 14.07.14

while(!q.empty())
{
    auto range = heap.top();  
    q.pop();
    if(!q.empty())
    {
        auto ceiling = *begin(heap.top());
        auto last = upper_bound(range, ceiling); // can be linear or binary search
        copy(begin(range), last, out)

        range = make_iterator_range(last, end(range));
        if(!empty(range))
            q.push(range);
    }
    else
    {
        copy(range, out);
    }
}

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

S>Да тут не суть важно, главное алгоритм, ведь где три, там и тридцать три. А массивы вообще на диске могут лежать.
Ну для трёх просто min_element может оказаться и быстрее кучи или сортированного массива...

S>Куча все таки наверное не очень хороший вариант. Можно, например, отсортировать и походить по крайнему пока не нарушится сортировка. Потом через lower_bound найти куда переместить крайнего, ну и по новой. log n на один поиск при переходе вместо 3 log n на push-pop в бинарной куче.
Это всё не имеет смысла. Вставлять что бы всё равно придётся двигать половину массива в среднем, так что можно просто одним прогоном пузырька сортировать на самом деле...

А куча, кстати, log n на pop и log n на push, а откуда третий?

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

E>А куча, кстати, log n на pop и log n на push, а откуда третий?

Это в асимптотике, а в операциях:

25.4.6.1 push_heap
Complexity: At most log(last — first) comparisons.

25.4.6.2 pop_heap
Complexity: At most 2 * log(last — first) comparisons.

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


EP>Это в асимптотике, а в операциях:
EP>

EP>25.4.6.1 push_heap
EP>Complexity: At most log(last — first) comparisons.

EP>25.4.6.2 pop_heap
EP>Complexity: At most 2 * log(last — first) comparisons.

IMHO, в этой задаче время будет тратится на перемещения элементов, а не на сравнения...
Так что эти оценки вообще не о чём.

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

E>IMHO, в этой задаче время будет тратится на перемещения элементов, а не на сравнения...
E>Так что эти оценки вообще не о чём.

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

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

Мой вариант:

#include "stdafx.h"

#include <iostream>

int a1[] = { 1, 5, 12, 28, 31 };
int a2[] = { 6, 9, 13 };
int a3[] = { 3, 7, 10, 15 };

int s[] = { sizeof(a1) / sizeof (int),
            sizeof(a2) / sizeof (int),
            sizeof(a3) / sizeof (int) };

int i[] = { 0, 0, 0 };
int * a[] = { a1, a2, a3 };

bool GetMin(int *a, int &n, int s, int &val)
{
    if (n < s && (val == 0 || a[n] < val))
    {
        val = a[n];
        return true;
    }
    return false;
}

bool GetNext(int &val)
{
    int ndx = -1;

    val = 0;

    for (int k = 0; k < 3; ++k)
    {
        if (i[k] >= 0 && GetMin(a[k], i[k], s[k], val) != false)
            ndx = k;
    }

    if (ndx >= 0)
    {
        if (i[ndx] >= s[ndx])
            i[ndx] = -1;
        else
            i[ndx] += 1;
        return true;
    }

    return false;
}

int main(int argc, char* argv[])
{
    int val = 0;
    while (GetNext(val))
    {
        std::cout << val << std::endl;
    }

    return 0;
}

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

E>Вообще речь идёт об альтернативе чему? Главная проблема STL в том, что это библиотека не понятно для чего...

Ну вот не холивара ради, никогда не понимал, почему в других языках (C, Perl, Python) как-то обходятся без монстров типа STL и Boost, и решают спокойно свои прикладные задачи

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


_>Ну вот не холивара ради, никогда не понимал, почему в других языках (C, Perl, Python) как-то обходятся без монстров типа STL и Boost, и решают спокойно свои прикладные задачи

Есть там всё, что есть в STL, но это не введенно в стандарт самого языка, что правильно.

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

A>>А с чего тормозить-то будет? Списки/векторы уже отсортированы, от них требуется только операция продвижения итератора вперёд.

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

Можешь ответить поподробнее? Судя по рейтингу ты знаешь о чём пишешь, а не глупость написал.
Это как-то связано с попаданием в кеш процессора?
Но в этом случае тоже на мой взгляд сложно получить разницу на порядок. Список также легко влезет в кеш. Разница только в том, что надо хранить указатель на сл. элемент, но это не так много.

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

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

watchmaker выше хорошо описал, попробую дополнить.

A>Это как-то связано с попаданием в кеш процессора?
A>Но в этом случае тоже на мой взгляд сложно получить разницу на порядок. Список также легко влезет в кеш. Разница только в том, что надо хранить указатель на сл. элемент, но это не так много.

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

Важно понимать, что кэш это не просто хранилище уже считанных значений, точнее в нём хранятся не только они.
Из памяти приходят не отдельные байты, а целые куски размером с cache-line — по 64 байта (естественно зависит от конкретной архитектуры железа).
То есть считав с произвольного места в памяти 4 байта, будет происходить полноценная перекачка из памяти в кэш аж 64 байт.

Если удачно подобрать структуру данных и алгоритм обхода, то все те "лишние" 60 байт которые пришли в кэш при первом запросе, будут использоваться следующими итерациями, а значит КПД использования memory bandwidth будет 100%. То есть, например, требуется обработать гигабайт, и перекачиваться из памяти в кэш будет именно гигабайт.
Примером этого является линейных обход массива — все элементы лежат плотно рядом с друг другом. Прочитав первый элемент с границы в 64 байта — мы также получим следующие лежащие за ним, и они не окажутся невостребованными.

При работе же со списком, в общем случае, запросив из random'ного места в памяти узел с int'ом — всё что придёт в кэш помимо самого узла, скорей всего окажется невостребованным (точнее оно может понадобится, когда уже переедет в следующий уровнеь кэша, или вообще в память).
Вот и считай — КПД использования memory bandwidth примерно 4/64*100% = 6.25%, или в 16 раз меньше чем у массива.

Если же payload больше 4 байт, то и КПД для списка улучшится.
Но, КПД использования пришедших cache-line — это не единственная проблема списков, там ещё много других проблем, например ещё нужно учитывать prefetcher

Автор: koodeer
Дата: 06.04.14

(помогающий скрыть latency при предсказуемых паттернах доступа (типа обхода массива), и бесполезный для списков, так как пока не пришёл новый узел — неизвестно что prefetch'ить).

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

---

Тест

#define _HAS_ITERATOR_DEBUGGING 0
#define _SECURE_SCL 0

#include <boost/exception/detail/type_info.hpp>
#include <boost/range/algorithm_ext.hpp>
#include <boost/range/algorithm.hpp>
#include <boost/range/numeric.hpp>
#include <boost/timer/timer.hpp>
#include <exception>
#include <iostream>
#include <iterator>
#include <vector>
#include <list>

#if defined(__GNUC__)
    #define NOINLINE __attribute__ ((noinline))
#elif defined(_MSC_VER)
    #define NOINLINE __declspec(noinline)
#else
    #define NOINLINE
#endif

template<int> NOINLINE void ASM_MARKER() { volatile int x = 0; (void)x; }

/******************************************************************************/
using namespace std;

template<typename Range>
void test(Range &r)
{
    cout << boost::type_name<Range>() << ": ";

    boost::timer::auto_cpu_timer t;

    ASM_MARKER<111>();
    volatile int result = boost::accumulate(r, 0);
    ASM_MARKER<222>();

    (void)result;
}

int main() try
{
    vector<int> v(40000000);
    boost::iota(v, 0);
    boost::random_shuffle(v);

    list<int> l(begin(v), end(v));

    l.sort();
    boost::sort(v);

    for(unsigned i=0; i!=2; ++i)
    {
        test(v);
        test(l);
    }
}
catch(const exception &e)
{
    cout << e.what() << endl;
}

Результат (MSVC2010 x64 Release):

class std::vector<int,class std::allocator<int> >:  0.022010s wall, 0.015600s user + 0.000000s system = 0.015600s CPU (70.9%)
class std::list<int,class std::allocator<int> >:  4.811541s wall, 4.820431s user + 0.000000s system = 4.820431s CPU (100.2%)
class std::vector<int,class std::allocator<int> >:  0.023067s wall, 0.031200s user + 0.000000s system = 0.031200s CPU (135.3%)
class std::list<int,class std::allocator<int> >:  4.812521s wall, 4.820431s user + 0.000000s system = 4.820431s CPU (100.2%)

Замечу что на MSVC2010 никакого автовекторизатора нет (он появился он только в следующей версии компилятора).
4.812521s / 0.023067s ~ 208.6x
ASM:

; vector
$LL61@test:
    add    ebx, DWORD PTR [rax]
    add    rax, 4
    cmp    rax, r11
    jne    SHORT $LL61@test
    
; list
$LL82@test@2:
    add    ebx, DWORD PTR [rax+16]
    mov    rax, QWORD PTR [rax]
    cmp    rax, r11
    jne    SHORT $LL82@test@2

LIVE DEMO on Coliru — тут уменьшенно N, чтобы вписаться в лимит времени.

---

P.S. Это относится не только к спискам. Например, если есть массив указателей на объекты (чем грешат многие "true-OO" языки), особенно перетасованных/пересортированных, то мы получим подобный эффект — каждое чтение имеет малое КПД, да ещё и из произвольного места.

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

_>Ну вот не холивара ради, никогда не понимал, почему в других языках (C, Perl, Python) как-то обходятся без монстров типа STL и Boost, и решают спокойно свои прикладные задачи

Ну там вроде бы никто такой задачи перед собой не ставил.
IMHO, фишка в том, что С++ -- это такой язык-конструктор языков. Типа для каждого проекта его допиливают создав библу, инструкцию программиста и т. д...
Ну и соответственно его стандартная библиотека тоже не фреймворк для решения каких-то понятных задач, а фреймворк для создания фреймворков.
Задача сложнее и решение сложнее, не лишённое некоторой красоты.
Только это всё при реальной разработке обычно нифига не нужно. А приходится тащить буст, так как голый стл ни для чего, кроме разработки аналога буста не годен. Без какой-то дополнительной библиотеки на голом стл писать малореально. Увы, но он так спроектирован. Это некий расширяемый пример как писать бесшовно расширяемы фреймворк, но он ни под что конкретно не доделан. В Перле тоже есть такая библа, только она в сиходниках интерпретатора спрятана, а тут кишки наружу.

Это всё моё IMHO, но я ещё раз призываю задавать вопросы в ОТДЕЛЬНОЙ ТЕМЕ. Не надо портит оценку решения всякой философией!

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


E>Ну там вроде бы никто такой задачи перед собой не ставил.

Там эта задача решена, на уровне синтаксиса языка.
Что вообще такое всё, что есть в STL? Вот есть в perl
хеши %h()-ассоциативные массивы, они же словари в питоне,
удобно. В C++ нет, хотя этот язык претендует на высокоуровневый,
с возможностью низкоуровневых оптимизаций, но с средствами для упрощения
и ускорения разработки прикладных приложений, прежде всего, и для этого
обязанный содержать развитые всокоуровневые структуры данных. Так же
про остальные: списки, массивы-всё это в упомянутых языках
на уровне синтаксиса с реализацией на уровне интерпретатора.
В погоне за "не отстать и перегнать" появляются костыли, вроде
STL, которые вводятся в стандарт. ИМХО получилось неуклюже.

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

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

Это называется merge sorting...
один этап -- merge.