Если бы программирование было аниме

Материал опубликован пользователем.
Нажмите кнопку «Написать», чтобы поделиться мнением или рассказать о своём проекте.

Написать
{ "author_name": "Sanjar Tolibjonov", "author_type": "self", "tags": [], "comments": 41, "likes": 27, "favorites": 37, "is_advertisement": false, "subsite_label": "avi", "id": 116983, "is_wide": true, "is_ugc": true, "date": "Thu, 26 Mar 2020 11:40:05 +0300", "is_special": false }
0
41 комментарий
Популярные
По порядку
Написать комментарий...
5

Оно уже давно им стало/

Ответить
0

XD
Есть такое на xiaomi пылесос?

Ответить
0

О да/

Ответить
4

А что, разве еще нет ни одного аниме про программирование?

Ответить

Праздничный волк

Станислав
1

есть несколько аниме про программистов, которые умирают и попадают в параллельный мир. припоминаю сюжеты, где один стал трапом и строил роботов, а в другом гг стал супер крутым магом за счет знания программирования. ну и еще он в бою на мечах был самый крутой почему-то, просто так, видимо

Ответить
5

 >программист-трап
Где-то такое я уже видел...

Ответить
8

У меня ирл есть знакомый программист, который сделал трансгендерный переход. Вроде сейчас на операцию собирается ложится.
Так что, уверен, это нормально для программистов!

Ответить
1

Ну с учетом личной жизни...сменить пол самое первое что в голову приходит 

Ответить
2

Боевой программист Ширасе

Ответить
0

Вот да. Не очень новое, но прикольное.

Ответить
1

Горничная дракон - первое, что приходит в голову. Она там на питоне писала

Ответить
0

New game еще

Ответить

Праздничный волк

1

зочем нужно while True? и разве не стоит избегать break? как увидел этот видос как-то, до сих пор не пойму.
и кстати, не знаю как там на питоне (это же он, да?), но с таким кодом, если первый элемент массива > количества элементов массива разве компилятор не выдаст ошибку? 

Ответить

Специализированный мангал

Праздничный
6

break/continue не надо бояться. while True тоже ок. Да и страх GOTO сейчас преувеличен. Я иногда немножко бомблю от того, как люди шарахаются GOTO при том, что в современных языках GOTO по сути и нет, а последний раз проблема с ним была годах так в 80х.

Ответить

Праздничный волк

Специализирован…
0

while True тоже ок

не понимаю, почему не использовать что-то типа
do{
tortoise = nums[tortoise];
hare  = nums[nums[hare]];
}while(tortoise != hare);

Ответить
6

в питоне нет конструкции do while, поэтому используется такой вариант как на видео

Ответить

Праздничный волк

Maksim
0

оу, печаль. ну тогда понятно. 

Ответить

Специализированный мангал

Праздничный
2

И то, и то ок. Если код не для палаты мер и весов, а для нормального проекта, то оба варианта норм, они не влияют на производительность, но при этом мозги у разных людей по-разному работают: кому-то удобно проверку засунусть в постусловие, кому-то прям на месте с break, а кому-то вообще проще рекурсивно (если их Lisp в детстве укусил).

Ответить

Праздничный волк

Праздничный
0

столько вопросов к коду из видео чето=\
хотя, я так понял, автор вроде типа видеоуроки по программированию ведет. вроде бы.

Ответить
0

а что с элементом массива значение которого больше размера массива?

Выкинет ошибку выхода за границу массива.
А код не странный, код нерабочий. Точнее, это просто буквальная перепечатка псевдокода. 
tortoise = nums[tortoise] 

hare = nums[nums[hare]]

Вот это должно быть:
tortoise = tortoise.next (взять следующий элемент связного списка)
hare = hare.next.next

Ответить

Праздничный волк

shaeron
0

так смысл в том, что hare у него не в два раза быстрее, другой алгоритм получается

Ответить
1

Да он же и сам привел название алгоритма, который использует. Это оно и есть, просто он не смог нормально прочитать описание и на полном серьёзе перевел вот это вот в код:
hare = f(f(hare)). 
https://en.wikipedia.org/wiki/Cycle_detection

Ответить
0

🎮 Codename: Tortoise
Дата релиза: 08.01.2020

Разработчик: JosieGameDev

🛒 itch.io

———

🎮 Hare

Разработчики: Tio_jolo, Zelun
Издатель: Zelun

🛒 Steam

Ответить

Праздничный волк

Специализирован…
0

а что с элементом массива значение которого больше размера массива? я вроде когда впервые увидел этот видос, попробовал где-то на каком-то сайте запустить схожий код на пхп и он выдал ошибку. питону пофиг что ли?

Ответить

Специализированный мангал

Праздничный
1

Про питон хз. В других языках это либо segfault, либо исключение. Не всматривался в код в видео, но возможно там просто косяк монтажа.

Ответить

Праздничный волк

Праздничный
0

ну ошибку, в плане что ругался, когда делал соответствующий массив. если брать массив из видео, то ок

Ответить
2

Ждем аниме адаптацию от Netflix

Ответить
0

Я чет не понял. Условие - найти повторяющиеся числа. Правильное решение - использовать алгоритм проверки зацикленности связного списка. Действительно, тривиальное решение.

Ответить

Геологический Петя

Олег
0

Ну, это первое, что пришло мне в голову, правда, я не мог понять, как это сделать без дополнительной памяти.

Ответить
0

Но что даст проверка зацикленности списка?
Есть массив: [2, x, 0, x, x, x, x]; Имеем зацикленный связный список. Как это знание (что список зацикленный) поможет нам узнать есть в массиве дубликаты или их нет?

Ответить
1

По условию задачи, в массиве нет элемента со значением 0, поэтому никакой цикл не может начинаться с нулевого элемента, и ты никогда не вернёшься в начало. И ты не вылетаешь за пределы массива только потому, что в нём n+1 элемент.

Т.е. если ты обходишь этот массив как список (по индексам), рано или поздно ты встретишь какой-то цикл (число элементов конечно), но пришёл ты туда извне этого цикла (по цепочке, начавшейся из элемента 0, который гарантированно не состоит ни в каком цикле). Значит существует элемент, в который можно прийти двумя способами.

Твой пример про независимые циклы имеет смысл. Фишка в том, что мы никогда их не трогаем. Пример:

[2, x, 5, x, x, 2, x, x, 9, 8]

Здесь цикл 8 -> 9 -> 8 живёт сам по себе, и никак не участвует в алгоритме. Нахождение этого цикла никак бы нам не помогло, но это не важно. Мы знаем, что мы найдём хоть какой-то (возможно другой) цикл, если начнём с нулевого элемента, и вон как раз там мы и отыщем дупликат.

Ответить
1

Ага, ну теперь понятно. Но это получается очень уж специфическое условие задания. Решение действительно элегантное и простое, но выглядит так, как-будто условие задания подогнано под это решение :)

Но было бы круто, если было бы такое же решение для общего случая: найти есть ли дубликаты для массива любых чисел (за линейное время, без создания дополнительных массивов и без модификации исходного :) ).

Ответить
1

Да полное говно решение, если честно.

Нормально работает только если твой массив достаточно мал, чтобы поместиться в last level cache, иначе это по факту становится ничем не лучше обычного односвязного списка. На каждый хоп будешь ждать по несколько сотен циклов, пока тебе из памяти данные доедут, чтоб узнать куда прыгать дальше. Префетчить тоже нечего, т.к. порядок непредсказуем. И тут мы по этому списку пробегаем несколько раз за одно решение. Короче совсем беда.

Я б лучше элементы по подгруппам посчитал несколько раз. Допустим у меня было 987'654'321 элементов. Положил на стек 1000 нулей, посчитал сколько у меня элементов в [0..999'999][1'000'000..1'999'999]...
(офк на практике ты хочешь отгрызать биты, так что будут степени двойки, но я иллюстрирую идею). Какая сумма оказалась больше ожидаемой (допустим в [77'000'000..77'999'999] оказалось не миллион элементов, а миллион-двадцать), в той группе и дупликат. Повторяем ещё раз, теперь игнорируя все элементы вне этого рейнжа, а для элементов внутри него считаем элементы в 1000 групп — [77'000'000..77'000'999], [77'001'000..77'001'999]. Какая сумма больше тыщи, там и наше число. Третий проход — и готово (можно его вообще заменить битфилдом, если хочется, т.к. тебя интересует лишь был ли уже такой элемент или нет).

Даже если числа 64-битные, и элементов убер-дохера, тебе легко хватит 5 проходов без вылаза за L1d кэш со своими суммами. Технически это O(logN) (по основанию зависящему от числа счётчиков), но на практике эти 5 проходов будут порядка так на два быстрее решения из видео (офк. если код на каком-нибудь питоне, то за накладные расходы не ручаюсь).

Но если тебе хочется чего-нибудь интересного из похожей области, да ещё и полезного на практике — HyperLogLog. Довольно точно оценивает количество уникальных элементов (не обязательно даже чисел) на гигантских множествах чего угодно. Скажем, есть у тебя полное собрание порнофанфиков по Гарри Поттеру, и тебе захотелось посчитать количество уникальных словосочетаний, берёшь и за один линейный проход получаешь оценку с ошибкой в пару процентов (и есть очень разумный трейдофф между ошибкой и стоимостью+памятью).

Ответить
1

О, спасибо! А вот это уже лучше. Правда использует дополнительную память, но зато размер ее константен.
Еще этот алгоритм хорошо распараллеливается в отличии от того, что на видео.
За ссылку на HyperLogLog спасибо.

Ответить
1

По памяти трейдофф же. Ты делаешь около ceil(logK(N)) проходов, и для этого тебе технически надо K-1 счётчиков (K просто удобнее, но вообще последний можно вывести как разницу между N и суммой других счётчиков). Т.е. в совсем синтетическом случае "ахаха, в память писать нельзя и стека у тебя нет, это микроконтроллер из 80х!" нужен лишь один регистр чтоб считать, сколько элементов меньше N/2 (не считая регистров под итерации цикла и прочую хурму), и потом искать уже для той половины, в которой оказалось элементов больше чем нужно.

Закончишь за ceil(log2(N)) проходов по массиву, но даже это может оказаться быстрее алгоритма из видео, если память достаточно медленная (что немного ломает аналогию с микроконтроллером, ну да чёрт с ним). Ежели наскрёб ещё 2 регистра (или автор задачи щедро даёт нам несколько байт, в которые можно писать), то уже log4, что вдвое быстрее.

Короче, полностью на твой выбор. Я б лично подобрал размер чтоб лезло в L1d или хотя бы L2 (надо мерять что будет быстрее для ожидаемого объёма данных), положил бы счётчики на стек, и дело с концом. Никаких аллокаций из кучи, всё компактно и красиво.

Ответить
0

🎮 10000000
Дата релиза: 25.07.2012
Рейтинг Metacritic: 67

Разработчики: EightyEightGames, EightyEight Games LTD, EightyEight Games
Издатели: EightyEightGames, EightyEight Games LTD

🛒 App StoreGoogle PlaySteam

Ответить
0

Аниме не смотрю, но знатно орнул

Ответить
0

Если бы программирование было аниме, то это было бы процесс погрязший в самокопирование - людьми, которые ничерта не знают что делают...Подождите-ка

Ответить
0

Ничего непонятно, но очень интересно!

Ответить
{ "jsPath": "/static/build/dtf.ru/specials/DeliveryCheats/js/all.min.js?v=05.02.2020", "cssPath": "/static/build/dtf.ru/specials/DeliveryCheats/styles/all.min.css?v=05.02.2020", "fontsPath": "https://fonts.googleapis.com/css?family=Roboto+Mono:400,700,700i&subset=cyrillic" }