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

·>Сложность алгоритмов всегда состоит из двух компонент.

Иногда больше. Например, временную сложность можно считать по сравнениям, а можно по swap'ам.

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

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

TB>Жги ещё!
Так что ты мне-то пишешь? Это же не моя цитата, пиши это Евгению.

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

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.

dot>Это не его слова, а цитирование "some people argue this is not really quicksort...",

Да, цитирование, которое он не просто так привёл — он прекрасно понимает что вопрос как минимум спорный, и поэтому вполне справедливо привёл это мнение.
И вот это an essense относится именно к "updates array inplace", а не то что ты сказал:

EP>>>>Там ключевое "an essense of quicksort". То есть "сущность quicksort".
dot>>>Да, т.е. собственно сам алгоритм quicksort, его сущность, а не детали реализации — inplace, indirection, swap, указатели, менеджмент памяти, ассемблеры и прочая левость к quicksort отношения не имеющая.

dot> далее он говорит, что та хаскелевая имплементация — именно и есть сам quicksort, дающий понять сущность самого алгоритма.

Нет, он говорит что вот такое описание помогает понять не именно сам quicksort, а некоторые алгоритмические особенности behind quicksort.
В оригинальный же quicksort входит не только сферический inplace, но и вполне конкретный partition.

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

Нет, автор конкретно описал и последовательный доступ по памяти, и отсутсвие random-access, и многоуровневую иерархию памяти.

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

Конкретно пример Страуструпа в главе "2. Myth 1: “To understand C++, you must first learn C”" из этой статьи.

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

Отличная, но начинать-то обучение с неё зачем?

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

Я говорю что то что есть в C, либо C-подобном подможестве C++ — вот это хуже, и с этого не нужно начинать обучение. Об этом собственно топик

dot>Зато реализация этого самого вектора с использованием malloc/free — гораздо интереснее, чем просто "вот у нас тут туча кода, которая абстрагирует индексируемый контейнер переменной длины".

Конечно интереснее, и Страуструп именно её и разбирает. Только делает это уже ближе к 600ой странице, в то время как vector был введён и использовался начиная с 100ой страницы.
Об этом и речь, всё это можно изучать — но не с самого начала, никакого "C first".

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

·>А куда деваться-то? Ведь "Даже тут будет существенное отличие".
·>Так что ты мне-то пишешь? Это же не моя цитата, пиши это Евгению.

Зачем писать Евгению, он вроде понимает, что такое инплейс, а ты нет.

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

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

dot>>Т.е. quicksort вообще никаким боком не inplace.
EP>Алгоритмы "на Python/Java" изучал?
Нет.. Когда я их начинал изучать это был ZX Basic. Python/Java ещё не существовало.

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

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

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

По времени, именно об этой сложности и говорил Qbit86 выше.
Я же вообще напрямую про сложность не говорил, я чётко сказал "глубина стэка".

dot>Сложность алгоритмов всегда состоит из двух компонент.

Не сложность "состоит из", а "у алгоритмов есть разные свойства/характеристики".

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

В случае оригинальной inplace quick sort, да — это ограничивает space complexity.

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

Только нижнюю границу, то есть Ω.

dot>Причём тут ограничивается или нет.

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

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

dot>>А ascii кодировка и десятичное представление чисел — совсем другой вопрос. Железо об этом ничего не знает, нет никаких чисел в железе, только биты-байты.
dot>>Написать преобразование int в ascii-символы и обратно — отличная учебная задача.

EP>Отличная, но начинать-то обучение с неё зачем?

За тем же, зачем изучение процессора начинают с простейшей логики. сначала простейшие элементы, потом всякие мультиплексоры, потом триггеры, потом появляются вещи посложнее — счетчики, шина, регистры. Вот здесь уже можно поговорить о вычислителях. Но перед этим изучается диодная или транзисторная логика, т.е. схемотехника.
И вот после всего этого начинается изучение процессора.

Я тебе страшное скажу — если речь просто "дать представление" то можно и без триггеров и логики, тупо на пальцах.

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

Q>Так консоль тест-раннера — это такой тренажёр и есть.

Это отстой. Тренажер это например робот, точка на экране и тд и тд. Любая игрушка может быть внятным тренажером.

Нужны вещи интуитивно понятные новичку. Вот робот который делает шаг вперед — это понятно и объяснять не надо.

А вот "test move forward passed" это непонятно, этому надо учить.

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

I>Вот робот который делает шаг вперед — это понятно и объяснять не надо.

А робот, который вместо шага вперёд вдруг попадает с экрана, потому что программист случайно рассчитал целевую точку относительно мира, а не локальной системы робота? Или робот, который вместо шага вперёд начинает очень быстро уезжать вдаль со скоростью один шаг за кадр? Типичные вещи в программировании игрушек, по собственному опыту. В общем случае отлаживать такое непросто, слишком много деталей; слишком обширен контекст, его тяжело изолировать.

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

I>>Вот робот который делает шаг вперед — это понятно и объяснять не надо.

Q>А робот, который вместо шага вперёд вдруг попадает с экрана, потому что программист случайно рассчитал целевую точку относительно мира, а не локальной системы робота? Или робот, который вместо шага вперёд начинает очень быстро уезжать вдаль со скоростью один шаг за кадр? Типичные вещи в программировании игрушек, по собственному опыту. В общем случае отлаживать такое непросто, слишком много деталей; слишком обширен контекст, его тяжело изолировать.

Это всё наглядно, понятно и самое главное — вызывает настоящий интерес. И мы не про общий случай, а про первые шаги.

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

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

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

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

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

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

Ну, "консоль юнит-тестов" — это не хардкорная консоль "введи буковки, чёрный фон", а готовый вариант UI, где перечислены имеющиеся тесты и видны результаты их прогона. Какая именно консоль — тут уж на вкус и цвет. Кто-то NUnit, кто-то нет.

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

MD>Ну, "консоль юнит-тестов" — это не хардкорная консоль "введи буковки, чёрный фон", а готовый вариант UI, где перечислены имеющиеся тесты и видны результаты их прогона. Какая именно консоль — тут уж на вкус и цвет. Кто-то NUnit, кто-то нет.

Для начинающего это ни о чем. Простецкая либа для рисования гораздо полезнее, ибо вызывает неподдельный интерес и азарт "О, а щас я добавлю пару строчек и получится Чебурашка !".