Контекст:
У меня есть редактор кода/текста, который я пытаюсь оптимизировать. На данный момент узким местом программы является языковой парсер, который сканирует все ключевые слова (их больше одного, но пишутся они в целом одинаково).
На моем компьютере редактор задерживает файлы примерно на 1,000,000 строк кода. На младших компьютерах, таких как Raspberry Pi, задержка начинается намного раньше (точно не помню, но думаю около 10,000 строк кода). И хотя я никогда не видел документов размером более 1,000,000 строк кода, я уверен, что они там есть, и я хочу, чтобы моя программа могла их редактировать.
Вопрос:
Это приводит меня к вопросу: какой самый быстрый способ найти список слов в большой динамической строке?
Вот некоторая информация, которая может повлиять на разработку алгоритма:
- ключевые слова
- уточняющие символы, которые могут быть частью ключевого слова (я называю их квалификаторами)
- большая строка
Решение узкого места:
Это (примерно) метод, который я сейчас использую для разбора строк:
// this is just an example, not an excerpt
// I haven't compiled this, I'm just writing it to
// illustrate how I'm currently parsing strings
struct tokens * scantokens (char * string, char ** tokens, int tcount){
int result = 0;
struct tokens * tks = tokens_init ();
for (int i = 0; string[i]; i++){
// qualifiers for C are: a-z, A-Z, 0-9, and underscore
// if it isn't a qualifier, skip it
while (isnotqualifier (string[i])) i++;
for (int j = 0; j < tcount; j++){
// returns 0 for no match
// returns the length of the keyword if they match
result = string_compare (&string[i], tokens[j]);
if (result > 0){ // if the string matches
token_push (tks, i, i + result); // add the token
// token_push (data_struct, where_it_begins, where_it_ends)
break;
}
}
if (result > 0){
i += result;
} else {
// skip to the next non-qualifier
// then skip to the beginning of the next qualifier
/* ie, go from:
'some_id + sizeof (int)'
^
to here:
'some_id + sizeof (int)'
^
*/
}
}
if (!tks->len){
free (tks);
return 0;
} else return tks;
}
Возможные решения:
Контекстные решения:
Я рассматриваю следующее:
Отсканируйте большую строку один раз и добавьте функцию для оценки/настройки маркеров токенов каждый раз, когда пользователь вводит данные (вместо повторного сканирования всего документа снова и снова). Я ожидаю, что это устранит узкое место, потому что синтаксический анализ требует намного меньше. Но это не исправляет программу полностью, потому что начальное сканирование может занять очень много времени.
Оптимизировать алгоритм сканирования токенов (см. ниже)
Я также рассмотрел, но отклонил следующие оптимизации:
- Сканирование кода, который только на экране. Хотя это устранило бы узкое место, это ограничило бы возможность поиска определяемых пользователем токенов (т. е. имен переменных, имен функций, макросов), которые появляются раньше, чем начало экрана.
- Переключение текста в связанный список (по узлу в строке), а не в монолитный массив. Это не очень помогает узкому месту. Хотя вставки/удаления будут выполняться быстрее, потеря индексированного доступа замедляет синтаксический анализатор. Я также думаю, что монолитный массив с большей вероятностью будет закэширован, чем разбитый список.
- Жесткое кодирование функции сканирования-токенов для каждого языка. Хотя это может быть лучшей оптимизацией для производительности, это не кажется практичным с точки зрения разработки программного обеспечения.
Архитектурное решение:
При использовании языка ассемблера более быстрый способ анализа этих строк заключается в загрузке символов в регистры и сравнении их по 4 или 8 байтам за раз. Необходимо принять во внимание некоторые дополнительные меры и меры предосторожности, такие как:
- Поддерживает ли архитектура невыровненный доступ к памяти?
- Все строки должны иметь размер
s, гдеs % word-size == 0, чтобы предотвратить нарушения чтения. - Другие?
Но эти проблемы кажутся легко решаемыми. Единственная проблема (кроме обычных проблем, возникающих при написании на ассемблере) заключается в том, что это не столько алгоритмическое решение, сколько аппаратное.
Алгоритмическое решение:
До сих пор я думал о том, чтобы программа изменила список ключевых слов, чтобы сделать алгоритм бинарного поиска более возможным.
Один из способов изменить их для этого — изменить размеры списка ключевых слов. Вот пример этого в C:
// some keywords for the C language
auto // keywords[0]
break // keywords[1]
case char const continue // keywords[2], keywords[3], keywords[4]
default do double
else enum extern
float for
goto
if int
long
register return
short signed sizeof static struct switch
typedef
union unsigned
void volatile
while
/* keywords[i] refers to the i-th keyword in the list
*
*/
Переключение размеров двумерного массива сделает его таким:
0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 3 3 3
1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2
-----------------------------------------------------------------
1 | a b c c c c d d d e e e f f g i i l r r s s s s s s t u u v v w
2 | u r a h o o e o o l n x l o o f n o e e h i i t t w y n n o o h
3 | t e s a n n f u s u t o r t t n g t o g z a r i p i s i l i
4 | o a e r s t a b e m e a o g i u r n e t u t e o i d a l
5 | k i u l r t s r t e o i c c d n g t e
6 | n l e n t n d f c t h e n i
7 | u t e f e l
8 | e r d e
// note that, now, keywords[0] refers to the string "abccccdddeeefffiilrr"
Это делает более эффективным использование алгоритма бинарного поиска (или даже простого алгоритма грубой силы). Но это только слова для первых символов в каждом ключевом слове, после чего ничто не может считаться «отсортированным». Это может помочь в небольших наборах слов, таких как язык программирования, но этого будет недостаточно для большого набора слов (например, во всем английском языке).
Что еще можно сделать для улучшения этого алгоритма?
Есть ли другой подход, который можно использовать для повышения производительности?
Примечания:
Этот вопрос от SO мне не помогает. Алгоритм Бойера-Мура-Хорспула (насколько я понимаю) — это алгоритм поиска подстроки внутри строки. Поскольку я анализирую несколько строк, я думаю, что есть гораздо больше возможностей для оптимизации.
