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

Question

У меня есть небольшой список ключевых слов. То, что я действительно хотел бы сделать, сродни:

case MyKeyword of
  'CHIL': (code for CHIL);
  'HUSB': (code for HUSB);
  'WIFE': (code for WIFE);
  'SEX': (code for SEX);
  else (code for everything else);
end;

К сожалению, оператор CASE нельзя использовать таким образом для строк.

Я мог бы использовать прямую конструкцию IF THEN ELSE IF, например ::10000*

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);

но я слышал, это относительно неэффективно.

То, что я делал вместо этого:

P := pos(' ' + MyKeyword + ' ', ' CHIL HUSB WIFE SEX ');
case P of
  1: (code for CHIL);
  6: (code for HUSB);
  11: (code for WIFE);
  17: (code for SEX);
  else (code for everything else);
end;

Это, конечно, не лучший стиль программирования, но он прекрасно работает для меня, и до сих пор не имел значения.

Так, как лучше всего переписать это в Delphi, чтобы оно было простым, понятным, но и быстрым?

(Для справки, я использую Delphi 2009 со строками Unicode.)

---

Продолжение:

Тоби рекомендовал, чтобы я просто использовал конструкцию If Then Else. Оглядываясь назад на мои примеры, в которых использовался оператор CASE, я вижу, насколько это приемлемый ответ. К сожалению, мое включение в CASE непреднамеренно скрыло мой настоящий вопрос.

Мне действительно все равно, какое это ключевое слово. Это просто бонус, если конкретный метод может идентифицировать его, как метод POS. Что мне нужно, это знать, есть ли ключевое слово в наборе ключевых слов.

Так что я действительно хочу знать, есть ли что-нибудь лучше, чем:

if pos(' ' + MyKeyword + ' ', ' CHIL HUSB WIFE SEX ') > 0 then

Эквивалент If Then Else не выглядит лучше в этом случае:

if (MyKeyword = 'CHIL') or (MyKeyword = 'HUSB') or (MyKeyword = 'WIFE') 
      or (MyKeyword = 'SEX') then

В комментарии Барри к вопросу Корнеля он упоминает об Универсальном TDictionary. Я еще не изучал новые коллекции Generic, и, похоже, я должен в них вникнуть. Мой вопрос здесь состоит в том, построены ли они для эффективности и как использование TDictionary сравнивается по внешнему виду и по скорости с двумя вышеупомянутыми строками?

---

В последующем профилировании я обнаружил, что объединение строк, как в: ('' + MyKeyword + ''), является ОЧЕНЬ дорогостоящим по времени и его следует по возможности избегать. Почти любое другое решение лучше, чем делать это.

Answer 1

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

Answer 2

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

Вот функция для использования:

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;

Answer 3

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

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

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

{AnsiMatchText & AnsiIndexText обеспечить кейс как функцию для решения со строками}

Answer 4

Ваша серия операторов 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, как только будет найден первый не соответствующий символ. Это будет быстрее, чем любое решение с использованием хэшей.

Answer 5

Для самого чистого кода лучше использовать 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 id of
  id_CHIL : ...
  id_HUSB : ...
end;

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

Answer 6

Я думаю, что

if x then

else

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

Answer 7

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

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

• о скольких ключевых словах идет речь? (какой порядок величины)
• фиксированный набор ключевых слов?
• много ли повторений во входном наборе? (то есть одни и те же ключевые слова X часто повторяются)
• каково ожидаемое соотношение попаданий / промахов? Ожидаете ли вы совпадение с одним ключевым словом на каждую тысячу входных слов или почти каждое слово будет найдено?

Например,

• для небольшого количества ключевых слов (скажем, около 20, в зависимости от реализации), издержки хэширования станут важными.
• Если вы можете получить идеальную схему хеширования (см. здесь для примера в C), вы можете избавиться от любой цепочки или аналогичной схемы, сбрасывая некоторые важные циклы. Опять же, это потребует, чтобы ваши ключевые слова и набор входных данных были известны заранее, что маловероятно.
• если в ключевых словах много повторений (и большая коллекция хэшей, с которой можно сравнивать), небольшой локальный кеш последних X слов может помочь.
• если вы ожидаете много явных промахов (или ваш алгоритм хеширования очень неэффективен; P) три может быть более эффективным, чем хеш-таблица.

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

Answer 8

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

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;

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

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