Каков самый быстрый способ проверить ключевое слово в списке ключевых слов в Delphi?

В основном для этой цели я использую функцию IndexText из StrUtils. Он похож на ваш подход pos, но возвращаемое значение не зависит от индивидуальной длины строк. В качестве уловки он также нечувствителен к регистру (используйте IndexStr, если вы этого не хотите).

function IndexText(const AText: string; const AValues: array of string): Integer; overload;

В комментарии к этим функциям фактически упоминается конструкция case:

{AnsiMatchText и AnsiIndexText предоставляют регистр-подобную функцию для работы со строками}

type TKeyword = ( ECHIL, EHUSB, EWIFE, ESEX )
const TKeyNames : array[TKeyword] of string = ( 'CHIL', 'HUSB', 'WIFE', 'SEX' );

Key : TKeyword

case Key of 
  ECHIL : (code for CHIL);
  EHUSB : (code for HUSB);
  EWIFE : (code for WIFE);
  ESEX  : (code for SEX);
  else (code for everything else);
end;

В общем, не используйте строки в качестве «ключей», используйте перечисления - они безопаснее, и вы получите значительное увеличение скорости.

К сожалению, в Delphi (насколько я знаю) нет стандартной реализации хеш-таблицы, которую было бы легко использовать, однако вы всегда можете свернуть свою собственную.

Кстати, code for SEX звучит намного веселее, чем "закодирую для пива": P

Вы можете использовать константную таблицу (которая должна быть отсортирована по альфа-каналу) и быструю двоичную сортировку. Это очень эффективно и не требует хеширования.

Вот функция, которую нужно использовать:

function IsKeyWord(const KeyWords: array of string; const aToken: String): Boolean;
// aToken must be already uppercase
var First, Last, I, Compare: Integer;
begin
  First := Low(Keywords);
  Last := High(Keywords);
  Result := False;
  while First <= Last do
  begin
    I := (First + Last) shr 1;
    Compare := CompareStr(Keywords[i],aToken);
    if Compare = 0 then
      begin
        Result := True;
        break;
      end
    else
    if Compare < 0  then
      First := I + 1 else
      Last := I - 1;
  end;
end;

А вот несколько примеров ключевых слов:

const
  PASCALKEYWORDS: array[0..100] of string =
  ('ABSOLUTE', 'ABSTRACT', 'AND', 'ARRAY', 'AS', 'ASM', 'ASSEMBLER',
   'AUTOMATED', 'BEGIN', 'CASE', 'CDECL', 'CLASS', 'CONST', 'CONSTRUCTOR',
   'DEFAULT', 'DESTRUCTOR', 'DISPID', 'DISPINTERFACE', 'DIV', 'DO',
   'DOWNTO', 'DYNAMIC', 'ELSE', 'END', 'EXCEPT', 'EXPORT', 'EXPORTS',
   'EXTERNAL', 'FAR', 'FILE', 'FINALIZATION', 'FINALLY', 'FOR', 'FORWARD',
   'FUNCTION', 'GOTO', 'IF', 'IMPLEMENTATION', 'IN', 'INDEX', 'INHERITED',
   'INITIALIZATION', 'INLINE', 'INTERFACE', 'IS', 'LABEL', 'LIBRARY',
   'MESSAGE', 'MOD', 'NAME', 'NEAR', 'NIL', 'NODEFAULT', 'NOT', 'OBJECT',
   'OF', 'OR', 'OUT', 'OVERRIDE', 'PACKED', 'PASCAL', 'PRIVATE', 'PROCEDURE',
   'PROGRAM', 'PROPERTY', 'PROTECTED', 'PUBLIC', 'PUBLISHED', 'RAISE',
   'READ', 'READONLY', 'RECORD', 'REGISTER', 'REINTRODUCE', 'REPEAT', 'RESIDENT',
   'RESOURCESTRING', 'SAFECALL', 'SET', 'SHL', 'SHR', 'STDCALL', 'STORED',
   'STRING', 'STRINGRESOURCE', 'THEN', 'THREADVAR', 'TO', 'TRY', 'TYPE',
   'UNIT', 'UNTIL', 'USES', 'VAR', 'VARIANT', 'VIRTUAL', 'WHILE', 'WITH', 'WRITE',
   'WRITEONLY', 'XOR');

  DFMKEYWORDS: array[0..4] of string = (
    'END', 'FALSE', 'ITEM', 'OBJECT', 'TRUE');

  CKEYWORDS: array[0..47] of string = (
  'ASM', 'AUTO', 'BREAK', 'CASE', 'CATCH', 'CHAR', 'CLASS', 'CONST', 'CONTINUE',
  'DEFAULT', 'DELETE', 'DO', 'DOUBLE', 'ELSE', 'ENUM', 'EXTERN', 'FLOAT', 'FOR',
  'FRIEND', 'GOTO', 'IF', 'INLINE', 'INT', 'LONG', 'NEW', 'OPERATOR', 'PRIVATE',
  'PROTECTED', 'PUBLIC', 'REGISTER', 'RETURN', 'SHORT', 'SIGNED', 'SIZEOF',
  'STATIC', 'STRUCT', 'SWITCH', 'TEMPLATE', 'THIS', 'THROW', 'TRY', 'TYPEDEF',
  'UNION', 'UNSIGNED', 'VIRTUAL', 'VOID', 'VOLATILE', 'WHILE');

  CSHARPKEYWORDS : array[0..86] of string = (
  'ABSTRACT', 'AS', 'BASE', 'BOOL', 'BREAK', 'BY3', 'BYTE', 'CASE', 'CATCH', 'CHAR',
  'CHECKED', 'CLASS', 'CONST', 'CONTINUE', 'DECIMAL', 'DEFAULT', 'DELEGATE', 'DESCENDING',
  'DO', 'DOUBLE', 'ELSE', 'ENUM', 'EVENT', 'EXPLICIT', 'EXTERN', 'FALSE', 'FINALLY',
  'FIXED', 'FLOAT', 'FOR', 'FOREACH', 'FROM', 'GOTO', 'GROUP', 'IF', 'IMPLICIT',
  'IN', 'INT', 'INTERFACE', 'INTERNAL', 'INTO', 'IS', 'LOCK', 'LONG', 'NAMESPACE',
  'NEW', 'NULL', 'OBJECT', 'OPERATOR', 'ORDERBY', 'OUT', 'OVERRIDE', 'PARAMS',
  'PRIVATE', 'PROTECTED', 'PUBLIC', 'READONLY', 'REF', 'RETURN', 'SBYTE',
  'SEALED', 'SELECT', 'SHORT', 'SIZEOF', 'STACKALLOC', 'STATIC', 'STRING',
  'STRUCT', 'SWITCH', 'THIS', 'THROW', 'TRUE', 'TRY', 'TYPEOF', 'UINT', 'ULONG',
  'UNCHECKED', 'UNSAFE', 'USHORT', 'USING', 'VAR', 'VIRTUAL', 'VOID', 'VOLATILE',
  'WHERE', 'WHILE', 'YIELD');

И пользоваться им очень просто:

  if IsKeyWord(PASCALKEYWORDS,UpperCase('BEGIN')) then
   ....

Вы можете легко изменить функцию IsKeyWord (), чтобы она возвращала индекс токена, если он вам нужен.

function KeyWordIndex(const KeyWords: array of string; const aToken: String): integer;
// aToken must be already uppercase
var First, Last, Compare: Integer;
begin
  First := Low(Keywords);
  Last := High(Keywords);
  while First <= Last do
  begin
    result := (First + Last) shr 1;
    Compare := CompareStr(Keywords[result],aToken);
    if Compare = 0 then
      exit else
    if Compare < 0  then
      First := result + 1 else
      Last := result - 1;
  end;
  result := -1; // not found
end;

Ваш ряд if операторов для проверки того, является ли ввод каким-либо из заданных ключевых слов, можно сократить, проверив отдельные символы, чтобы как можно скорее выйти из строя. Ваш пример

if MyKeyword = 'CHIL' then (code for CHIL)
else if MyKeyword = 'HUSB' then (code for HUSB)
else if MyKeyword = 'WIFE' then (code for WIFE)
else if MyKeyword = 'SEX' then (code for SEX)
else (code for everything else);

можно заменить на

KW := kwOther;
if MyKeyword <> '' then begin
  case MyKeyword[1] of
    'C': if MyKeyword = 'CHIL' then KW := kwCHIL;
    'H': if MyKeyword = 'HUSB' then KW := kwHUSB;
    'S': if MyKeyword = 'SEX' then KW := kwSEX;
    'W': if MyKeyword = 'WIFE' then KW := kwWIFE;
  end;
end;
case KW of
  kwCHIL: {code for CHIL};
  kwHUSB: {code for HUSB};
  kwSEX: {code for SEX};
  kwWIFE: {code for WIFE};
else
  {code for everything else};
end;

Для ключевых слов без учета регистра case будет проверять верхний и нижний регистр, а для сравнения будет использоваться AnsiCompareText(). Если у вас есть несколько ключевых слов с одной и той же первой буквой, вы можете вложить эти case операторы, но удобочитаемость, вероятно, скоро пострадает из-за очень небольшого прироста скорости.

Увеличивая это до максимума, вы можете реализовать конечный автомат, который использует PChar для вычисления следующего состояния, которое будет переходить к случаю else, как только будет обнаружен первый несовпадающий символ. Это будет быстрее, чем любое решение, связанное с хешами.

я думаю

if x then

else

безусловно, лучшее решение. Ваше собственное решение очень неэлегантно, и для незначительного повышения эффективности оно того не стоит. Конструкция if then else идеально подходит для того, что вы хотите.

Для наиболее чистого кода лучше использовать case с перечислениями или if..else со строками, как предлагали другие. Однако есть несколько нестандартных решений, если вы действительно хотите туда попасть.

Один из них - использовать хэш-карту строк, которая подобна списку, «проиндексированному» по строкам. Значения в списке будут указателями процедур на код, который вы хотите выполнить для каждой строки. Все процедуры должны иметь одни и те же точные параметры - и вам нужно будет написать хэш-карту самостоятельно или найти ту, которую вы можете использовать, например в JVCL.

// prepare the hash map
myHashMap[ 'CHIL' ] := @procToCallForChil;
myHashMap[ 'HUSB' ] := @procToCallForHusb;

// use the hash map
type
  TPrototypeProc = procedure( your-parameters-here );
var
  procToCall : TPrototypeProc;
begin
  @procToCall := myHashMap[ 'CHIL' ];
  procToCall( your-parameters-here );
end;

Два, и это что-то странное, что я пробовал однажды: если и только если ваши строки идентификаторов умещаются в 4 символа (как во всех ваших примерах), и они являются строками ansi (а не строками Unicode), вы можете сопоставить строки с целыми числами напрямую. 32-битное целое число эквивалентно по размеру 4-байтовой строке, поэтому вы можете:

function FourCharStringToInteger( const s : ansistring ) : integer;
begin
  assert(( length( s )  = 4 ), 'String to convert must be exactly 4 characters long!');
  move( s[1], result, 4 );
end;

Любой строковый идентификатор короче 4 символов должен быть дополнен пробелами, а строки чувствительны к регистру («chil» и «CHIL» дают разные значения). Чтобы использовать это с оператором case, вам нужно предварительно вычислить значения, которые могут или не могут подходить для ваших целей:

id_CHIL := FourCharStringToInteger( 'CHIL' );

И, наконец, вы можете иметь оператор case:

case id of
  id_CHIL : ...
  id_HUSB : ...
end;

Это код "особой заботы", и он может иметь значение только в том случае, если у вас есть сотни или более строк идентификаторов - на самом деле этого не следует делать вообще :) Его, безусловно, легко сломать. Я согласен, хотя эти case-заявления более аккуратны, чем бесконечные череды ... else ... блоков.

отказ от ответственности: ответ основан на обновленном описании проблемы, т.е. просто проверяет, совпадает ли строка или нет.

Если вы действительно хотите добиться максимальной производительности, вам может помочь некоторая дополнительная информация о ваших наборах данных.

• how many keywords are we talking about? (what order of magnitude)
• is the set of keywords fixed?
• is there a lot of repetition in the input set? (i.e. the same X keywords often repeat)
• what is the expected hit/miss ratio like? Do you expect to match one keyword for every thousand input words, or do you expect almost every word to be found?

Например,

• for a small amount of keywords (let's say about 20, depending on the implementation), the overhead of hashing will become important.
• If If you get can get a perfect hashing scheme (see here for an example in C), you can get rid of any chaining or similar scheme, shaving off some important cycles. Then again, this would require both your keywords and input set to be known up front, which isn't very likely.
• if there is a lot of repetition in the keywords (and a large hash collection to match against), a small local cache of the last X words could help.
• if you expect a lot of blatant misses (or your hash algorithm is very inefficient ;P) a trie could be more efficient than a hash table.

Однако большинство из них немного экстремальны для общих задач настройки производительности. Я бы, вероятно, сначала профилирую стандартные реализации "хешированного набора" (универсальные шаблоны delphi, jcl и т. Д.), Чтобы увидеть, какая из них лучше всего работает с вашим набором задач.

Вы также можете переключиться на более объектно-ориентированный подход и иметь что-то вроде

TCommand = class
public
  procedure Execute; virtual; abstract;
end;
TCommandClass = class of TCommand;

и пусть фабрика создаст для вас команды

TCommandFactory = class
public
  procedure RegisterKeyWord (const Keyword : String; CmdClass : TCommandClass);
  function  CreateCommand (const Keyword : String) : TCommand;
end;

Тогда вызывающий код выглядел бы так же просто, как:

CommandFactory.CreateCommand (Keyword).Execute;

Таким образом, вы локализовали и инкапсулировали все строки ключевых слов в простой фабричный класс, что значительно упрощает последующие изменения языка ввода. Использование этого командного подхода имеет другие преимущества, такие как легкая расширяемость.

Я знаю, что это может быть истолковано как не ответ на ваш вопрос, потому что дело не в том, как быстро вы это сделаете. Но это еще один подход, о котором, возможно, стоит подумать.