В предыдущей статье я предложил мысленный эксперимент: можно моделировать планы выполнения SQL в Javascript и использовать его для разработки базы данных, которая поддерживает примеры планов. Такая система может позволить создавать новые языки запросов или использовать алгоритмы вставки в приложении обработки данных (например, можно захотеть сделать «создание индекса» для запроса LINQ, который фактически относится к оперативной памяти). данные).
В этой статье я рассмотрю проблему под другим углом зрения: структуру данных, которая может обрабатывать большие объемы данных в памяти.
И в R, и в Python / Pandas существует богатая поддержка объекта, называемого DataFrame, который сильно напоминает таблицу. Если вы загрузите файлы в них, в конечном итоге вы найдете один достаточно большой, чтобы исчерпать память, даже если у вас много оперативной памяти. Как только это произойдет, вам придется прибегнуть к другим методам — было бы предпочтительнее сохранить модель программирования и иметь инструменты для изящной обработки объема данных.
Во-первых, важно иметь достаточно большую таблицу базы данных для тестирования. Google n-grams предоставляет хорошие примеры: это количество слов и фраз из книг Google (отсканированных книг), сгруппированных по годам. Существует много тысяч этих файлов — я выбрал файл из двух словосочетаний, начинающийся с «th», то есть 30 ГБ текста.
Следующая команда unix разбивает файл на маленькие блоки — я экспериментально определил размер блоков, имея в виду около 64 КБ, так как это приемлемое значение для размеров дисковых блоков в реляционной базе данных.
split -l 2500 -a 4 googlebooks-engall-2gram-20120701-th
Это создает множество файлов, которые называются последовательно, с такими именами, как xaaaa, xaaab, xaaac, aaaad и т. Д.
Эти файлы могут быть тривиально загружены в R в фрейм данных, например, если полный файл не поддерживает это:
data <- read.table(
'g:\\n-grams\\xaaae',
header=TRUE,
sep="\t",
fileEncoding="windows-1252")
colnames(data) <- c('word', 'year', 'occurs', 'books')
> class(data)
[1] "data.frame"
Годовые диапазоны начинаются с 1800-2008, вот пример нескольких строк:
1800-2009.
“phrase” “year” “# times” “# books” The stupid 1800 6 6 The stupid 1801 13 13 The stupid 1802 11 11 The stupid 1803 11 8 The stupid 1804 12 12 The stupid 1805 3 3 The stupid 1806 6 6 The stupid 1807 6 6 The stupid 1808 3 3 The stupid 1809 11 11 The stupid 1810 17 17 The stupid 1811 17 16 The stupid 1812 4 4 The stupid 1813 7 5
Вы также можете выполнять запросы к этим данным, хотя это, очевидно, только поиск загруженного блока.
subset(data, select=c(word, year))
2489 THE GROWL 1885
2490 THE GROWL 1887
2491 THE GROWL 1903
2492 THE GROWL 1908
2493 THE GROWL 1952
2494 THE GROWL 1956
2495 THE GROWL 1958
subset(data, select=c(word, year), subset=(year == 1968))
word year
140 THE ED_NOUN 1968
296 THE EFFORT_NOUN 1968
356 THE EMBROIDERY_NOUN 1968
535 THE ENCYCLOPAEDIA 1968
Типичная файловая система хранит блоки в дереве B + для быстрой вставки и поиска. Эти деревья, как правило, короткие и широкие, что сокращает количество прыжков, чтобы найти запись, и отслеживает от одного узла к следующему на листьях, что поддерживает сканирование диапазонов дерева.
Я нашел работоспособную реализацию Javascript для дерева B + , которую я использовал для демонстрации в этой статье.
API для этой реализации довольно прост в использовании. У него есть интересное свойство: когда вы выполняете «поиск», он остается в этом месте до следующего поиска, поэтому вы можете перемещаться по нижней части дерева, если хотите.
t = new tree(3) t.insert(1, “data1”) t.insert(2, “data2”) t.seek(2)
Чтобы заполнить это дерево, нам нужно добавить наши номера блоков — это дерево требует целых чисел для ключей. Поскольку файлы, созданные выше для блоков, называются «aaa», «aab» и т. Д., Это base-26, поэтому мы можем преобразовать его в числа:
function location_int(file) {
block = file.substring(1);
power = 1;
result = 0;
for (i in block) {
result += power * (block[block.length - i - 1].charCodeAt(0) -
'a'.charCodeAt(0));
power *= 26;
}
return result;
}
undefined
location_int('aaab')
1
location_int('aaac')
2
location_int('aaad')
3
location_int('aabe')
30
location_int('aaba')
26
location_int('aqym')
11452
Это довольно легко пойти и другим путем:
function getFile(file_num) {
res = (file_num).toString(26);
filename = '';
for (i in res) {
code = res[i].charCodeAt(0)
if (code >= 97 && code <= 122)
filename += String.fromCharCode(code + 10)
else
filename += String.fromCharCode(code - 48 + 97)
}
while(filename.length < 4) {
filename = 'a' + filename;
}
return 'x' + filename;
}
getFile(0)
"xaaaa"
getFile(14522)
"xavmo"
getFile(11452)
"xaqym"
Теперь, когда мы определили эти отношения, мы можем просто вставить все числа в дерево следующим образом:
for (i = 1; i < 14521; i++) {
var msg = “gary” + i;
t.insert(i, {getData:function() { return msg; } });
}
t.seek(1000)
t.recnum.f()
На первый взгляд это кажется немного глупым — мы изобрели самый сложный в мире массив. Мы случайно наткнулись на опрятную функцию базы данных: индекс упорядоченных таблиц. Эта таблица оказывается предварительно отсортированной по слову, а затем по году, что дает прирост производительности для определенных запросов — например, «подсчет (отличное слово)» может выполняться без сохранения большого «набора» слов в БД для некоторых экономия памяти.
В реляционной базе данных хранилище не обязательно хранит строки в каком-либо определенном порядке. Каждая вставка может заполнять слот на существующей странице, поэтому несколько последовательных вставок могут размещать данные в случайных местах. Интересно, что можно влиять на подкачку в Oracle во время массовых операций: «таблица TRUNCATE» говорит ему немедленно удалить все страницы, пропуская откат, не проверяя их содержимое, а «INSERT / * + append * /» говорит ему создать новую page — пропустите шаг поиска пустых слотов на существующих страницах (хорошо для одной массивной вставки и очень медленно для многих маленьких вставок).
Обратите внимание, что я оставил вышеупомянутые объекты на каждом узле пустыми — при доступе к узлу он будет загружен в память. Поскольку я делаю это в браузере, я собираюсь загрузить блок, используя Ajax. Как только блок загружен один раз, метод getData заменит себя запомненной копией данных, что помогает последующим запросам (вот почему запрос будет выполняться быстрее при втором запуске, или как один запрос может повлиять на производительность последующие запросы):
function ajaxData() {
var data = null;
$.ajax({
url: "blocks/" + parent.block,
async: false
}).done(function(blockData) {
data = blockData.split("\n")
for (var i = 0; i < data.length; i++) {
data[i] = data[i].split("\t")
}
});
page.parent.getData = function() {
return data; // memoized!
}
return data;
}
Это решает проблемы загрузки и кэширования блоков данных, но мы все равно собираемся исчерпать ОЗУ, если выполняем длинный запрос — нам нужен способ выкинуть блоки из системы и вернуться в состояние «выгружено».
var pages = new Array(10)
var pageIdx = 0
function mallocData() {
var newPage = malloc(this)
return newPage.parent.getData(); // will trigger an ajax call
}
function malloc(parent) {
pageIdx = (pageIdx + 1) % pages.length;
var page = pages[pageIdx];
if (page.parent) {
page.parent.getData = mallocData
}
page.parent = parent;
parent.getData = ajaxData
return page;
}
Теперь мы можем объединить это с деревом.
function buildTree() {
var t = new tree(3);
for (var i = 1; i < 14521; i++) {
var block = getFile(i)
t.insert(i, {block: block, getData: mallocData} )
}
return t;
}
t.seek(1000)
t.recnum
Object {block: "xabmm", getData: function}
block: "xabmm"
t.getData()
Array[2501]
[0 … 99]
0: Array[4]
0: "thoroughly disrupts"
1: "2008"
2: "10"
3: "9"
Здесь показаны первые строки 1000-го файла. Если вы затем загружаете 11 блоков, первый блок удаляется и, в конце концов, освобождается сборщиком мусора (он установлен на низком уровне для целей тестирования — очевидно, вам нужно гораздо больше оперативной памяти).
Это, я полагаю, хорошая реализация DataFrame для больших таблиц — он поддерживает запросы «покажи первые 100 строк», типичные для исследований, и хорошо масштабируется для разбивки по проблемным большим наборам данных.
Можно создать цикл по этой таблице, чтобы сгенерировать индекс — отображение записей {«the dog»: «xamym»}, которое говорит вам, с чего начать поиск конкретной записи — после создания этого индекса поиск будет довольно быстрым. При правильной реализации эти индексы могут использоваться API-интерфейсами R или Pandas DataFrame (или системой, подобной LINQ) для поддержки значительных улучшений производительности без перестройки системы, которая рушится под нагрузкой.