ソートされたNSMutable配列と回答インデックスパスにオブジェクトを追加します

Question

私はTopicと呼ばれるクラスの並べ替えられた可変配列を持っています。トピックは、パブリケーションの配列を表します。私はトピックをテーブルに提示し、定期的にWebサービスから新しいパブリケーションを取得します。新しいパブリケーションが到着したら、アニメーションを使ってテーブルに追加したいと思います。

私はこの配列に追加し、正しいインデックスパスに答えるために必要な計算作業です。誰かがこれより直接的な方法を提案することはできますか？

// add a publication to the topic model. if the publication has a new topic, answer 
// the index path of the new topic 
- (NSIndexPath *)addPublication:(Publication *)pub { 

    // first a search to fit into an existing topic 
    NSNumber *topicId = [pub valueForKey:@"topic_id"]; 
    for (Topic *topic in self.topics) { 
     if ([topicId isEqualToNumber:[topic valueForKey:"id"]]) { 
      // this publication is part of an existing topic, no new index path 
      [topic addPublication:pub]; 
      return nil; 
     } 
    } 

    // the publication must have a new topic, add a new topic (and therefore a new row) 
    Topic *topic = [[Topic alloc] initWithPublication:publication]; 
    [self.topics addObject:topic]; 

    // sort it into position 
    [self.topics sortUsingSelector:@selector(compareToTopic:)]; 

    // oh no, we want to return an index path, but where did it sort to? 
    // yikes, another search! 
    NSInteger row = [self.topics indexOfObject:topic]; 
    return [NSIndexPath indexPathForRow:row inSection:0]; 
} 

// call this in a loop for all the publications I fetch from the server, 
// collect the index paths for table animations 
// so much computation, poor user's phone is going to melt! 

最初の検索を回避する方法はありません。しかし、配列に新しいものを追加し、並べ替えを維持し、配置された場所を覚えておくより効率的なやり方がありますか？

Answer 1

これはほとんど問題ではありません。 NSArraysare actually hashesであり、検索は真の配列よりもはるかに高速です。とにかくいくつの話題がありますか？

パフォーマンスを測定して不良と判断した場合は、B-treeを使用して調べることができます。 Kurt Revis氏は、Core Foundationの同様の構造（binary heap）へのリンクで以下のようにコメントしています。CFBinaryHeap

もう1つのオプション（測定する必要があります）は、初めてアレイを歩いているときに比較を行うことです。あなたは、スポットをマークし、直接挿入を行うことができます。

NSUInteger insertIndex = 0; 
NSComparisonResult prevOrder = NSOrderedDescending; 
for (Topic *topic in self.topics) { 
    NSComparisonResult order = [topicId compareToTopic:topic]; 
    if (NSOrderedSame == order) { 
     // this publication is part of an existing topic, no new index path 
     [topic addPublication:pub]; 
     return nil; 
    } 
    else if(prevOrder == NSOrderedDescending && 
      order == NSOrderedAscending) 
    { 
     break; 
    } 
    insertIndex++; 
    prevOrder = order; 
} 

_{申し訳ありませんが、私はこれをテストしていませんのでご注意ください。}

これは実際にあなたがそれを書いたやり方よりも優れているかどうかはわかりません。

は明らかにの処理が遅すぎない限り、コンピュータの処理について心配する必要はありません。

Answer 2

ソートされたリストに値を挿入するのはかなり簡単です。たとえば、数字「3」を「1,2,7,9」のリストに挿入する方法について考えてみましょう。あなたはまったく同じことをしたい。

forループを使用して、インデックスで配列をループします。

オブジェクトごとにcompareToTopic:を使用して、挿入するオブジェクトと比較します。

挿入する適切なインデックスが見つかったら、-[NSArray insertObject:atIndex:]を使用して挿入します。

次に、そのインデックスを使用してNSIndexPathを返します。

編集：他の回答が指摘するように、バイナリ検索は高速になりますが、正しく取得するには間違いなくトリッキーです。

Answer 3

あなたがしたことは正しいと思います。別の方法があります。独自のバイナリ検索の実装方法を記述することができます。 （わずか数行のコードしかありません）。そして、新しいオブジェクトが収まるべきインデックスを取得することができます。そしてinsertObject：atIndex：メソッドを使用して、必要なインデックスに新しいオブジェクトを追加します。