Елена Щелкунова «Сложность алгоритмов»
Вставка
- Опубліковано 26 вер 2024
- Про сложность алгоритмов слышали, наверное, все. Это одна из популярных тем для вопросов на собеседованиях. А вот так, чтобы знать на память, как считается сложность того или иного алгоритма - это уже свойственно не всем.
Так или иначе, если знания не используются, то они забываются. Елене посчастливилось продолжительное время работать с задачами оптимизации времени исполнения кода, как на фронте, так и на бэке. И зачем спрашивается держать такие знания в себе?
Предлагаем вместе вспомнить теорию, погрузиться в некоторые тонкости и нюансы реализации коллекций в .NET и узнать для себя что-то новое.
Эмм... 38:09 Предлагается сделать Dictionary для хранения входящих и исходящих узлов... Очевидно, что ключи в таком случае будут повторяться, а это недопустимо в Dictionary. Или, я ошибаюсь?
Да, там в зале сразу поправили, что как вариант, надо Dictionary по ключу находим узел, а в массиве список переходов.
абстрактные алгоритмы - это не сложно, 95% алгоритмов кнут описал в своих великолепных книшках, а вот сложное - это железные алгоритмы, потому что они завязаны собственно на железо, и самое сложное - алгоритмы завязанные на исполняющую среду, и вот это и есть главная проблема, которую вообще никто не рассматривает
на пальцах: абстрактные алгоритмы - это не сложно, сложнее - железные алгоритмы, ещё сложнее - алгоритмы настроенные [заточенные] на исполняющую среду, потому что описывается всё, кроме работы исполняющей среды, исполняющую среду никто никогда не описывает
а теперь реальная задачЬка:
1. сгенерируйте 10 мультов рандомных строк, замерьте время генерации этих строк
2. замерьте время __последовательного__ доступа к строкам
3. сгенерируйте 10 мультов рандомных строк, но __многопоточно__ , замерьте время многопоточной генерации этих строк
4. докажите, что строки нагенерированные многопоточно - рандомны
5. замерьте время __последовательного__ доступа к строкам, нагенерированным многопоточно
6. вы потеряете быстрый доступ к строкам, нагенерированным многопоточно
7. объясните что происходит, __на__ __самом__ __деле__
8. вы никогда не сможете объяснить, потому что вы не знаете как работает рантайм, и это самое сложное и есть, всё остальное - не сложно
а теперь реальная реальность:
все эти абстрактные алгоритмы, всякое разное от кнута - всё это работает, но оно автоматически устарело, потому что мирок ойтишечки принципиально изменился, потому что теперь всё работает многопоточно, и всё ранее работающее, все абстрактные алгоритмы, все железные алгоритмы - становятся не нужны, потому что они отвратительно работают в многопотоке, а для многопотока нужно перекарячивать всё __по__ __новой__ , абсолютно всё что было - нужно перепиливать на многопоток - и это нереально сложная задача и есть
задача выше - приведена, задача кажется тривиальной, и ранее на однопотоке она и решалась тривиально, но мирок изменился, и теперь эта казалось бы тривиальная задача по генерации строк - стала предельно __не__ __тривиальной__
а теперь главная суть - тотальный вменяемый переезд на многопоток, на многопоточные алгоритмы - это нереальной сложности задача, это самое сложное и есть, это и есть задачи массового ближайшего будущего в ойтишечке, а кто этого не понимает - отвалится, потому что никакой алгоритм, никакая программка на однопотоке никому не нужны, а соответственно и древние одичалые юзающие древние бесполезные алгоритмы - не нужны
добро пожаловать в реальный мирок ближайшего будущего
и ага, для тех кто ничего не понял, на пальцах:
если вы не способны карячить банальные массивы многопоточно, если вы не способны изменять массивы многопоточно, если вы не способны играть в многопоток - вы уже отстали от жизни лет на десять как минимум, вам дали проц например на 12 ядер - а вы даже банальный массив не в состоянии накарячить на этих двенадцати ядрах
пс: массив это банальный пример, но вы и с банальностями не справляетесь, задумайтесь над этим
ппс: выводы
Смотришь на симпотичную девушку и параллельно готовишься к собесу по алгосам
автор ведосика объясняет [и не может объяснить] опять и снова банальность, её [банальность] придумали в 70-ых прошлого века, и вот эта банальность:
программы - это данные и алгоритмы над этими данными, только это полуправда, а вот истина:
программы - это __подготовленные__ данные и узкозаточенные алгоритмы над этими __подготовленными__ данными для этих алгоритмов
данные - как розовая абстракция в вакууме никому не нужны, а равно и алгоритмы как абстракция в вакууме - тоже никому не нужны
Барышня, вам корона не жмёт?