NSDictionary, NSArray, NSSet и эффективность
У меня есть текстовый файл приблизительно с 200 000 строк. Каждая строка представляет объект с несколькими свойствами. Я только перерываю одно из свойств (уникальный идентификатор) объектов. Если уникальный идентификатор, который я ищу, совпадает с уникальным идентификатором текущего объекта, я собираюсь читать остальную часть значений объекта.
Прямо сейчас, каждый раз, когда я ищу объект, я просто считал целый текстовый файл линию за линией, создаю объект для каждой строки и вижу, является ли это объект, я ищу - который является в основном самым неэффективным способом сделать поиск. Я хотел бы считать все те объекты в память, таким образом, я могу позже перерыть их более эффективно.
Вопрос, что самый эффективный путь состоит в том, чтобы выполнить такой поиск? Является NSArray с 200,000 записями хорошим способом сделать это (я сомневаюсь относительно этого)? Как насчет NSSet? С NSSet действительно ли возможно только искать одно свойство объектов?
Спасибо за любую справку!
- Ry
3 ответа
@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 .
200 000 объектов звучат так, как будто вы можете столкнуться с ограничениями памяти, в зависимости от размера объектов и вашей целевой среды. Еще одна вещь, которую вы можете рассмотреть, - это преобразовать данные в базу данных SQLite, а затем проиндексировать столбцы, по которым вы хотите выполнить поиск. Это обеспечит хороший компромисс между эффективностью и потреблением ресурсов, поскольку вам не придется загружать полный набор в память.
Используйте NSDictionary для сопоставления идентификаторов с объектами.То есть: используйте ID как ключ, а объект как значение. NSDictionary - единственный класс коллекции, который поддерживает эффективный поиск ключей. (Или поиск по ключу)
Словари - это другой вид коллекции, чем другие классы коллекций. Это ассоциативная коллекция (сопоставляет идентификаторы с объектами в вашем случае), тогда как остальные являются просто контейнерами для нескольких объектов. NSSet содержит неупорядоченные уникальные объекты, а NSArray содержит упорядоченные объекты (может содержать дубликаты).
ОБНОВЛЕНИЕ:
Чтобы избежать перераспределения при чтении записей, используйте метод dictionaryWithCapacity: . Если вы знаете (приблизительное) количество записей до их чтения, вы можете использовать его для предварительного выделения достаточно большого словаря.