поэтому я предлагаю аутпут бенчей в обмен на исходники бенчей :)

лол

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

не помню, мб даже на cpp-sort есть этот бенч

ну, в моей текущей вселенной timsort это сам по себе мартышкин труд :)

ну, в моей текущей вселенной timsort это сам по себе мартышкин труд :)

я не понимаю, почему ты не хочешь просто взять и почитать, почему эта сортировка хороша и в каких случаях

но это уже дело твоё.

потому что я много разной информации в гугле читал, и по статистике 90% авторов этой инфы попросту не разбираются, что пишут

это безумно заметно, когда начинаешь читать инфу по темам, в которых реально разобрался

это безумно заметно, когда начинаешь читать инфу по темам, в которых реально разобрался

Согласен, есть такая проблема. Но у неё есть идеальное решение - просто берёшь и читаешь исходную научную работу

и вот что-то мне лично ни разу не попадались бестолковые бумаги

Согласен, есть такая проблема. Но у неё есть идеальное решение - просто берёшь и читаешь исходную научную работу

Ага, тут недавно инфа была

https://arxiv.org/pdf/1705.11035.pdf

http://playfulprogramming.blogspot.com.by/2017/06/constexpr-quicksort-in-c17.html

тестом размером 9 опровергли работу D. P. Dobkin, L. Snyder, 1979

тестом размером 9 опровергли работу D. P. Dobkin, L. Snyder, 1979

так, а где я утверждал, что в работах нет ошибок?))

просто в практической области оригинальную работу 1993 года читать странно

процессоры по-другому работали)

а всякие статьи "мы тут пореализовывали методы" пишет обычно нубло

а можно пример такой статьи?

http://webcache.googleusercontent.com/search?q=cache:lMk9YY-awqsJ:www.cccg.ca/proceedings/2003/26.ps+&cd=3&hl=en&ct=clnk&gl=ru

не вижу ничего плохого в том, что кто-то что-то реализует, чего ещё нет и что можно скопировать себе в случае необходимости (поправка - карйне желательно, чтобы чуваки писали это верно)

http://webcache.googleusercontent.com/search?q=cache:lMk9YY-awqsJ:www.cccg.ca/proceedings/2003/26.ps+&cd=3&hl=en&ct=clnk&gl=ru

1) нет имплементации - это минус 2) Зато хоть результаты тестов дали - и это уже имеет пользу

1) нет имплементации - это минус 2) Зато хоть результаты тестов дали - и это уже имеет пользу

ага, а еще они не заметили, что D. P. Dobkin, L. Snyder, 1973 содержит ошибку

как отправная точка при выборе алгоритмов - пойдёт. Но безоговорочно я бы полагаться на такую работу наверное не стал бы

хотя метод реализовывали

ага, а еще они не заметили, что D. P. Dobkin, L. Snyder, 1973 содержит ошибку

бывает со всеми

бывает со всеми

или забыли вообще перепроверить все доказательства в работе :)

или забыли вообще перепроверить все доказательства в работе :)

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

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

кстати, а есть специалисты? я слышал краем уха, что структуры типа set<int> реализуемы с log log, что там с константами

кстати, а есть специалисты? я слышал краем уха, что структуры типа set<int> реализуемы с log log, что там с константами

есть штуки подобия деревеьв ван-эмде-боаса

крайне спецефичны, и поэтому как обобщённое решение не подходит

насколько я знаю, красно-чёрное нельяза разогнать до log log

также я не слышал о различных таких модификациях для сплей, АВЛ, декартовых и иных деревьев

там важно, что int, разумеется нельзя разогнать красно-черное

потому что есть порог сортировки n * log n

фигня в том, что если std::sort не устраивает, то timsort это как раз попытка специфичного решения

там важно, что int, разумеется нельзя разогнать красно-черное

поэтому я и сказал тебе про ван-эмде-боаса (у этой штуки есть какое-то более нормальное название, нго я его забыл).

да, я уже нашел его

не успел прочитать

фигня в том, что если std::sort не устраивает, то timsort это как раз попытка специфичного решения

std::sort никто менять не собиарется, и если кто-то попытается заменить имплементацию стандартного сорта на тимсорт, я буду крайне против и топить против этого

но как ещё одна очень хорошая альтернатива. Если ты знаешь, что данные в целом неплохо так сорированы, то почему не воспользоваться гтовым годным алгоритмом уже?

вообще я в свое время изучал вопрос о поведении декартовых (любых подобных merge-based) деревьев на недосортированных массивах... пытаюсь вспомнить судорожно

также я не слышал о различных таких модификациях для сплей, АВЛ, декартовых и иных деревьев

Это теоретически невозможно в общем случае

Да, я это уже сказал)

Это теоретически невозможно в общем случае

а тут у человека не общий случай, в том то и дело

про общий я то знаю

Слава, что ты думаешь о timsort? Ну, кроме того, что из-за него на КФ нельзя яву положить на объектах :D

вообще я в свое время изучал вопрос о поведении декартовых (любых подобных merge-based) деревьев на недосортированных массивах... пытаюсь вспомнить судорожно

Там совершенно точно получалось, что если хранить отрезки в качестве treap, суммарно запросы "посортить подотрезок" и "изменить число" выполняются быстрее квадрата

Слава, что ты думаешь о timsort? Ну, кроме того, что из-за него на КФ нельзя яву положить на объектах :D

Про cf - ну это скорее квиксорт в джаве плохо реализован для примитивных типов, а не преимущество тимсорта

Про cf - ну это скорее квиксорт в джаве плохо реализован для примитивных типов, а не преимущество тимсорта

я с джавами знаком слабо. А в чём причина того, что квиксорт там такой херовый?

я с джавами знаком слабо. А в чём причина того, что квиксорт там такой херовый?

там реализация с квадратом в худшем

по крайней мере, была

там реализация с квадратом в худшем

Да

там реализация с квадратом в худшем

да-да. А почему?

потому что разработчики явы не запарились

я знаю, что там говно акое-то написано (как и в libc++)

поэтому же у них все хеш-коллекции ложатся в худшем

потому что разработчики явы не запарились

что-то мне не не верится, что там прям всем плевать на это

да-да. А почему?

Потому что не хотели вносить недетерминизм, а гарантированные методы выбирать хороший pivot замедляют средний случай

сейчас бы париться по поводу недетерминизма алгоритма сортировки массива

Потому что не хотели вносить недетерминизм, а гарантированные методы выбирать хороший pivot замедляют средний случай

подожди, есть же еще метод просто написать полурекурсивную реализацию и ограничить число шагов

это вообще никак не замедляет средний случай

сейчас бы париться по поводу недетерминизма алгоритма сортировки массива

Java, сэр

ERROR: S client not available

это вообще никак не замедляет средний случай

Константу увеличивает прилично, как я понимаю

https://www.reddit.com/r/programming/comments/4jlkhv/accu_2016_keynote_by_andrei_alexandrescu/

Константу увеличивает прилично, как я понимаю

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

https://www.reddit.com/r/programming/comments/4jlkhv/accu_2016_keynote_by_andrei_alexandrescu/

Александреску вроде что-то придумывал новое

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

А, я понял о чем ты, так можно наверное

Александреску... у меня до сих пор в одном файле написано ` #ifdef ALEXANDRESCU #error "Too easy for Alexanrescu" #endif //копипаста из локи

собственно, там static_assert всякие для C++98

А, я понял о чем ты, так можно наверное

qsort(l, r) //... qsort(l, m); qsort(m+1, r); ==> qsort(l, r) for (iterations++) { //... if (iterations > MAGIC_CONSTANT) { heapsort(l, r); break; } qsort(with minimal length ((l, m), (m+1, r))) (l, r) = with maximal length ((l, m), (m+1, r)) }

magic constant? ?

ну да

вроде там на самом деле current_constant = r - l; и потом current_constant = current_constant / 2 + current_constant/4 в таком духе

вместо расчета итераций

как получается 0 - уходим в хипсорт

А кто название давал?

я просто налобал в поле ввода же

вроде, именно такие схемы во всяких MS std::sort

с кучей ифов еще на маленькие массивы скидываться в INSERTION

Там нужно примерно посчитать, сколько в среднем должно быть итераций такой штуки

Если это число превосходится, инпут специально построен против текущей реализации qsort

Поэтому мы уходим в heapsort

Люди, у меня например есть строка 2 + 2 и мне нужно её сплитнуть. Как это сделать?

Люди, у меня например есть строка 2 + 2 и мне нужно её сплитнуть. Как это сделать?

#supapro

Люди, у меня например есть строка 2 + 2 и мне нужно её сплитнуть. Как это сделать?

Чат supapro.cxx: https://telegram.me/joinchat/BYlFbD3eN3JMaG34hyh96w

Люди, у меня например есть строка 2 + 2 и мне нужно её сплитнуть. Как это сделать?

stringstream

eval

в спп есть евал?

(в спп есть все)

можно и сделать

Люди, у меня например есть строка 2 + 2 и мне нужно её сплитнуть. Как это сделать?

Написать монадический комбинатор парсеров.

Кажется чатик помер давно

А нет, у меня сбилась дата. (Показал январь 3)