Как эффективно анализировать jd-файл bigdata (wikidata) в C ++?
У меня есть один файл JSON, который составляет около 36 ГБ (из Викиданных), и я хочу получить к нему доступ более эффективно. В настоящее время я использую API-интерфейс quickjsons SAX в C ++, но анализ всего файла занимает на моей машине около 7415200 мс (= 120 минут). Я хочу получить доступ к объектам json внутри этого файла в соответствии с одним из двух первичных ключей («имя» или «ключ-сущности» -> т.е. «переполнение стека» или «Q549037»), которые находятся внутри объекта json. Это означает, что мне нужно проанализировать весь файл в худшем случае.
Поэтому я подумал о двух подходах:
- разделение большого файла на миллиарды маленьких файлов — с именем файла, которое указывает имя / ключ сущности (т.е. Q549037.json / Stack_Overflow.json или Q549037 # Stack_Overflow.json) -> не уверен в перегрузке в хранилище
- построение какого-то индекса от первичных ключей к
ftell()положение в файле. Создание индекса должно занять около 120 минут (как, например, анализ), но доступ должен быть быстрее, чем- то есть использовать что-то вроде двух
std::unorderedmap(может снова столкнуться с проблемами с памятью) - индексные файлы — создайте два файла: один с записями, отсортированными по имени, и другой, отсортированными по ключу объекта (создание этих файлов, вероятно, займет намного больше времени из-за сортировки)
- то есть использовать что-то вроде двух
Какова лучшая практика для такой проблемы?
Какой подход я должен следовать? Есть другие идеи?
Решение
Я думаю, что проблема производительности не из-за разбора. Использование SAX API в RapidJSON уже должно обеспечивать хорошую производительность и дружественную память. Если вам нужно получить доступ ко всем значениям в JSON, это может быть лучшим решением.
Тем не менее, из описания вопроса, кажется, читает все значения за один раз не ваше требование. Вы хотите прочитать немного (возможно, небольшое количество) значения определенных критериев (например, по первичным ключам). Тогда чтение / разбор все не подходит для этого случая.
Вам понадобится механизм индексации. Это можно сделать с помощью позиции в файле. Если данные в позициях также являются допустимым JSON, вы можете искать и передавать их в RapidJSON для анализа этого значения JSON (RapidJSON может прекратить синтаксический анализ, когда полный JSON анализируется, kParseStopWhenDoneFlag).
Другими вариантами являются преобразование JSON в какую-то базу данных, базу данных SQL, базу данных значений ключей или пользовательские. Благодаря предоставленным средствам индексирования вы будете быстро запрашивать данные. Это может занять много времени для преобразования, но хорошая производительность для последующего поиска.
Обратите внимание, что JSON — это формат обмена. Он не был предназначен для быстрых индивидуальных запросов на большие данные.
Обновление: недавно я обнаружил, что есть проект пол-индекс это может удовлетворить ваши потребности.
Другие решения
Напишите свой собственный анализатор JSON, минимизирующий распределение и перемещение данных. Также канаву мульти-символ для прямой ANSI. Однажды я написал анализатор XML для анализа XML-файлов 4 ГБ. Я попробовал MSXML и Xerces, у которых были незначительные утечки памяти, которые при использовании на таком большом количестве данных фактически исчерпали бы память. Мой синтаксический анализатор фактически остановит выделение памяти, как только достигнет максимального уровня вложенности.
Ваше определение проблемы не позволяет дать точный ответ.
Интересно, почему вы хотите использовать JSON? Это, конечно, не лучший формат для быстрого доступа к большим данным.
Если вы интенсивно используете данные вики, почему бы не преобразовать их в более управляемый формат?
Должно быть легко автоматизировать определение БД, соответствующее формату ваших записей, и раз и навсегда преобразовать большой кусок JSON в записи БД.
Вы можете остановить преобразование БД в любой момент, когда захотите (т. Е. Сохранить каждый блок JSON в виде простого текста или улучшить его).
В минимальном случае вы получите таблицу БД, содержащую ваши записи, проиндексированные по имени и ключу.
Конечно, менее грязный, чем использование вашей файловой системы в качестве базы данных (путем создания миллионов файлов с именем name + key) или написание специального кода для поиска записей.
Это, вероятно, также сэкономит вам много места на диске, поскольку внутреннее хранилище БД обычно более эффективно, чем простое текстовое представление.
Я сделал небольшой анализ данных из Википедии. Я особенно заинтересован в извлечении уравнений, поэтому меня интересует только часть файла.
Во-первых, если вас интересуют данные WikiMedia, гораздо проще получить учетную запись Labs. Это займет около дня, и это позволит вам выполнять большую часть кода на своих компьютерах, избегая необходимости загружать несколько гигабайт. Имея учетную запись Labs, вы должны иметь возможность запускать код на достаточно современной репликации базы данных, избегая необходимости полностью использовать json.
Я использую простую программу на Python для анализа данных, она в основном выполняет несколько регулярных выражений в каждой строке; один, чтобы найти строки, содержащие <title>...</title> так что я знаю, что это за статья в Википедии, и еще несколько, чтобы найти пространство имен и математические теги. Он может обработать файл размером 160 МБ за 13 секунд, поэтому он может обработать все 36 ГБ менее чем за час.
Этот код создает текстовые файлы только с данными, которые меня интересуют. Если вы заинтересованы, код
import sys
import re
dump = len(sys.argv)>1 and sys.argv[1]=='-d'
titleRE = re.compile('<title>(.*)</title>')
nsRE = re.compile('<ns>(.*)</ns>')
mathRE = re.compile('</?math(.*?)>')
pageEndRE = re.compile('</page>')
supOc = 0
supCc = 0
subOc = 0
subCc = 0
title =""attr = ""ns = -1
inEqn = 0
for line in sys.stdin:
m = titleRE.search(line)
if m :
title = m.group(1)
expression = ""if dump : print line
inEqn = 0
m = nsRE.search(line)
if m :
ns = m.group(1)
start = 0
pos = 0
m = mathRE.search(line,pos)
while m :
if m.group().startswith('<math'):
attr = m.group(1)
start = m.end()
pos = start
expression = ""inEqn = 1
if m.group() == '</math>' :
end = m.start()
expression = ' '.join([expression,line[start:end]])
print title,'\t',attr,'\t',expression.lstrip().replace('<','<').replace('>',
'>').replace('&','&')
pos = m.end()
expression = ""start = 0
inEqn = 0
m = mathRE.search(line,pos)
if start > 0 :
expression = line[start:].rstrip()
elif inEqn :
expression = ' '.join([expression,line.rstrip()])
Извините, если это немного загадочно, но это не было предназначено для общественного потребления. Пример вывода
Arithmetic mean a_1,\ldots,a_n.
Arithmetic mean A
Arithmetic mean A=\frac{1}{n}\sum_{i=1}^{n} a_i
Arithmetic mean \bar{x}
Каждая строка имеет название статьи и уравнение латекса. Это сокращает объем данных, с которыми мне нужно работать, до более управляемых 500 тыс. Я не уверен, что такая стратегия подойдет для вашего приложения.
Для основных данных энвики разбить дамп XML на 27 меньших файлов примерно одинакового размера. Вы можете найти несколько файлов разумного размера, с которыми проще работать, чем с одним гигантским файлом или миллионами крошечных файлов. Это может быть легко разделить по первой букве в названии статьи, давая менее ста файлов каждый меньше, чем гигабайт.