Полтора года назад Юра обошел дерево в ширину алгоритмом, и вы представьте себе, это действительно было нужно сделать!
Да, алгоритмы нужны не везде и не всегда. Но когда они действительно нужны, если разработчик их не занет, он даже не поймет, что они там нужны.
Заводить в команде отдельного "алгоритмиста" тоже не вариант по той же причине — остальные разработчики должны понять, что его нужно призвать. Или придется ему ревьювить все изменения в коде, что не скейлится.
Про списки — тут не было однозначного обсуждения в сторону списков (наоборот, субтред начался с того, что при наличии массива делать quicksort на списках в ФП стиле как-то вредно)
Тред начался с того, что тут привели простую и изящную реализацию квиксорта, которая сортирует списки. Я весь тред пытаюсь доказать, что она плохая.
Этот алгоритм для поиска медианы на практике не используют.
Шутка про него:
Он, хоть и линейный, но константа там такая, что ее на логарифм хватит и еще на квадрат чуть-чуть останется.
Этот алгоритм, наверно, был бы любимым примером всяких ненавистников и презирателей О-большое и другой мутной математики в программировании, если бы они про него знали.
В остальном я с вами согласен, квадратичный случай для квиксорта на практике не проблема совсем и с ним можно бороться. Но это нисколько не отменяет основной мысли моих постов: Квиксорт хорош для сортировки массивов на месте. Настолько хорош, что используют именно его, даже если надо при этом накручивать сортировки хипсортом по достижении определенной глубины рекурсии или использовать рандом, оставляя хоть мизерный, но шанс повиснуть.
Но все эти приемущества квиксорта отсутсвуют при сортировке списков, что тут и пытались делать. Отсаются только недостатки. Поэтому вот такая реализация квиксорта, хоть и короче применяемой на практике — она плохая. Если вас попросят на интервью отсортировать списки — не надо писать квиксорт. Если вас попросят написать именно квиксорт, то не надо сортирвать списки (добавлю, что это плохой вопрос, если вас спросили именно про квиксорт — вам попался плохой интервьювер).
Нет, вы не правы. Ответ на вопрос — вероятность, что Вы — единственный ребенок коткретного моряка, ПРИ УСЛОВИИ, ЧТО ВЫ СУЩЕСТВУЕТЕ. Очевидно, да, что если вас что-то спросили — вы есть.
Вся соль в том, что события существования и обладания братом/сестрой связаны. Поэтому вылезают всякие условные вероятности и неочевидные ответы.
Отношение в том, что вам известен факт, что вас спросили. От того, кого и как спрашивают, зависит вероятность, что спросят именно Вас. А дальше Баесовская вероятность и т.д. Опять же, вот пример: эксперементатор спрашивает сына, только если он один. В этом случае, если вас спросили — у вас брата точно нет.
Да! И в посте весь этот парадокс и антропный принцип как раз из-за того что не спрашивается, что выпало на монете. Вопрос задается (м.б. самому себе) конкретному ребенку, ПРИ УСЛОВИИ, что этот конкретный ребенок существует.
И в чём Вы видите проблему?
Сумма вероятностей 1/2 «нет детей» и 1/2 «двое детей» строго 1
Проблема в том, что если кто-то или сам ребенок спрашивает, если у него брат, то этот брат точно есть. Потому что в случае решки ребенка бы не было вообще. Напоминаю, тут мы говорим о модифицированной задаче, где детей либо 2, либо 0.
Хотя монетка все такая же честная и в половине бросков приведет к двум детям, ответ на вопрос — 100% есть брат. И тут тоже ОДИН отец ОДИН РАЗ бросил монету. Но вероятность — 100%!
Вот вам контрпример. Допустим моряк подбрасывает монетку и если выпадает решка — то не делает детей, если орел — делает двух. Вы — ребенок этого конкретного моряка. Какая вероятность что вы — единственный ребенок. Очевидно, 0. Но как так, ведь КОНКРЕТНЫЙ МОРЯК бросал монетку. 50% по вашей логике выходит.
Если спрашивают только одного ребенка, когда их 2 — то вероятность 1/2. Если спрашивают обоих детей — то вероятность 1/3.
Да, звучит контр интуитивно, если ребенок, таки один. Как это вероятность зависит от поведения эксперементаторов в воображаемом сценарии? А представьте теперь, что эксперементатор спрашивает ребенка, только если их два. Тогда вероятность быть единственым сыном — 0. Если вас, таки, спросили.
Почему вы счиатете, что строки в которых более 33% данного, выбранного символа — средние? Если брать не '\', а какой-нибудь 0x01? А только такие при экранировании увеличатся хотя бы на треть, как base64 сделает со всеми строками.
Если сроки случайные — то наоборот.
Как раз в случайных строках и будет наперед выбранный символ встречаться меньше процента. И раздуются они на этот несчастный процент. В средней случайной строке все возможные символы встречаются почти одинаковое количество раз.
Это как сравнивать пузырек и квиксорт. Да, у квиксорта константа больше и в худшем случае он будет медленее пузырька. Но на практике (для больших массивов) используют квиксорт, а не пузырек. Так и тут. Экранирование для некоторых входных данных будет хуже base64, но для абсолютного большинства случайных строк оно будет лучше. Если же входные данные не случайные и там преобладает некоторый символ — просто возьмите другой символ экранирования.
Более того, я уже привел алгоритм, который гарантированно не раздувает строки более чем на 1% при этом требует константной памяти и выполняется за один проход по строке. Из base64 вы такого никогда не сделаете.
Совершенно верно, но по условию задачи строки бесконечно длинные
Читаем 250 символов, выбираем наиредчайший и используем его для экранирования в этом куске. Повторяем, пока строка не кончилась.
Распаковщик читает символ для экранирования, потом читает до символов <экран>0. Если распаковано 250 символов, считывается новый символ экранирования.
Ваш аргуемент, что в худшем случае строка раздуется в 2 раза — он не абсолютно объективный. Потому что таких плохих входных строк мало, а тех которые почти не раздуются — их много. Т.е. в среднем и в лучшем случае алгоритм с экранированием сильно лучше base64.
Я, как интервьювер, предпочел бы ответ с экранированием. Да, дополнительный вопрос про экономию места был бы в обоих случаях. Но если экранирование можно соптимизировать до 0.5% ухудшения всегда, то base64 никак уже не улучшить.
Не такой уж плохой подход: в худшем случае он увеличивает строку на треть, тогда как экранирование символов — вдвое.
Но при этом и в лучшем случае длина увеличивается на треть. А в экранировании можно использовать для экранирования любой из символов, который встречается в строке меньше других. Если выбирать из всех 255 символов, то можно гарантировать увеличение максимум на пол процента + 1 символ. А в лучшем случае, если данные не случайны, то вообще без увеличения.
Но главный минус выбранного подхода — автор не смог его запрограммировать. Экранирование в этом случае было бы гораздо проще, т.к. там не надо битовых операций.
Той абсолютной однородности, которую вы допускаете — нет. Ведь есть горы и океаны — неоднородность, однако. Из примерной однородности в среднем не следует, что любая конфигурация должна повторятся бесконечное количество раз.
Если вы творите бесконечную Вселенную, то генерируя ее фрагменты рано или поздно у вас кончатся уникальные комбинации, как если бы вы собирали мир из Лего. Поэтому, если вы существуете, то существуете в бесконечном количестве копий.
Это только если все различные комбинации должны встречатся бесконечное количество раз, что вообще ниоткуда не следует. На практике, пустое пространство встречается бесконечное количество раз, а Земля — всего один.
Да, правоторговцы очень хотят совместить для себя все плюсы лицензий и физических товаров. Когда пользователь хочет что-то сделать с продуктом, то это просто лицензия, с кучей искуственных ограничений. Но при этом нелегальное использование — это воровство в глазах правоторговцев.
Описанная вами схема со специальными маркерами — весьма корявое ДРМ, неудобное для пользователей, и ничего на самом деле не защищающее. Вы купите книгу, а через год магазин закроется и сервер проверки этих маркеров выключит — и вы уже не сможете читать честно купленную книгу.
В 10 винде вообще есть встроенное средство записи экрана через Game bar.
Интересно, его это горе-дрм тоже как-то отключает?
j0hns1lver, Есть ли у Вас возможность проверить?
Да, алгоритмы нужны не везде и не всегда. Но когда они действительно нужны, если разработчик их не занет, он даже не поймет, что они там нужны.
Заводить в команде отдельного "алгоритмиста" тоже не вариант по той же причине — остальные разработчики должны понять, что его нужно призвать. Или придется ему ревьювить все изменения в коде, что не скейлится.
Звучит дико интересно! Могли бы вы поделиться ссылкой на контекст?
Duo разве похоронили? Не слышал об этом ничего.
А про способы оплаты разве что-то уже известно? С чего вы взяли, что это будет подписка без покупки, а не подписка+покупка?
Тред начался с того, что тут привели простую и изящную реализацию квиксорта, которая сортирует списки. Я весь тред пытаюсь доказать, что она плохая.
Этот алгоритм для поиска медианы на практике не используют.
Он, хоть и линейный, но константа там такая, что ее на логарифм хватит и еще на квадрат чуть-чуть останется.
Этот алгоритм, наверно, был бы любимым примером всяких ненавистников и презирателей О-большое и другой мутной математики в программировании, если бы они про него знали.
В остальном я с вами согласен, квадратичный случай для квиксорта на практике не проблема совсем и с ним можно бороться. Но это нисколько не отменяет основной мысли моих постов: Квиксорт хорош для сортировки массивов на месте. Настолько хорош, что используют именно его, даже если надо при этом накручивать сортировки хипсортом по достижении определенной глубины рекурсии или использовать рандом, оставляя хоть мизерный, но шанс повиснуть.
Но все эти приемущества квиксорта отсутсвуют при сортировке списков, что тут и пытались делать. Отсаются только недостатки. Поэтому вот такая реализация квиксорта, хоть и короче применяемой на практике — она плохая. Если вас попросят на интервью отсортировать списки — не надо писать квиксорт. Если вас попросят написать именно квиксорт, то не надо сортирвать списки (добавлю, что это плохой вопрос, если вас спросили именно про квиксорт — вам попался плохой интервьювер).
Нет, вы не правы. Ответ на вопрос — вероятность, что Вы — единственный ребенок коткретного моряка, ПРИ УСЛОВИИ, ЧТО ВЫ СУЩЕСТВУЕТЕ. Очевидно, да, что если вас что-то спросили — вы есть.
Вся соль в том, что события существования и обладания братом/сестрой связаны. Поэтому вылезают всякие условные вероятности и неочевидные ответы.
Отношение в том, что вам известен факт, что вас спросили. От того, кого и как спрашивают, зависит вероятность, что спросят именно Вас. А дальше Баесовская вероятность и т.д. Опять же, вот пример: эксперементатор спрашивает сына, только если он один. В этом случае, если вас спросили — у вас брата точно нет.
Да! И в посте весь этот парадокс и антропный принцип как раз из-за того что не спрашивается, что выпало на монете. Вопрос задается (м.б. самому себе) конкретному ребенку, ПРИ УСЛОВИИ, что этот конкретный ребенок существует.
Проблема в том, что если кто-то или сам ребенок спрашивает, если у него брат, то этот брат точно есть. Потому что в случае решки ребенка бы не было вообще. Напоминаю, тут мы говорим о модифицированной задаче, где детей либо 2, либо 0.
Хотя монетка все такая же честная и в половине бросков приведет к двум детям, ответ на вопрос — 100% есть брат. И тут тоже ОДИН отец ОДИН РАЗ бросил монету. Но вероятность — 100%!
Вот вам контрпример. Допустим моряк подбрасывает монетку и если выпадает решка — то не делает детей, если орел — делает двух. Вы — ребенок этого конкретного моряка. Какая вероятность что вы — единственный ребенок. Очевидно, 0. Но как так, ведь КОНКРЕТНЫЙ МОРЯК бросал монетку. 50% по вашей логике выходит.
Если нет никакого эксперементатора, а следовательно и эксперемента, само понятие вероятности не имеет смысла.
Если спрашивают только одного ребенка, когда их 2 — то вероятность 1/2. Если спрашивают обоих детей — то вероятность 1/3.
Да, звучит контр интуитивно, если ребенок, таки один. Как это вероятность зависит от поведения эксперементаторов в воображаемом сценарии? А представьте теперь, что эксперементатор спрашивает ребенка, только если их два. Тогда вероятность быть единственым сыном — 0. Если вас, таки, спросили.
Почему вы счиатете, что строки в которых более 33% данного, выбранного символа — средние? Если брать не '\', а какой-нибудь 0x01? А только такие при экранировании увеличатся хотя бы на треть, как base64 сделает со всеми строками.
Как раз в случайных строках и будет наперед выбранный символ встречаться меньше процента. И раздуются они на этот несчастный процент. В средней случайной строке все возможные символы встречаются почти одинаковое количество раз.
Это как сравнивать пузырек и квиксорт. Да, у квиксорта константа больше и в худшем случае он будет медленее пузырька. Но на практике (для больших массивов) используют квиксорт, а не пузырек. Так и тут. Экранирование для некоторых входных данных будет хуже base64, но для абсолютного большинства случайных строк оно будет лучше. Если же входные данные не случайные и там преобладает некоторый символ — просто возьмите другой символ экранирования.
Более того, я уже привел алгоритм, который гарантированно не раздувает строки более чем на 1% при этом требует константной памяти и выполняется за один проход по строке. Из base64 вы такого никогда не сделаете.
Читаем 250 символов, выбираем наиредчайший и используем его для экранирования в этом куске. Повторяем, пока строка не кончилась.
Распаковщик читает символ для экранирования, потом читает до символов <экран>0. Если распаковано 250 символов, считывается новый символ экранирования.
Ваш аргуемент, что в худшем случае строка раздуется в 2 раза — он не абсолютно объективный. Потому что таких плохих входных строк мало, а тех которые почти не раздуются — их много. Т.е. в среднем и в лучшем случае алгоритм с экранированием сильно лучше base64.
Я, как интервьювер, предпочел бы ответ с экранированием. Да, дополнительный вопрос про экономию места был бы в обоих случаях. Но если экранирование можно соптимизировать до 0.5% ухудшения всегда, то base64 никак уже не улучшить.
Но при этом и в лучшем случае длина увеличивается на треть. А в экранировании можно использовать для экранирования любой из символов, который встречается в строке меньше других. Если выбирать из всех 255 символов, то можно гарантировать увеличение максимум на пол процента + 1 символ. А в лучшем случае, если данные не случайны, то вообще без увеличения.
Но главный минус выбранного подхода — автор не смог его запрограммировать. Экранирование в этом случае было бы гораздо проще, т.к. там не надо битовых операций.
Той абсолютной однородности, которую вы допускаете — нет. Ведь есть горы и океаны — неоднородность, однако. Из примерной однородности в среднем не следует, что любая конфигурация должна повторятся бесконечное количество раз.
Тоже хотел об этом написать.
Это только если все различные комбинации должны встречатся бесконечное количество раз, что вообще ниоткуда не следует. На практике, пустое пространство встречается бесконечное количество раз, а Земля — всего один.
Да, правоторговцы очень хотят совместить для себя все плюсы лицензий и физических товаров. Когда пользователь хочет что-то сделать с продуктом, то это просто лицензия, с кучей искуственных ограничений. Но при этом нелегальное использование — это воровство в глазах правоторговцев.
Описанная вами схема со специальными маркерами — весьма корявое ДРМ, неудобное для пользователей, и ничего на самом деле не защищающее. Вы купите книгу, а через год магазин закроется и сервер проверки этих маркеров выключит — и вы уже не сможете читать честно купленную книгу.