Сохранение массива отсортировано - при настройке, получении или позже?

Question

В качестве помощи для изучения цели c/oop, я разрабатываю приложение iOS для хранения и отображения периодических измерений массы тела. У меня есть singleton, который возвращает mutablearray общего хранилища объекта измерения. Каждое измерение будет иметь как минимум дату и вес тела, и я хочу иметь возможность добавлять исторические измерения.

Я хотел бы показать результаты измерений в порядке дат. Каков наилучший способ сделать это? Насколько я могу видеть, следующие параметры: 1) при добавлении измерения - я переопределяю addobject для сортировки общего хранилища каждый раз после добавления измерения; 2) при получении mutablearray я сортирую его или 3) получаю mutablearray в любом порядке, когда это происходит в общем хранилище, затем сортируйте его при отображении таблицы/диаграммы.

Вероятно, данные будут получены чаще, чем добавлено новое значение, поэтому вариант 1 уменьшит избыточную сортировку общего хранилища - так что это лучший способ, да?

Answer 1

Вы можете использовать модифицированную версию (1). Вместо того, чтобы сортировать полный массив каждый раз, когда вставлен новый объект, вы используете метод, описанный здесь: https://stackoverflow.com/a/8180369/1187415, чтобы вставить новый объект в массив в нужном месте.

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

Поскольку вы сказали, что данные чаще извлекаются, чем новые данные, это кажется более эффективным.

Answer 2

Если я забуду ваш специальный случай, этот вопрос не так-то просто ответить. Есть два основных решения:

1. Keep массив несортированный и при попытке доступа к элементу и массив не отсортирован, то разбирайтесь. Назовем это «ленивая сортировка».

2. Хранить массив отсортированным при вставке элементов. Обратите внимание, что речь идет не о добавлении нового элемента в конец, а затем сортировке всего массива. Речь идет о поиске того, где элемент должен быть (двоичный поиск) и разместить его там. Назовем это «отсортированная вставка».

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

Пример:

1. Вы хотите вставить сотни элементов в массиве, а затем получить доступ к элементам, а затем снова вставить сотни элементов, то доступ. Таким образом, вы будете вставлять значения в большие куски. В этом случае ленивая сортировка будет лучше.

2. Вы часто вставляете отдельные элементы, и вы часто будете обращаться к элементам. Тогда отсортированная вставка будет иметь лучшую производительность.

3. Что-то посередине (между вставкой 1 и вставкой десятков элементов). Вам, вероятно, не важно, какой из методов будет использоваться.

(Обратите внимание, что можно использовать также специализированные структуры, чтобы сохранить массив отсортирован, не основаны на NSArray, например, структуры на основе сбалансированного дерева, сохраняя при этом число элементов в поддереве).