Утилиты Unix, такие как sort, find, grep, diff и др., Очень удобны для выполнения быстрых задач, иногда вообще без написания кода.
Я хотел знать, какие алгоритмы они используют внутри и как разумно выбрать конкретный алгоритм для конкретной задачи? Например, если сортировка получает огромный входной файл, будут ли она использовать разные алгоритмы для разных размеров данных?
Разумно ли переключается grep при поиске различных наборов данных?
text-processing
grep
sort
coreutils
Kamaal
источник
источник
grep
,egrep
илиfgrep
.Ответы:
Unix - это просто стандарт, он определяет, что должны делать реализации, а не как они должны это делать.
Поэтому реализации grep / sort / find, скорее всего, будут использовать разные подходы в разных системах (и даже в одной системе, например в Linux, есть параллельные реализации).
Для Linux вы всегда можете заглянуть в исходный код.
источник
Вас может заинтересовать это сообщение в списке рассылки, написанное автором GNU grep, которое объясняет некоторые из оптимизаций GNU grep. Еще одно приятное исследование от ridiculous_fish (автора Hex Fiend)
источник
Стандарт UNIX не определяет детали реализации стандартных системных инструментов, за исключением действительно редких случаев. Вы можете найти последнюю версию Single Unix Specification здесь (предупреждение: требуется регистрация).
Имея это в виду, каждая UNIX (System V и прямые потомки, такие как BSD, Solaris, Mac OS X и т. Д.) Или операционная система на основе UNIX (далёкие потомки или аналогичные: Linux, Minix) имеют свои собственные реализации утилит, описанных в спецификация UNIX. Например, взгляните на FreeBSD и Linux / GNU Coreutils . Помните, что некоторые инструменты представляют собой отдельный проект, например, GNU diff или GNU grep . Кроме того, еще один факт заключается в том, что некоторые реализации этих инструментов могут найти дорогу в других UNIX-подобных системах в качестве стандартных, чем те, для которых они были изначально написаны, например, для некоторых gnu coreutils в freebsd или GCC.
Бонус: чтобы обернуть голову вокруг семейного древа UNIX, взгляните на этот график .
источник
Это интересный вопрос (+1 за это). Я понятия не имею, каков ответ, но на вашем месте я бы посмотрел исходный код типичных утилит GNU, чтобы получить представление об их алгоритмах.
Я так не думаю. Не цитируйте меня, так как я не могу сказать вам со 100% уверенностью, но я действительно так не думаю. Философия вещей UNIX заключается в том, что одна вещь делает одну вещь и только одну вещь. Вот почему у нас есть несколько версий Grep (
grep
,egrep
,fgrep
).Кроме того, идея состоит в том, чтобы делать одно и только одно во время выполнения. Разное поведение и алгоритмы могут быть настроены в качестве аргументов командной строки, так что одна и та же программа может действовать немного по-разному (и, возможно, немного более оптимизировано) между запусками. Хорошие примеры являются
wc
иdiff
командой.Однако поведенческая адаптация основана на конфигурации (через аргументы строки cmd); они не меняют / не адаптируют поведение во время выполнения. Как правило, это ненужная сложность для типа артефактов, к которым стремятся инструменты UNIX.
Такая сложность больше подходит для более сложных, менее универсальных инструментов IMO.
источник
Я так не думаю, но он переключается на «быстрый» не-RE алгоритм, когда ему присваивается флаг -f (или он вызывается как fgrep).
источник