Разработка шаблона для отслеживания соответствия строк UITableView основным данным в постоянное время

Question

Когда моя модель меняется, я хочу анимировать изменения в UITableView, вставляя / удаляя строки. Для этого мне нужно знать порядковый номер данной строки (чтобы я мог построить NSIndexPath), что мне трудно сделать за время, превосходящее линейное.

Например, предположим, что у меня есть список записей адресной книги, которые вручную отсортированы пользователем, то есть отсутствует «упорядочивающий» ключ, представляющий порядок сортировки. Существует также соответствующий UITableView, который показывает одну строку на запись адресной книги. Когда UITableView запрашивает источник данных, я запрашиваю NSMUtableArray, заполненный моими записями, и возвращаю необходимые данные в постоянное время для каждой строки.

Однако, если в базовой модели произошли изменения, я получаю уведомление «Джо Смит, id # 123 был удален». Теперь у меня есть дилемма. Наивным подходом было бы сканировать массив, определить индекс, по которому находится Джо Смит, и затем попросить UITableView удалить эту точную строку из представления, а также удалить ее из массива. Однако сканирование займет линейное время для завершения.

Теперь у меня может быть NSDictionary, который позволяет мне находить Джо Смита за постоянное время, но это не приносит мне большой пользы, потому что мне все еще нужно найти его порядковый индекс в массиве, чтобы дать команду UITableView удалить та строка, которая снова является линейным поиском. Кроме того, я мог бы решить сохранить порядковый номер каждого объекта внутри самого объекта, чтобы сделать его постоянным, но он будет устаревать после первого такого обновления, поскольку все последующие значения индекса будут изменены из-за удаления объекта.

Так что же является правильным шаблоном проектирования для точного отражения изменений модели в UITableView в экономичное (или, по крайней мере, логарифмическое) время?

Answer 1

Я бы добавил поле ключа в поле вашего адреса, чтобы вы могли выполнить поиск в двоичном дереве. Например, предположим, что ваша модель данных, которая передает UITableView, выглядит следующим образом:

NSString  *name;
NSString  *address;

Вы можете подумать о добавлении ключевого поля, например:

NSInteger keyIndex;
NSString  *name;
NSString  *address;

Если вы не хотите, чтобы ключ ассоциировался с моделью данных (поскольку это абстракция контроллера представления и может просто представлять порядок сортировки массива), вы можете оставить коляску NSMutableArray NSNumber. (или если производительность действительно критична, используйте настраиваемый управляемый C-Array с malloc / calloc / free) рядом с моделью данных.

KeyIndex затем заполняется, когда вы инициализируете ваш источник данных (или передаете данные в UITableView после сообщения перезагрузки). Затем это дает упорядоченное ключевое поле для очень быстрого выполнения и должно иметь порядок O * ln (n).

Вам нужно будет сохранить поле «Ключ», когда пользователь удаляет и изменяет порядок. Однако вы делаете это без ключевого поля где-то, и я не верю, что вы выйдете из линейного поиска.