Так же, как есть кэш, забывающий и кеширующий оптимальные алгоритмы, есть ли поиск оптимальных алгоритмов?
Кэш-алгоритмы (не обращая внимания | оптимальные | осведомленные) обычно учитывают время поиска в своей модели. Если нет, то есть примеры моделей, которые учитывают время поиска, и есть ли анализ алгоритмов в этой модели.
1 ответ
Да, я лично написал поиск чувствительных алгоритмов. Файловые системы, безусловно, используют структуры данных, чувствительные к поиску (которые аналогичны алгоритмам).
Например, NTFS (и многие другие файловые системы) хранят данные в формате B-дерева, чтобы минимизировать поиск и оптимизировать для последовательного чтения.
К сожалению, вы задаете этот вопрос в 2014 году, когда твердотельные накопители и другие технологии находятся на грани полного замещения вращающихся носителей. Твердотельные накопители подвергаются некоторому штрафу за поиск, но они могут обрабатывать десятки тысяч запросов в секунду по сравнению с вращающимися жесткими дисками, которые, вероятно, не могут обрабатывать даже 100 запросов в секунду. Это заставляет искать гораздо меньше проблем, чем в прошлые годы.
Аналогичная и более актуальная проблема - когерентность строк кэша на процессоре. Скорость оперативной памяти не поспевает за скоростью процессора, а многоядерные процессоры сделали NUMA реальной проблемой производительности. Чтобы оптимизировать производительность, многие реализации алгоритмов вынуждены использовать как можно меньше памяти и использовать соседнюю память чаще, чем удаленную.
Например, структура данных кучи гораздо более дружественна кешу, чем дерево. Чувствительный к производительности код выберет использование кучи над деревьями, когда это практичный выбор.
Эта проблема с кешем была главной проблемой производительности, по крайней мере, в последнее десятилетие. Почти все нетривиальные программы работают быстрее, когда их оптимизируют по размеру, а не по скорости, и причиной является потеря кэша.