2

私はこのコードを持っています

var
arr: TArray<string>;
e1, e2, e3, e4: string;
begin

e1 := 'val1';
e2 := 'val2';
e3 := 'val3';
e4 := 'val4';

arr := TArray<string>.Create(e1, e2, e3, e4);

e1からe4が上記の配列に2回存在するかどうかを確認する必要があります。これを行うための最良の方法は何ですか？また、要素にnull値があるかどうかのチェックもスキップする必要があります。

また、このアレイを手動で解放する必要があるかどうかもアドバイスしてください

ありがとう

4

4 に答える 4

9

アルゴリズムで遊ぶ楽しみのために; 元の配列が大きい場合（単純なアルゴリズムを非実用的にするのに十分O(n^2)であり、OPはジェネリックを含むバージョンのDelphiを使用しているため、ソートせずにTDictionary<string, integer>すべての文字列を追跡し、重複を識別するためにを使用することを提案します。

これは、いくつかの理由で効率的です。

  • TDictionaryは一定時間の挿入を提供します、それはほとんどO(n)です。アレイのサイズは最初からわかっているので、TDictionary大きくすることなく使用できます。これにより、アルゴリズム全体が作成されますO(n)。
  • 文字列はすでに配列内にあり、Delphi文字列は参照カウントされるため、文字列を配列に入れても実際には文字列がコピーされません。
  • このアルゴリズムでは、アレイは1回だけウォークされます。

コード：

type
  TZeroWidthRecord = record
  end;

function FindFirstDuplicate(const ArrayOfString: array of string): Integer;
var Dict: TDictionary<string, TZeroWidthRecord>;
    i: Integer;
    ZW: TZeroWidthRecord;
begin
  Dict := TDictionary<string, TZeroWidthRecord>.Create(Length(ArrayOfString));
  try
    for i:=0 to High(ArrayOfString) do
      try
        Dict.Add(ArrayOfString[i], ZW);
      except on E:Exception do
        Exit(i);
      end;
  finally Dict.Free;
  end;
  // No duplicates found:
  Result := -1;
end;

Davidのコメントに答えるために、このTDictionaryベースのアルゴリズムをアルゴリズムと比較する短いテストプログラムを作成しましたsort-and-search。文字列のランダム配列を作成してから、最初の重複を見つけてみました。私のアレイには重複が含まれていません。重複があった場合、TDictionaryの実行時間は平均的な最初のヒットの重複に比例します。たとえば、平均してTDictionaryがアレイの中央で重複を検出した場合、TDictアルゴリズムの平均実行時間は半分になります。ソートベースのアルゴリズムは配列全体をソートする必要があり、ソートは最も時間がかかるものです。

ソートや辞書ベースのアルゴリズムと同様に、現実的なデータでテストする必要があります。たとえば、OPの質問で短い文字列を使用してテストした場合、TDictとsortの間に競合は発生しません。Dictは、些細な長さの配列でも高速になります。しかし、平均文字列長が増加すると、ソートベースのアルゴリズムが改善され始めます。ただし、これも文字列によって異なります。たとえば、ほとんどの文字列が長いプレフィックスを共有する場合、並べ替えアルゴリズムの「比較」段階にかなり時間がかかり、TDictionaryの見栄えが再び良くなります。

テストテーブル1、重複なし

*==========*===========================*
|          | Number of strings         |
| Avg str  | in the Array for          |
| length   | TDictionary to be faster  |
*======================================*
| 7        | 33                        |
| 10       | 73                        |
| 13       | 73                        |
| 16       | 163                       |
| 19       | 163                       |
| 22       | 366                       |
| 25       | 366                       |
| 28       | 549                       |
| 37       | 2776                      |
| 40       | 2776                      |
| 43       | 2776                      |
| 46       | 4164                      |
| 49       | 9369                      |
| 52       | 9369                      |
| 55       | 9369                      |
| 58       | 21079                     |
*==========*===========================*

テストテーブル2、アレイの1/2で複製

これは、最初の重複がアレイの真ん中に見つかった場合の結果になります。平均文字列長58の大きな違いに注意してください。

*==========*===========================*
|          | Number of strings         |
| Avg str  | in the Array for          |
| length   | TDictionary to be faster  |
*======================================*
| 30       | 109                       |
| 33       | 163                       |
| 36       | 163                       |
| 58       | 366                       |
*==========*===========================*

テストテーブル3、1/4で複製

そして、これは、最初の重複がアレイの約1/4で見つかった場合に発生します。

*==========*===========================*
|          | Number of strings         |
| Avg str  | in the Array for          |
| length   | TDictionary to be faster  |
*======================================*
| 29       | 73                        |
| 32       | 73                        |
| 38       | 73                        |
| 57       | 109                       |
*==========*===========================*

これがテストアプリケーションです：http：//pastebin.com/vDznwKtZ

于 2013-01-25T16:23:59.827 に答える
6

動的配列を解放する必要はありません。これらはマネージ型であり、コンパイラーは、オブジェクトへの参照がなくなると、オブジェクトが破棄されることを確認します。

重複の検出に関しては、次のように行うことができます。

function HasDuplicates(const arr: array of string): Boolean;
var
  i, j: Integer;
begin
  for i := 0 to high(arr) do
    if arr[i]<>'' then
      for j := i+1 to high(arr) do
        if arr[i]=arr[j] then
          exit(True);
  Result := False;
end;

「null」と言うとき、文字列のコンテキストでは、文字列が空であることを意味すると思います。

これは複雑さO（n ^ 2）のアルゴリズムです。配列が大きい場合、それは悪いニュースです。

アレイが注文された場合は、O（n）アルゴリズムを使用してテストを実行できます。

function OrderedHasDuplicates(const arr: array of string): Boolean;
var
  i: Integer;
begin
  for i := 0 to high(arr)-1 do
    if arr[i]<>'' then
      if arr[i]=arr[i+1] then
        exit(True);
  Result := False;
end;

当然、これらの関数は、どのインデックスが重複しているかを識別するために簡単に変更できます。

function IndexOfDuplicate(const arr: array of string): Integer;
var
  i: Integer;
begin
  for Result := 0 to high(arr) do
    if arr[Result]<>'' then
      for i := Result+1 to high(arr) do
        if arr[Result]=arr[i] then
          exit;
  Result := -1;
end;
于 2013-01-25T15:06:14.757 に答える
4

文字列が2回存在するかどうかを確認するには、TStringListの機能を使用します。TStringListオブジェクトを作成し、配列のすべての要素（文字列）を追加し、SortedプロパティをTrueに設定してから、最初から最後までループして、現在の要素が最後の要素と等しいかどうかを確認します。等しい場合は、複製。

TStringListを使用する主な利点は、提供される並べ替え機能です。

于 2013-01-25T15:11:04.683 に答える
2

TArray型は、ジェネリックスフレーバーの古典的な動的配列です。このタイプはDelphiによって管理されるため、関連するメモリを手動で解放する必要はありません。オブジェクトまたはその他の動的に作成された変数を格納する場合でも、そのメモリを解放する必要がありますが、配列自体は解放しません。

特にTArrayでは、どちらもマネージドタイプであるため、メモリについてはまったく気にしません。

順序付けされていない配列で重複をチェックするには、それをループして、各要素について、配列の残りの部分と比較する必要があります。

var
  arr: TArray<string>;
  e1, e2, e3, e4: string;
  I, J: Integer;
begin
  e1 := 'val1';
  e2 := 'val2';
  e3 := 'val3';
  e4 := 'val4';

  arr := TArray<string>.Create(e1, e2, e3, e4);
  //check for duplicates
  for I := low(arr) to High(arr) do
    for J := I + 1 to High(arr) do
      if arr[I] = arr[J] then
        ShowMessage('A duplicate was found');

最後に、文字列をnullにすることはできないため、null要素をチェックする必要はありません。

正確には、空の文字列（''）は実際にはnilポインターですが、それは話の反対側です。

于 2013-01-25T15:05:15.193 に答える