Здравствуйте, kaa.python, Вы писали:
KP>А почему нел6взять unique из views?
Все, что во views, создает обертку, содержащую ссылку на переданный аргумент, а все что в actions, меняет контейнер и передает его дальше. Так как to_vector возвращает новый объект, то views::unique к нему не применить, иначе получим висящую ссылку.
Здравствуйте, Nuzhny, Вы писали:
KP>>Сложность у решения на range будет, я полагаю что n log n за счет сортировки, ну и в целом будут еще какие-то немаленькие коэффиценты, да и банальные пенальти за память из за перетасовки данных. N>Сложность будет выше, т.к. надо будет удалять дубликаты,
std::unique делает один линейный проход с тривиальными перемещениями.
N>в std::vector это ооочень не бесплатно.
KP>Только вот в мире за пределами C++ такие вопросы как ты задаешь вообще никого не парят, по вполне себе очевидным причинам — будет тормозить так поправим, главное явной квадратичной и выше сложности не городить.
В мире за пределами С++ есть например юниксовые команды sort и uniq которые должны рабать именно так: sort|uniq и еще comm которая тоже после sort применяется. Так что это как бы немного очевидно.
Как много веселых ребят, и все делают велосипед...
В последние годы комитет пытается угодить всем, вот и за функциональный стиль плотно взялись, на что нам range-v3 как бы и намекает. Я тут решил попробовать написать с использованием этой библиотеки простой тестик, пока что по ощущениям выходит что нахер это надо, утомительно ребусы компилятора разгадывать пытаясь угодать что же пошло не так. Но может кто знает как заставить эту штуку работать?
Хочу совсем простого, есть массив массивов, его надо объеденит в один, выкинуть дубликаты, отсортировать, и взять 3 минимамльных элемента. Само собой всё надо сделать максимально приближено к функциональному стилю.
Хочу простого, для иллюстрации пример на Clojure, где такое можно сделать красиво и элегантно:
Здравствуйте, kaa.python, Вы писали:
KP>Но хочется без разбиения на 2 этапа и, конечно же, без дубликатов
Меня пугают все эти штуки в том плане, что непонятно, с какой сложностью окажется решение. В итоге ты получаешь 3 минимальных элемента, это можно сделать императивно за N log3, то есть тупо за один проход. У тебя же там много всяких действий только для развлечения или без них не получится найти 3 минимума? Как вычислить сложность полученного решения в таком функиональном стиле?
Здравствуйте, ononim, Вы писали:
KP>>Только вот в мире за пределами C++ такие вопросы как ты задаешь вообще никого не парят, по вполне себе очевидным причинам — будет тормозить так поправим, главное явной квадратичной и выше сложности не городить. O>В мире за пределами С++ есть например юниксовые команды sort и uniq которые должны рабать именно так: sort|uniq и еще comm которая тоже после sort применяется. Так что это как бы немного очевидно.
А почему реализация функционального концепта в языке программирования должна равняться на Юникс-утилиты, а не, к примеру, на коммерческие функциональные языки?
Здравствуйте, 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) (тоже из прошлого века).
Здравствуйте, 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++, то надо терпеть и запоминать
Здравствуйте, Nuzhny, Вы писали:
N>Меня пугают все эти штуки в том плане, что непонятно, с какой сложностью окажется решение. В итоге ты получаешь 3 минимальных элемента, это можно сделать императивно за N log3, то есть тупо за один проход. У тебя же там много всяких действий только для развлечения или без них не получится найти 3 минимума? Как вычислить сложность полученного решения в таком функиональном стиле?
Это довольно интересный и в чем-то философский вопрос. Начнем с того, что у меня нет цели сделать быстрое решение. У меня есть цель попробовать разные новые фичи C++, который я, мало того что уже изрядно подзабыл, так еще новых вещей и не трогал вообще. Так же хочтеся написать красиво и читабельно, в функциональном стиле. Что проще читать — функциональный или императивный код, это отдельный вопрос, конечно, но C++ как ни крути читабельностью похвастаться сам по себе не может, но функциональный налет может эту ситуацию немного скрасить.
Сложность у решения на range будет, я полагаю что n log n за счет сортировки, ну и в целом будут еще какие-то немаленькие коэффиценты, да и банальные пенальти за память из за перетасовки данных.
Только вот в мире за пределами C++ такие вопросы как ты задаешь вообще никого не парят, по вполне себе очевидным причинам — будет тормозить так поправим, главное явной квадратичной и выше сложности не городить. К примеру я сейчас написал себе transpose для C++ который у меня вышел как-то так:
Но если бы этот самый 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. И если что-то будет тормозить, то придётся не разбираться, а тупо переписывать. Мне стрёмно, когда я не могу посмотреть в отладчике какой-то код или вставить в него логи.
Здравствуйте, Шахтер, Вы писали:
Ш>А вот не надо на С++ писать как на 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.
Здравствуйте, kaa.python, Вы писали:
KP>На мой взгляд текущая реализация ranges::views::unique не корректна, так как она вводит в заблуждение тем, что находится в views которые как бы ленивые. Судя по реализации этого вида просто не должно быть, а должно быть только действие ranges::actions::sort.
Тем более в c++ какая идеология? Не платить за то, что не используешь, а в clojure я практически уверен будет оверхед на выполнение distinct для УЖЕ отсортированное последовательности.
Здравствуйте, Evgeny.Panasyuk, Вы писали:
EP>Это не попытка "угодить всем", а вполне логичный шаг по стандартизации давно существующей и успешно применяемой практики Boost.Range EP>Range'и как концепция отлично дополняют итераторы, и существуют в других языках типа D.
Здравствуйте, Evgeny.Panasyuk, Вы писали:
EP>В этом нет ничего удивительного, учитывая поведение std::unique из ISO C++ прошлого века. EP>Такой вариант вполне логичный и оправданный — во-первых это более общо, во-вторых позволяет не делать лишнюю работу. Например таким же образом работает uniq(1) (тоже из прошлого века).
Извини, я сориентироваться хочу. Ты принципиально не читаешь ответы в теме, а пишешь свой для начала?
Здравствуйте, kaa.python, Вы писали:
KP>А почему реализация функционального концепта в языке программирования должна равняться на Юникс-утилиты
Ну она базируется на std::unique из C++1998. Но, даже если не знать про std::unique, а только про uniq — то существование такого интерфейса (отличного от distinct) должно натолкнуть на мысль таки заглянуть в документацию, и прочитать что именно делает используемая команда, а не строить догадки. В то что ты не знал ни про uniq, ни про std::unique — верится с трудом
KP>, а не, к примеру, на коммерческие функциональные языки?
Что ты называешь "коммерческими", какие преимущества аргументации эта "коммерческость" даёт по сравнению со стандартизированной uniq?
KP>(distinct [2 2 1 5 4 4 4 ]) KP>=> (2 1 5 4)
Это странный пример в обсуждаемом контексте, так как unique/uniq выдаст такой же результат
KP>Функциональные концепции в языке должны базироваться на подходах принятых в функциональных языках, по причинам, которые я вот тут объяснял
Ну вот если бы стоял выбор между интерфейсами uniq и distinct для Range'ей, то я бы выбрал uniq.
Во-первых, это более общо — например нужно удалить именно последовательные дубликаты, а не все.
Во-вторых, быстрее если данные уже в нужном порядке.
Тем не менее, и у интерфейса distinct тоже есть преемущества, так что в идеале нужны оба.
Здравствуйте, Evgeny.Panasyuk, Вы писали:
EP>Ну она базируется на std::unique из C++1998.
Это прекрасно, как сочетается std::unique и заявленная ленивость?
EP> Но, даже если не знать про std::unique, а только про uniq — то существование такого интерфейса (отличного от distinct) должно натолкнуть на мысль таки заглянуть в документацию, и прочитать что именно делает используемая команда, а не строить догадки. В то что ты не знал ни про uniq, ни про std::unique — верится с трудом
Везде разные имена, где-то distinct, где-то uniq, как в моем примере с Clojure и Elixir
EP>Что ты называешь "коммерческими", какие преимущества аргументации эта "коммерческость" даёт по сравнению со стандартизированной uniq?
Довольно очевидное — это некий устаявшийся паттерн поведения, который могу ожидать люди имевшие опыт с инструментом. Но, знаю-знаю, это не C++-путь, у нас надо изобрести свой правильный велосипед с квадратными колесами.
KP>>(distinct [2 2 1 5 4 4 4 ]) KP>>=> (2 1 5 4)
EP>Это странный пример в обсуждаемом контексте, так как unique/uniq выдаст такой же результат
N>Ну, это и правда больше упражнение, благо для матриц сейчас библиотек достаточно и вряд ли кто-то решит писать сам. А необходимость поиска нескольких минимальных/максимальных элементов иногда встречается, реализации из коробки нет, вот и приходится самому думать. Что предлагают делать разработчики на Питоне? Сортировать! На втором месте уже np.argpartition, про который говорят, что он сработает за линейное время, что неверно в общем случае. И только где-то там самый быстрый алгоритм — heapq.nlargest. Хотя именно с кучей можно быстрее всего найти k-top элементов. Не хочется, чтобы С++ уходил в эту же сторону, краткость не решает.
Не читай советских газет перед обедом (с)
def kth(a, n):
m = a.shape[0]
perc = (np.arange(m-n,m)+1.0)/m*100
return np.percentile(a, perc)
N>Да, у меня есть проф деформация и я не очень люблю Питон из-за этого. Иногда кажется, что программирование на нём сродни программированию на Делфи: "А какой компонет может сделать ххх?" Только в Питоне слово "компонет" заменяется на "пакет". (Это конечно снобизм, я на нём сам такой же и с удовольствием пишу говноутилиты для парсинга и перекладывания разных штук, не выходя за рамки стантартных пакетов.) N>Но глобально, я не понимаю, что стоит за вывеской питоновских import xxx, ни тут, за вывеской ranges. И если что-то будет тормозить, то придётся не разбираться, а тупо переписывать. Мне стрёмно, когда я не могу посмотреть в отладчике какой-то код или вставить в него логи.
Здравствуйте, kaa.python, Вы писали:
EP>>Ну она базируется на std::unique из C++1998. KP>Это прекрасно, как сочетается std::unique и заявленная ленивость?
А что смущает? Например имя/интерфейс views::transform базируется на std::transform — одно ленивое, другое энергичное
KP>Везде разные имена, где-то distinct, где-то uniq, как в моем примере с Clojure и Elixir
Суть не в именах, а в том что в природе встречается и тот и другой интерфейс.
EP>>Что ты называешь "коммерческими", какие преимущества аргументации эта "коммерческость" даёт по сравнению со стандартизированной uniq? KP>Довольно очевидное — это некий устаявшийся паттерн поведения, который могу ожидать люди имевшие опыт с инструментом. Но, знаю-знаю, это не C++-путь, у нас надо изобрести свой правильный велосипед с квадратными колесами.
Аллё гараж, какой ещё C++-путь, интерфейсу uniq(1) много десятков лет, он к тому же стандартизирован в POSIX.