Здравствуйте, Evgeny.Panasyuk, Вы писали:
EP> dot>Гы-гы. Как ты сделаешь inplace quicksort хотя бы массива строк разной длины? EP> Полный inplace видимо никак, но будет хотя бы одна индерекция вместо двух.
Понятно. Т.е. quicksort невозможно использовать для сортировки строк. Интересно получается...
EP> dot>dot>А это ты считаешь quicksort-м? EP> dot>
EP> Нет. И даже ортодоксальные ФП'исты это отмечают: Erik Meijer (28:25)
Ты видимо не понял, что он сказал: "This is quicksort expressed in haskell... some people argue that it is really not quicksort... because ...inplace array.... in another hand if you want to understand the algorithm behind quicksort, then this is fabulous description".
Т.е. для понимания самого алгоритма — это то что надо. А inplace, индирекции, эффективный swap — это всё оптимизации — заставить работать некий алгоритм на конкретном железе как можно быстрее.
EP> EP>> EP>>Обычно соответствующий используемому железу. EP> EP>> dot>Железо меняется, да даже и обычный современный комп — там и 32 бита, и 64, EP> EP>> Пусть меняется, суть-то везде примерно одинаковая, и она ниже уровнем чем C.
EP> dot>Для курса обучения желательно использовать что-то что не менятеся. EP> Ну и пусть используют ASM под обычный PC — архитектуры меняются редко, не говоря уж о том что старый x32 код работает на x64 процессорах.
Можно, конечно. Но на асме сейчас вообще никто не пишет.
EP> dot>С++ это уже такая свалка всего, что за деревьями леса не видно. EP> Поэтому и нужно выбрать правильное подмножество для начального обучения, об этом собственно и топик. EP> dot>Например. В С пишем "a = b" — это просто mov в железе. А в С++ может быть что угодно. EP> 1. И что? Некоторые начинают начальное обучение вообще с Python — там ещё дальше от железа.
Потому что питон — проще чем С++, С проще чем С++. Для обучения С++ — хуже. Чем меньше уделять приходится уделять внимание деталям языка — тем лучше.
Скажем, для реализации quicksort совершенно неважно сколько индирекций, что использовать — ссылки, указатели или значения, и т.п.
EP> 2. В C++ для регулярных типов, с которых начинается обучение, "a = b" как раз и имеет вполне предсказуемое поведение, например что для int'ов, что для std::vector. Я бы сказал даже самое предсказуемое среди всего мейнстрима, так как value semantics и там и там.
Зато далеко от железа.
Здравствуйте, ·, Вы писали:
EP>> dot>Гы-гы. Как ты сделаешь inplace quicksort хотя бы массива строк разной длины? EP>> Полный inplace видимо никак, но будет хотя бы одна индерекция вместо двух. dot>Понятно. Т.е. quicksort невозможно использовать для сортировки строк. Интересно получается...
Использовать нечто похожее можно, здесь вопрос чисто терминологический.
EP>> dot>dot>А это ты считаешь quicksort-м? EP>> dot>
EP>> Нет. И даже ортодоксальные ФП'исты это отмечают: Erik Meijer (28:25) dot>Ты видимо не понял, что он сказал:
Я прекрасно понял.
dot>"This is quicksort expressed in haskell... some people argue that it is really not quicksort... because ...inplace array....
Там ключевое "an essense of quicksort". То есть "сущность quicksort".
dot> in another hand if you want to understand the algorithm behind quicksort, then this is fabulous description". dot>Т.е. для понимания самого алгоритма — это то что надо.
Для понимая другого алгоритма. Оригинальный quicksort помимо inplace ещё и ограничивает глубину стэка логарифмом.
dot>А inplace, индирекции, эффективный swap — это всё оптимизации — заставить работать некий алгоритм на конкретном железе как можно быстрее.
А алгоритмы пишутся в том числе для конкретного железа. inplace у quicksort был с самого рождения, и в качестве преимуществ как раз описывается скорость на многоуровневой системе памяти. Что и сейчас актуально, также как и пятьдесят лет назад.
EP>> dot>С++ это уже такая свалка всего, что за деревьями леса не видно. EP>> Поэтому и нужно выбрать правильное подмножество для начального обучения, об этом собственно и топик. EP>> dot>Например. В С пишем "a = b" — это просто mov в железе. А в С++ может быть что угодно. EP>> 1. И что? Некоторые начинают начальное обучение вообще с Python — там ещё дальше от железа. dot>Потому что питон — проще чем С++, С проще чем С++.
Начальное подмножество C сложнее правильного (сабж) начального подмножества C++.
dot>Для обучения С++ — хуже. Чем меньше уделять приходится уделять внимание деталям языка — тем лучше.
Так на C++ на начальном этапе меньше всяких отвлечений. Взял vector, и заполняй как хочешь. В то время как на C будет куча лишнего кода.
EP>> 2. В C++ для регулярных типов, с которых начинается обучение, "a = b" как раз и имеет вполне предсказуемое поведение, например что для int'ов, что для std::vector. Я бы сказал даже самое предсказуемое среди всего мейнстрима, так как value semantics и там и там. dot>Зато далеко от железа.
Здравствуйте, Evgeny.Panasyuk, Вы писали:
EP>1. И что? Некоторые начинают начальное обучение вообще с Python — там ещё дальше от железа.
Не любое обучение ЯП есть обучение программированию. Питон используется для обучению программирования с нуля, что бы оставить самый минимум. Вот система типов здесь уже совершенно лишняя.
EP>2. В C++ для регулярных типов, с которых начинается обучение, "a = b" как раз и имеет вполне предсказуемое поведение, например что для int'ов, что для std::vector. Я бы сказал даже самое предсказуемое среди всего мейнстрима, так как value semantics и там и там.
Да, нынче люди уже рождаются со встроеным пониманием stl и разных контейнеров.
Re[9]: [C++] CppCon 2015: Kate Gregory “Stop Teaching C"
Здравствуйте, Ops, Вы писали:
I>>А вот идиомой в Си будет класс, наследование, полиморфизм и тд. Тот же полиморфизм реализовывается в частном случае через void*.
Ops>Я это и имел в виду. И как тебе такой полиморфизм, полезнее для ног, нежели в плюсах?
Для обучения — полезнее. Ровно самый минимум. На таких примерах и надо показывать, где какие проблемы, откуда берутся, как решаются.
В противном случае вырастает поколение `std::vector это правильно, потому что нам так сказали`
Re[10]: [C++] CppCon 2015: Kate Gregory “Stop Teaching C"
Здравствуйте, ·, Вы писали:
·>А что, string разве inplace?
Я не распарсил фразу. Поясни, что ты имеешь в виду. Ты хочешь, чтобы сорт переставлял буковки строк, не меняя указатели на буферы? На кой хрен это надо?
Re[11]: [C++] CppCon 2015: Kate Gregory “Stop Teaching C"
Здравствуйте, Evgeny.Panasyuk, Вы писали:
EP>>> dot>Гы-гы. Как ты сделаешь inplace quicksort хотя бы массива строк разной длины? EP>>> Полный inplace видимо никак, но будет хотя бы одна индерекция вместо двух. dot>>Понятно. Т.е. quicksort невозможно использовать для сортировки строк. Интересно получается... EP>Использовать нечто похожее можно, здесь вопрос чисто терминологический.
И как это нечто похожее будет называться? Almost, but not quite, entirely unlike quicksort.
dot>>"This is quicksort expressed in haskell... some people argue that it is really not quicksort... because ...inplace array.... EP>Там ключевое "an essense of quicksort". То есть "сущность quicksort".
Да, т.е. собственно сам алгоритм quicksort, его сущность, а не детали реализации — inplace, indirection, swap, указатели, менеджмент памяти, ассемблеры и прочая левость к quicksort отношения не имеющая.
dot>> in another hand if you want to understand the algorithm behind quicksort, then this is fabulous description". dot>>Т.е. для понимания самого алгоритма — это то что надо. EP>Для понимая другого алгоритма. Оригинальный quicksort помимо inplace ещё и ограничивает глубину стэка логарифмом.
Эта хаскелловая имплементация тоже ограничивает, выбор pivot point будет лишь влиять на то, что будет считаться worst case для данной имплементации алгоритма.
dot>>А inplace, индирекции, эффективный swap — это всё оптимизации — заставить работать некий алгоритм на конкретном железе как можно быстрее. EP>А алгоритмы пишутся в том числе для конкретного железа. inplace у quicksort был с самого рождения, и в качестве преимуществ как раз описывается скорость на многоуровневой системе памяти. Что и сейчас актуально, также как и пятьдесят лет назад.
Актуально для реализации, но мы вроде об обучении.
EP>>> dot>С++ это уже такая свалка всего, что за деревьями леса не видно. EP>>> Поэтому и нужно выбрать правильное подмножество для начального обучения, об этом собственно и топик. EP>>> dot>Например. В С пишем "a = b" — это просто mov в железе. А в С++ может быть что угодно. EP>>> 1. И что? Некоторые начинают начальное обучение вообще с Python — там ещё дальше от железа. dot>>Потому что питон — проще чем С++, С проще чем С++. EP>Начальное подмножество C сложнее правильного (сабж) начального подмножества C++.
В каком месте? Единственное что в C сложно — это printf/scanf (хотя стримы в С++ не сильно проще). Но их можно избежать, скажем, через getchar/putchar/fgets/puts.
dot>>Для обучения С++ — хуже. Чем меньше уделять приходится уделять внимание деталям языка — тем лучше. EP>Так на C++ на начальном этапе меньше всяких отвлечений. Взял vector, и заполняй как хочешь. В то время как на C будет куча лишнего кода.
Если ты знаешь что такое vector.
dot>>Зато далеко от железа. EP>А зачем на начальном этапе близко к железу?
Чтобы понимать как это работает унутре. Как один из языков, которым нужно обучать, чтобы дать представление о системном уровне.
Для алгоритмов — нужны другие языки, а для С++ места нет.
но это не зря, хотя, может быть, невзначай
гÅрмония мира не знает границ — сейчас мы будем пить чай
Здравствуйте, Evgeny.Panasyuk, Вы писали:
dot>>И чем хуже Питон|Ява в этом случае? Даже swap двух элементов массива можно сделать. EP>Оригинальный quicksort это полностью inplace алгоритм — перемещаются сами объекты/структуры, а не ссылки на них.
In-place — это не про то, что перемещаются сами объекты, а не ссылки на них. In-place — это про то, что не требуется большого (больше константного) вспомогательного объёма памяти. Даже в C++ при сортировке строк ты будешь не копировать байтовые массивы туда-сюда, а swap'ать ссылки на них (хотя извне std::string и ведёт себя как value-тип). В этом отношении сортировка в C++ не будет отличаться от сортировки в .NET, и не станет от этого менее in-place.
EP>Оригинальный quicksort помимо inplace ещё и ограничивает глубину стэка логарифмом.
Оригинальный QuickSort как раз не ограничивает глубину вызовов, поэтому она может вырождаться до эн, и общая сложность в худшем случае деградирует до эн-квадрат. Поэтому и приходится вводить хаки, чтобы при определённой пороговой глубине переключаться на алгоритмы типа сортировки кучей или вставками с гарантированным эг-лог-эн в худшем случае.
Глаза у меня добрые, но рубашка — смирительная!
Re[11]: [C++] CppCon 2015: Kate Gregory “Stop Teaching C"
Здравствуйте, T4r4sB, Вы писали:
TB>·>А что, string разве inplace? TB>Я не распарсил фразу. Поясни, что ты имеешь в виду. Ты хочешь, чтобы сорт переставлял буковки строк, не меняя указатели на буферы? На кой хрен это надо?
Мне ни на кой хрен не надо, это Evgeny.Panasyuk пишет
Оригинальный quicksort это полностью inplace алгоритм — перемещаются сами объекты/структуры, а не ссылки на них.
И ВНЕЗАПНО оказалось, что строки отсортировать нельзя, ибо перемещаются не сами массивы символов, а ссылки на начало|конец.
но это не зря, хотя, может быть, невзначай
гÅрмония мира не знает границ — сейчас мы будем пить чай
Re[3]: [C++] CppCon 2015: Kate Gregory “Stop Teaching C"
Здравствуйте, Abyx, Вы писали:
A>Цель — это обучение людей которые будут работать на должности "разработчик С++", или будут поддерживать код на С++.
Я бы поостерёгся брать человека без хорошего знания чистого C.
A>И Kate Gregory объясняет, что если всё учить в правильном порядке, то оказывается что всё очень просто, можно обойтись без игр "а добавлю-ка я звездочку с этой строны, вдруг соберется"
Дьявол в деталях. Писать код действительно просто. Откомпилировать его может оказаться сложнее. Я практически моментально нахожу причину ошибки компиляции в случае С-кода. В случае C++ иногда приходится напрягаться... А чтобы исправить ошибку в runtime может понадобится умение ковыряться в кишках, а это, большей частью, сишные концепции. К индусской концепции «один пишет, другой фиксит баги» я отношусь настороженно.
Re[12]: [C++] CppCon 2015: Kate Gregory “Stop Teaching C"
Здравствуйте, Evgeny.Panasyuk, Вы писали:
EP>Оригинальный quicksort это полностью inplace алгоритм — перемещаются сами объекты/структуры, а не ссылки на них.
Эдак у тебя строки квиксортом сбороть не выйдет.
Re[8]: [C++] CppCon 2015: Kate Gregory “Stop Teaching C"
Здравствуйте, ·, Вы писали:
EP>> Он quick-то во многом благодаря этому, и используется по сей день (пусть и временами внутри introsort). ·>Гы-гы. Как ты сделаешь inplace quicksort хотя бы массива строк разной длины?
Ахинею он выдал. Inplace это значит,
1 элементы контейнера не пересоздаются, а перемещаются с помощью swap
2 Контейнер не пересоздаётся, перемещаются только элементы унутре контейнера
3 что унутре контейнера — объекты, структуры или ссылки на них — никому не интересно.
То есть, тру квиксорт это жесточайше мутабельный алгоритм.
Re[11]: [C++] CppCon 2015: Kate Gregory “Stop Teaching C"
Здравствуйте, Ikemefula, Вы писали:
I>Здравствуйте, Abyx, Вы писали:
LVV>>>Подумаешь, открытие... LVV>>>Да мы так уже лет 7-8 учим.
A>>Молодцы. А кто-то до сих пор учит по Bullshildt'у.
I>Шылдт устарел. Нужно учить так, что бы не в консоли колупаться, а получать внятный визуальный результат.
Консоль юнит-тестов — что может быть лучше для современного новичка?
Re[13]: [C++] CppCon 2015: Kate Gregory “Stop Teaching C"
Оригинальный quicksort это полностью inplace алгоритм — перемещаются сами объекты/структуры, а не ссылки на них.
TB>·>И ВНЕЗАПНО оказалось, что строки отсортировать нельзя, ибо перемещаются не сами массивы символов, а ссылки на начало|конец. TB>Ты не понимаешь, что такое "сама структура" в случае строки
Я прекрасно понимаю, что под "сама структура" вы понимаете то, что удобно, чтобы обосновать свой тезис "quicksort это полностью inplace алгоритм".
но это не зря, хотя, может быть, невзначай
гÅрмония мира не знает границ — сейчас мы будем пить чай
Re[5]: [C++] CppCon 2015: Kate Gregory “Stop Teaching C"
Здравствуйте, Mr.Delphist, Вы писали:
I>>Шылдт устарел. Нужно учить так, что бы не в консоли колупаться, а получать внятный визуальный результат.
MD>Консоль юнит-тестов — что может быть лучше для современного новичка?
Трудно придумать что либо хуже этого
Re[9]: [C++] CppCon 2015: Kate Gregory “Stop Teaching C"
Здравствуйте, Ikemefula, Вы писали:
EP>>> Он quick-то во многом благодаря этому, и используется по сей день (пусть и временами внутри introsort). I>·>Гы-гы. Как ты сделаешь inplace quicksort хотя бы массива строк разной длины? I>Ахинею он выдал. Inplace это значит, I>1 элементы контейнера не пересоздаются, а перемещаются с помощью swap I>2 Контейнер не пересоздаётся, перемещаются только элементы унутре контейнера I>3 что унутре контейнера — объекты, структуры или ссылки на них — никому не интересно.
А если говорить совсем строго, с т.з. теории — то quicksort требует больше памяти, чем константа. Для стека требуется O(log(N)) памяти, в худшем случае O(N).
Т.е. quicksort вообще никаким боком не inplace. Вот bubble sort — да, inplace.
I>То есть, тру квиксорт это жесточайше мутабельный алгоритм.
Поэтому — не обязательно, мутабельность не присуща квиксорту. Да, эффективные реализации скорее всего будут стараться двигать как можно меньше, выделять как можно меньше памяти, распологать байты CPU-cache-friendly, но на O-сложность это никак не влияет.
но это не зря, хотя, может быть, невзначай
гÅрмония мира не знает границ — сейчас мы будем пить чай
