Добавить объект в отсортированный массив NSMutable и указать путь индекса ответа

Question

У меня есть отсортированный изменяемый массив класса с именем Topic. Темы представляют собой множество публикаций. Я представляю темы в таблице и периодически извлекаю новые публикации из веб-службы. Когда появится новая публикация, я бы хотел добавить в таблицу анимацию.

Меня беспокоит вычислительная работа, которую мне нужно сделать, чтобы добавить в этот массив и ответить на правильный путь индекса. Может кто-нибудь предложить более прямой путь, чем этот:

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

Довольно просто вставить значение в отсортированный список. Подумайте, например, как бы вы вставили число «3» в список «1, 2, 7, 9». Вы хотите сделать то же самое.

Цикл по массиву по индексу, используя цикл for.

Для каждого объекта используйте compareToTopic:, чтобы сравнить его с объектом, который вы хотите вставить.

Когда вы найдете соответствующий индекс для вставки, используйте -[NSArray insertObject:atIndex:] для его вставки.

Затем верните NSIndexPath с этим индексом.

Редактировать: и, как указывают другие ответы, бинарный поиск будет быстрее - но определенно сложнее получить правильное.

Answer 2

Это почти наверняка не проблема;NSArrays на самом деле хэши , и поиск выполняется намного быстрее, чем для истинного массива.Сколько тем вы можете иметь в любом случае?

Тем не менее, если вы измеряете производительность и находите ее плохой, вы можете использовать B-дерево ;Курт Ревис прокомментировал ниже ссылку на аналогичную структуру ( двоичная куча ) в Core Foundation: CFBinaryHeap .

Другой вариант (который также должен быть измерен) может быть, чтобы сделать сравнение, как вы проходите массив в первый раз;Вы можете отметить место и выполнить вставку напрямую:

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 3

То, что вы сделали, правильно, я думаю. Есть другой способ. Вы можете написать свой собственный метод реализации бинарного поиска. (Который имеет всего несколько строк кода). И вы можете извлечь индекс, в который должен вписаться новый объект. И добавить новый объект в требуемый индекс, используя метод insertObject: atIndex:.