0

2つの並べ替え NSMutableArraysがあります（または、重要ではない他のコレクションを使用できます）。最初の配列から2番目の配列にオブジェクトを挿入し、2番目の配列で並べ替え順序を保持する必要があります。それを行うための最適な（最速の）方法は何ですか？既知の優れたアルゴリズムをすべて実装できますが、私の質問は、すでにいくつかの組み込みメソッドがあるかどうかです。そうでない場合、私の場合の最良のアルゴリズムは何ですか？

4

5 に答える 5

3

本当の答えは次のようになります：あなたが尋ねているので、それは異なります：ソート順を維持しながら、ある配列から別の配列にオブジェクトを挿入する最速の方法は何ですか。

ソートされた配列の正しい場所に挿入する方法は組み込まれていません。2つのアレイを足し合わせるだけで同じ効果を得ることができますが、「最速の方法」ではありません。

実際に高速になるのは、アレイに含まれるデータの量、アレイ1とアレイ2のデータの比率（一方のアレイにもう一方のアレイよりもはるかに多くのデータが含まれる）など、さまざまな要因によって異なります。

注：おそらく、単純なソリューションから始めて、パフォーマンスの問題が発生した場合にのみ最適化する必要があります。ただし、大規模なデータセットを使用して測定を行い、ユーザーが持っている可能性のあるすべてのデータでソリューションが機能することを確認します。

あるソートされた配列から別のソートされた配列へのアイテムの挿入

オブジェクトを適切な場所に挿入して2つの配列をマージする場合は、通常のアルゴリズムが適用されます。小さい配列を大きい配列に挿入し、すべてのアイテムを1つずつではなく、可能な場合はソートされたシーケンス全体を挿入するようにしてください。

最高のパフォーマンスを得るinsertObjects:atIndexes:には、オブジェクトを1つずつ挿入するのではなく、を使用してバッチ挿入を行うようにしてください。

indexOfObject:inSortedRange:options:usingComparator:オプションを指定すると、各項目を他の配列に挿入する必要があるインデックスを見つけるために使用できNSBinarySearchingInsertionIndexます。また、使用しているコンパレータは、配列をソートしたコンパレータと同じである必要があります。そうでない場合、結果は「未定義」になります。

これを念頭に置いて、あなたはこのようなことをするでしょう

Create mutable index
For every ITEM in SMALLER ARRAY
    Find the index where to insert ITEM in LONGER ARRAY
    Add (the insertion location + the location in the short array) as the index in the mutable set.
Next item.

Batch insert all items.

のドキュメントにinsertObjects:atIndexes:は、「以前の挿入が行われた後にインデックスで指定された対応する場所」と記載されています。これは、2つの並べ替えられた配列の場合、インデックスの低いすべてのアイテムがすでに追加されていることを意味します。したがって、短い配列のオブジェクトのインデックスを、から返された値に追加する必要がありますindexOfObject:inSortedRange:options:usingComparator:。

もう1つの（おそらく非常に時期尚早な最適化）方法は、ループ内のすべてのアイテムのsortedRangeを減らして、挿入するアイテムがより大きいことがわかっている配列の部分を検索する必要がないようにすることです。

おそらく他にも多くの最適化を行うことができます。あなたはまだ最初に測定する必要があります！うまくいけば、これはあなたが始めるのに役立つでしょう。

于 2012-06-11T13:46:19.103 に答える
2 
NSArray *newArray=[firstArray arrayByAddingObjectsFromArray:secondArray];
newArray = [newArray sortedArrayUsingSelector:@selector(localizedCaseInsensitiveCompare:)];
于 2012-06-11T13:46:35.537 に答える
2

まず、最初の配列のすべてのオブジェクトを2番目の配列に追加してから、2番目の配列を再利用します。どれくらいの時間がかかりますか。許容できる場合は、そこで停止します。

そうでない場合は、バイナリ検索を試して、最初の配列の各項目の2番目の配列の挿入点を見つけることができます。両方の配列がソートされているため、毎回最後の挿入ポイントを下限として使用することで、検索を最適化できる場合があります。このようなもの：

NSInteger insertionPoint = -1;
for (id object in array1)
{
    insertionPoint = [self binarySearch: array2 for: object lowerBound: insertionPoint + 1];
    [array2 insertObject: object atIndex: insertionPoint];
}
于 2012-06-11T15:13:04.893 に答える
1

ココアクラスNSSortDescriptorとsortedArrayUsingDescriptors:fromNSArrayは、あなたが求めていることを実行する必要があります。

sortUsingDescriptors:可変配列を使用しているため、新しい配列を作成せずに可変配列を並べ替える方法を使用することをお勧めします。

于 2012-06-11T13:46:11.167 に答える
0

こちらのドキュメントを参照して、NSArrayの並べ替え方法のいずれかが機能するかどうかを確認してください。http://developer.apple.com/library/mac/#documentation/Cocoa/Reference/Foundation/Classes/NSArray_Class/NSArray.html。メソッドまで下にスクロールでき、ソート用の7つの組み込みメソッドがあります。おそらく、2つの配列を組み合わせて、sortedArrayUsingComparator：または他のメソッドの1つを実行することができます。

于 2012-06-11T13:48:14.610 に答える