Оптимизировать проверку префиксов строк при переборе файла - PullRequest
Новая
       62

Оптимизировать проверку префиксов строк при переборе файла

0 голосов
/ 08 ноября 2019

Я пишу сценарий в форме 

while read LINE 
do
    [[ $LINE =~ ^headertag1 ]] && function1 && continue
    [[ $LINE =~ ^headertag2 ]] && function2 && continue
    ...
done < filename

По мере увеличения количества тегов я буду делать слишком много проверок на строку. Я могу попытаться отсортировать общие теги выше, но я не думаю, что это решает фундаментальную проблему. Я не инженер-программист. Существуют ли концепции / методы программирования, которые могут улучшить эту ситуацию?

Ответы [ 3 ]

1 голос
/ 08 ноября 2019

Тест, который вы выполняете для каждого тега 

    [[ $LINE =~ ^headertag1 ]] && function1 && continue

Чрезвычайно дешево (в регулярном выражении памяти. Скорее всего, это займет часть времени ввода-вывода, связанного с чтением LINE (из файла илидругой процесс.) Если вы не выполняете тест большое количество раз, эта реализация является разумной.

Примечание о стиле: Если все шаблоны совпадают с префиксами (или другими простыми конструкциями), рассмотритеиспользование bash оператора case 

case "$LINE" in
   header1*) function1 ;;
   header2*) function2 ;;
   ...
esac

Это сделает код более элегантным, но не изменит производительность - RE и подстановочный знак просты.

1 голос
/ 08 ноября 2019

Не уверен, что здесь, но если вы ищете, чтобы привести в порядок свой код и вам скучно, добавляя его, если охрана повторяется, то, возможно, эта идея поможет: 

#!/bin/bash

tags[tag1]="some regex1"
tags[tag2]="some regex2"
tags[tag3]="some regex3"

function action() {
  echo "perl -pe '${tags[$tag]} other-file.txt'"
}

while read LINE; do
  for tag in "${!tags[@]}"; do
    [[ $LINE =~ ^$tag ]] && action "${tags[$tag]}"
  done
done < filename

Не уверен, что ОП спрашивает что-токак это.

1 голос
/ 08 ноября 2019

Да, для двоих вы можете сначала найти самый длинный общий префикс обоих (здесь люди задались вопросом, как это сделать в Bash Самый длинный общий префикс двух строк в bash ), а затем сначала проверить, соответствуют ли строкиначните с него, а затем, удалив его из тега и строки, проверьте, начинаются ли строки с остального.

Для более чем двух вам нужно создать дерево, также известное как дерево префиксовhttps://en.wikipedia.org/wiki/Trie.

Эта статья в Википедии гласит:

Для оптимизированного по пространству представления дерева префиксов см. Дерево компактных префиксов .

И имея самые длинные общие префиксы, это то, что вы будете иметь.

Поскольку Bash не имеет многомерных ассоциативных массивов, вам придется либо учитывать https://en.wikipedia.org/wiki/Trie#Implementation_strategies, либо встраивать какой-либо другой язык сценариев, например Perl или Python, или GNU Awk (gawk), который, в отличие от стандартного Awk, вводит многомерный ассоциативныймассивs .

Использование оптимизации реализации ассоциативных массивов Bash

Как предлагается в comment , мы можем рассмотреть возможность взять только тег с более простым регулярным выражением и использовать егов качестве ключа для ассоциативного массива, который несколько оптимизирован в Bash (мы можем выяснить, насколько хорошо он подходит для наших нужд в источниках:

, если мы знаем, что это ограничено - как, , если мы знаем, что за ним всегда сразу следует : или что-то , когда его не содержится, и используется более простое регулярное выражение, например: 

[[ $LINE =~ ^(.*): ]] && "${DICTIONARY_OF_FUNCTIONS["${BASH_REMATCH[1]}"]}"

или Использование оптимизации Bash'sфункции хранят

, если все ваши теги похожи, /[a-z][a-z0-9]+/ или иным образом приняты Bash в качестве имен функций и разграничены, как в методе с ассоциативными массивами Bash, то вы можете использовать вышеуказанный метод для интерполяции имен функций,как, 

function the_function_for_tag_headertag1() {
    echo "hey it's the first one"
}
[[ $LINE =! ^(.*): ]] && {
    func_name="the_function_for_tag_${BASH_REMATCH[1]}"
    type "${func_name}" && "${func_name}"
}
...