Удалось ещё больше ускорить, да ещё и вынести один линейный поиск в отдельную процедуру.
Вспомогательная процедура:
Код:
PROCEDURE EQ (IN s: ARRAY OF BYTE; begin, end: INTEGER; IN word: ARRAY OF BYTE; length: INTEGER): BOOLEAN;
VAR i: INTEGER;
BEGIN i := 0;
IF begin + length <= end THEN
WHILE (i < length) & (s[begin + i] = word[i]) DO INC(i) END
END;
RETURN (i = length)
END EQ;
Основная процедура:
Код:
PROCEDURE MultiFind* (IN s: ARRAY OF BYTE; begin, end, wordCount: INTEGER; IN words: ARRAY OF ARRAY OF BYTE; IN lens: ARRAY OF INTEGER; OUT word, pos: INTEGER);
VAR w: INTEGER; sb: BYTE; h: ARRAY 64*1024 OF BYTE;
BEGIN word := -1; pos := -1; w := 0;
WHILE w < wordCount DO
h[w] := words[w][0]; INC(w) (* засасываем в кэш процессора первые буквы слов *)
END;
WHILE begin < end DO
sb := s[begin]; w := 0;
WHILE (w < wordCount) & ~((h[w] = sb) & EQ(s, begin, end, words[w], lens[w])) DO
INC(w)
END;
IF w < wordCount THEN
word := w; pos := begin; begin := end
END;
INC(begin)
END
END MultiFind;
ускорение в
2.93 раз при wordCount = 100, sourceLength = 100'000'000
ускорение в
3.35 раз при wordCount = 1'000, sourceLength = 10'000'000
ускорение в
3.56 раз при wordCount = 10'000, sourceLength = 1'000'000
ускорение в
4.73 раз при wordCount = 100'000 sourceLength = 100'000
1) Основной вклад в ускорение вносит запоминание первых букв слов в отдельном массивчике. Чтобы они лежали в одном месте непрерывной памяти, а не были разбросаны по далёким местам двумерного массива.
2) Так как слова сравниваются редко (много вариантов отсекается сразу по первой букве), то код сравнения слов можно вынести в отдельную процедуру без потери эффективности. В главной процедуре остаётся всего два вложенных цикла.
3) Кэширование sb := s[begin]; не принципиально, ускоряет на чуть-чуть, но я всё же не удержался и добавил и его тоже.
Производительность измерял в 64-разрядной системе на C# на машине с процессором i7 2600K, память 1600 MHz. Затем программу на C# переписал на Компонентном Паскале. Программу на Компонентном Паскале в 32-разрядном Блэкбоксе не испытывал, так что под Блэкбоксом результаты могут быть иными.
Вход
FAQ
Поиск
