range-v3 и модный C++ - C/C++. Прикладные вопросы

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

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

Хочу простого, для иллюстрации пример на Clojure, где такое можно сделать красиво и элегантно:

(def v1 (list (list 3 4 5 1 7)
              (list 1 3 6 3 8)))

(-> v1
    flatten
    distinct
    sort
    (#(take 3 %)))

Пока что у меня на C++ вышла вот такая хреновина, которая, почему-то, отказывается убирать дубликаты

std::vector<std::vector<size_t>> v1 = { { 3, 4, 5, 1, 7 }, { 1, 3, 6, 3, 8 } };

std::vector<size_t> joined = v1 | ranges::views::join | ranges::views::unique |
                                 ranges::to<std::vector<size_t>> | ranges::actions::sort;
std::vector<size_t> res( joined.begin(), joined.begin() + 3 );

Но хочется без разбиения на 2 этапа и, конечно же, без дубликатов

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

KP>Пока что у меня на C++ вышла вот такая хреновина, которая, почему-то, отказывается убирать дубликаты

Очерёдность sort и unique перепутана.


  std::vector<size_t> res = v1 | ranges::views::join
                               | ranges::to_vector
                               | ranges::actions::sort
                               | ranges::actions::unique
                               | ranges::actions::take (3);

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

F>Очерёдность sort и unique перепутана.

F>


F>  std::vector<size_t> res = v1 | ranges::views::join
F>                               | ranges::to_vector
F>                               | ranges::actions::sort
F>                               | ranges::actions::unique
F>                               | ranges::actions::take (3);

F>

А почему нел6взять unique из views?

А, понял, документацию надо читать:

views::unique
Given a range, return a new range where all consecutive elements that compare equal save the first have been filtered out.

Эрик Ниблер (вот тут) говорит, что views::unique работает только с последовательными элементами.

views::unique
Given a range, return a new range where all consecutive elements that compare equal save the first have been filtered out.

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

R>Эрик Ниблер (вот тут) говорит, что views::unique работает только с последовательными элементами.
R>

R>views::unique
R>Given a range, return a new range where all consecutive elements that compare equal save the first have been filtered out.

Ага, нашел уже. Не очень удобно получается, из за того что часть функционала в actions, часть во views, но т.к. мы в мире C++, то надо терпеть и запоминать

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

KP>А почему нел6взять unique из views?

Все, что во views, создает обертку, содержащую ссылку на переданный аргумент, а все что в actions, меняет контейнер и передает его дальше. Так как to_vector возвращает новый объект, то views::unique к нему не применить, иначе получим висящую ссылку.

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

KP>Но хочется без разбиения на 2 этапа и, конечно же, без дубликатов

Меня пугают все эти штуки в том плане, что непонятно, с какой сложностью окажется решение. В итоге ты получаешь 3 минимальных элемента, это можно сделать императивно за N log3, то есть тупо за один проход. У тебя же там много всяких действий только для развлечения или без них не получится найти 3 минимума? Как вычислить сложность полученного решения в таком функиональном стиле?

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

N>Меня пугают все эти штуки в том плане, что непонятно, с какой сложностью окажется решение. В итоге ты получаешь 3 минимальных элемента, это можно сделать императивно за N log3, то есть тупо за один проход. У тебя же там много всяких действий только для развлечения или без них не получится найти 3 минимума? Как вычислить сложность полученного решения в таком функиональном стиле?

Это довольно интересный и в чем-то философский вопрос. Начнем с того, что у меня нет цели сделать быстрое решение. У меня есть цель попробовать разные новые фичи C++, который я, мало того что уже изрядно подзабыл, так еще новых вещей и не трогал вообще. Так же хочтеся написать красиво и читабельно, в функциональном стиле. Что проще читать — функциональный или императивный код, это отдельный вопрос, конечно, но C++ как ни крути читабельностью похвастаться сам по себе не может, но функциональный налет может эту ситуацию немного скрасить.

Сложность у решения на range будет, я полагаю что n log n за счет сортировки, ну и в целом будут еще какие-то немаленькие коэффиценты, да и банальные пенальти за память из за перетасовки данных.

Только вот в мире за пределами C++ такие вопросы как ты задаешь вообще никого не парят, по вполне себе очевидным причинам — будет тормозить так поправим, главное явной квадратичной и выше сложности не городить. К примеру я сейчас написал себе transpose для C++ который у меня вышел как-то так:

template <typename T>
std::vector<std::vector<T>> transpose( const std::vector<std::vector<T>> &inputs )
{
    assert( !inputs.empty() );
    size_t                      line_len  = inputs[0].size();
    size_t                      input_len = inputs.size();
    std::vector<std::vector<T>> res( line_len );
    for( size_t n = 0; n < input_len; n++ )
    {
        const auto &in_line = inputs[n];
        assert( line_len == in_line.size() );
        for( size_t m = 0; m < line_len; m++ )
        {
            res[m].emplace_back( in_line[m] );
        }
    }

    return res;
}

Но если бы этот самый transpose был бы реализован в range-v3, то можно было бы написать красиво и читаемо, пусть и менее элегантно чем, к примеру, на Clojure:

(defn transpose [v]
  (apply mapv vector v))

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

А вообще я решаю задачки отсюда

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

KP>Сложность у решения на range будет, я полагаю что n log n за счет сортировки, ну и в целом будут еще какие-то немаленькие коэффиценты, да и банальные пенальти за память из за перетасовки данных.

Сложность будет выше, т.к. надо будет удалять дубликаты, в std::vector это ооочень не бесплатно.

KP>Только вот в мире за пределами C++ такие вопросы как ты задаешь вообще никого не парят, по вполне себе очевидным причинам — будет тормозить так поправим, главное явной квадратичной и выше сложности не городить.

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

KP>Тут сложность решения, я полагаю, будет линейная, единственный вопрос — это коэффициент, но так ли он важен в подавляющем большинстве задач?

Ну, это и правда больше упражнение, благо для матриц сейчас библиотек достаточно и вряд ли кто-то решит писать сам. А необходимость поиска нескольких минимальных/максимальных элементов иногда встречается, реализации из коробки нет, вот и приходится самому думать. Что предлагают делать разработчики на Питоне? Сортировать! На втором месте уже np.argpartition, про который говорят, что он сработает за линейное время, что неверно в общем случае. И только где-то там самый быстрый алгоритм — heapq.nlargest. Хотя именно с кучей можно быстрее всего найти k-top элементов. Не хочется, чтобы С++ уходил в эту же сторону, краткость не решает.

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

N>Сложность будет выше, т.к. надо будет удалять дубликаты, в std::vector это ооочень не бесплатно.

А если задуматься не о сложности алгоритма, а с сложности поддержки и читабельности кода?

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

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

N>Ну, это и правда больше упражнение, благо для матриц сейчас библиотек достаточно и вряд ли кто-то решит писать сам. А необходимость поиска нескольких минимальных/максимальных элементов иногда встречается, реализации из коробки нет, вот и приходится самому думать. Что предлагают делать разработчики на Питоне? Сортировать! На втором месте уже np.argpartition, про который говорят, что он сработает за линейное время, что неверно в общем случае. И только где-то там самый быстрый алгоритм — heapq.nlargest.

На первом месте, по оценкам, как раз ответ с argpartition, это просто особенность работы SO.

N>Хотя именно с кучей можно быстрее всего найти k-top элементов. Не хочется, чтобы С++ уходил в эту же сторону, краткость не решает.

Думаю что не уйдет, на C++ пишут фанаты оптимизации всего и вся, при этом часто забывающие о том, что:

Преждевременная оптимизация — корень всех (или большинства) проблем в программировании.

Дональд Кнут

Твоя реакция тоже показательна, кстати: "а не будет ли оно тормозить?". Ну, как минимум с точки зрения алгоритмической сложности нет, т.к. там явно худший случай n log n, но с точки зрения программиста на C++ этого обычно недостаточно. Когда-то мне казалось что именно так и надо, сейчас я уже не уверен и больше склоняюсь к к тому, что пока сложность ниже квадратичной и прогоны приложения показывают что оно не откланяется по скорости от желаемого, его лучше не трогать и акцентироваться на читабельности

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

KP>Твоя реакция тоже показательна, кстати: "а не будет ли оно тормозить?". Ну, как минимум с точки зрения алгоритмической сложности нет, т.к. там явно худший случай n log n, но с точки зрения программиста на C++ этого обычно недостаточно. Когда-то мне казалось что именно так и надо, сейчас я уже не уверен и больше склоняюсь к к тому, что пока сложность ниже квадратичной и прогоны приложения показывают что оно не откланяется по скорости от желаемого, его лучше не трогать и акцентироваться на читабельности

Да, у меня есть проф деформация и я не очень люблю Питон из-за этого. Иногда кажется, что программирование на нём сродни программированию на Делфи: "А какой компонет может сделать ххх?" Только в Питоне слово "компонет" заменяется на "пакет". (Это конечно снобизм, я на нём сам такой же и с удовольствием пишу говноутилиты для парсинга и перекладывания разных штук, не выходя за рамки стантартных пакетов.)
Но глобально, я не понимаю, что стоит за вывеской питоновских import xxx, ни тут, за вывеской ranges. И если что-то будет тормозить, то придётся не разбираться, а тупо переписывать. Мне стрёмно, когда я не могу посмотреть в отладчике какой-то код или вставить в него логи.

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

KP>В последние годы комитет пытается угодить всем,

Это называется проститутки.

KP>Хочу простого, для иллюстрации пример на Clojure, где такое можно сделать красиво и элегантно:

А вот не надо на С++ писать как на Clojure! Товарищ Страуструп сколько раз это повторял!
Не для этого С+ создан!

Да, и кстати, я конечно немного выпил, но как ты собираешься выделять уникальные элементы до сортировки?
Поделись рецептиком!

(-> v1
flatten
distinct
sort
(#(take 3 %)))

KP>Только вот в мире за пределами C++ такие вопросы как ты задаешь вообще никого не парят, по вполне себе очевидным причинам — будет тормозить так поправим, главное явной квадратичной и выше сложности не городить.
В мире за пределами С++ есть например юниксовые команды sort и uniq которые должны рабать именно так: sort|uniq и еще comm которая тоже после sort применяется. Так что это как бы немного очевидно.

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

Ш>А вот не надо на С++ писать как на Clojure! Товарищ Страуструп сколько раз это повторял!

Хотелось бы избавиться от ощущения "а мне Рабинович напел", поможешь с цитатой или ссылкой на источник?

Ш>Не для этого С+ создан!

Ну как не создан, если в C++20 появились ranges?

Ш>Да, и кстати, я конечно немного выпил, но как ты собираешься выделять уникальные элементы до сортировки?
Ш>Поделись рецептиком!

Вот так, а что?

(distinct [2 2 1 5 4 4 4 ])
=>; (2 1 5 4)

В функциональных языках ты можешь работать с ленивыми последовательностями, что, кстати и для ranges::views справедливо как минимум по утверждению автора библиотеки. Как ты иначе предлагаешь лениво получать уникальные значения из бесконечного списка или вывод какого-либо генератора фильтровать? На мой взгляд текущая реализация ranges::views::unique не корректна, так как она вводит в заблуждение тем, что находится в views которые как бы ленивые. Судя по реализации этого вида просто не должно быть, а должно быть только действие ranges::actions::sort.

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

KP>>Только вот в мире за пределами C++ такие вопросы как ты задаешь вообще никого не парят, по вполне себе очевидным причинам — будет тормозить так поправим, главное явной квадратичной и выше сложности не городить.
O>В мире за пределами С++ есть например юниксовые команды sort и uniq которые должны рабать именно так: sort|uniq и еще comm которая тоже после sort применяется. Так что это как бы немного очевидно.

А почему реализация функционального концепта в языке программирования должна равняться на Юникс-утилиты, а не, к примеру, на коммерческие функциональные языки?

Clojure:

(distinct [2 2 1 5 4 4 4 ])
=> (2 1 5 4)

(-> [2 2 1 5 4 4 4 ]
    distinct
    sort)
=> (1 2 4 5)

Elixir:

iex(5)> [2, 2, 1, 5, 4, 4, 4] |> Enum.uniq
[2, 1, 5, 4]
iex(6)> [2, 2, 1, 5, 4, 4, 4] |> Enum.uniq |> Enum.sort
[1, 2, 4, 5]

Функциональные концепции в языке должны базироваться на подходах принятых в функциональных языках, по причинам, которые я вот тут объяснял.

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

KP>На мой взгляд текущая реализация ranges::views::unique не корректна, так как она вводит в заблуждение тем, что находится в views которые как бы ленивые. Судя по реализации этого вида просто не должно быть, а должно быть только действие ranges::actions::sort.

Так она и ленивая, просто ranges::views::unique обертка вокруг O(n) std::unique ( https://en.cppreference.com/w/cpp/algorithm/unique ) со всеми вытекающими отсюда последствиями.

Тем более в c++ какая идеология? Не платить за то, что не используешь, а в clojure я практически уверен будет оверхед на выполнение distinct для УЖЕ отсортированное последовательности.

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

V>Так она и ленивая, просто ranges::views::unique обертка вокруг O(n) std::unique ( https://en.cppreference.com/w/cpp/algorithm/unique ) со всеми вытекающими отсюда последствиями.

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

V>Тем более в c++ какая идеология? Не платить за то, что не используешь, а в clojure я практически уверен будет оверхед на выполнение distinct для УЖЕ отсортированное последовательности.

Основная идеология C++ — максимально задолбаться заучивая 100500 правил и изобрести 100500+1 велосипед для своего "уникального случая"

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

KP>В последние годы комитет пытается угодить всем, вот и за функциональный стиль плотно взялись, на что нам range-v3 как бы и намекает.

Это не попытка "угодить всем", а вполне логичный шаг по стандартизации давно существующей и успешно применяемой практики Boost.Range

Range'и как концепция отлично дополняют итераторы, и существуют в других языках типа D.

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

R>>Эрик Ниблер (вот тут) говорит, что views::unique работает только с последовательными элементами.
R>>

R>>views::unique
R>>Given a range, return a new range where all consecutive elements that compare equal save the first have been filtered out.

KP>Ага, нашел уже.

В этом нет ничего удивительного, учитывая поведение std::unique из ISO C++ прошлого века.
Такой вариант вполне логичный и оправданный — во-первых это более общо, во-вторых позволяет не делать лишнюю работу. Например таким же образом работает uniq(1) (тоже из прошлого века).

От:	kaa.python	РСДН профессионально мёртв и завален ватой.
Дата:	25.07.20 04:11
Оценка:	2 (1)

	От:	foxafox
	Дата:	25.07.20 04:37
	Оценка:	18 (1) +1

От:	kaa.python	РСДН профессионально мёртв и завален ватой.
Дата:	25.07.20 04:45
Оценка:

	От:	Reset
	Дата:	25.07.20 04:49
	Оценка:	18 (1)

От:	kaa.python	РСДН профессионально мёртв и завален ватой.
Дата:	25.07.20 04:53
Оценка:

От:	Nuzhny	https://github.com/Nuzhny007
Дата:	25.07.20 09:49
Оценка:	+1

	От:	Evgeny.Panasyuk
	Дата:	26.07.20 09:26
	Оценка:	-1