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

·>Я прекрасно понимаю, что под "сама структура" вы понимаете то, что удобно, чтобы обосновать свой тезис "quicksort это полностью inplace алгоритм".

Если у нас массив указателей на MegaObject, то для тебя инплейс — это когда свапают сами MegaObjectы? Лол)

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

TB>·>Я прекрасно понимаю, что под "сама структура" вы понимаете то, что удобно, чтобы обосновать свой тезис "quicksort это полностью inplace алгоритм".
TB>Если у нас массив указателей на MegaObject, то для тебя инплейс — это когда свапают сами MegaObjectы? Лол)
А если у тебя массив указателей на TinyObject. Это как-то повлияет на inplace-ность? Причём вообще указатели, swap, размер объектов и прочее когда мы говорим о quicksort?

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

·>А если у тебя массив указателей на TinyObject. Это как-то повлияет на inplace-ность? Причём вообще указатели, swap, размер объектов и прочее когда мы говорим о quicksort?

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

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

A>>И Kate Gregory объясняет, что если всё учить в правильном порядке, то оказывается что всё очень просто, можно обойтись без игр "а добавлю-ка я звездочку с этой строны, вдруг соберется"
M>Дьявол в деталях. Писать код действительно просто. Откомпилировать его может оказаться сложнее. Я практически моментально нахожу причину ошибки компиляции в случае С-кода. В случае C++ иногда приходится напрягаться... А чтобы исправить ошибку в runtime может понадобится умение ковыряться в кишках, а это, большей частью, сишные концепции. К индусской концепции «один пишет, другой фиксит баги» я отношусь настороженно.

Искать ошибки компиляции — это сложно? А ошибки в рантайме, в продакшене, проще чтоли искать?
С++ как раз добавляет много ошибок компиляции, чтобы ошибки ловились на этапе компиляции, а не в рантайме.

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

EP>>Оригинальный quicksort помимо inplace ещё и ограничивает глубину стэка логарифмом.
Q>Оригинальный QuickSort как раз не ограничивает глубину вызовов, поэтому она может вырождаться до эн,

Ограничивает глубину стэка логарифмом. Это явно описано в оригинальной статье Хоара.
И я уже это подробно объяснял

Автор: Evgeny.Panasyuk
Дата: 22.05.15

:

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

Q>>>Быструю сортировку можно и без рекурсивных вызовов организовать, эмулировав стек, но так обычно не делают в стандартных библиотеках. То есть почему-то не спешат менять потенциальный StackOverflowEcxeption на потениальный OutOfMemoryException. Добавляют при необходимоти guard глубины рекурсии, и живут себе, поди, без штрафов к премиям.

EP>Справедливости ради, в нормальной quicksort глубина стэка гарантированно ограничена O(ln(N)), в worst case.
EP>Там внутри две рекурсии — по левой стороне массива и по правой. Для той у которой размер массива больше — делают ручной tail call. То есть рекурсия происходит всегда в меньшую сторону, причём это может быть как левая, так и правая сторона.
EP>Размер меньшей части гарантированно меньше половины размера исходного массива, то есть рекурсия как минимум делится пополам, что гарантирует логарифмическую глубину.

Q>и общая сложность в худшем случае деградирует до эн-квадрат.

Глубина стэка != сложность алгоритма.

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

TB>·>А если у тебя массив указателей на TinyObject. Это как-то повлияет на inplace-ность? Причём вообще указатели, swap, размер объектов и прочее когда мы говорим о quicksort?
TB>Алгоритм инплейсен относительно того, что непосредственно хранится в массиве, а не того, чего хочешь ты, вот и всё.
Алгоритму quicksort вообще по барабану inplace-ность. Неужели непонятно?

TB>А если мы храним в векторе номера файлов в папке, то при свапе надо открывать файлы и переписывать их содержимое, да?
Если принять за истину это: "Оригинальный quicksort это полностью inplace алгоритм — перемещаются сами объекты/структуры, а не ссылки на них." — да, придётся переписывать или признать, что это не quicksort. Номер файла — это же ссылка.
Хотя более рационально признать сказанное Евгением ахинеей.

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

I>Здравствуйте, Mr.Delphist, Вы писали:

I>>>Шылдт устарел. Нужно учить так, что бы не в консоли колупаться, а получать внятный визуальный результат.

MD>>Консоль юнит-тестов — что может быть лучше для современного новичка?

I>Трудно придумать что либо хуже этого

Т.е. надо заставить новичка сначала вбить какой-то boilerplate? В виде UI или ещё чего-то? Не понимаю.

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

EP>Глубина стэка != сложность алгоритма.
А что?
Ради справки: глубина стека включается в размер потребляемой памяти, "algorithm space complexity". Ты, похоже, путаешь с "algorithm time complexity".

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

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".
dot>Да, т.е. собственно сам алгоритм quicksort, его сущность, а не детали реализации — inplace, indirection, swap, указатели, менеджмент памяти, ассемблеры и прочая левость к quicksort отношения не имеющая.

Не надо фантазировать из цитаты чётко ясно к чему относится "an essense":

this is not really quicksort, because, you know, an essense is that it takes an array and updates array inplace.

dot>>> in another hand if you want to understand the algorithm behind quicksort, then this is fabulous description".
dot>>>Т.е. для понимания самого алгоритма — это то что надо.
EP>>Для понимая другого алгоритма. Оригинальный quicksort помимо inplace ещё и ограничивает глубину стэка логарифмом.
dot>Эта хаскелловая имплементация тоже ограничивает, выбор pivot point будет лишь влиять на то, что будет считаться worst case для данной имплементации алгоритма.

Каким образом она ограничивает глубину стэка?
Глубина стэка в оригинальном quicksort логарифмическая, независимо от выбора pivot point, даже в worst case. Подробно описал чуть выше.

dot>>>А inplace, индирекции, эффективный swap — это всё оптимизации — заставить работать некий алгоритм на конкретном железе как можно быстрее.
EP>>А алгоритмы пишутся в том числе для конкретного железа. inplace у quicksort был с самого рождения, и в качестве преимуществ как раз описывается скорость на многоуровневой системе памяти. Что и сейчас актуально, также как и пятьдесят лет назад.
dot>Актуально для реализации, но мы вроде об обучении.

Это часть самого алгоритма, так как его описал автор.

EP>>>> dot>С++ это уже такая свалка всего, что за деревьями леса не видно.
EP>>>> Поэтому и нужно выбрать правильное подмножество для начального обучения, об этом собственно и топик.
EP>>>> dot>Например. В С пишем "a = b" — это просто mov в железе. А в С++ может быть что угодно.
EP>>>> 1. И что? Некоторые начинают начальное обучение вообще с Python — там ещё дальше от железа.
dot>>>Потому что питон — проще чем С++, С проще чем С++.
EP>>Начальное подмножество C сложнее правильного (сабж) начального подмножества C++.
dot>В каком месте?

Везде — и обход последовательностей, и работа с контейнерами, и ввод-вывод и т.д. и т.п.

dot>Единственное что в C сложно — это printf/scanf (хотя стримы в С++ не сильно проще). Но их можно избежать, скажем, через getchar/putchar/fgets/puts.

Каким образом будешь числа выводить? itoa? Да уж — поменял шило на мыло

dot>>>Для обучения С++ — хуже. Чем меньше уделять приходится уделять внимание деталям языка — тем лучше.
EP>>Так на C++ на начальном этапе меньше всяких отвлечений. Взял vector, и заполняй как хочешь. В то время как на C будет куча лишнего кода.
dot>Если ты знаешь что такое vector.

Так его и предлагается изучать с самого начала. Страуструп например так и делает
В чём проблема-то?

dot>>>Зато далеко от железа.
EP>>А зачем на начальном этапе близко к железу?
dot>Чтобы понимать как это работает унутре.

Зачем это при начальном обучении? С самых первых дней?

dot>Как один из языков, которым нужно обучать, чтобы дать представление о системном уровне.
dot>Для алгоритмов — нужны другие языки, а для С++ места нет.

Твоё мнение я услышал.

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

EP>>Глубина стэка != сложность алгоритма.
dot> А что?

Можно иметь квадратичный алгоритм даже при констатнтном размере стэка

В случае же оригинального quicksort, даже в worst case (когда выполняется квадратичное число операций) глубина стэка — логарифмическая, это гарантия.

dot>Ради справки: глубина стека включается в размер потребляемой памяти, "algorithm space complexity". Ты, похоже, путаешь с "algorithm time complexity".

Я не путаю. Я конкретно сказал что ограничивается глубина стэка. Про algorithm time complexity это твои фантазии.

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

EP>>Глубина стэка != сложность алгоритма.
·>:wow: А что?
·>Ради справки: глубина стека включается в размер потребляемой памяти, "algorithm space complexity". Ты, похоже, путаешь с "algorithm time complexity".

Я писал комментарий относительно глубины «логического стэка», которая включает в том числе ручной хвостовой «вызов», и от которой зависит сложность. Но «физический стэк» — да, можно ограничить. Это не влияет на принципиальную логическую структуру вызовов и асимптотическую сложность; но один хвосторекурсивный вызов можно подхачить так, чтоб он не увеличивал глубину реального стека, а переиспользовал «стекфрейм».

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

dot>>>И чем хуже Питон|Ява в этом случае? Даже swap двух элементов массива можно сделать.
EP>>Оригинальный quicksort это полностью inplace алгоритм — перемещаются сами объекты/структуры, а не ссылки на них.
Q>In-place — это не про то, что перемещаются сами объекты, а не ссылки на них. In-place — это про то, что не требуется большого (больше константного) вспомогательного объёма памяти.

Да, согласен обычно имеется в виду именно это. Только при этом допускается логарифмический вспомогательный объём. В приведённой же ФП версии нет даже этого.
Но в оригинальном quicksort также описывается что перемещаются сами данные, а разбиение происходит последовательно по памяти с двух концов диапазона, и явно указанно отсутствие random-access.

Q>В этом отношении сортировка в C++ не будет отличаться от сортировки в .NET

Даже тут будет существенное отличие. В .NET/Java элемент массива строк — это по сути указатель на указатель на буфер — двойная индерекция. В C++ же максимум одна, а то и ноль в случае SSO.

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

MD>>>Консоль юнит-тестов — что может быть лучше для современного новичка?

I>>Трудно придумать что либо хуже этого

MD>Т.е. надо заставить новичка сначала вбить какой-то boilerplate? В виде UI или ещё чего-то? Не понимаю.

Почему обязательно должен быть какой то бойлерплейт ? Нужен тренажер, возможно с UI. Главное что бы результат был мгновенный, понятный и интересный пользователю. ни разу не видел, что бы новичкам было интересно в консоль втыкать.

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

·>Если принять за истину это: "Оригинальный quicksort это полностью inplace алгоритм — перемещаются сами объекты/структуры, а не ссылки на них." — да, придётся переписывать или признать, что это не quicksort. Номер файла — это же ссылка.

А если эти числа — номера домов на улице, то надо сносить дома и строить их в другом месте?
Жги ещё!

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

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

TB>>·>А если у тебя массив указателей на TinyObject. Это как-то повлияет на inplace-ность? Причём вообще указатели, swap, размер объектов и прочее когда мы говорим о quicksort?
TB>>Алгоритм инплейсен относительно того, что непосредственно хранится в массиве, а не того, чего хочешь ты, вот и всё.
·>Алгоритму quicksort вообще по барабану inplace-ность. Неужели непонятно?

Наоборот. Тот самый квиксорт именно инплейсный, смотри о чем говорит Эрие Мейер.

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

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".
dot>>Да, т.е. собственно сам алгоритм quicksort, его сущность, а не детали реализации — inplace, indirection, swap, указатели, менеджмент памяти, ассемблеры и прочая левость к quicksort отношения не имеющая.
EP>Не надо фантазировать из цитаты чётко ясно к чему относится "an essense":
EP>

EP>this is not really quicksort, because, you know, an essense is that it takes an array and updates array inplace.

Это не его слова, а цитирование "some people argue this is not really quicksort...", далее он говорит, что та хаскелевая имплементация — именно и есть сам quicksort, дающий понять сущность самого алгоритма.

EP>>>Для понимая другого алгоритма. Оригинальный quicksort помимо inplace ещё и ограничивает глубину стэка логарифмом.
dot>>Эта хаскелловая имплементация тоже ограничивает, выбор pivot point будет лишь влиять на то, что будет считаться worst case для данной имплементации алгоритма.
EP>Каким образом она ограничивает глубину стэка?
EP>Глубина стэка в оригинальном quicksort логарифмическая, независимо от выбора pivot point, даже в worst case. Подробно описал чуть выше.
Ограничение — logN в среднем случае, так называемая наивная реализация quicksort, но quicksort она не перестаёт быть.

EP>>>А алгоритмы пишутся в том числе для конкретного железа. inplace у quicksort был с самого рождения, и в качестве преимуществ как раз описывается скорость на многоуровневой системе памяти. Что и сейчас актуально, также как и пятьдесят лет назад.
dot>>Актуально для реализации, но мы вроде об обучении.
EP>Это часть самого алгоритма, так как его описал автор.
Т.е. если бы автор описал алгоритм на фортране, то единственный способ написать quicksort это фортран?

dot>>>>Потому что питон — проще чем С++, С проще чем С++.
EP>>>Начальное подмножество C сложнее правильного (сабж) начального подмножества C++.
dot>>В каком месте?
EP>Везде — и обход последовательностей, и работа с контейнерами, и ввод-вывод и т.д. и т.п.
А конкретно? Ну кроме printf/scanf?

dot>>Единственное что в C сложно — это printf/scanf (хотя стримы в С++ не сильно проще). Но их можно избежать, скажем, через getchar/putchar/fgets/puts.
EP>Каким образом будешь числа выводить? itoa? Да уж — поменял шило на мыло
А ascii кодировка и десятичное представление чисел — совсем другой вопрос. Железо об этом ничего не знает, нет никаких чисел в железе, только биты-байты.
Написать преобразование int в ascii-символы и обратно — отличная учебная задача.

dot>>>>Для обучения С++ — хуже. Чем меньше уделять приходится уделять внимание деталям языка — тем лучше.
EP>>>Так на C++ на начальном этапе меньше всяких отвлечений. Взял vector, и заполняй как хочешь. В то время как на C будет куча лишнего кода.
dot>>Если ты знаешь что такое vector.
EP>Так его и предлагается изучать с самого начала. Страуструп например так и делает
EP>В чём проблема-то?
Но чем, например, java.lang.ArrayList<> или [] в Питоне хуже? Зато реализация этого самого вектора с использованием malloc/free — гораздо интереснее, чем просто "вот у нас тут туча кода, которая абстрагирует индексируемый контейнер переменной длины".

dot>>>>Зато далеко от железа.
EP>>>А зачем на начальном этапе близко к железу?
dot>>Чтобы понимать как это работает унутре.
EP>Зачем это при начальном обучении? С самых первых дней?
А с самых первых дней С и С++ и не нужны, лучше взять что-то более простое. Java — проще, Python — проще. А с совсем первых дней вообще берут какой-нибудь Scratch

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

I>>3 что унутре контейнера — объекты, структуры или ссылки на них — никому не интересно.
·>А если говорить совсем строго, с т.з. теории — то quicksort требует больше памяти, чем константа. Для стека требуется O(log(N)) памяти, в худшем случае O(N).
·>Т.е. quicksort вообще никаким боком не inplace. Вот bubble sort — да, inplace.

инплейс это про исходный контейнер, а не затраты дополнительной памяти.
Я же объяснил
1 — контейнер не пересоздаётся
2 — элементры не пересоздаются
3 -элементы менаются местами чз swap

Всё. Что тебе непонятно, с чем ты не согласен ?

I>>То есть, тру квиксорт это жесточайше мутабельный алгоритм.
·>Поэтому — не обязательно, мутабельность не присуща квиксорту.

Наоборот. Смотри внимательно: https://channel9.msdn.com/Series/C9-Lectures-Erik-Meijer-Functional-Programming-Fundamentals/Lecture-Series-Erik-Meijer-Functional-Programming-Fundamentals-Chapter-1

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

EP>>>Глубина стэка != сложность алгоритма.
dot>> А что?
EP>Можно иметь квадратичный алгоритм даже при констатнтном размере стэка
Квадратичный по времени или памяти?! Сложность алгоритмов всегда состоит из двух компонент.

EP>В случае же оригинального quicksort, даже в worst case (когда выполняется квадратичное число операций) глубина стэка — логарифмическая, это гарантия.
Т.е. по памяти он логарифмической сложности.

dot>>Ради справки: глубина стека включается в размер потребляемой памяти, "algorithm space complexity". Ты, похоже, путаешь с "algorithm time complexity".
EP>Я не путаю. Я конкретно сказал что ограничивается глубина стэка. Про algorithm time complexity это твои фантазии.
Глубина стека определяет сложность алгоритма по памяти. Причём тут ограничивается или нет.

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

dot>А если говорить совсем строго, с т.з. теории — то quicksort требует больше памяти, чем константа. Для стека требуется O(log(N)) памяти, в худшем случае O(N).

В худшем случае log2(N), это явно описано в оригинальной статье Энтони Хоара.

dot>Т.е. quicksort вообще никаким боком не inplace.

Алгоритмы "на Python/Java" изучал?

I>>То есть, тру квиксорт это жесточайше мутабельный алгоритм.
dot>Поэтому — не обязательно, мутабельность не присуща квиксорту.

Мутабельность у него в крови.

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

MD>>>>Консоль юнит-тестов — что может быть лучше для современного новичка?
I>Нужен тренажер, возможно с UI. Главное что бы результат был мгновенный, понятный и интересный пользователю. ни разу не видел, что бы новичкам было интересно в консоль втыкать.

Так консоль тест-раннера — это такой тренажёр и есть. UI с красными и зелёными полосками, и деревом разных тестовых методов, мгновенный результат, можно запускать код прям из раннера, смотреть время выполнения, можно выводить в текстовый вывод всякое.