Да не был он прав. Чувак с нескольких раз таки и не понял, что автор рассматривал алгоритм, подходящий для данных заранее неизвестного — потенциально бесконечного — размера (что типично для поточной обработки). И что доля выборки имеет право быть гигантской — и тогда все эти идеи про то, что константа перевесит асимптотику окажутся неверны. Да и откуда он вообще взял какую-то «базу», откуда делается обращение.
Впрочем, автор оригинального поста косноязычен и не умеет доносить свою мысль.
Ээээ.... Если вы самостоятельно не можете придумать алгоритм и лишь запоминаете готовые, это не значит, что никто не может. Особенно, если речь про такой незамысловатый алгоритм как решето Эратосфена.
Это автоматически балансирующие размер хеш-таблицы. Так что да, set(arr) - это точно O(n), если у объектов операцию хеширования писали прямыми руками. И `key in set` - это точно O(1), если мы говорим про амортизированную сложность в среднем и не предполагаем, что тут произошла атака на алгоритм хеширования.
Тестирование или/и доказательство корректности алгоритма является неотъемлемой частью решения алгоритмической задачи.
Всё-таки, в алгоритмических задачах тестирование «на минималках»: тут нет ни внешних сервисов, ни некорректных данных, ни многих других проблема реальной разработки.
Есть немало причин и за ручной ввод/вывод, и за ввод/вывод посредством передачи данных в функцию. В любом случае, это точно не главная сложность в решении большей части задач (кроме задач, где именно ввод-вывод является лимитирующим фактором; да, такое тоже бывает).
В реальной жизни нужно ещё заметить, что баг произошёл. И, если он произошёл давно, то с вероятностью, воспроизвести его уже никак не получится.
Представьте себе, что вы разрабатываете базу данных и сажаете баг, который проявляется в очень редких случаях, но при этом портит данные.
>Так вот, не обязательно сразу раскрывать непосредственно данные, а в индивидуальном порядке намекнуть, мол у вас нет проверки на отрицательные числа. И только через некоторое время, если уж совсем никак, открыть входные данные.
Так и происходит. Наставник смотрит на тест, на код и пытается навести на мысль о том, что могло пойти не так. Иногда может задать наводящий вопрос. Иногда может прокомментировать ошибку в коде программы, когда проблема не связана с основным алгоритмам, а касается каких-то частностей. В редких случаях может выдать тест. Ещё бывает, что наставник придумывает сходный тестовый пример и обсуждает со студентом, как программа будет работать на нём. Всё зависит от конкретной задачи и конкретной ошибки.
Это зависит от того, какой стиль учёбы вам подходит. Кому-то лучше заходит самообразование. Другим требуется групповая работа, дедлайны и возможность задать вопрос преподавателю (Яндекс.Практикум как раз из этой категории). Некоторых держит себя в тонусе учёба в процессе работы над реальным проектом.
Оценка памяти тоже может описываться в терминах О-нотации.
В разных языках отличается и потребление памяти, и скорость вычислений, и скорость IO. И время исполнения тоже плавает от запуска к запуску.
Но лимиты, же для разных языков тоже возможно выставить различные.
Оба подхода имеют право на жизнь.
Безусловно, проще писать код в предположении, что данные уже лежат в переменных.
Но в некоторых задачах нетривиально придумать, как правильно считать данные. Например, понять, что данные вообще не нужно сохранять в памяти, а нужно обрабатывать на лету. Или понять, нужно ли вам хранить данные графа в виде матрицы или списков смежности.
Впрочем, признаю, что это не самый частый кейс.
Спасибо за статью!
У меня вопрос по первой части. Вы пишете, что из документов делаете стримы. А нет ли у вас среди генерируемых стримов текстов вопросов, которые мог бы задать пользователь к этой статье? Кажется, задача генерации вопросов к тексту должна очень хорошо решаться сетями — и тогда вы получаете супер-релевантный мэтч.
1) Изучать математику для программиста очень полезно, но это не обязательная программа. Знание вышмата увеличит ваш горизонт в несколько раз. Но всё равно существует много работ, где это не требуется.
2) Java — плохой язык в качестве первого. Возьмите что-то более простое. Питон, паскаль (PascalABC вполне норм) или хотя бы javascript (хотя там свои сложности). Когда освоитесь с базовыми вещами и получите опыт с какими-нибудь пет-прожектом, возвращайтесь к джаве.
3) Не пытайтесь сразу постичь все сто слоёв абстракции. Выбрали один уровень — посмотрите два слоя вглубь и один вверх. Этого на первом этапе достаточно.
Вот изучаете вы массивы. Вам точно нужно изучить, как с ними работать. Если копнуть, тут же всплывут вопросы: как их хранит в памяти ваш компилятор/интерпретатор; сколько времени выполняются разные операции и почему; есть ли отличие в массивах между разными языками, и почему. Если копнуть ещё чуть глубже, вам придется изучать выделение памяти и системные вызовы, устройство оперативной памяти и кэшей процессора, привлекать понятие амортизированной сложности алгоритма итд; а ещё глубже — и вот вы уже углубились в электронику, а затем и в физику. Это как чтение википедии — заныриваешь в одном месте, всплываешь в двадцати ссылках от исходной статьи. Остановитесь на одном-двух «хопах» и обучение пойдет быстрее.
Вы не учитываете одну важную вещь. Большинство людей, которые начинают изучать программирование (это обычно 5/7/9 класс обычной средней школы) не планируют становится программистами. И совершенно не готовы погрузиться в изучение нюансов. Поэтому главный признак, которым должен обладать первый язык — он должен давать возможность быстро сделать что-то содержательное, чтобы хоть пробудить интерес. Я по этой причине топлю за питон: простой и позволяет в 5 строк сделать очень многое: хоть график построить, хоть сервачок написать. И наличие REPL-а позволяет очень быстро проверять гипотезы, когда не знаешь, как правильно.
Да, явная типизация может помочь в обучении, но жить без неё вполне можно (тем более, что в современном питоне есть опциональные аннотации типов). А вот без быстрого старта язык непригоден для большинства.
Сейчас в школе или паскаль, или питон обычно.
Учить java первым языком — глупая затея. С одной стороны это слишком низкоуровнево, с другой стороны много концепций приходится объяснять сразу. У меня был буквально один урок, когда школьница попросила её обучить джаве. И на том моменте, когда для чтения числа с клавиатуры нужно сделать обёртку из буфферизованного потока, а потом из ридера, я понял, что затея провальная.
И это мы ещё опускаем заклинания public static void main (но они не только в джаве, конечно). Даже на плюсах проще стартовать, имхо.
Вспоминаю, сколько суток моего времени убито на танцы с бубном вокруг винды — и плачу.
Все-то программы там ставятся сходу. Антивирус на винде говорит исключительно успокаивающие вещи, пока я пытаюсь решить свою цель «пообщаться с другом».
А у дикарей с других операционных систем небось и браузера-то нет (а браузер, наверное, 90% потребностей в компе закрывает). А когда мне нужно отправить файл, контекстное меню на двадцать пунктов «отправить селфи» и «может все-таки отправить селфи (аутлук спешит на помощь)» меня отговорит от этих глупостей. Тем более, что мои файлы и так уже в майкрософтовском облаке; ой, там не хватило места, но давайте мы посмотрим ещё раз, вдруг место освободится (нам понадобится для этого всего три ядра вашего ноутбука из четырех).
Нет, я не фанат линукса; с ним у меня тоже было много проблем. Но все проблемы, которые вы описываете, абсолютно универсальны. Единственное место, где линукс проигрывает винде в простоте и удобстве — это офисные программы.
// Есть ещё, конечно, мак. Но я так и не осилил тамошний графический интерфейс и раскладку клавиатуры, так что мне про него особо нечего сказать, кроме того, что интуитивность его переоценена.
Мы платим вам за то, чтобы вы косили траву. Времени на заточку косы в вашем трудовом договоре не предусмотрено.
Бизнесу с таким подходом — удачи, она ему понадобится.
Но на каждой итерации объекты меняют положения и скорости, а значит и интеральное изображение меняется. Как вы его обновляете, чтобы не тратить O(M*N) на каждом шаге по времени?
Если бы голосовую связь делали через TCP, даже очень быстрый, случалась бы такая ситуация: соединение прервалось по какой-то причине, десять секунд разговора пришли к вам с опозданием. И что вам с ними теперь делать, слушать на удвоенной скорости, пока разговор идет дальше и люди ждут вашего ответа?
Дополню это несколько утверждением, вступающим отчасти в противоречие с вашим.
Система голосования не выявляет реальных предпочтений голосующего (насколько я понимаю, в теории игр такого типа вопросы рассматриваются). Например, если вы считаете, что человек заслуживает тройки, вам следует ставить ему кол, ведь вы понимаете, что ваша оценка усреднится с оценками тысяч других людей, которые голосуют не столь экстремально.
Ваш комментарий плохо состарился. Несколько раз в месяц мне стабильно режут и OpenVPN, и Outline на свои сервера.
Если более точно, CC BY-SA. Именно SA не позволяет менять лицензию.
Да не был он прав. Чувак с нескольких раз таки и не понял, что автор рассматривал алгоритм, подходящий для данных заранее неизвестного — потенциально бесконечного — размера (что типично для поточной обработки). И что доля выборки имеет право быть гигантской — и тогда все эти идеи про то, что константа перевесит асимптотику окажутся неверны. Да и откуда он вообще взял какую-то «базу», откуда делается обращение.
Впрочем, автор оригинального поста косноязычен и не умеет доносить свою мысль.
Ээээ.... Если вы самостоятельно не можете придумать алгоритм и лишь запоминаете готовые, это не значит, что никто не может. Особенно, если речь про такой незамысловатый алгоритм как решето Эратосфена.
Это автоматически балансирующие размер хеш-таблицы.
Так что да, set(arr) - это точно O(n), если у объектов операцию хеширования писали прямыми руками.
И `key in set` - это точно O(1), если мы говорим про амортизированную сложность в среднем и не предполагаем, что тут произошла атака на алгоритм хеширования.
Всё-таки, в алгоритмических задачах тестирование «на минималках»: тут нет ни внешних сервисов, ни некорректных данных, ни многих других проблема реальной разработки.
В реальной жизни нужно ещё заметить, что баг произошёл. И, если он произошёл давно, то с вероятностью, воспроизвести его уже никак не получится.
Представьте себе, что вы разрабатываете базу данных и сажаете баг, который проявляется в очень редких случаях, но при этом портит данные.
Так и происходит. Наставник смотрит на тест, на код и пытается навести на мысль о том, что могло пойти не так. Иногда может задать наводящий вопрос. Иногда может прокомментировать ошибку в коде программы, когда проблема не связана с основным алгоритмам, а касается каких-то частностей. В редких случаях может выдать тест. Ещё бывает, что наставник придумывает сходный тестовый пример и обсуждает со студентом, как программа будет работать на нём. Всё зависит от конкретной задачи и конкретной ошибки.
В разных языках отличается и потребление памяти, и скорость вычислений, и скорость IO. И время исполнения тоже плавает от запуска к запуску.
Но лимиты, же для разных языков тоже возможно выставить различные.
Безусловно, проще писать код в предположении, что данные уже лежат в переменных.
Но в некоторых задачах нетривиально придумать, как правильно считать данные. Например, понять, что данные вообще не нужно сохранять в памяти, а нужно обрабатывать на лету. Или понять, нужно ли вам хранить данные графа в виде матрицы или списков смежности.
Впрочем, признаю, что это не самый частый кейс.
У меня вопрос по первой части. Вы пишете, что из документов делаете стримы. А нет ли у вас среди генерируемых стримов текстов вопросов, которые мог бы задать пользователь к этой статье? Кажется, задача генерации вопросов к тексту должна очень хорошо решаться сетями — и тогда вы получаете супер-релевантный мэтч.
2) Java — плохой язык в качестве первого. Возьмите что-то более простое. Питон, паскаль (PascalABC вполне норм) или хотя бы javascript (хотя там свои сложности). Когда освоитесь с базовыми вещами и получите опыт с какими-нибудь пет-прожектом, возвращайтесь к джаве.
3) Не пытайтесь сразу постичь все сто слоёв абстракции. Выбрали один уровень — посмотрите два слоя вглубь и один вверх. Этого на первом этапе достаточно.
Вот изучаете вы массивы. Вам точно нужно изучить, как с ними работать. Если копнуть, тут же всплывут вопросы: как их хранит в памяти ваш компилятор/интерпретатор; сколько времени выполняются разные операции и почему; есть ли отличие в массивах между разными языками, и почему. Если копнуть ещё чуть глубже, вам придется изучать выделение памяти и системные вызовы, устройство оперативной памяти и кэшей процессора, привлекать понятие амортизированной сложности алгоритма итд; а ещё глубже — и вот вы уже углубились в электронику, а затем и в физику. Это как чтение википедии — заныриваешь в одном месте, всплываешь в двадцати ссылках от исходной статьи. Остановитесь на одном-двух «хопах» и обучение пойдет быстрее.
Да, явная типизация может помочь в обучении, но жить без неё вполне можно (тем более, что в современном питоне есть опциональные аннотации типов). А вот без быстрого старта язык непригоден для большинства.
Учить java первым языком — глупая затея. С одной стороны это слишком низкоуровнево, с другой стороны много концепций приходится объяснять сразу. У меня был буквально один урок, когда школьница попросила её обучить джаве. И на том моменте, когда для чтения числа с клавиатуры нужно сделать обёртку из буфферизованного потока, а потом из ридера, я понял, что затея провальная.
И это мы ещё опускаем заклинания public static void main (но они не только в джаве, конечно). Даже на плюсах проще стартовать, имхо.
Все-то программы там ставятся сходу. Антивирус на винде говорит исключительно успокаивающие вещи, пока я пытаюсь решить свою цель «пообщаться с другом».
А у дикарей с других операционных систем небось и браузера-то нет (а браузер, наверное, 90% потребностей в компе закрывает). А когда мне нужно отправить файл, контекстное меню на двадцать пунктов «отправить селфи» и «может все-таки отправить селфи (аутлук спешит на помощь)» меня отговорит от этих глупостей. Тем более, что мои файлы и так уже в майкрософтовском облаке; ой, там не хватило места, но давайте мы посмотрим ещё раз, вдруг место освободится (нам понадобится для этого всего три ядра вашего ноутбука из четырех).
Нет, я не фанат линукса; с ним у меня тоже было много проблем. Но все проблемы, которые вы описываете, абсолютно универсальны. Единственное место, где линукс проигрывает винде в простоте и удобстве — это офисные программы.
// Есть ещё, конечно, мак. Но я так и не осилил тамошний графический интерфейс и раскладку клавиатуры, так что мне про него особо нечего сказать, кроме того, что интуитивность его переоценена.
Бизнесу с таким подходом — удачи, она ему понадобится.
Система голосования не выявляет реальных предпочтений голосующего (насколько я понимаю, в теории игр такого типа вопросы рассматриваются). Например, если вы считаете, что человек заслуживает тройки, вам следует ставить ему кол, ведь вы понимаете, что ваша оценка усреднится с оценками тысяч других людей, которые голосуют не столь экстремально.