Алгоритмы нехватки памяти для адресации больших массивов - PullRequest
Новая
       10

Алгоритмы нехватки памяти для адресации больших массивов

2 голосов
/ 21 мая 2010

Я пытаюсь иметь дело с очень большим набором данных. У меня есть k = ~ 4200 матриц (разных размеров), которые нужно сравнивать комбинаторно, пропуская неуникальные и самостоятельные сравнения. Каждое из k (k-1) / 2 сравнений создает матрицу, которую необходимо индексировать по отношению к своим родителям (то есть можно узнать, откуда она взялась). Удобный способ сделать это - (треугольно) заполнить массив ячеек размером k на k результатом каждого сравнения. Это в среднем ~ 100 X ~ 100 матриц. Используя поплавки одинарной точности, он в целом обрабатывает до 400 ГБ.
Мне нужно 1) сгенерировать массив ячеек или его части, не пытаясь поместить все это в память, и 2) получить доступ к его элементам (и их элементам) таким же образом. Мои попытки оказались неэффективными из-за зависимости от eval() MATLAB, а также от save и clear, встречающихся в циклах. 

for i=1:k
    [~,m] = size(data{i});
    cur_var = ['H' int2str(i)];
    %# if i == 1; save('FileName'); end; %# If using a single MAT file and need to create it.
    eval([cur_var ' = cell(1,k-i);']);
    for j=i+1:k
        [~,n] = size(data{j});
        eval([cur_var '{i,j} = zeros(m,n,''single'');']);
        eval([cur_var '{i,j} = compare(data{i},data{j});']);
    end
    save(cur_var,cur_var); %# Add '-append' when using a single MAT file.
    clear(cur_var);
end

Другая вещь, которую я сделал, - это выполнить разбиение, когда mod((i+j-1)/2,max(factor(k(k-1)/2))) == 0. Это делит результат на наибольшее количество кусков одинакового размера, что кажется логичным. Индексация немного сложнее, но не так уж и плоха, потому что можно использовать линейный индекс.

Кто-нибудь знает / видит лучший способ?

Ответы [ 2 ]

1 голос
/ 22 мая 2010

Вот версия, которая сочетает в себе быстродействие с использованием минимального объема памяти.

Я использую fwrite / fread, чтобы вы все еще могли использовать parfor (и на этот раз я убедился, что он работает :)) 

%# assume data is loaded an k is known

%# find the index pairs for comparisons. This could be done more elegantly, I guess.
%# I'm constructing a lower triangular array, i.e. an array that has ones wherever
%# we want to compare i (row) and j (col). Then I use find to get i and j
[iIdx,jIdx] = find(tril(ones(k,k),-1));

%# create a directory to store the comparisons
mkdir('H_matrix_elements')
savePath = fullfile(pwd,'H_matrix_elements');

%# loop through all comparisons in parallel. This way there may be a bit more overhead from
%# the individual function calls. However, parfor is most efficient if there are 
%# a lot of relatively similarly fast iterations.
parfor ct = 1:length(iIdx)

   %# make the comparison - do double b/c there shouldn't be a memory issue 
   currentComparison = compare(data{iIdx(ct)},data{jIdx{ct});

   %# create save-name as H_i_j, e.g. H_104_23
   saveName = fullfile(savePath,sprintf('H_%i_%i',iIdx(ct),jIdx(ct)));

   %# save. Since 'save' is not allowed, use fwrite to write the data to disk
   fid = fopen(saveName,'w');

   %# for simplicity: save data as vector, add two elements to the beginning
   %# to store the size of the array
   fwrite(fid,[size(currentComparison)';currentComparison(:)]);  % ' #SO formatting

   %# close file
   fclose(fid)
end



%# to read e.g. comparison H_104_23
fid = fopen(fullfile(savePath,'H_104_23'),'r');
tmp = fread(fid);
fclose(fid);

%# reshape into 2D array.
data = reshape(tmp(3:end),tmp(1),tmp(2));
1 голос
/ 21 мая 2010

Вы можете избавиться от вызовов eval и clear, назначив имя файла отдельно. 

for i=1:k
    [~,m] = size(data{i});
    file_name = ['H' int2str(i)];    
    cur_var = cell(1, k-i);
    for j=i+1:k
        [~,n] = size(data{j});
        cur_var{i,j} = zeros(m, n, 'single');
        cur_var{i,j} = compare(data{i}, data{j});
    end
    save(file_name, cur_var); 
end

Если вам нужно, чтобы сохраненные переменные принимали разные имена, используйте опцию -struct для сохранения. 

str.(file_name);
save(file_name, '-struct', str);
...