delphi - 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ステートメントは文字列のように使用することはできません。

ストレートのIFTHENELSE 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);

しかし、これは比較的非効率的だと聞きました。

代わりに私がやっていたことは次のとおりです。

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で書き直して、シンプルでわかりやすく、しかも高速にするための最良の方法は何でしょうか。

（参考までに、Unicode文字列でDelphi 2009を使用しています。）

ファローアップ：

Tobyは、IfThenElse構文を使用することをお勧めします。CASEステートメントを使用した私の例を振り返ると、それがどのように実行可能な答えであるかがわかります。残念ながら、CASEを含めると、私の本当の質問がうっかり隠されてしまいました。

私は実際にそれがどのキーワードであるかを気にしません。特定のメソッドがPOSメソッドと同じように識別できる場合、これは単なるボーナスです。私が必要としているのは、キーワードがキーワードのセットに含まれているかどうかを知ることです。

だから本当に私はより良いものがあるかどうか知りたいです：

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

この場合、IfThenElseに相当するものは良くないようです。

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

Kornelの質問に対するBarryのコメントの中で、彼はTDictionaryGenericに言及しています。私はまだ新しいジェネリックコレクションを取り上げていません。それらを掘り下げる必要があるようです。ここでの私の質問は、それらが効率のために構築されているかどうか、そしてTDictionaryを使用すると、外観と速度が上記の2つの行とどのように比較されるかということです。

後のプロファイリングで、（'' + MyKeyword +''）のような文字列の連結は時間的に非常にコストがかかるため、可能な限り避ける必要があることがわかりました。他のほとんどの解決策は、これを行うよりも優れています。

score 7 · Accepted Answer

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

score 5 · Accepted Answer

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;

score 3 · Accepted Answer

ほとんどの場合、私はその目的のためにStrUtilsのIndexText関数を使用します。これはposアプローチに似ていますが、戻り値は文字列の個々の長さに依存しません。ギミックとして、大文字と小文字を区別しません（これが不要な場合は、IndexStrを使用してください）。

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

これらの関数へのコメントは、実際にはケース構成に言及しています。

{AnsiMatchTextとAnsiIndexTextは、文字列を処理するためのケースのような関数を提供します}

score 3 · Accepted Answer

入力が指定されたキーワードのいずれかであるかどうかを確認する一連の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ステートメントをネストできますが、速度がほとんど向上しないため、読みやすさがすぐに低下する可能性があります。

これを最大限に活用すると、a を使用して次の状態を計算するステートマシンを実装できます。これは、一致しない最初の文字が見つかるとすぐPCharにそのケースに分岐します。elseハッシュを含むどのソリューションよりも高速です。

score 2 · Accepted Answer

私は思います

if x then

else

断然最良のソリューションです。あなた自身のソリューションは非常に洗練されておらず、効率のわずかな改善には価値がありません。if then else コンストラクトは、必要なものに最適です。

score 2 · Accepted Answer

最もクリーンなコードの場合、他の人が示唆しているように、列挙型でケースを使用するか、文字列で if..else を使用するのが最善です。ただし、本当にそこに行きたい場合は、人里離れた場所にいくつかの解決策があります.

1 つは文字列ハッシュマップを使用することです。これは、文字列によって "インデックス付けされた" リストのようなものです。リスト内の値は、各文字列に対して実行するコードへのプロシージャポインターになります。すべてのプロシージャはまったく同じパラメータを持つ必要があり、ハッシュマップを自分で作成するか、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;

2つ、これは私が一度試した奇妙なものです:識別子文字列が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... ブロックの際限のない行列よりもきちんとしているという点には同意します。

score 1 · Accepted Answer

免責事項：回答は、更新された問題ステートメントに基づいています。つまり、文字列が一致するかどうかを確認するだけです。

パフォーマンスの最後のビットを本当に使いたい場合は、データセットに関するいくつかの追加情報が役立つ可能性があります。

いくつのキーワードについて話しているのですか？（桁違い）
キーワードのセットは固定されていますか？
入力セットに多くの繰り返しがありますか？（つまり、同じXキーワードが頻繁に繰り返されます）
予想されるヒット/ミス率はどのようなものですか？1000個の入力単語ごとに1つのキーワードに一致することを期待しますか、それともほぼすべての単語が見つかることを期待しますか？

例えば、

少量のキーワード（実装によっては約20など）の場合、ハッシュのオーバーヘッドが重要になります。
完全なハッシュスキームを取得できる場合（ Cの例については、ここを参照）、いくつかの重要なサイクルを削減して、チェーンまたは同様のスキームを取り除くことができます。繰り返しになりますが、これにはキーワードと入力セットの両方を事前に知っておく必要がありますが、これはあまりありそうにありません。
キーワードに多くの繰り返しがある場合（および照合する大きなハッシュコレクションがある場合）、最後のX語の小さなローカルキャッシュが役立つ可能性があります。
多くの露骨なミスが予想される場合（またはハッシュアルゴリズムが非常に非効率的である; P）、トライはハッシュテーブルよりも効率的である可能性があります。

ただし、これらのほとんどは、一般的なパフォーマンス調整タスクには少し極端です。おそらく、最初に標準の「ハッシュセット」実装（delphiジェネリック、jclなど）のプロファイルを作成して、問題セットでどれが最適に機能するかを確認します。

score 0 · Accepted Answer

よりオブジェクト指向のアプローチに切り替えて、次のようなものにすることもできます

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;

このようにして、単純なファクトリクラスにすべてのキーワード文字列をローカライズしてカプセル化したので、後で入力言語を簡単に変更できます。このコマンドベースのアプローチを使用すると、拡張が容易になるなどの利点があります。

これはあなたの質問に対する答えではないと解釈されるかもしれません。しかし、これは検討する価値のある別のアプローチです。

delphi - Delphiのキーワードのリストでキーワードをチェックする最も速い方法は何ですか？

8 に答える 8

Related

Reference