Бинарный поиск XML с диска SAX-подобным способом - мудро? Возможный?

Question

Мне нужно искать в (потенциально) большом XML-файле элементы с определенной временной меткой на скоростях типа кадра в анимации.

Я делал нечто похожее в недавнем проекте, но там XML был достаточно маленьким, чтобы поместиться в памяти, поэтому я разобрал его на массив простых объектов и выполнил бинарный поиск. БУМ! супер-быстрый поиск по 800 с лишним временных меток за кадр.

На этот раз XML-файлы могут быть достаточно большими, чтобы сделать их анализ в памяти глупой идеей (это вещи iOS, поэтому объем ОЗУ ограничен). Решение в моей голове - сделать SAX-подобный анализ потока из файла, но с настраиваемым указателем. Таким образом, я мог бы переместить этот указатель вокруг файла в другом двоичном поиске, проанализировать следующий полный узел в файле и использовать его, чтобы сообщить, куда переходит указатель поиска.

Хорошая теория, я думаю. Однако, просматривая интернет, я не смог найти парсер SAX, который позволял бы устанавливать его текущий номер строки в файле. Многие из них предоставляют вам доступ только для чтения в качестве статуса, но ни один не разрешает эту крайне важную настройку позиции.

SO. Кто-нибудь знает библиотеку XML для разбора, которая имеет такую ​​возможность? Опять же, это мир iOS, поэтому все, что основано на C / C ++, подойдет, но бонусные баллы, если у него есть оболочка Obj-C.

Answer 1

Вы не можете сделать это безопасно в XML, по крайней мере, напрямую. Вы сказали, что хотите перейти к определенному номеру строки, но это может вам не помочь, потому что XML не основан на строках. И вы не можете легко перейти к n -ому дочернему узлу некоторого узла, потому что это требует полного анализа XML.

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

Если вы сделаете это таким образом, вам придется анализировать весь файл один раз (операция O (n)), но затем вы можете перейти на любой узел и выполнить быстрый анализ (в O (1)), что должно сделать бинарный поиск производительный.

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