NSDictionary, NSArray, NSSet и эффективность

Question

У меня есть текстовый файл, около 200 000 строк.Каждая строка представляет объект с несколькими свойствами.Я только ищу через одно из свойств (уникальный идентификатор) объектов.Если уникальный идентификатор, который я ищу, совпадает с уникальным идентификатором текущего объекта, я собираюсь прочитать остальные значения объекта.

Прямо сейчас, каждый раз, когда я ищу объект, я простоПрочитайте весь текстовый файл построчно, создайте объект для каждой строки и посмотрите, является ли это искомый объект - что является в основном самым неэффективным способом поиска.Я хотел бы прочитать все эти объекты в память, чтобы впоследствии я мог более эффективно осуществлять их поиск.

Вопрос в том, как наиболее эффективно выполнить такой поиск?Является ли NSArray на 200 000 записей хорошим способом сделать это (я сомневаюсь в этом)?Как насчет NSSet?С помощью NSSet можно ли искать только одно свойство объектов?

Спасибо за любую помощь!

- Ry

Answer 1

@ yngvedh является верным в том смысле, что NSDictionary имеет время поиска O (1) (как ожидается для структуры карты). Однако после некоторого тестирования вы можете видеть, что NSSet также имеет время поиска O (1). Вот основной тест, который я сделал, чтобы придумать это: http://pastie.org/933070

По сути, я создаю 1 000 000 строк, а затем время, которое у меня уходит на получение 100 000 случайных строк как из словаря, так и из набора. Когда я запускаю это несколько раз, набор на самом деле выглядит быстрее ...

dict lookup: 0.174897
set lookup: 0.166058
---------------------
dict lookup: 0.171486
set lookup: 0.165325
---------------------
dict lookup: 0.170934
set lookup: 0.164638
---------------------
dict lookup: 0.172619
set lookup: 0.172966

В вашем конкретном случае, я не уверен, что любой из них будет тем, что вы хотите. Вы говорите, что хотите, чтобы все эти объекты были в памяти, но действительно ли они вам нужны, или вам просто нужно несколько из них? Если это последнее, то я, вероятно, прочитал бы файл и создал бы идентификатор объекта для сопоставления смещения файла (т. Е. Запомнил, где находится каждый идентификатор объекта в файле). Затем вы можете посмотреть, какие из них вы хотите, и использовать смещение файла, чтобы перейти к нужному месту в файле, проанализировать эту строку и двигаться дальше. Это работа для NSFileHandle.

Answer 2

Используйте NSDictionary для сопоставления идентификаторов с объектами. То есть: используйте идентификатор в качестве ключа и объект в качестве значения. NSDictionary - единственный класс коллекции, который поддерживает эффективный поиск ключей. (Или поиск ключа вообще)

Словари - это другой тип коллекции, чем другие классы коллекции. Это ассоциативная коллекция (привязывает идентификаторы к объектам в вашем случае), тогда как остальные являются просто контейнерами для нескольких объектов. NSSet содержит неупорядоченные уникальные объекты, а NSArray содержит упорядоченные объекты (может содержать дубликаты).

UPDATE:

Чтобы избежать перераспределения при чтении записей, используйте метод dictionaryWithCapacity:. Если вы знаете (приблизительное) количество записей до их чтения, вы можете использовать их для предварительного выделения достаточно большого словаря.

Answer 3

200 000 объектов звучат так, как будто вы можете столкнуться с ограничениями памяти, в зависимости от размера объектов и вашей целевой среды. Еще одна вещь, которую вы можете рассмотреть, - преобразовать данные в базу данных SQLite, а затем проиндексировать столбцы, по которым вы хотите выполнить поиск. Это обеспечит хороший компромисс между эффективностью и потреблением ресурсов, поскольку вам не придется загружать полный набор в память.