Структура данных Java для хранения плоских данных XML для последующего доступа

Question

У меня есть плоская структура XML объемом 5 МБ, которую я хочу получить позже. Я использую XOM Parser в Java для синтаксического анализа XML, и я не хочу, чтобы цикл на все дерево каждый раз, когда я хочу получить данные, поскольку требуется время из-за размера файла.

XML-выглядит следующим образом

<TypeDesc Type="Person" Id="1" PKey="X0" xml:lang="EN" ShDes="t1" LongDes="test 1"/> 
<TypeDesc Type="Person" Id="2" PKey="X1" xml:lang="EN" ShDes="t2" LongDes="test 2"/> 
<TypeDesc Type="Person" Id="3" PKey="X3" xml:lang="EN" ShDes="t3" LongDes="test 2"/> 
... 
<TypeDesc Type="Person" Id="n" PKey="PAYMN" xml:lang="EN" ShDes="PAYMN" LongDes="payment"/> 
<TypeDesc Type="Student" Id="1" PKey="X0" xml:lang="EN" ShDes="t1" LongDes="good"/> 
<TypeDesc Type="Student" Id="2" PKey="X1" xml:lang="EN" ShDes="t2" LongDes="bad"/> 
<TypeDesc Type="Student" Id="3" PKey="X3" xml:lang="EN" ShDes="t3" LongDes="fair"/> 
... 
<TypeDesc Type="Student" Id="n" PKey="PAYMN" xml:lang="EN" ShDes="PAYMN" LongDes="fair"/> 

В моей LOGIC я хочу, чтобы извлечь longDes из узлов, если PKEY = SOMESTUFF И Type = OtherStuff

зацикливание на все это и получение, если longDes другие атрибуты удовлетворяются очень дорого.

Как сохранить мои данные, чтобы я мог получить к ним доступ в O (1) вместо O (n), чтобы я выполнял цикл всего XML за один раз и доступ к структуре данных для последующих итераций.

Answer 1

Я использовал хэш-таблицу для хранения данных. Построена хэш-таблица для каждого типа. Ключ каждой хэш-таблицы - это конкатенация всех атрибутов, с которыми я хочу проверить, и сохраненное значение - это то, что я хочу получить. Он очень эффективен и близок к O (1)

Answer 2

Вы вряд ли найдете процедуру поиска по постоянному времени для ее удовлетворения в ее текущей форме. Кроме того, поиск по постоянному времени определенного требования или вы делаете это как часть мерцающей точки зрения статуса/настройки вашего проекта? А.К.А. "the XY problem". Лучшее, что вы, скорее всего, найдете, - это алгоритм O(n log n) или O(log n); см Big O Cheatsheet

Я рекомендую вам пересмотреть существующие рамки, которые позволят разбор этой структуры:

1. Xstream
2. JAXB
3. XML Beans

Если вы счастливы с XOM, не беспокойтесь, перейдя, но я считаю, что вам нужно рассмотреть структуру данных, когда вы ищете, h, используя индекс или сохраняя его в эффективной форме - например, Дерево префикса/Trie - и затем сериализуйте его на диск/хранилище, чтобы повторный анализ был быстрее, чем очевидный компромисс между пространством и временем?

Кроме того, ваши данные имеют быть в XML? Можете ли вы преобразовать его в другой формат? Например, буферы протоколов или размещение данных в базе данных (SQL или NoSQL), хотя это может быть чрезмерным в зависимости от того, что вы делаете?

Я также задаюсь следующие вопросы:

1. Как получить с учетом этой информации? Я теряю информацию, которая может помочь в поиске?
2. Будет ли полезная помощь search algorithm?
3. Эти данные отсортированы? Могу ли я сортировать его эффективно, чтобы последующие поисковые запросы были более эффективными?