sortedArrayUsingFunction:context:hint:

Discussion 議論

The new array contains references to the receiving array’s elements, not copies of them. それらのコピーではなく、受け手側の持つ要素に対する参照を含んでいる新しい配列。

This method is similar to sortedArrayUsingFunction:context:, except that it uses the supplied hint to speed the sorting process. When you know the array is nearly sorted, this method is faster than sortedArrayUsingFunction:context:. If you sorted a large array (N entries) once, and you don’t change it much (P additions and deletions, where P is much smaller than N), then you can reuse the work you did in the original sort by conceptually doing a merge sort between the N “old” items and the P “new” items. このメソッドはsortedArrayUsingFunction:context:に似ていますが、それがソート処理をはかどらせるために提供されるヒントを使うところが違います。この配列がおおよそソートされるのをあなたが知っているとき、このメソッドはsortedArrayUsingFunction:context:よりも高速です。あなたがある大きな配列（N個の登録項目）を一旦ソートしたならば、そしてあなたがそれをほとんど変更しないならば（P個の追加と削除、ここでPはNよりはるかに少ない）、そのときあなたは、あなたが元のソートにおいて行った作業を再利用することが、概念的にNの「旧」項目とPの「新」項目間のマージソートの実行によって可能です。

To obtain an appropriate hint, use sortedArrayHint. You should obtain this hint when the original array has been sorted, and keep hold of it until you need it, after the array has been modified. The hint is computed by sortedArrayHint in O(N) (where N is the number of items). This assumes that items in the array implement a -hash method. Given a suitable hint, and assuming that the hash function is a “good” hash function, -sortedArrayUsingFunction:context:hint: sorts the array in O(P*LOG(P)+N) where P is the number of adds or deletes. This is an improvement over the un-hinted sort, O(N*LOG(N)), when P is small. 適切なヒントを入手するには、sortedArrayHintを使います。あなたは、元の配列がソートされ終わったときにこのヒントを取得して、配列が修正され終わった後、あなたがそれを必要とするまでそれを保持し続けなければなりません。このヒントはsortedArrayHintによってO(N)で計算されます（ここでNは項目の数です）。これは、配列の中の項目が-hashメソッドを実装することを前提とします。適切なヒントを与えられて、そしてハッシュ関数が「良好な」ハッシュ関数であると仮定して、-sortedArrayUsingFunction:context:hint:は配列をO(P*LOG(P)+N)でソートします、ここでPは追加または削除の数です。これは、O(N*LOG(N))が小さい場合、ヒント無しのソート、Pより向上するところです。

The hint is simply an array of size N containing the N hashes. To re-sort you need internally to create a map table mapping a hash to the index. Using this map table on the new array, you can get a first guess for the indexes, and then sort that. For example, a sorted array {A, B, D, E, F} with corresponding hash values {25, 96, 78, 32, 17}, may be subject to small changes that result in contents {E, A, C, B, F}. The mapping table maps the hashes {25, 96, 78, 32, 17} to the indexes {#0, #1, #2, #3, #4}. If the hashes for {E, A, C, B, F} are {32, 25, 99, 96, 17}, then by using the mapping table you can get a first order sort {#3, #0, ?, #1, #4}, so therefore create an initial semi-sorted array {A, B, E, F}, and then perform a cheap merge sort with {C} that yields {A, B, C, E, F}. このヒントは単に大きさNの配列でN個のハッシュを含んでいます。再ソートするにはあなたは内部的にマップテーブルを作成してハッシュをインデックスとマッピングする必要があります。このマップを新しい配列上で使用して、あなたはそれらインデックスに対する最初の推測を得て、それからそれをソートすることができます。例えば、対応するハッシュ値 {25, 96, 78, 32, 17} を持つソートされた配列 {A, B, D, E, F} は、内容 {E, A, C, B, F} という結果になる小さな変更にさらされるかもしれません。マッピングテーブルは、ハッシュ {25, 96, 78, 32, 17} をインデックス {#0, #1, #2, #3, #4} にマップします。{E, A, C, B, F} に対するハッシュが {32, 25, 99, 96, 17} ならば、そのときマッピングテーブルを使うことによってあなたは第一次ソート {#3, #0, ?, #1, #4} を得ることができ、それによってまず初めに半ばソートされた配列 {A, B, E, F} を作成して、それから {C} と安価なマージソートを行うことができ、それは {A, B, C, E, F} を生成します。