Блог

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

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

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

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

— Ry

@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 .

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

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

Обновить:

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

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