4

これは、CS 担当者が理論で輝くための演習です。

要素を含む 2 つのコンテナがあるとします。フォルダ、URL、ファイル、文字列、それは本当に問題ではありません。

追加と削除を計算するANアルゴリズムとは何ですか?

注意: この問題を解決する方法が多数ある場合は、回答ごとに 1 つの方法を投稿して、分析して投票できるようにしてください。

編集：すべての回答は、4つのコンテナで問題を解決します。頭の2つだけでも使えますか？

4

5 に答える 5

5

一意のアイテムのリストが 2 つあり、順序は問題ではないと仮定すると、それらは両方ともリストではなくセットと考えることができます。

リスト A を 1 つの円とし、リスト B をもう 1 つの円とするベン図を考えると、これら 2 つの交点が定数プールになります。

この交差点のすべての要素を A と B の両方から削除すると、A に残っているものはすべて削除され、B に残っているものはすべて追加されます。

したがって、A を反復して B の各項目を探します。見つかった場合は、A と B の両方から削除します。

A は削除されたもののリスト、B は追加されたもののリストです。

おもう...

[編集] わかりました、新しい「2 つのコンテナーのみ」という制限により、同じことが引き続き保持されます。

foreach( A ) { 
  if( eleA NOT IN B ) {
    DELETED
  }
}
foreach( B ) {
  if( eleB NOT IN A ) {
    ADDED
  }
}

次に、新しいリストを作成したり、古いリストを破棄したりしません...しかし、前の例のように時間がかかります。短いリストをループして、長いリストから要素を削除するだけです。ここでは、両方のリストを実行する必要があります

私の最初のソリューションは 4 つのコンテナーを使用せず、2 つのコンテナーを破壊しただけだと主張したいと思います ;-)

于 2008-09-24T13:46:33.187 に答える
1

私はしばらくこれを行っていませんが、アルゴリズムは次のようになると思います...

sort left-list and right-list
adds = {}
deletes = {}
get first right-item from right-list
get first left-item from left-list
while (either list has items)
  if left-item < right-item or right-list is empty
    add left-item to deletes
    get new left-item from left-list
  else if left-item > right-item or left-list is empty
    add right-item to adds
    get new right-item from right-list
  else
    get new right-item from right-list
    get new left-item from left-list

右リストと左リストの関係に関して、 deletes には削除されたアイテムが含まれ、addsには新しいアイテムが含まれるようになりました。

于 2008-09-24T13:43:34.007 に答える
0

不足している情報：追加/削除をどのように定義しますか？たとえば、リスト（AとB）がサーバーAとサーバーBの同じディレクトリを示している場合、それは同期しています。10日間待ってからリストを再度生成して比較した場合、何かが削除されたかどうかを確認するにはどうすればよいですか？私はできません。サーバーAにファイルがあり、サーバーBに見つからない、またはその逆であることがわかります。これは、ファイルがサーバーAに追加されたため（つまり、ファイルがBで見つからなかったため）、またはファイルがサーバーBで削除されたため（したがって、ファイルがBで見つからなくなったため）、ファイル名のリスト。

私が提案する解決策として、OLDという名前のリストとNEWという名前のリストがあると仮定します。OLDで見つかったが、NEWでは見つからなかったものはすべて削除されました。NEWで見つかったが、OLDでは見つからなかったものがすべて追加されました（たとえば、同じサーバー上の同じディレクトリのコンテンツですが、リストは異なる日付で作成されています）。

さらに、重複はないと仮定します。つまり、どちらのリストのすべてのアイテムも、次の意味で一意です。このアイテムをリストの他のアイテムと比較すると（この比較がどのように機能するかに関係なく）、アイテムは自分のアイテムよりも小さいか大きいと常に言えます。と比較していますが、決して等しくはありません。たとえば、文字列を処理する場合、辞書式順序でそれらを比較でき、同じ文字列がリストに2回含まれることはありません。

その場合、最も単純な（ただし、必ずしも最良の解決策ではありません）は次のとおりです。

  1. 古いリストを並べ替えます。たとえば、リストが文字列で構成されている場合は、アルファベット順に並べ替えます。並べ替えが必要なのは、バイナリ検索を使用して、オブジェクトがリストに存在すると仮定して、リスト内のオブジェクトをすばやく見つけることができる（または、リストにオブジェクトがまったく存在しないとすばやく判断できる）ためです。リストがソートされていない場合、オブジェクトの検索はO（n）の複雑さを持ちます（リスト上のすべてのアイテムを調べる必要があります）。リストがソートされている場合、複雑さはO（log n）のみです。これは、リスト上のアイテムを一致させようとするたびに、リスト上のアイテムの50％が一致しないことを常に除外できるためです。リストに100個のアイテムがある場合でも、アイテムを見つける（またはアイテムがリストにないことを検出する）には、最大7回のテストが必要です（または8回ですか？とにかく、100回よりはるかに少ないです）。NEWリストをソートする必要はありません。

  2. 次に、リストの削除を実行します。新しいリストのすべてのアイテムについて、古いリストでこのアイテムを見つけてみてください（バイナリ検索を使用）。アイテムが見つかった場合は、このアイテムをOLDリストから削除し、NEWリストからも削除します。これはまた、除去が進むほどリストが小さくなり、ルックアップがどんどん速くなることを意味します。リストからアイテムを削除しても、リストの正しい並べ替え順序には影響しないため、削除フェーズでOLDリストを再利用する必要はありません。

  3. 削除の最後に、両方のリストが空になる可能性があります。その場合、それらは等しくなります。それらが空でない場合、古いリストに残っているすべてのアイテムは、新しいリストにないアイテムです（そうでない場合は、それらを削除しました）。したがって、これらは削除されたアイテムです。まだ新しいリストにあるすべてのアイテムは、古いリストになかったアイテムです（ここでも、別の方法で削除しました）。したがって、これらは追加されたアイテムです。

于 2008-09-24T14:09:40.370 に答える
0

リスト内のオブジェクトは「一意」ですか？この場合、最初に2つのマップ（ハッシュマップ）を作成し、次にリストをスキャンして、マップ内のすべてのオブジェクトを検索します。

map1
map2
removedElements
addedElements

list1.each |item|
{
    map1.add(item)
}
list2.each |item|
{
    map2.add(item)
}
list1.each |item|
{
    removedElements.add(item) unless map2.contains?(item)
}
list2.each |item|
{
    addedElements.add(item) unless map1.contains?(item)
}

RubyとJavaを混ぜ合わせた恐ろしいメタ言語でごめんなさい:-P

最終的に、 removedElementsにはlist1に属する要素が含まれますが、list2には含まれず、addedElementsにはlist2に属する要素が含まれます。

マップ/辞書でのルックアップは一定であると見なされる可能性があるため、操作全体のコストはO（4 * N）です。一方、リスト内の各要素を線形/二分探索すると、そのO（N ^ 2）になります。

編集：最後のチェックを2番目のループに移動することを考え直すと、ループの1つを削除できます...しかしそれは醜いです... :)

list1.each |item|
{
    map1.add(item)
}
list2.each |item|
{
    map2.add(item)
    addedElements.add(item) unless map1.contains?(item)
}
list1.each |item|
{
    removedElements.add(item) unless map2.contains?(item)
}
于 2008-09-24T14:13:00.223 に答える
0

ジョーが言ったこと。また、リストが大きすぎてメモリに収まらない場合は、外部のファイル ソート ユーティリティまたはマージ ソートを使用します。

于 2008-09-24T13:47:08.693 に答える