Проблема с крупными массивами

[Mantius]

Создаем массив, скажем, двумерный:

Код: Выделить всё

array [1..62500,1..20000] of real;

либо аналогичный по своей сути, но трехмерный:

Код: Выделить всё

array [1..250,1..250,1..20000] of real;

в обоих случаях при попытке обращения к элементу с достаточно большими номерами(например, [1,1,1] пишется нормально, а [10,10,10] уже нет) компилится нормально, но при запуске готового приложения на строке операции с массивом(в моем случае-это присваивание) вылетает с ошибкой:

project raised exception class "External: SIGSEGV"

Если вместо 62500 элементов писать хотя бы 10 000, то уже работает нормально со всеми элементами.
Лазарус 0.9.26
FPC 2.2.2
Проверялось на ХР и висте.

[*vmr]

1) 250 * 250 * 20 000 * SizeOf(real) = 7.5 Гига (размер real принят за шесть байт)
2) 10 000 * 20 000 * SizeOf(real) = 1.2 Гига

Думаю сдесь мысль понятна


3) 10 * (250 * 20 000 * 6) + 10 * 20 000 * 6 + 10*6 = 300000000 + 1200000 + 60 = 301 200 060 = 301 Мб
Вот сдесь уже интереснее... может стоит проверить с каких адресов ФПЦ размещает данные...

[Mantius]

Думаю сдесь мысль понятна

Ну в целом понятна, непонятно что мне делать теперь?

Вот сдесь уже интереснее... может стоит проверить с каких адресов ФПЦ размещает данные...

Ошибка это появляется в зависимости от размерности массива, т.е. это как раз и есть ее проявление при попытке работать с большими массивами.

[shade]

Ну в целом понятна, непонятно что мне делать теперь?

1. использовать разряженыхе массивы (sparse array).
2. использовать внешнюю память (диск) + кеширование, написать класс обёртку для работы с таким массивом
3. может быть использовать B-деревья...
4. использовать потоковую обработку (подходит с случае если можно изменить алгоритм так, чтобы каждый элемент исходного массива читаться один раз,... или могут быть вариации)

всё зависит от задачи...

[Mantius]

Задача-построение многослойного персептрона(нейронной сети). В принципе, с внутренними слоями особых проблемы быть не должно, а вот входной слой данных просто огромен получается.
Какой вариант для моей задачи будет оптимальным?

[Vadim]

Какой вариант для моей задачи будет оптимальным?

Не использовать статические массивы вообще.
К примеру можно воспользоваться связанными списками. Мне, к примеру, нравится компонент TStringList. Это симулятор динамического (безразмерного) массива. Достоинство в том, что можно использовать для данных всю (т.е. 2 ГБ или 3 ГБ, если выставлен соответствующий ключ в boot.ini) динамическую память для данных. Окромя строки, TStringList содержит ещё и указатель на аналогичный компонент, за счёт чего можно строить связанные списки. Обращаться к ним можно так же как и к массиву - по индексу:
StringList.Strings[i] - к строке
StringList.Objects[i] - к объекту

[Mantius]

Спасибо большое! Постараюсь на днях поискать инфу об этом элементе и его применении, потом отпишусь о результатах. Только один вопрос:

т.е. 2 ГБ или 3 ГБ, если выставлен соответствующий ключ в boot.ini

Вот тут какой ключ выставлять нужно?

[Vadim]

А Вы уверены, что у Вас данных будет более чем 2 ГБ?

[shade]

Задача-построение многослойного персептрона(нейронной сети). В принципе, с внутренними слоями особых проблемы быть не должно, а вот входной слой данных просто огромен получается.Какой вариант для моей задачи будет оптимальным?

Думаю потоковая думаю что нужно копать в стороноу потоковой обработка (stream, не пупать с thread).

[Mantius]

А Вы уверены, что у Вас данных будет более чем 2 ГБ?

Нет, конечно.
Могу примерно описать что потребуется: 62500 не очень больших(real просто за глаза) дробных значений во входном слое, в первом скрытом слое будет порядка 20 000-25 000 ячеек в каждой из которой будет храниться 62500 небольших дробных чисел(по количеству нейронов входного слоя), следующий слой будет примерно в 3 раза меньше предыдущего и опять в каждой его ячейке по числу на каждую ячейку предыдущего слоя и так далее. Всего около 7 слоев, НО, как я представляю, основную нагрузку дает именно первый слой(точнее, связи между входным и скрытым слоями, число которых равно произведению количества элементов входного слоя на число элементов скрытого слоя), потому остальные можно, в принципе, и не брать в расчет.

Думаю потоковая думаю что нужно копать в стороноу потоковой обработка (stream, не пупать с thread).

Не дадите ссылочку где почитать подробнее?

Добавлено спустя 8 минут 15 секунд:
Почитал про TStringList, но ведь данные в нем хранятся как строки, не слишком ли расточительно будет вместо массивов из real преобразовывать всё в строку, а потом обратно в число?
В нашем случае только в первом слое будет более 2 000 000 000 таких преобразований, а при обучении сети таких действий будет выполнено несколько сотен, может даже тысяч.
Да и сколько будут весить 2 000 000 000 строк?

Про stream вообще не понял как и что делать...

[Vadim]

Mantius
Ну давайте посчитаем, сколько это займёт примерно... Вместо Real используем нечто более современное - Single.
Входной слой: 62 500 х 4 = 250 000
Первый слой: 25 000 х 4 х 62 500 х 4 = 25 000 000 000
Второй слой: 8 300 х 4 х 62 500 х 4 = 8 300 000 000
Третий слой: 2 700 х 4 х 62 500 х 4 = 2 700 000 000
Четвёртый слой: 926 х 4 х 62 500 х 4 = 926 000 000
Пятый слой: 308 х 4 х 62 500 х 4 = 308 000 000
Шестой слой: 103 х 4 х 62 500 х 4 = 103 000 000
Седьмой слой: 34 х 4 х 62 500 х 4 =34 000 000
Итого: 37 371 МБ или 37 ГБ. Это если не считать расходов памяти на разные служебные цели.
Делаем вывод, что оперативной памяти Вам не хватит, если Вы используете 32-ух разрядную версию какой-либо операционной системы. Для 64-ёх разрядной ОЗУ вполне хватит, вот только деньги, мать их за ногу...
Ситуация патовая. Что тут можно предпринять? Использовать дешёвую память, т.е. жёсткий диск. Для хранения данных наиболее целесообразно использовать какой либо сервер базы данных, т.к. там уже есть все методы занесения и извлечения данных, а так же манипуляций ими.

[shade]

Не дадите ссылочку где почитать подробнее?

Ни одна ссылка на ум не приходит.
Да и нет ничего мудрёного в этой идее:

У вас откуда-то берутся данные, либо из файла, либо снимаются с каких-то датчиков. Вы эти данные представляете себе мыслено в виде последовательности/потока значений. Например, в вашем случае на входе матрица M*N, её можно представить виде последовательности M рядов в каждом из которых N значений, всё вместе - поток значений размером M*N.

Например, эта матрица записана в файле, вначале файла, два целых числа M (число строк, до 1000) и N (число столбцов, до 1000), далее следуют M*N значений (real) ячеек. Нужно усреднить значения в матрице: получит матрицу K*L, где K = M/2, L = N/2, а каждое значение - среднее арифметическое остальных соседних 4 клеток исходной матрицы.

Входная матрица занимает 1000 * 1000 * 6 = 6 000 000 ~ 6Гб.
Выходная матрица занимает 500 * 500 * 6 = 1 500 000 ~ 1,5Гб

Входная матрица в памяти не умещатся, выходная если и вместиться, то в притык (т.к. на пользовательское простанство на 32-биных системах выделяется ~ 2Гб, в котором кроме ваших данных ещё располагается ваш код и код используемых библиотек, в том числе системных).

Но одна строка выходной матрицы занимает 500 * 6 = 3000 ~ 3Кб, т.е. мы можем смело держать в памяти одну выходную строку. А значит мы можем вычислять результирующую матрицу построчно. Чтобы вычислить одну строку выходной матрицы, нам нужно прочитать две строки входной матрицы - (12Кб).


Отсюда пишем алгоритм:

Код: Выделить всё

var
  inp, outp: TFileStream;
  x: array [0..1, 0..999] of real;
  y: array [0..500] of real;
  m, n: Integer;
  k, l: Integer;
  i, j: Integer;
begin
  inp := TFileStream.Create(inputFileName, fmOpenRead);
  outp := TFileStream.Create(outputFileName, fmCreate);

  // читаем размеры
  inp.ReadBuffer(m, sizeof(m));
  inp.ReadBuffer(n, sizeof(n));

  // вычисляем размеры выходной матрицы
  k := m div 2;
  l := n div 2;

  // запишем в выходной поток размеры результирующей матрицы
  outp.WriteBuffer(k, sizeof(k));
  outp.WriteBuffer(l, sizeof(l));

  // цикл по строкам внешней матрицы
  for i := 0 to k-1 do
  begin
    // читаем две строки входной матрицы
    inp.ReadBuffer(@x[0], n * sizeof(x[0,0]);
    inp.ReadBuffer(@x[1], n * sizeof(x[0,0]);
   
    // вычисляем строку выходной матрицы
    for j := 0 to l-1 do
      y[j] := (x[0, 2*j] + x[0, 2*j+1] + x[1, 2*j] + x[1, 2*j+1]) / 4;

    // Записываем строку выходной матрицы
    oup.WriteBuffer(@y[0], l * sizeof(y[0]));
  end;

  inp.free;
  outp.free;
end;


Пушу без проверки, потому могут быть ошибки - главное суть - читам из потока пару строк, вычисляем результирующую строку и записываем в поток результат. Алгоритм обрабатывает матрицу размером до 6Гб, но расходует при этом в пределах 20 Кб под буферы. Нужно только придумать алгоритм, возможно нужно изменить формат входных данных, или считать ячейки с датчиков в каком-то особом порядке...

опять всё от задачи зависит... например, чтобы перемножить две матрицы, то будет проще, если вторая матрица уже транспонирована...

[Mantius]

Второй слой: 8 300 х 4 х 62 500 х 4 = 8 300 000 000

немного не так: второй скрытый слой связывается с первым скрытым слоем, т.е. умножать нужно на 25 000, а не на 62 500 и так далее.

Первый слой: 25 000 х 4 х 62 500 х 4 = 25 000 000 000

и вот здесь тоже немного иначе: мы храним ОДНУ связь для одной пары элементов из входного и скрытого слоя. Т.е. получаем, что одна четверка лишняя.
Конечно, крайне нежелательно, но думаю, что можно было бы попытаться уменьшить входные данные размера до 200*200, т.е. 40 000 элементов.
Да, я вот щас подумал, входной слой-это оттенки серого для точек с картинки размером 250*250, так что для них можно использовать минимальный byte, но вот скрытый слой, который состоит из 62500*25000 элементов уже в любом случае должен состоять из небольших дробных чисел.
Может быть есть варианты хитростей с переменными? Например, заменить дробные значения целыми, умноженными на 1000 или на 1000 000 чтоб наверняка?

опять всё от задачи зависит... например, чтобы перемножить две матрицы, то будет проще, если вторая матрица уже трансонирована...

Я тоже изначально это всё представлял как просто набор матриц 250*250, 144*144 и т.д.(делим сторону первой матрицы на корень из 3, округляем в меньшую сторону до целых, получаем сторону следующей матрицы. Последняя матрица имеет размер 2*2.) Но проблема в том, что в таком случае нужна уже четырехмерная матрица 250*250*144*144(т.е. каждому элементу матрицы размера 144*144 соответствует своя матрица размера 250*250, итого 144*144*250*250 элементов).

[Vadim]

Например, заменить дробные значения целыми

Целое значение тоже занимает в памяти 4 байта для 32-ух разрядной ОС.

так что для них можно использовать минимальный byte

Можно. Только компилятор будет к каждому байту добавлять ещё три, т.к. ему удобнее считать адреса кратные четырём. Придётся изменить тип данных на packet record, чтобы этого избежать. Но при этом Вы тут же резко потеряете в скорости обработки данных.
Лучше подумайте над использованием базы данных.

немного не так

Ну возьмите сами подсчитайте, всё таки я Вашей задачи не знаю. Принцип подсчёта я Вам показал.

[Mantius]

Ну возьмите сами подсчитайте, всё таки я Вашей задачи не знаю. Принцип подсчёта я Вам показал.

Входной слой: 62 500 х 4 = 250 000
Первый слой: 25 000 х 4 х 62 500 = 6 250 000 000
Второй слой: 8 300 х 4 х 25 000 = 830 000 000
Третий слой: 2 700 х 4 х 8 300 = 89 640 000
ну дальше, собсно, можно и не считать. Да, и насчет слоев, на первое время последними слоями также можно пожертвовать, но вот без первого, который как раз всё и решает, обойтись не получится.
в итоге получим примерно 7-8 Гб.

Лучше подумайте над использованием базы данных.

Какие есть варианты?