Комментарии 29
Я ГА не читал, но пробовал читать Кнута - и когда учился на младших курсах в универе, и в аспирантуре, и когда наяривал литкод для прохождения технических интервью. И каждый раз это был очень плохой опыт, книги очень тяжело читать, и этот псевдокод еще очень странный и далёкий от современного программирования.
При всём уважении к этому фундаментальному справочнику, это очень плохой учебник и плохой материал для подготовки к интервью, мне кажется его некорректно сравнивать с настоящими учебниками.
А что бы вы посоветовали?
Как учебник - Algorithm Design (John Kleinberg, Éva Tardos), для подготовки к интервью - Elements of Programming Interviews, как справочник - Кормена.
Algorithms от Sedgewick'а (с вполне практичными примерами на Java)
Classic Computer Science Problems in Python (тоже практичней некуда, еще и владение Python'ом подкачаете)
Algorithms Design Manual от Skiena (имхо, одна из самых популярных рекомендаций в FAANG'ах)
и этот псевдокод еще очень странный и далёкий от современного программирования
Да эти примеры кода далеки от того, что каждый из нас увидит в коде коллеги или напишет сам. Но есть у такого подхода и преимущество. Во-первых, он позволяет точнее оценить стоимость алгоритма и, например, сравнить два алгоритма с одинаковой асимптотикой. У Кнута много таких примеров, где изначальный алгоритм оптимизируется и показывается за счет чего и на сколько именно получен выигрыш. Такая возможность появляется как раз благодаря тому, что код написан на машинном языке и хорошо видно сколько чего выполняется. Во-вторых, при таком подходе невозможна магия. Рукава закатаны и все прекрасно видно. Никаких допущений, что язык или библиотека, что-то сделали, а ты об этом не рассказал. Два примера. В том же ГА при описании быстрой сортировки приведен вот такой код:
return quicksort(less) + [pivot] + quicksort(greater)Код работает правильно, все понятно, все приближено к современной реальности. Но за этой простотой и понятностью скрываются циклы и копирования. Эффективность такой реализации сомнительна. Второй пример: в Алгоритмике при объяснении метода двух указателей на примере сортировки слиянием можно увидеть вот такой код:
merge(v.begin() + l, v.begin() + mid, v.begin() + mid, v.begin() + r, c.begin());Не изучавшему STL будет сложно понять, что это std::merge из C++ и что тут на самом деле цикл и внутри него if, копирование и инкремент одного из двух указателей. Код короткий и хорошо понятный опытному C++ разработчику. Но для всех других такая высокоуровневость скорее помешает понять алгоритм.
Я не буду утверждать, что код у Кнута хорошо читается и переводится на нормальные языки. Но мое мнение, что не в этом его цель. Для понимания алгоритма у Кнута к каждой программе сначала идет пошаговое текстовое описание на человеческом языке и иллюстрация.
Но я соглашусь. Текст тяжелый, половина книг - упражнения и решения к ним. Это совсем не тоже, что каталог для практиков как у GoF.
Согласен, начинать учить программирование по Кнуту - смерти подобно, это то же что рекомендовать начинать изучение теорвера - по Ширяеву, физики - по Ландау-Лифшицу. Да есть немногие гении, кому это зайдет с самого начала, для всех остальных - это скорее отобъет всякое желание изучать что-то дальше. Цель образования - зажечь любопытство - все остальное уже дело времени.
Уже обсуждалась эта книга неоднократно на хабре. Мнения 50/50. Я бы не назвал это "Профессиональной литературой". Подтвержу слова статьи, что во второй половине книги автор перестает "грокать" и начинает "плавать". Это наводит на мысль, что глубоко изучать сложные алгоритмы все равно придется по другой литературе.
@nikolaysmartynovты пишешь "хотелось бы каталога алгоритмов". На мой взгляд монография Donald E. Knuth "The Art of Computer Programming" остается наилучшим вариантом. Другой вопрос, что это не публицистика, а научный труд, который читать - труд не меньший :)
В своем комментарии https://habr.com/ru/post/439576/comments/#comment_19802200 я отмечал, что иначально Grokking Algorithms была выпущена с большим количеством ошибок, и перевод ситуацию только ухудшил. Некоторые исправления автор разместил тут: https://adit.io/errata.html , я нашел еще несколько ошибок, сообщил автору, но в errata правки пока не появились.
ты пишешь "хотелось бы каталога алгоритмов". На мой взгляд монография Donald E. Knuth "The Art of Computer Programming" остается наилучшим вариантом.
К сожалению на русском можно купить только первые три тома. Четвертый том не найти. Остальные и вовсе не переводились. А похоже именно там комбинаторика, статистические методы, NP-полные задачи и т.п. По крайней мере этого нет в первых трех томах. Можно конечно и в электронном, и на английском почитать, но это не совсем то.
Еще стоит упомянуть, что за эти три тома придётся выложить пол зарплаты....
На озоне электронные версии вполне вменяемых денег стоят (по 1500 за том) https://www.ozon.ru/product/iskusstvo-programmirovaniya-tom-1-osnovnye-algoritmy-148568216/?sh=taJR1JgKXg
разумеется бумажные версии стоят уже космических денег (не понимаю правда почему), но это, думаю, вполне себе достойная альтернатива
Для тех, кто действительно будет это читать, выучить английский - не самая большая проблема, для всех остальных - это лишь будет макулатура на полке.
Так ведь, четвертый том Кнут таки и не закончил (и, наверное, уже не закончит никогда). А "остальных" и вовсе не существует в природе.
А в скиллбоксе не знаешь какие книги рекомендуют? В списке литературы для поступления в шад, не видел такой книги.
Не могу сказать, ибо не знаю. Но видимо, там рекомендуют какую-то более серьезную литературу. Возможно, что-то что перечислил HotkeyM или SibProgrammer.
Книжка "Грокаем алгоритмы" - точно не учебник. Простоватая, мне не зашла. Как-то все скользко, мутно. Все книги про алгоритмы делятся на 2-е части или заумные вроде Кнута, например, где ты с 20 страницы понимаешь, что ты ничего не понимаешь или простые до нельзя, вот как эта, что-то типа алгоритмы в комиксах, где вроде бы все понятно, но ничего не ясно. А вот "золотой середины" по книгам здесь очень мало.
Я бы порекомендовал Ананий Левитин "Алгоритмы: введение в разработку и анализ" мне очень понравилась. Просто о сложном. Я бы даже бумажный экземпляр купил, может кто подскажет где?
Jon Kleinberg, Eva Tardos Algorithm design
Роберт Седжвик, фундаментальные алгоритмы на c++
Обе есть на русском , читабельные , понятные
Если честно, название и описание этой книги очень сильно вводит в заблуждение. Мне ее рекомендовал один из преподавателей практикума, словами вроде "Позволит намного лучше понять и разобраться в алгоритмах в целом". И когда я её покупал, думал о том что там будут какие то хитрые алгоритмы, досканальный разбор, может придется вспомнить универский матан, но нет. Как чтение для совсем новичков имхо - очень даже. Но чтобы вот "грокаем" - ну точно нет.
Если английский — не проблема, то у Introduction to algorithms недавно вышло 4 издание. На русский переведено пока только третье, но кардинальных отличий нет. Динамическое программирование там есть :)
ГА хороша именно что для первичного ознакомления с алгоритмами
Ух. Когда-то книжка дала базу для олимпиад по информатике. Не то чтобы я сразу научился во все таски, но понял, что даже сложные алгоритмы могут быть простыми и понятными при должном подходе, после чего стал искать для всех непонятных действий такие объяснения. Простые, может даже глупые, но которые работают. И как-то пошло)
Если вы в районе нуля, это хорошая отправная точка. Хотя бы понять зачем это и как.
Возможно, алгоритмы `Aditya Y. Bhargava` не самые быстрые, да и изучил я треть от книги. Но! Все приведенные примеры ГА рабочие, на их основе я создал свою реализацию. Для тестов прошу ознакомиться с моим репозиторием github. https://github.com/DamianMorozov/Console.GrokkingAlgorithms
После чего, прошу привести конкретные тесты на замер сравнения производительности вашей реализации и моей (полностью основанной на исходных кодах ГА).
Если лень делать тесты, скидывайте ссылку на свой репо с вашей реализацией, я найду время сравнить производительность.
- Тест 1. Сортируем массивы.
- Тест 2. Сортируем списки.
- Тест 3. Сортируем файлы со строками.
прошу привести конкретные тесты на замер сравнения производительности вашей реализации и моей (полностью основанной на исходных кодах ГА)
Если обе реализации основаны на алгоритме, который в книге, то нет смысла что-то сравнивать. Одно дело взять реализацию варианта быстрой сортировки выбором с обменом и сравнить с реализацией варианта быстрой сортировки расщеплением, а потом сравнить потребление памяти и времени и глубину стека. А так что мы будем сравнивать? Кто сколько наоптимизировал отойдя от того, что есть в книге?
скидывайте ссылку на свой репо с вашей реализацией
Ссылка дана в конце статьи.
Все приведенные примеры ГА рабочие, на их основе я создал свою реализацию
Ключевая часть "на их основе я создал свою реализацию". А вот с "Все приведенные примеры ГА рабочие" есть проблемы. Например, в главе 9 есть пример с самой длинной общей подпоследовательностью двух строк. Автор берет слова с одинаковым количеством букв, причем первые буквы совпадают. Это очень удобно, так как не надо думать о начальных условиях и тому подобном. На практике, приведенный в книге код легко выйдет за левую и верхнюю границы. Это никак не учитывается при обращении к предыдущей строке/ячейке. Ровно также из ниоткуда появляется значение первой ячейки.
if word_a[i] == word_b[j]:
cell[i][j] = cell[i-1][j-1] + 1
else:
cell[i][j] = max(cell[i-1][j], cell[i][j-1]) Ссылка дана в конце статьи.
Не могу понять в вашем репо, примеры использования алгоритмов.
Не могу понять в вашем репо, примеры использования алгоритмов.
Примеры использования можно найти в тестах. Для Java использован Spock, а для C++ - CUnit.
Например, задача оптимизации туристического рюкзака из 9-й главы
def "9.2"() {
given:
Map<String, Ex_9.ItemInfo> inventory = [water : new Ex_9.ItemInfo(10.0, 3),
book : new Ex_9.ItemInfo(3.0, 1),
food : new Ex_9.ItemInfo(9.0, 2),
jacket: new Ex_9.ItemInfo(5.0, 2),
camera: new Ex_9.ItemInfo(6.0, 1),]
int bagSize = 6
when:
Set<String> result = new Ex_9().optimizeBagDynamic(inventory, bagSize)
then:
result ==~ ['water', 'food', 'camera']
}
Здравствуйте, дорогие первоклассники! Поскольку учебники по математики имеют мало общего с тем что вам пригодится во взрослой жизни, мы не будем их читать. Начнем пожалуй с мат. анализа. Вот прекрасная книга для студентов вузов. Итак начнем.. Интеграл от икс по дэикс... Итак далее
Грокаем алгоритмы