2

TList の子孫から重複を削除するためにこの関数を作成しましたが、これが特定の条件で問題を引き起こす可能性があるかどうか、およびパフォーマンスがどのように向上するか疑問に思っていました。

オブジェクトポインタで動作するようです

function TListClass.RemoveDups: integer;
var
  total,i,j:integer;
begin
  total:=0;
  i := 0;
  while i < count do begin
    j := i+1;
    while j < count do begin
      if items[i]=items[j] then begin
       remove(items[j]);
       inc(total);
      end
      else
        inc(j);
    end;
    inc(i);
  end;
  result:=total;
end;

更新: これはより速く動作しますか?

function TDrawObjectList.RemoveDups: integer;
var
  total,i,j:integer;
  templist:TLIST;
begin
  templist:=TList.Create;
  total:=0;
  i := 0;
  while i < count do
    if templist.IndexOf(items[i])=-1 then begin
      templist.add(i);
      inc(i);
    end else begin
      remove(items[i]);
      inc(total);
    end;
  result:=total;
  templist.Free;
end;

別のリストが必要です。

4

2 に答える 2

1

単なる仮説：

インターフェース

TInterfaceList で、そのリストにのみ存在するオブジェクトをインターフェース化した場合は、オブジェクトの参照カウントを確認できます。リストを逆方向にループし、refcount > 1 のすべてのオブジェクトを削除します。

カスタムカウンター

これらのオブジェクトを編集できる場合は、インターフェースなしで同じことができます。オブジェクトがリストに追加されるとカウンターを増やし、削除されるとカウンターを減らします。

もちろん、これは実際にこれらのオブジェクトにカウンターを追加できる場合にのみ機能しますが、質問では境界が正確に明確ではなかったため、これが許可されているかどうかはわかりません.

利点は、重複を削除するときではなく、挿入するときではなく、他のアイテムを探す必要がないことです。並べ替えられたリストで重複を見つけることは (コメントで述べたように) より高速になる可能性がありますが、まったく検索する必要がない場合は、最速のルックアップよりも優れています。

于 2012-10-23T15:11:37.113 に答える
1

前述のように、解決策は O(N^2) であり、アイテムの大きなセット (1000 秒) では非常に遅くなりますが、カウントが低いままである限り、実装がシンプルで簡単であるため、最善の策です。事前にソートされている場所と、他のソリューションにはより多くのコードが必要であり、実装エラーが発生しやすくなります。

これはおそらく、同じコードを別のよりコンパクトな形式で記述したものです。リストのすべての要素を実行し、現在の要素の右側にある重複をそれぞれ削除します。逆ループで行われている限り、削除は安全です。

function TListClass.RemoveDups: Integer;
var
  I, K: Integer;
begin
  Result := 0;
  for I := 0 to Count - 1 do //Compare to everything on the right
  for K := Count - 1 downto I+1 do //Reverse loop allows to Remove items safely
    if Items[K] = Items[I] then
    begin
      Remove(Items[K]);
      Inc(Result);
    end;
end;

本当に 5000 項目のリストになる場合は、最適化を後で行うことをお勧めします。また、上記のように、アイテムをリストに追加する際に重複をチェックすると、次のように保存できます。

  • 重複のチェックは時間内に配布されるため、ユーザーには目立ちません
  • だまされた場合は、早期に終了することを期待できます
于 2012-10-23T10:11:07.660 に答える