Здравствуйте, Piko, Вы писали:
P>Здравствуйте, minorlogic, Вы писали:
M>>Зачем мне ?
P>действительно, зачем тебе. Люди и на "газели" деньги зарабатывают
Если тебе интересно ты и пробуй.
... << RSDN@Home 1.2.0 alpha 5 rev. 1539>>
Ищу работу, 3D, SLAM, computer graphics/vision.
Re[2]: std::sort не работает на бидирекшен итераторах
Здравствуйте, sdf, Вы писали:
M>>Зачем изначально было делать std::sort на RandomAccessIterator? M>>Во первых всегда можно разделить имплементации для рандом и бидирекшен. sdf>Вроде бы основная проблема была в том, что разделить имплементацию для рандом и бидерекшен во время включения в стандарт STL, было нетривиально. sdf>Концептов в С++ нет до сих пор, а SFINAE тогде вроде еще не было.
Здравствуйте, sdf, Вы писали:
sdf>Здравствуйте, minorlogic, Вы писали:
sdf>Так же, как RandomAccess и без изменения асимптотики, его выбирать нельзя, т.к. для RandomAccess поиск серединного элемента занимает O(1), а для bidirectional чтобы получить средний элемент вам нужно будеть сделать O(длины участка/2) вызовов ++
Хотя, верно, все равно потом делается прохол по всему участку. Будет медленнее. но асмтотика останется той же. Вопрос закрыт.
Re: std::sort не работает на бидирекшен итераторах
Здравствуйте, minorlogic, Вы писали:
M>Собственно идеологический вопрос.
... M>Это меня одного озадачивает ?
согласен, не симметрично. можно запилить запрос в https://groups.google.com/a/isocpp.org/forum/?fromgroups#!forum/lib-proposals (главное сыроежку туда не пускать).
может быть сочли редко-используемым, может было мало времени и просмотрели(stl вообще предложили на очень позднем этапе стандартизации), может ещё что.
примечательно что на MSVC10 std::stable_sort работает с std::list
Re[2]: std::sort не работает на бидирекшен итераторах
Здравствуйте, minorlogic, Вы писали:
M>Здравствуйте, sdf, Вы писали:
sdf>>ORLY? И как выбирать pivor element, используя median three, если нет RandomAccess?
M>Например так же как и для RandomAccess. Асимптотику это не изменит.
ORLY?
Так же, как RandomAccess и без изменения асимптотики, его выбирать нельзя, т.к. для RandomAccess поиск серединного элемента занимает O(1), а для bidirectional чтобы получить средний элемент вам нужно будеть сделать O(длины участка/2) вызовов ++
Re: std::sort не работает на бидирекшен итераторах
Зачем изначально было делать std::sort на RandomAccessIterator?
Во первых всегда можно разделить имплементации для рандом и бидирекшен.
Во вторых обычно используемый introsort отлично работает с обьеими видами итераторов.
И наоборот std::lower_bound эффективно работать может только с RandomAccessIterator но принимает Forward.
Это меня одного озадачивает ?
... << RSDN@Home 1.2.0 alpha 5 rev. 1539>>
Ищу работу, 3D, SLAM, computer graphics/vision.
Re[2]: std::sort не работает на бидирекшен итераторах
кстати, может они планирует сделать это в контексте концепций. То есть не будут тратить время на формальный proposal пока нет концепций. Так как с ними определение будет по-другому выглядеть.
Re: std::sort не работает на бидирекшен итераторах
Здравствуйте, minorlogic, Вы писали:
M>Собственно идеологический вопрос.
M>Зачем изначально было делать std::sort на RandomAccessIterator?
M>Во первых всегда можно разделить имплементации для рандом и бидирекшен. M>Во вторых обычно используемый introsort отлично работает с обьеими видами итераторов.
ORLY? И как выбирать pivor element, используя median three, если нет RandomAccess?
Re: std::sort не работает на бидирекшен итераторах
Здравствуйте, minorlogic, Вы писали:
M>Собственно идеологический вопрос.
M>Зачем изначально было делать std::sort на RandomAccessIterator?
M>Во первых всегда можно разделить имплементации для рандом и бидирекшен.
Вроде бы основная проблема была в том, что разделить имплементацию для рандом и бидерекшен во время включения в стандарт STL, было нетривиально.
Концептов в С++ нет до сих пор, а SFINAE тогде вроде еще не было.
Re[2]: std::sort не работает на бидирекшен итераторах
Здравствуйте, sdf, Вы писали:
sdf>Вроде бы основная проблема была в том, что разделить имплементацию для рандом и бидерекшен во время включения в стандарт STL, было нетривиально.
Дык и обобщенную можно собрать без накладных расходов.
... << RSDN@Home 1.2.0 alpha 5 rev. 1539>>
Ищу работу, 3D, SLAM, computer graphics/vision.
Re[4]: std::sort не работает на бидирекшен итераторах
Piko:
P>кстати, может они планирует сделать это в контексте концепций.
Насколько я помню, первый стандарт с Concepts планировали выпустить примерно в 2022 году. Тем, кому хочется иметь дело с этой фичей, осталось подождать совсем чуть-чуть
Re[5]: std::sort не работает на бидирекшен итераторах
Здравствуйте, Masterkent, Вы писали:
P>>кстати, может они планирует сделать это в контексте концепций. M>Насколько я помню, первый стандарт с Concepts планировали выпустить примерно в 2022 году. Тем, кому хочется иметь дело с этой фичей, осталось подождать совсем чуть-чуть
а когда следующий?
по мне так то лучше дольше и надёжней.
по поводу концепций — я больше всего жду аксиомы.
Re[2]: std::sort не работает на бидирекшен итераторах
Здравствуйте, minorlogic, Вы писали:
M>Забавное наблюдение. Наколеночная qsort обогнала MSVC2010 реализацию std::list<>.sort на случайных данных , раза в 2ва
2. ISO, list sort:
"Effects: Sorts the list according to the operator< or the comp function object. This operation shall be
stable: the relative order of the equivalent elements is preserved. If an exception is thrown the order
of the elements in *this is unspecified. Does not affect the validity of iterators and references.
23 Complexity: Approximately N logN comparisons, where N is distance(begin(), end())."
Стабильность + Сложность(даже не сложность, а количество сравнений). А что у тебя?
Re[4]: std::sort не работает на бидирекшен итераторах
Здравствуйте, minorlogic, Вы писали:
P>>1. попробуй отсортировать последовательность {N, N-1, N-2, N-3, N-4 ...} M>Зачем мне ?
ну ты же говоришь, что типа у тебя быстрее в два раза.
Сравни на этих данных
P>>Стабильность + Сложность(даже не сложность, а количество сравнений). А что у тебя? M>Написал же, "наколеночный qsort"
Здравствуйте, minorlogic, Вы писали:
P>>ну ты же говоришь, что типа у тебя быстрее в два раза. P>>Сравни на этих данных M>Я написал же, что на случайных данных, внимательно читай.
list.sort обладает свойством стабильности + его сложность всегда O(NlogN).
В твоём же варианте стабильности нет. И сложность может взрываться в самый неподходящий момент, на самом не подходящем N, до O(N^2).
Ну ещё хинт.
Сравни std::sort и std::stable_sort.
В чём вообще смысл? Что ты хотел показать своим сравнением? То что qsort может обгонять стабильную сортировку с O(NlogN) сложностью? Ну и?
Re[8]: std::sort не работает на бидирекшен итераторах
Здравствуйте, minorlogic, Вы писали:
P>>1. попробуй отсортировать последовательность {N, N-1, N-2, N-3, N-4 ...} M>Зачем мне ?
Практика показывает, что значительно более типичный, чем полностью случайные, шаблон входных данных сортировки это кусочно-упорядочённый массив из отдельных не сильно длинных отрезков. (Например, это было обоснованием метода TimSort.) Если сортировка сильно страдает на упорядочённых данных, то она пострадает и на таких, следовательно, её практическая ценность резко ниже.
P>>Стабильность + Сложность(даже не сложность, а количество сравнений). А что у тебя? M>Написал же, "наколеночный qsort"
Надеюсь, разделяющий элемент таки выбирается случайно?
The God is real, unless declared integer.
Re[5]: std::sort не работает на бидирекшен итераторах
Здравствуйте, netch80, Вы писали:
N>Практика показывает, что значительно более типичный, чем полностью случайные, шаблон входных данных сортировки это кусочно-упорядочённый массив из отдельных не сильно длинных отрезков. (Например, это было обоснованием метода TimSort.) Если сортировка сильно страдает на упорядочённых данных, то она пострадает и на таких, следовательно, её практическая ценность резко ниже.
Я рад что так много людей осваивает базовые понятия об алгоритмах, но мне совершенно это не интересно. Если сможете добавить что то в ветку про inplace radix sort, там я с удовольствием почитаю.
P>>>Стабильность + Сложность(даже не сложность, а количество сравнений). А что у тебя? M>>Написал же, "наколеночный qsort"
N>Надеюсь, разделяющий элемент таки выбирается случайно?
Я же код привел.
... << RSDN@Home 1.2.0 alpha 5 rev. 1539>>
Ищу работу, 3D, SLAM, computer graphics/vision.
Re[6]: std::sort не работает на бидирекшен итераторах
Здравствуйте, minorlogic, Вы писали:
M>Я рад что так много людей осваивает базовые понятия об алгоритмах, но мне совершенно это не интересно.
Данную фразу я что-то не понял. Непонятно, что именно не интересно — базовые понятия или то, что их кто-то осваивает С другой стороны, если базовые понятия не учитывать, то и в глубинные можно не лезть. Некоторые особенности вашего спора показывают как минимум проблемы с восприятием друг другом общих понятий у другого.
M>Я же код привел.
Я не понял, что речь именно об этом коде. Сбило с толку то, что собеседник привёл в качестве контрпримера просто обратно упорядочённую последовательность. Если выбирается серединный элемент (насколько я понял этот код), то его контрпример неактуален.
А вообще, то что у Вас получилось, это не классический qsort, а его гибрид с интервальной обменной (ван Эмдена).
M>Про TimSort, посмотрите на сообщение и дату тут http://rsdn.ru/forum/alg/683817.1
Посмотрел. Согласно википедии Timsort был показан миру в 2002. Если идеей было показать определённый порядок дат, то боюсь, что немного не сложилось. Но в общем понятно, что идеи Вам знакомы. Тогда остаётся, что такая... мнэээ... однобокая реакция на того собеседника — больше вызвана стилем подачи и чистыми эмоциями. Тогда вопросов больше нет.
The God is real, unless declared integer.
Re[7]: std::sort не работает на бидирекшен итераторах
Здравствуйте, netch80, Вы писали:
N>Здравствуйте, minorlogic, Вы писали:
M>>Я рад что так много людей осваивает базовые понятия об алгоритмах, но мне совершенно это не интересно.
N>Данную фразу я что-то не понял. Непонятно, что именно не интересно — базовые понятия или то, что их кто-то осваивает
Второе.
N>Посмотрел. Согласно википедии Timsort был показан миру в 2002. Если идеей было показать определённый порядок дат, то боюсь, что немного не сложилось.
Сама идея совсем не нова и есть решения почище и поизящнее. Мне немгого странно почему многие носятся с Timsort, который к тому же и требует дополнительной памяти в оригинальной имплементации .
N> Но в общем понятно, что идеи Вам знакомы. Тогда остаётся, что такая... мнэээ... однобокая реакция на того собеседника — больше вызвана стилем подачи и чистыми эмоциями. Тогда вопросов больше нет.
Ветка же с С++ про STL , а не " я открыл первый раз книжку по сортировкам и столько узнал!"
... << RSDN@Home 1.2.0 alpha 5 rev. 1539>>
Ищу работу, 3D, SLAM, computer graphics/vision.
Re[5]: std::sort не работает на бидирекшен итераторах
Здравствуйте, Masterkent, Вы писали:
M>Piko:
P>>кстати, может они планирует сделать это в контексте концепций.
M>Насколько я помню, первый стандарт с Concepts планировали выпустить примерно в 2022 году. Тем, кому хочется иметь дело с этой фичей, осталось подождать совсем чуть-чуть
Сдаётся мне что я свой С++ компилятор с этой фичей напишу раньше.
Здравствуйте, minorlogic, Вы писали:
M>Сама идея совсем не нова и есть решения почище и поизящнее. Мне немгого странно почему многие носятся с Timsort,
Ну, наверно, его ведь не просто так перетащили в несколько существенно разных применений? Наверно, по совокупности параметров он оказался лучше альтернатив. А сейчас стал образцом для равнения именно по этой причине.
M> который к тому же и требует дополнительной памяти в оригинальной имплементации .
Для требования стабильности дополнительная память резко повышает скорость и не является чрезмерной ценой. Проблема именно в смысле этого требования (стабильности), а также в том, что большинство контейнерных библиотек дают 1 алгоритм, максимум 2, считая, что ими адекватно покрываются все случаи.
M>Ветка же с С++ про STL , а не " я открыл первый раз книжку по сортировкам и столько узнал!"
Я бы в Вашей ситуации скорее сказал что-то вроде "на этих данных проблем нет, смотрите внимательнее"...
А Ваша реализация, если не путаю, таки страдает на специально подготовленных данных (когда средний элемент отрезка даёт крайнее из значений его элементов), вырождаясь в O(N**2). Уже известны случаи DoS подачей таких данных. Подозреваю, что собеседник пытался что-то такое вычислить, но не смог адекватно подобрать пример.
The God is real, unless declared integer.
Re[9]: std::sort не работает на бидирекшен итераторах
Здравствуйте, netch80, Вы писали:
N>А Ваша реализация, если не путаю, таки страдает на специально подготовленных данных (когда средний элемент отрезка даёт крайнее из значений его элементов), вырождаясь в O(N**2). Уже известны случаи DoS подачей таких данных. Подозреваю, что собеседник пытался что-то такое вычислить, но не смог адекватно подобрать пример.
Эта тема хорошо описана в литературе и к топику не имеет отношения. Недостатки интросорта и т.п. никак не могут служить аргументом к невозможности сортировать на бидирекшн итераторах.
... << RSDN@Home 1.2.0 alpha 5 rev. 1539>>
Ищу работу, 3D, SLAM, computer graphics/vision.
Re: std::sort не работает на бидирекшен итераторах
Здравствуйте, minorlogic, Вы писали:
M>Во первых всегда можно разделить имплементации для рандом и бидирекшен.
Можно и forward.
M>Во вторых обычно используемый introsort отлично работает с обьеими видами итераторов.
Неверно. Так как структура heap'а неявно закодирована в массиве, и на каждой операции нужно прыгать по нему, то операции (а-ля std::pop_heap) вырождаются с O(ln(N)) до O(N), а сортировка с O(N*ln(N)) до O(N^2).