Все любят смеяться над новичками, которые норовят придумать свой уникальный алгоритм или хэш со сложностью доступа O(n) в лучшем случае (true story!). Однако бывает, что мозг далеко уже не младших программистов порождает нежизнеспособных колченогих уродцев, которые значительно хуже существующих аналогов. А остановить их некому. Поэтому на этой неделе я сделаю несколько постов про алгоритмы и структуры данных, которые не входят в стандартный курс по программированию. Это не какие-то передовые достижения науки, да и информацию по ним по всем можно легко найти в Интернете. Но если не знаешь, что именно искать, то можно так никогда и не найти.Updated 24.08.2010
В рамках недели были рассмотрены следующие темы
Расстояние Левенштейна
Фильтр Блума
Красно-черные деревья
Развернутые списки
Списки с одновременным доступом Тима Брея
И бонус с дружественного блога Поиск подстроки в строке: алгоритм Кнута-Морриса-Пратта
Ссылки по теме:
What should be in your programming toolbox?
5 more essentials for your programming toolbox
Programmer’s Toolbox Part 3: Consistent Hashing. Об этом же на русском Консистентные хэши (Consistent hashing)
А что считается стандартным курсом по программированию?
ОтветитьУдалитьДмитрий Scriptin
ОтветитьУдалитьА что считается стандартным курсом по программированию?
Это не какой-то формальный термин. Просто пообщавшись с выпускниками различных вузов я примерно представляю чего там дают, а что нет. Например, двоичные деревья дают всем, но про красно-черные не рассказывают.
Я целиком и полностью "за" такое начинание :) Очень-очень хорошая идея.
ОтветитьУдалитьЯ совсем недавно на похожую тему писал - Stop rolling your own CSV parser. Велосипедизм не всегда плохая идея. Не обращайте внимание на заголовок - мы таки написал свой парсер :)
ОтветитьУдалитьКонечно, в области алгоритмов многое уже давно сказано. И, конечно, существующие алгоритмы неплохо знать, поэтому цикл статей будет полезен (хотя есть примеры, когда это мешает - об этом ниже).
Но когда стоит вопрос - взять готовое решение, которое немного не подходит, или написать свое, идеально подходящее для своей уникальной задачи, - то опытным разработчикам стоит хорошо подумать.
И, напоследок, история из General Electric. C 1930х новым инженерам GE ставилась задача - изобрести покрытие для лампочки без зоны перегрева. Знающие тихонько хихикали, потому что решения этой задаче не было. До 1952 года, когда один из новичков таки не придумал эту лампочку.
Вспомнил одну историю из своего школьного детства.
ОтветитьУдалитьСидел я как-то дома и выдумывал какой-то алгоритм из комбинаторики. Кажется, это был подсчет перестановок заданной длины или что-то в этом духе.
Так вот, путем перебора для небольших чисел я установил, что алгоритм работает. Сложно сказать, был ли алгоритм полностью верный.
А соль истории в том, что тогда я даже не знал про комбинаторику и про алгоритмы вообще, действовал чисто интуитивно, исправляя найденные ошибки. Я даже о факториале не знал, действовал сложением и умножением.
Вот такой был мой первый велосипед. Жаль, что не записал тогда.
А вот полезная ссылочка: Список алгоримтов (англ.)
вот список "самых важных" CS алгоритмов The Most Important Algorithmsудивительно, что о очень многих я даже не слышал.
ОтветитьУдалитьСпасибо Alena буду сильно рад если вы продолжите эту борьбу с велосипедами и танками.
ОтветитьУдалитьПочему на фото палец вверх? Аллах акбар?
ОтветитьУдалить2scoder.by
ОтветитьУдалить>мы таки написал свой парсер :) < C русским языка таки совсем плохая,да?
>Почему на фото палец вверх? Аллах акбар?<+1+1.
Анонимный
ОтветитьУдалитьПочему на фото палец вверх? Аллах акбар?
Иногда палец - это просто палец...
Hashtables: hashtables are arguably the single most important data structure known to mankind. You absolutely have to know how they work. Again, it's like one chapter in one data structures book, so just go read about them. You should be able to implement one using only arrays in your favorite language, in about the space of one interview.
ОтветитьУдалить(c) Cool Google Employee
Красно-черные деревья дают в вузах. С плохими студентами вы общаетесь.
ОтветитьУдалитьПодтверждаю, красно черные деревья преподаются. Вопрос конечно в качестве преподавания...
ОтветитьУдалитьДобрый день Алёна, в рамках борьбы с антивелосипедистами, начал вести свой блок. Если интересно чем плох STL, то почитайте.
ОтветитьУдалитьhttp://y-engine.blogspot.com/