Какая функция сортировки используется в NSArray?

Question

Это действительно вопрос из трех частей, но я сам ответил на первый вопрос:

Я работаю на iPhone, с множеством объектов (до 200) на экране. Каждый объект должен смотреть, если он перекрывает другие объекты, и действовать соответственно. Моя первоначальная наивная реализация состояла в том, чтобы каждый объект проходил через список каждого другого объекта, чтобы проверить их ограничивающие рамки (используя CGRectInsersectsRect).

Итак, мой вопрос (и ответ): какой метод лучше? Моя новая реализация состоит в том, чтобы сортировать массив каждого кадра, используя сортировку вставкой (поскольку данные будут в основном уже отсортированы) по y-позиции каждого объекта, а затем проверять только ближайший объект по обе стороны от одного поиска, чтобы увидеть, он находится в диапазоне по вертикали, затем проверьте по горизонтали.

Первый вопрос: является ли сортировка вставкой методом, который я хочу использовать для массива объектов, которые имеют тенденцию перемещаться случайным образом, но только в небольшой степени, поэтому они в основном остаются в порядке, основанном на последнем кадре? Также: какой алгоритм сортировки использует NSArray, когда я вызываю

- sortedArrayUsingSelector:

Я бы предположил, что он использует быструю сортировку, поскольку она наиболее полезна в общем случае. Кто-нибудь знает, если я ошибаюсь? Кто-нибудь знает, могу ли я изменить метод сортировки или мне придется написать собственную функцию сортировки?

Второй вопрос: есть ли функция для извлечения элементов из отсортированного массива с использованием бинарного поиска, а не наивного подхода, который, как я предполагаю, используется

- indexOfObject:

или я должен был бы написать свой собственный?

Answer 1

NSArray использует много различных структур данных внутри, в зависимости от того, сколько объектов в массиве. См. запись в блоге Питера Аммона для получения дополнительной информации. Но в основном это означает, что вы не можете ожидать, что произойдет что-то подобное. Иногда стоит написать собственную реализацию массива с использованием массивов C, чтобы вы могли сами управлять сортировками.

Определенно, есть гораздо более быстрые способы обнаружения столкновений. Изучите иерархии ограничивающих томов, такие как деревья KD или подобные.

Насколько я знаю, indexOfObject: единственный способ, но он потенциально не так глуп, как вы думаете. Для NSDictionary все можно изменить, поэтому они могут использовать некоторые из этих смартов в NSArray.