Вхід і реєстрація
Навчання · 25 січня 2021, 23:43 3630
EA

Teach yourself CS

Я вижу, тут часто обсуждают литкод и 500к в долине, поэтому, думаю, тут много знающих людей.
Сабж: работаю в лидерах рынка, зп в топе рейтинга (не 10к, но рядом), так что деньги не причина. 30 еще нет, так что время и силы, относительно, есть

Очень хочется выучить cs чтобы разбираться как все работает и не впадать в ступор от постов юры зновяка. ВО есть, но инженерное и полученное на тройки.

Видел сайт teachyourselfcs и двигаюсь sicp -> concrete math -> computer architecture -> cormen

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

Теми: computer science
👍ПодобаєтьсяСподобалось3
До обраногоВ обраному7
LinkedIn
Дозволені теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter
Дозволені теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter
EA 06.09.2021 15:14

One more update: полностью прошел сикп, достиг просветления и забил на cs.

Відповісти
Підтримати
EA 21.05.2021 12:07

Короткий апдейт.
Фактически, прошло 6 месяцев со старта, CLRS я забросил после 3 главы (оценивание сложности ОЧЕНЬ пригодилось), справочники читать не очень интересно. Вместо этого полностью сконцентрировался на SICP и могу сказать, что это одна из самых фундаментальных книг в моей жизни: книга затрагивает практически все, что можно вычислить в этом мире, а примеры подобраны просто идеально под сам текст.
В общем, если у кого-то нет формального образования в CS и хочется понять о чем эта наука вообще — не уверен, что есть лучшая альтернатива.

Відповісти
Підтримати
smoothie consumer 24.05.2021 00:32

кстати, от авторов SICP вышла новая книга — Software Design for Flexibility.
mitpress.mit.edu/...​ftware-design-flexibility

Відповісти
Підтримати
EA
EA 01.06.2021 21:55

Видел, спасибо.
Пока что решил разобраться в вычислениях вообще, а не именно в написании программ

Поэтому в дополнение к sicp начал читать feedback systems (astrom, murray) и introduction to the theory of computation (sipser).

Обе требуют базового (очень) матана

Відповісти
Підтримати
smoothie consumer
Anatoly Angst 02.04.2021 15:58

Яка у Вас мета? В цілому це дуже велика інвестиція по часу яка ростягнеться на десятиріччя, і власне буде супроводжувати все кар’єрне життя. Розібратись як ВСЕ працює точно не вийде.
edit: прочитав коменти, фан так фан, могу понять.

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

Я рухаюсь приблизно по цьому ресурсу (знайшов його вже після sicp та nand2tetris), але без поспішання та особливо жорсткого плану.
Прочитав та вирішив сікп («відкриті» задачи та задачі не на scheme не робив) приблизно за рік (не фултайм).
Прочитав та зробив всі проекти в nand2tetris. Також зробив дещо складнішу версію компілятору (будував AST як явну структуру а не потоком). Хотів додавати туди ще фічі та оптимізації, але стало впадло. На це теж пішов приблизно рік.

Зараз читаю Designing data intensive applications, тому що бачу деякий імпакт для роботи, ну і самому цікаво.

В планах зайнятись ОС та низькорівневим програмуванням, але для цього варто було б взяти саббатікал на півроку мінімум, а зараз це не дуже виходить.

Щодо алгоритмів: кормена дуже лаять всі, мені здається це більше просто довідник з алгоритмів? Я проходив на курсері седжвіка, мені дуже сподобалось, не знаю чи він там ще є.

P.S. Ще купив новий «сікп» в папері, називається «Software Design for Flexibility: How to Avoid Programming Yourself into a Corner». Поки що листаю по вечорах під настрій, виглядає дещо пафосно, читається важкувато. І ще вона набагато менше ніж я сподівався, великі поля а сама якась вузька (може такий форм фактор у всіх MIT Press?).

Відповісти
Підтримати
EA 01.04.2021 20:43

Спустя 2 месяца (где-то 4-6 часов в неделю): 2 главы clrs и 100 страниц sicp.

Как-то совсем невесело :(

Відповісти
Підтримати
Artyom Krivokrisenko 01.04.2021 22:28

Ты практические упражнения по SICP делаешь? Если да, в какой IDE компилируешь/запускаешь код?

Відповісти
Підтримати
EA
EA 02.04.2021 07:14

Да, mit scheme

stackoverflow.com/...​install-mit-scheme-on-mac

Пишу в vim, запускаю из командной строки

Відповісти
Підтримати
Artyom Krivokrisenko
Tymchyshyn Vitalii Researcher 02.04.2021 02:19
2 месяца (где-то 4-6 часов в неделю)

тобто менше 9-ти тижнів по 4-6 годин, що грубо дає годин 40.
в такому випадку

2 главы clrs и 100 страниц sicp.

виглядає як цілком нормальний темп для технічної літератури

Відповісти
Підтримати
EA
EA 02.04.2021 07:16

Возможно, но более практическую литературу (по языкам, бд, фреймворкам), получалось читать сильно быстрее

Відповісти
Підтримати
Tymchyshyn Vitalii
Tymchyshyn Vitalii Researcher 02.04.2021 14:27

так це нормально. було б дивно, якби всі книжки були однаково складні. зазвичай складність зростає зі зростанням абстрактності теми, а також по мірі віддалення від знайомих тем.

Відповісти
Підтримати
EA
Mobile 02.04.2021 13:28

сам делал и ранстоне и беркли — очень толковые курсы. если вы не студент цс где нада доказывать алгоритмы то оно никогда вам не пригодиться

Відповісти
Підтримати
anonymous
Vlad Stelmahovsky Software Engineer в Verity AG 21.02.2021 23:14

просто надо играть в контру регулярно. так и научишься

Відповісти
Підтримати
smoothie consumer 26.01.2021 21:11

вот эта книжка по архитектуре с той же подборки teach yourself CS очень годная. Всю не читал, лишь кусками, но мне понравилась книга.
csapp.cs.cmu.edu/3e/home.html

Відповісти
Підтримати
Bot Bot 26.01.2021 21:10

Зачем учить что-то? Чтобы продаить или поиграться для фана. Вот от сюда и отталкивайся. В противном случае потратишь кучу времени в никуда или с крайне малым толком, уж лучше на женщин или путешествия потратить.

Відповісти
Підтримати
smoothie consumer 26.01.2021 21:09

Yuriy Znovyak дал советы. Ждём других олимпиадников в треде

Відповісти
Підтримати
John Kelly 26.01.2021 14:31

Коментар порушує правила спільноти і видалений модераторами.

EA 26.01.2021 14:38

Коментар порушує правила спільноти і видалений модераторами.

John Kelly 26.01.2021 15:17

Коментар порушує правила спільноти і видалений модераторами.

John Kelly 26.01.2021 15:20

Коментар порушує правила спільноти і видалений модераторами.

Yuriy Znovyak РПЗ з ДВРЗ з ВО без ВП і своєю ЖП 26.01.2021 06:35

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

Ну і власне я, мабуть, вчив абсолютно все неправильно і в зворотньому порядку.

Я почав з того, що рішав вистрадував всякі олімпіадні задачки і все йшло дуже туго. Потім на всеукраїнській олімпіаді УМФЛівці показали Кормена («introduction to algorithms», він же «вступ до алгоритмів» він же «алгоритмы: построение и анализ») і я його прочитав — там, імхо, є 99% з усього, що може бути потрібно з алгоритмів. Це щось тіпа як річний курс алгебри або матану на технічних спеціальностях — є інші більш вузькоспеціалізовані теми, але без цього далі ніяк — це спільна база всіх технарів. Власне я спочатку прочитав Кормена тупо як художню книжку, просто все підряд. Там багато чого лягло на підготовлену землю — все-таки деякі задачі я рішав і без нього і тому розумів про що йдеться, але було дуже класно бачити коротке і елегантне рішення якоїсь задачі в 10 рядків, яке у мене займало 300 рядків. Власне просто прочитати книжку залишає в голові можливо не дуже багато, але посіює якісь зерна «о! щось таке чув». Далі коли рішав задачі, то вже практично завжди було відчуття що «о, та таке ж було в Кормені», тоді брав і перечитував потрібний розділ і дорішував задачу — без перечитування розділу майже ніколи не вдавалось :(.

Десь в кінці четвертого року такої кар’єри програмування (і в кінці першого року програмування на С++) я нареші прочитав книжку по самій мові програмування — і знову ж таки мій рівень зразу ж сильно скачкоподібно виріс — я більше не підбирав всліпу варіанти поки компілятор не схаває мій код. І нарешті зрозумів, чому можна писати sort(a.begin(), a.end(), cmp) якщо cmp — функція, а от цю ж саму функцію так просто в set або map не передати.

Комп. Архітектура це для мене той предмет, який от я в різних місцях нахапався. Власне я навіть віддалено добре його не знаю, але почалось все з асемблерних вставок щоб прискорити графіку (PC Underground була афігенною книжкою) — там мої знання десь на рівні 8086 процесору (навіть не 80386 з protected mode’ом). Власне того фіговенького асемблеру хватило, щоб лазити з дизасемблером в чужі програми. Багато чого дізнався вже в університеті на курсі АрхЕОМ, лол. Наприклад про те, як числа з плаваючою комою представлені.

В принципі, практична архітектура дуже швидко розчехляється коли пробуєш щось СИЛЬНО оптимізувати. От тоді буквально в перший же день розбираєшся з тим як працює пам’ять, що означає вирівнювання, що за кеш процесора і навіщо він, що таке векторні операції, і так далі. Наприклад спробуй написати свій чесний парсер цілих чисел (дано строку, треба інт) і вижати з нього по-максимуму. Ну і навпаки — дано інт, треба вивести строкою. Потім подивись що інші бібліотеки для цього роблять (хінт: глянь фейсбуковий фоллі: github.com/facebook/folly зокрема github.com/...​master/folly/docs/Conv.md але повний список теж може сподобатись github.com/...​er/folly/docs/Overview.md).

Власне якщо спробуєш щось оптимізувати на яві, то моментально розберешся з різницею між Integer і int. На наступний день дізнаєшся, що слідуючи офіціним рекомендаціям і пишучи class Point { public double x, y; } ти далеко не заїдеш — занадто великі накладні витрати на об’єкт. Дуже сильно заціниш те, що в інших мовах є struct. Ну а щоб в яві хоч трохи в пам’ять влазило почнеш писати double[] x, y і будеш сам слідкувати за пам’яттю (в даному випадку вільні індекси) і перевинейдеш Object Pool.

Якщо спробуєш оптимізувати щось на запис з вінчестера (наприклад я відносно недавно брав курс по алгоритмах на зовнішній пам’яті), то дуже швидко проникнешся сучасним швидкостям вінчестерів. Старі HDD (з крутящимся диском) — 150мб/сек, SSD по SATA — ~550мб/сек, SSD по PCIe (NVMe) — 2.5-3gb/sec. Pop Quiz: а оперативка-то скільки? У нас в курсі була задача відсортувати великий масив чисел на вінчестері. Тут буквально зразу ж дізнаєшся про приколи з random access і послідовним доступом і зразу стане ясно чому використовували B-Trees в базах даних. Ну а ще дізнаєшся класичний трюк, що краще дані стискати перед тим як записувати на диск — zstd (github.com/facebook/zstd) може писати під 500мб/сек, тобто якщо ти стискаєш данні в 2 рази, то ти з SATA SSD зможеш витиснути не 550мб/сек, а цілу 1000мб/сек. Там ще велика імовірність, що якщо у тебе в каталозі буде багато файликів, то ти швидко дізнаєшся що доступ до них тільки в теорії швидкий (стає актуальним коли запишеш 100500 маленьких файликів в один каталог).

Та сама шутка з сєткою — треба щось оптимізувати і моментально розчехлишся в різних видах poll’ів, потоках, як віддавати запити, і так далі. en.wikipedia.org/wiki/C10k_problem

Лінукс крута штука і я з ним ще в школі грався, але жопою відчув його тільки коли на роботі прийшлось використовувати. Ємакс теж прийшлось вчити через роботу. Цікаво що я тепер ним користуюсь в багатьох випадках навіть коли є кращі інструменти — та ж intellij або goland. Як би треба вже хоч собі визнати що ємакс не завжди найкращий інструмент для всіх можливих задач. Власне всі конфіги ємаксу написані на ліспі (elisp’і якщо точніше, elisp == emacs lisp), тому я його «трохи» знаю (+ в університеті було, в одному курсі з Прологом, до речі). Але я всерівно гуглю базовий синтаксис :(. Власне це я до того, що у мене до SICP руки так і не дійшли, хоча вона висить в моєму to read списку вже 10 років.

«Конкретна математика» прикольна, але, здається, скоріш для сильно вузькоспеціалізованих математиків і дуже теоретичного CS. На практиці частіше тупий мат аналіз і алгебра пригоджувалися частіше. Скільки буде 1^2 + 2^2 + 3^2 + ... + n^2? та обмеж зверху x^2, візьми і візьми інтеграл від 0 до n і матимеш приблизну оцінку в 1/3 n^3. Що? Тобі треба точно? Ну то розпиши наскільки ти помилився і там матимеш арифметичну прогресію і отримаєш точне значення.

Власне не думаю що на конкретну математику треба тратити час — набагато кориснішим буде вивчити щось тіпа SQL — сучасні бази даних це реально супер потужна штука. Або просто перечитати книжку по своїх теперішніх тулзах, якими користуєшся — майже 100% знайдеш щось нове, що сильно збільшить продуктивність.

Власне якщо хочеш алгоритми, то просто прочитай (як художню книжку) Кормена і тупо почни рішати задачі. Найвеселіше це всякого роду контести — за 1 годину контесту ти набагато більше викладешся (і відповідно навчишся) ніж за 1 годину самоосвіти без таймеру. Для контестів є і codeforces і leetcode. Власне рішай задачі, викладай свій код, читай чужий код, проси код рев’ю, роби код рев’ю — це набагато простіше робити з учбовими абстрактними задачками типу літкоду, а не з проектом на 100500 депенденсів. Тобі будуть прилітати брутальні рев’ю, але в більшості випадків вони будуть по ділу і реально допоможуть.

От реально єдина область, чиї знання абсолютно ніде більше не пригодились це сучасний front end. Може я предвзятий і тупий, але реально це якась постійна боротьба зі своїм середовищем. Тіпа бібліотеки, які фіксять проблеми із-за використання інших бібліотек. Заплатки поверх заплаток поверх заплаток.

P.S. Жодного матюку на все полотно тексту? Я і сам о***в, якщо чесно.

Відповісти
Підтримати
EA 26.01.2021 07:07

Ого, ответ впечатлил

Ну то есть кормен остается? Я часто слышал, что это оверкилл и можно скиенну или седжвика почитать (мне они сильно проще показались)

Собственно, много чего из того, что ты написал, я и так знаю. Но в силу того, что нет системности, это часто выглядит как булждание в трех соснах: кастомеру на митинге залить можно, а что-то больше — с трудом )

В свое время как раз пролетел мимо лидера, потому что родителям навтирал что знаю, а на самом деле нет :D

P.S. А ты заканчивал шад, есть ли смысле сейчас? Учитывая что это два года довольно жесткого обучения?

Відповісти
Підтримати
Yuriy Znovyak
Yuriy Znovyak РПЗ з ДВРЗ з ВО без ВП і своєю ЖП 26.01.2021 08:23

Я читав і Седжвіка і Скієну — Кормен 100% краще. Навіть в Кормені може бути забагато інфи.

Глави 1,2 (вступ, швидкість росту функцій) потрібні
Главу 3 (сумування) було б непогано, але нічого страшного якщо просто будеш в курсі того, що там відбувається (реально практично все що може бути потрібно з Конкретної Математики є в цій главі)
Глава 4 (рекурентні співвідношення) непогано би, але не страшно якщо без неї. Це, по суті, динамічне програмування. Але його краще на інших прикладах освоювати — на всяких літкодах і олімпіадках повно задач на динамічне програмування. Основна ідея це позначити f(...) — результат і виразити через f(...) з меншими аргументами.
Глава 5 (множини) це тупо математичний опис всі об’єктів. Непогано знати, там майже все інтуітивно. Ти хіба і так не знаєш, що таке цикл в графі?
Глава 6 (комбінаторика) це норм, але може бути важко, і користь буде не зразу. Можна залишити «на потім»

Частина 2 про сортування ... трохи затаскана тема, але це класика, на якій показують прийоми, які потім будуть використовуватись для всіх інших алгоритмів.
Глава 7. Це про кучу, якою реалізовують priority queue!
Глава 8. Це про quick sort. Прикольний алгоритм, але там цікавіші різного роду аналізи.
Глава 10. Це якраз про те, як використати quick sort щоб знайти k-ий по величині елемент за лінійний час. Якщо ти зрозумієш quick sort, то замітиш, що він ділить масив на 2 куски: зліва всі <= pivot, справа всі > pivot. Так от, k-ий елемент ясно де знаходиться — зліва чи справа. І шукаємо цей елемент у відповідному куску, а інший кусок взагалі не чіпаємо. Таким чином получається що на першій ітерації ти опрацьовуєш n елементів, на другій половину (тільки одну з 2х частин), тому ~n/2, на третій половину половини, тому ~n/4, ... ітого n+n/2+n/4+...=2n=O(n). От і сумування пригодилось :).
Глава 9. Про сортування не на порівняннях. Теж дуже кльово. Як мінімум знатимеш чому хуєсосять дебілів, які кажуть що не можна відсортувати масив швидше ніж O(nlogn) — в прицнипі вони праві якщо говорити про сортування порівнянням (тобто єдине що ти можеш сказати про про любі два елементи це те, чи a < b, чи ні). Але якщо сортуєш інти/дабли, то можна і за лінію, лол.

Частина 3 про структури даних це те, що лікар прописав.
Глава 11 всього лиш 20 сторінок і там розкажуть 95% того, що треба знати про стеки/черги/деки і зв’язні списки.
Глава 12 про хеш таблиці — ваще сама часта структура даних
Глави 13, 14, 15 це вже трохи глибоко, але всерівно прикольно і красиво. Можна бігло пролистати главу 14 (про червоно-чорні дерева), щоб знати що таке є. В C++ в STL set/map реалізовані якраз червоно чорними деревами.

Частина 4 про побудову алгоритмів дуже-дуже потрібна. Там про динаміку, жадність і аморт аналіз. Аморт аналіз це те, як зробити щоб push_back/append в масив щоб він працював за О(1) в середньому. Це афігенно корисно знати.

Частина 5 про більш складні структури даних це збірна солянка.

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

Глава 22 про системи неперетинающихся множин — афігенно красива структура даних. Нею часто можна замінити деякі алгоритми на графах (наприклад дізнатись чи є цикли).

Глава 23 про алгоритми на графах — must have. 90% алгоритмів на графах з співбесід це пошук в ширину або глибину. Бля, та навіть обхід структури каталогів це пошук в глибину. Перебір це пошук в глибину. Короче реально must have. Я б не заморочувався сильно-зв’язними компонентами (хоча знати що це таке не внапряг).

Глава 24 про найменші покриваючі дерева. Ну тіпа вся глава — 12 сторінок і там багато картинок. Власне не впадло прочитати, але не те щоб супер корисно. Тут якраз вспливе як використовуються кучі (глава 7) і системи неперетинающихся множин (глава 22).

Глава 25 про найкоротші шляхи з одної вершини — Дейкстру треба знати (причому вспливе як використовують кучі), Беллмана-Форда не обов’язково, але там всього-лиш 3 рядки, тому не впадлу :).

Глава 26 про найкоротші шляхи між усі парами вершин — красиво, але окрім олімпіад ніде не використається.

Глава 27 про максимальний потік — теж чисто олімпіадна тема. Ну або ти з кафедри Дослідження Операцій, тільки вони це називають транспортною задачею, але суть та сама.

Глава 28 про сортірующі сєті — єбала, не пригодиться.
Глава 29 про арифметичні схеми — єбала, не пригодиться.
Глава 30 про паралельні алгоритми — тяжко сказати, скоріш єбала чим ні
Глава 31 про матриці — якщо ти не займаєшся МЛ або не сильно шариш лін алгебру, то пропускай — не заціниш і не знатимеш куди тулити.
Глава 32 чомусь відсутня в тій рандомній pdf’ці яку я нагуглив
Глава 33 про теоретико числові алгоритми — скоріш можеш пропустити, хіба що цікаво буде. Мені подобається теорія чисел, я читав :).
Глава 34 про пошук підстрок. От з одної сторони хороша тема, з іншої тут реально можна на довго застрягти — реально важко розбирати алгоритми.
Глава 35 про обчислювальну геометрію можна пропустити, хіба що ти в олімпіади йдеш або чимось з комп графікою займаєшся (і то ...).
Глава 36 про NP-повноту — ну тіпа таке ... корисно знати, щоб розуміти про що народ говорить.
Глава 37 про наближені алгоритми — скоріш не потрбіно. Варто знати що існують наближені алгоритми для тих-то задач, але аналіз можна не читати.

а что-то больше — с трудом

Найбільша користь буде саме з нарішаних задачок. Код стане чистішим 100%.

P.S. А ты заканчивал шад, есть ли смысле сейчас? Учитывая что это два года довольно жесткого обучения?

Закінчив :). Було реально важко, але мені дуже-дуже-дуже сподобалось. По-доброму заздрю москвичам, які були в цій тусовці, а не заочно по відосіках. Я досі час від часу беру звідти курси ... щось давно нічого не брав, але в цьому семестрі точно візьму візьму по розпізнаванню аудіо. Там дуже багато цікавих курсів — хочеться взяти все, але нагрузка дуже велика і приходиться кидати напівдорозі :(.

Відповісти
Підтримати
EA
EA 26.01.2021 09:15

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

Відповісти
Підтримати
Yuriy Znovyak
Yuriy Znovyak РПЗ з ДВРЗ з ВО без ВП і своєю ЖП 26.01.2021 11:17

Якщо під кнутом ти маєш на увазі «Конкретну Математику», то ок. Якщо «Мистецтво Програмування» (TAOCP == The Art Of Computer Programming), то можеш сміло відкласти її до кращих часів. Прото в TAOCP мало потрібних тем, але ті кілька наявних тем настільки нагружені різними фактами, що за деревами не видно лісу. Чимось схоже як би хтось описав що таке 3 («три»). От TAOCP по нагруженості схожий на ось цю статтю вікіпедії: en.wikipedia.org/wiki/3

Тобто якщо добре вмієш програмувати, то без проблем — читай, дізнаєшся багато нового. Але якщо обмежений час, то хотілось би швидше побачити користь, бо інакше легко поневіритись і забити на все це діло.

Відповісти
Підтримати
EA
EA 26.01.2021 11:29

Taocp выглядит очень масштабно, поэтому я ее заменил sicp.

Відповісти
Підтримати
Yuriy Znovyak
De Money 26.01.2021 21:29

Як шанувальник Кормена я хочу сказати, шо подібне розмеження, де там єбала є дуже корисними, бо він таки трішечки TLDR. Я б ще FFT додав до єбали.

Відповісти
Підтримати
Yuriy Znovyak
Yuriy Znovyak РПЗ з ДВРЗ з ВО без ВП і своєю ЖП 26.01.2021 22:05

Не надо — FFT афігенний і дууууже красивий! Мало того, він супер потужний і дуже багато де приміняється. Майже весь аудіопроцесінг на ньому побудований. Завдяки FFT можна дуже легко робити «згортки», і як тільки ти відчуєш цю штуку ти їх бачитимеш повсюду.

Ну от тобі задача: є дві бітові строки: text і pat. Тобі треба знайти такий зсув z, що співпадає максимальна кількість відповідних бітиків в text[z:z+len(pat)] і pat. Наприклад: text = «1011», pat="11«. При z=0 співпадає 1, при z=1 співпадає 1, при z=2 співпадає 2.

З ФФТ це тривіально робиться за O(NlogN), де N = len(text) + len(pat).

Очевидно, що не обов’язково обмежуватись бітовими строками — от нехай у тебе вже є масив значень (аудіо запис), і ти шукаєш в ньому підмасив (інший аудіосигнал), де «ціною» буде сума квадратів різниць. Наприклад:
t = [100, 110, 90, 130, 90]
s = [110, 110]
позиція 0: s=[110, 110] vs [100, 110]; cost=(110-100)^2 + (110-110)^2 = 10^2 + 0 = 100
позиція 1: s=[110, 110] vs [110, 90]; cost=(110-110)^2 + (110-90)^2 = 0 + 20^2 = 400
позиція 2: s=[110, 110] vs [90, 130]; cost=(110-90)^2 + (110-130)^2 = 20^2 + 20^2 = 800
...
це теж робиться за NlogN.

Я в свій час навіть на картинки FFT натягнув був.

Відповісти
Підтримати
De Money
Сергій Машковський C# Developer 01.02.2021 00:18

важлива заувага: ваш «синопсис» на 2 пункти відстає від поданого тут: uk.wikipedia.org/wiki/Вступ_до_алгоритмів

Відповісти
Підтримати
Yuriy Znovyak
Artyom Krivokrisenko 21.02.2021 10:31
Частина 4 про побудову алгоритмів дуже-дуже потрібна. Там про динаміку, жадність і аморт аналіз. Аморт аналіз це те, як зробити щоб push_back/append в масив щоб він працював за О(1) в середньому. Це афігенно корисно знати.

Не думал пока особо, но такой вариант.

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

Если мы вместо копирования будем держать данные в старом блоке, и до-аллоцировать блоки побольше «в конце». Скажем, каждый новый блок в 2 раза больше предыдущего. Блоки, разумеется, не будут физически contiguous.

В итоге данные в массиве будут не одним большим блоком памяти, а несколькими большими.

Предположим, что malloc имеет O(1) времени. Также предположим, что мы за O(1) можем из индекса i вычислить индекс блока, в котором этот i будет лежать (block_index) и оффсет в этом блкое (block_offset). Математика там относительно простая, тогда lookup тоже будет за O(1)

Годится?

Другой вариант, если извратиться, потребует кастомного менеджера памяти и возможность манипулировать страницами.

Условно, резервируем под массив 1 гигабайт виртуальной памяти (или 16 гигабайт — пох, в 64-битном пространстве на всех хватит). Но физически мапим только первые 4 кб. Когда доходим до предела 4КБ — докидываем еще одну страницу в виртуальное пространство и так далее. В продвинутом случае даже никаких проверок не надо писать — когда дойдем до конца страницы, случится page_fault (который нам надо как-то отловить), и мы можем на лето докинуть страницу.

Відповісти
Підтримати
Yuriy Znovyak
Yuriy Znovyak РПЗ з ДВРЗ з ВО без ВП і своєю ЖП 21.02.2021 16:14
Годится?

Хороша спроба, але ніт. Власне задача трохи неправильно поставлена була, бо я не до кінця сказав в якій моделі ми працюємо. Для теоретичного CS якраз прийнято вважати, що ми аналізуємо алгоритми на RAM машинах (en.wikipedia.org/...​iki/Random-access_machine), де немає багатьох екзотичних штук, зокрема вірутальної пам’яті і так далі.

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

Абсолютно правильно.

Если мы вместо копирования будем держать данные в старом блоке, и до-аллоцировать блоки побольше «в конце». Скажем, каждый новый блок в 2 раза больше предыдущего.

Теж все правильно. Головне, що новий блок (!)в(!) X раз більше, а не (!)на(!) X елементів більше. Саме завдяки цьому геметричному росту получається амортизований час роботи O(1).

Блоки, разумеется, не будут физически contiguous.

От тут получається якраз проблема. По-перше ти зробив не вектор — твої елементи більше не йдуть послідовно в пам’яті. Плюс ти втрачаєш можливість робити швикдий lookup за O(1), бо тепер тобі треба дізнатись в який блок йде [ind]. Наприклад vec[0] — 0-ий блок (розміру 2^0==1), vec[1] і vec[2] йдуть в 1-ий блок (розміру 2^1==2), vec[3]..vec[6] — 2-ий блок (розміру 2^2==4), vec[k] — log2(k+1)-ий блок. Але навіть тут 2 проблеми:
(1). log2() не так то легко і взяти
(2). ти робиш ще один indirection, тобто тобі треба data[block_ind][new_ind_within_block].

(1) можна обійти. Власне тобі треба не чесний log2(), а тільки цілу частину від лог2, при тому, що береться лог2 від теж цілого числа. Власне це дає тобі можливість заюзати багато різни трюків, найкращий з яких — процесорну команду LZCNT (leading zero count == порахувати кількість ведущих нулів, в gcc робиться через __builtin_clz; en.wikipedia.org/...​iki/SSE4#POPCNT_and_LZCNT). Але це трохи халтура.

А от (2) це вже «погано» — воно буде сильно повільніше за класичний вектор.

Предположим, что malloc имеет O(1) времени.

Угу, тут це дійсно обов’язкове припущення. Без нього далеко не заїдеш :).

Другой вариант, если извратиться, потребует кастомного менеджера памяти и возможность манипулировать страницами.

Це вже зовсім окрема розмова. Хоча ти правильно підмітив — ми тут говоримо про «вектор», але насправді це афігенно leaky abstraction, бо ми відкидуємо львину долю архітектури компів, вважаємо, що у нас є афігенний malloc, який працює за O(1), ... Тобто да, стандартний вектор це реалізація спрощеного вектора з любої книжки по CompSci... Відповідно, очевидно, можна вижати ще трохи швидкості, які трохи заглибитись в деталі. Зокрема глянь FBVector з facebook’ової folly: github.com/...​er/folly/docs/FBVector.md

Власне ось мінімальна реалізація класичного вектора (соррі, якщо є баги, бо писав браузері):

template<typename T>
struct Vec {
  int size, cap;
  T* data;
  Vec() {
    data = new T[1];
    size = 0;
    cap = 1;
  }

  void push_back(const T& e) {
    if (size == cap) {
      T* new_data = new T[cap*2];  // вважаємо, що new повертає неініціалізовану пам'ять за O(1).
      for (int i = 0; i < size; i++)  // проблема із-за цього циклу
        new_data[i] = data[i];  
      delete data;  // вважаємо, що delete теж за O(1).
      data = new_data;
      cap *= 2;
    }
    data[size] = e;
    size++;
  }

  T get(int ind) { return data[ind]; }
};

Власне в аморт аналізі є так званий accounting method, який дозволяє рахувати амортизований час роботи + з нього практично зразу видно те, як деамортизувати структуру даних (щоб в гіршому випадку було за O(1)). Відповідно деамортизація виглядає так (я прогнав через rot13.com/)

grzcyngr<glcranzr G>
fgehpg Irp {
  vag fvmr, pnc, ahz_pbcvrq;
  G* qngn, arkg_qngn;

  Irp() {
    qngn = arj G[1];
    arkg_qngn = arj G[2];
    fvmr = 0;
    pnc = 1;
    ahz_pbcvrq = 0; // arkg_qngn[:ahz_pbcvrq] == qngn[:ahz_pbcvrq]
  }

  ibvq chfu_onpx(pbafg G& r) {
    vs (fvmr == pnc) { // nyy snfg abj!
      qryrgr qngn;
      qngn = arkg_qngn;
      arkg_qngn = arj G[pnc*4];
      pnc *= 2;
      ahz_pbcvrq = 0;
    }
    qngn[fvmr] = r;
    fvmr++;

    // pbcl 2 sebz qngn gb arkg_qngn -- qrnzbegvmngvba unccraf urer.
    arkg_qngn[ahz_pbcvrq] = qngn[ahz_pbcvrq];
    ahz_pbcvrq++;
    arkg_qngn[ahz_pbcvrq] = qngn[ahz_pbcvrq];
    ahz_pbcvrq++;
  }

  G trg(vag vaq) { erghea qngn[vaq]; }
};
Очевидно, що тут все менш оптимально ніж в амортизованому варіанті. Але така ціна за O(1) в гіршому випадку :).

Якщо любиш класичні CS задачі на структури даних, то спробуй ще рішити такі:

  1. Як зробити вектор, з якого можна pop_back() і щоб він ніколи не займав більше ніж O(n) додаткової пам’яті. Тобто в класичному векторі можна зробити багато разів pop_back(), але, на жаль, cap/size не обмежена (говоримо про size>0, звісно). Хочеться щоб було обмежено :-).
  2. Реалізуй чергу (структуру даних, яка вміє робити enqueue(x) і deque() -> x), через стек (структуру даних, яка вміє робити push(x) і pop() -> x за O(1)). Треба щоб enqueue і deque були за O(1) в середньому (тобто амортизовано).
  3. (З зірочкою) Деамортизуй чергу з попередньої задачі. Тобто щоб операції були за O(1) в гіршому випадку.
  4. Реалізуй deque за допомогою стеків.
  5. Реалізуй C++’овий deque (www.cplusplus.com/reference/deque/deque в C++). То ж саме, що і вектор, тільки ще можна push_front() і pop_front(). Треба за O(1) (аморт, не в гіршому випаку), звісно.
Відповісти
Підтримати
Artyom Krivokrisenko
Artyom Krivokrisenko 22.02.2021 09:18
От тут получається якраз проблема. По-перше ти зробив не вектор — твої елементи більше не йдуть послідовно в пам’яті.

Похоже, это фишка std::vector, согласно которой элементы должны идти подряд в памяти:

The elements are stored contiguously, which means that elements can be accessed not only through iterators, but also using offsets to regular pointers to elements. This means that a pointer to an element of a vector may be passed to any function that expects a pointer to an element of an array.

Например, в Rust таких гарантий не дается, поэтому можно что-то химичить.

Если же пилить drop-in replacement для std::vector, то нужно учитывать другой момент — там [] возвращает mutable reference на элемент, а не сам элемент. Это значит, что элемент можно будет изменять (при условии если не произошел ресайз внутреннего буфера данных, тогда ссылка будет недействительна).

В варианте, предложенном вами, как я понимаю, такую штуку не реализовать, так как каждый элемент находится в двух местах (data и data_new), и в определенный момент мы переключаемся из одного в другое. Если какие-то изменения были сделаны в data до того, как элемент был скопирован в data_new, они будут потеряны.

Можно извратиться и сделать чтоб присвоение работало для примитивных типов, но для сложных типов я не представляю как в С++ это реализовать (я только начал С++ учить, поэтому могу каких-то моментов пока не знать)

Відповісти
Підтримати
Yuriy Znovyak
Yuriy Znovyak РПЗ з ДВРЗ з ВО без ВП і своєю ЖП 24.02.2021 00:42
можно что-то химичить.

Ну основна штука вектора в тому, що він швидкий — такий же, як і native пам’ять. А чим більше ти логіки навісиш на оператор [], тим повільніше воно працюватиме.

Если же пилить drop-in replacement для std::vector, то нужно учитывать другой момент — там [] возвращает mutable reference на элемент, а не сам элемент.

Ох бля ... внатурі. Я навіть якось не подумав про це... І проксями тут не обійдешся :(.

В варианте, предложенном вами
вами

Ух ... нарешті дійшло що мене муляє — звертання на «ви» замість «ти». Якось на «ви» підрозумиває різний соц. рівень, а на «ти» якось ... щиріше (?).

Відповісти
Підтримати
Artyom Krivokrisenko
Artyom Krivokrisenko 24.02.2021 10:21
Ох бля ... внатурі. Я навіть якось не подумав про це... І проксями тут не обійдешся :(.

После года с лишним на Rust я такую фигню начал спинным мозгом чувствовать :)

Відповісти
Підтримати
Yuriy Znovyak
Yuriy Znovyak РПЗ з ДВРЗ з ВО без ВП і своєю ЖП 26.01.2021 07:33

У Річарда Фейнмана є шикарна цитата «If you cannot explain something in simple terms, you don’t understand it». Найдієвіший спосіб досконально розібратись як щось працює це реалізувати самому з основних принципів — комп’ютер не обманеш.

Реально прикольно написати якийсь код, який відтворює якийсь формат файлів. BMP просто, GIF складніше, JPEG ще складніше. mp3 -> wav. Можна розібратись що саме знаходиться в .exe файлі (або elf в лінуксі, Mach-O в маку). Можна установити TCP або SSL коннекшен вручну, тобто самому сформувати пакети. Можна реалізувати емулятор якогось старого процесора. Можна написати простенький інтерпритатор якоїсь своєї простенької мови. Компілятор асемблера афігеть як прикольно.

В математиці те ж саме — можна роками вчити формулу дискримінанту квадратного рівняння, але якщо ти не знає звідки він береться, то це до сраки. І навпаки, якщо знаєш звідки він береться, то вивести його буде просто.

Відповісти
Підтримати
Yuriy Znovyak
Tymchyshyn Vitalii Researcher 27.01.2021 01:57
Скільки буде 1^2 + 2^2 + 3^2 + ... + n^2? та обмеж зверху x^2, візьми і візьми інтеграл від 0 до n і матимеш приблизну оцінку в 1/3 n^3

а в мене одразу рука тягнеться писати генератрису ))

Відповісти
Підтримати
Yuriy Znovyak
Олексій Пєніє 26.01.2021 01:05

Коментар порушує правила спільноти і видалений модераторами.

Yuriy Znovyak РПЗ з ДВРЗ з ВО без ВП і своєю ЖП 26.01.2021 06:50

Коментар порушує правила спільноти і видалений модераторами.

Олексій Пєніє 26.01.2021 11:31

Коментар порушує правила спільноти і видалений модераторами.

EA 26.01.2021 11:35

Коментар порушує правила спільноти і видалений модераторами.

EA 26.01.2021 07:20

Коментар порушує правила спільноти і видалений модераторами.

Олексій Пєніє 26.01.2021 10:45

Коментар порушує правила спільноти і видалений модераторами.

EA 26.01.2021 11:02

Коментар порушує правила спільноти і видалений модераторами.

Tymchyshyn Vitalii Researcher 26.01.2021 00:30
не впадать в ступор от постов юры зновяка

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

Відповісти
Підтримати
EA 26.01.2021 07:09

Ну у меня болеее конкретное направление — разобраться в алгоритмах и архитектуре. Потом может еще какую-то теорию информации поучу

Відповісти
Підтримати
Tymchyshyn Vitalii
Дон 26.01.2021 00:03

Коментар порушує правила спільноти і видалений модераторами.

Олексій Пєніє 26.01.2021 01:07

Коментар порушує правила спільноти і видалений модераторами.

Андрей Осипов 25.01.2021 23:49
работаю в лидерах рынка, зп в топе рейтинга (не 10к, но рядом), так что деньги не причина. 30 еще нет

никогда такого не было и вот опять

Відповісти
Підтримати

Підписатись на коментарі

Не підписуватись
Скористайтесь акаунтом
×
з умовами використання сайту і політикою конфіденційності.