3

たくさんのNSArrayがあると想像してください。配列にはすべて、NSValuesでラップされたCGPointが含まれています。すべての要素が一意ではありません。そのため、特定の要素が複数の配列に表示される可能性があります。結果の配列に一意の要素だけが含まれるように、これらの配列を1つの配列に結合する最も速い方法は何ですか？

現在、私は次のようにしています：

  1. を使用して各アレイをNSSetに挿入しますsetByAddingObjectsFromArray
  2. 結果の配列にセットの内容を入力します

別のオプションはこれです：

  1. すべての配列を1回トラバースし、各値をNSDictionaryに挿入します（まだ存在しない場合）
  2. 辞書のキーを1回トラバースし、それぞれを結果の配列に挿入します

従来のランタイム分析では、最初のオプションはO(n log n)すべての初期配列の要素数でスケーリングする必要があるとされています（すべての要素をトラバースし、それぞれをバイナリ検索ツリーなどにログ時間で挿入します）。2番目のアプローチの場合、実行時間はO(n)、ルックアップとハッシュテーブルへの挿入が償却された一定時間で実行されるためです。ただし、Appleのデータ構造について少し読んだ後、それらが従来のデータ構造のように動作すると仮定するのはばかげているようです。

4

2 に答える 2

3

これらのアプローチは両方とも と の間のどこかにO(n)ありO(n log n)、 n は十分にlog n小さく、制限されて小さい可能性が高いため、定数要因がこれらのどれが最も速いかを決定する可能性があります。

この時点で、ユースケースのように見えるデータを実際にベンチマークすることが最善の方法です。

確かではありませんが、NSSet もハッシュで実装されていると思います。

于 2012-10-21T17:34:35.490 に答える
1

実際には...その時間はほぼ同じになると思いますが、NSDictionaryの場合、そのNSDictionaryにキーをコピーする必要があるため、メモリのオーバーヘッドが少し発生します。どちらも同じようNSDictionaryに機能します。NSSet

  1. hash一意性がチェックされます
  2. 両方のアイテムが同じキャッシュを持っている場合、isEqual呼び出されています

あなたが言及したように、アプローチに大きな違いはありません。

于 2012-12-05T17:44:02.910 に答える