Objekt zu sortierten NSMutable-Array hinzufügen und Indexpfad antworten

Question

Ich habe ein sortiertes veränderbares Array einer Klasse namens Topic. Die Themen repräsentieren eine Reihe von Publikationen. Ich präsentiere die Themen in einer Tabelle und hole regelmäßig neue Publikationen von einem Web-Service ab. Wenn eine neue Publikation eintrifft, möchte ich sie mit einer Animation zur Tabelle hinzufügen.

Was mich stört, ist die Rechenarbeit, die ich tun muss, um in dieses Array hinzuzufügen und den richtigen Indexpfad zu beantworten. Kann jemand einen direkteren Weg als das vorschlagen:

// 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! 

Es gibt keine um die erste Suche, ich denke. Aber gibt es eine effizientere Möglichkeit, einem Array eine neue Sache hinzuzufügen, eine Art zu pflegen und sich daran zu erinnern, wo es platziert wurde?

Answer 1

Dies ist fast sicher kein Problem; NSArraysare actually hashes, und die Suche ist viel schneller als es für ein echtes Array wäre. Wie viele Themen haben Sie möglicherweise?

Immer noch, wenn Sie die Leistung messen und es schlecht finden, könnten Sie in der Verwendung eines B-tree; Kurt Revis kommentierte unten mit einem Link zu einer ähnlichen Struktur (a binary heap) in Core Foundation: CFBinaryHeap.

Eine andere Option (die auch gemessen werden müsste) könnte der Vergleich sein, wenn Sie das Array das erste Mal durchlaufen; Sie können die Stelle markieren und das Einfügen direkt tun:

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; 
} 

_{Bitte beachten Sie, dass ich nicht getestet haben, sorry.}

Ich bin mir nicht sicher, ob das tatsächlich besser oder schneller ist als die Art, wie Sie es geschrieben haben.

Mach dir keine Sorgen über die Arbeit, die der Computer macht, es sei denn, es ist nachweisbar tun es zu langsam.

Answer 2

Es ist ziemlich einfach, einen Wert in eine sortierte Liste einzufügen. Denken Sie darüber nach, wie Sie beispielsweise die Zahl "3" in die Liste "1, 2, 7, 9" einfügen würden. Du willst genau dasselbe machen.

Durchlaufen Sie das Array nach Index und verwenden Sie eine Schleife for.

Verwenden Sie für jedes Objekt compareToTopic:, um es mit dem Objekt zu vergleichen, das Sie einfügen möchten.

Wenn Sie den entsprechenden Index zum Einfügen finden, verwenden Sie -[NSArray insertObject:atIndex:], um ihn einzufügen.

Dann geben Sie einen NSIndexPath mit diesem Index zurück.

Edit: und, wie die anderen Antworten zeigen, wäre eine binäre Suche schneller - aber definitiv schwieriger, richtig zu machen.

Answer 3

Was Sie getan haben, ist richtig, denke ich. Es geht auch anders. Sie können Ihre eigene binäre Suchimplementierungsmethode schreiben. (Das hat nur wenige Zeilen Code). Und Sie können den Index abrufen, in den das neue Objekt passen soll. Fügen Sie das neue Objekt mithilfe von insertObject: atIndex: method zum gewünschten Index hinzu.