как очень быстро сгенерировать двумерный массив с разными длинами "веток"

Question

Я программист на Delphi.В программе мне нужно генерировать двумерные массивы с разной длиной «ветвей».Они очень большие, и операция занимает несколько секунд (раздражает).

Например:

var a: array of array of Word;
  i: Integer;

begin
   SetLength(a, 5000000);
   for i := 0 to 4999999 do
      SetLength(a[i], Diff_Values);
end;

Мне известна команда SetLength (a, dim1, dim2), но это не так.применимо.Даже не устанавливая минимальное значение (> 0) для dim2 и продолжая оттуда, потому что min для dim2 равно 0 (некоторые «ветви» могут быть пустыми).

Итак, есть ли способ сделать это быстро?Не просто на 5,10%, а действительно БЫСТРО ...

Спасибо.

Answer 1

При работе с большим количеством данных необходимо проделать большую работу, и это накладывает теоретический минимум на количество времени, за которое это может быть выполнено.

Для каждого из 5миллион итераций, вам нужно:

• Определить размер "ветви" как-то
• Выделить новый массив соответствующего размера из диспетчера памяти
• Нольизрасходовать всю память, используемую новым массивом (SetLength сделает это автоматически)

Шаг 1 полностью находится под вашим контролем и, возможно, может быть оптимизирован.2 и 3, однако, примерно такие же быстрые, как они, если вы используете современную версию Delphi.(Если вы используете старую версию, вам может быть полезно установить FastMM и FastCode, которые могут ускорить эти операции.)

Другая вещь, которую вы можете сделать, если это уместно, это отложенная инициализация .Вместо того, чтобы пытаться выделить все 5 миллионов массивов одновременно, просто сначала выполните SetLength(a, 5000000);.Затем, когда вам нужно попасть в «ветку», сначала проверьте, равна ли ее длина 0. Если это так, она не была инициализирована, поэтому инициализируйте ее до нужной длины.Это не экономит время в целом, на самом деле это займет немного больше времени в целом, но затрачивает время инициализации, поэтому пользователь не замечает.

Если ваша инициализация уже настолько быстрая, как и будетполучить, и ваша ситуация такова, что ленивая инициализация не может быть использована здесь, тогда вам в основном не повезло.Это цена работы с большими объемами данных.

Answer 2

В дополнение к баллам Мэйсона, есть еще несколько идей, которые следует учитывать:

Если длины ветвей никогда не меняются после их распределения, и у вас есть верхняя граница для общего количества элементов, которые будут сохраненыв массиве всех ветвей вы можете сэкономить время, выделив один огромный кусок памяти и разделив «ветви» внутри этого блока.Ваш массив станет одномерным массивом указателей, и каждая запись в этом массиве указывает на начало данных для этой ветви.Вы отслеживаете «конец» используемого пространства в вашем большом блоке с помощью одной переменной-указателя, а когда вам нужно зарезервировать пространство для новой «ветви», вы берете текущее значение «конечного» указателя в качестве начала новогопереходите и увеличивайте указатель «end» на количество места, которое требуется для перехода.Не забудьте округлить до границ меча, чтобы избежать штрафов за несоосность.

Этот метод потребует большего использования указателей, но он дает возможность устранить все накладные расходы на выделение кучи или, по крайней мере, заменить общие цели.Распределение кучи с помощью специально созданного очень простого и очень быстрого субраспределителя, который соответствует вашей конкретной схеме использования.Он должен выполняться быстрее, но для написания и тестирования потребуется больше времени.

Этот метод также позволяет избежать фрагментации кучи и уменьшает высвобождение всей памяти до одного освобождения (вместо миллионов отдельных выделений).в вашей нынешней модели).

Еще один совет для рассмотрения: если первое, что вы всегда делаете с каждым вновь выделенным «ответвлением» массива, это назначение данных каждому слоту, то вы можете исключить шаг 3 в примере Мейсона -вам не нужно обнулять память, если все, что вы собираетесь сделать, это немедленно назначить в нее реальные данные.Это сократит ваши операции записи в память наполовину.

Answer 3

Я только что проверил ваш точный код с константой Diff_Values, рассчитал время, используя GetTickCount() для элементарной синхронизации.Если Diff_Values равно 186, это займет 1466 миллисекунд, если Diff_Values равно 187, произойдет сбой с Out of Memory.Знаете, Out of Memory означает Out of Address Space, не совсем Out of Memory.

По моему мнению, вы выделяете столько данных, что у вас заканчивается ОЗУ, а Windows начинает подкачку , этопочему это медленноВ моей системе у меня достаточно оперативной памяти для процесса, чтобы выделить столько, сколько он хочет;И так будет до тех пор, пока не произойдет сбой.

Возможные решения

• Очевидное: не выделяйте так много!
• Придумайте способ размещения всех данныхв один непрерывный блок памяти: помогает с фрагментацией адресного пространства.Аналогично тому, как распределяется двумерный массив с фиксированным размером на «ветвях», но если ваши «ветки» имеют разные размеры, вам нужно будет составить другую математическую формулу на основе ваших данных.
• Посмотрите на другие структуры данных, возможно те, которые кешируются на диске (чтобы уменьшить ограничение адресного пространства 2 Гб).

Answer 4

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

Примечание :Даже если вы не можете разместить данные в одном непрерывном блоке памяти, вы все равно можете использовать эту технику, выделив несколько больших блоков и затем сложив их вместе.

Сначала сформируйте вспомогательный массив,colIndex, который должен содержать индекс первого столбца каждой строки.Установите длину от colIndex до RowCount+1.Вы строите это, устанавливая colIndex[0] := 0, а затем colIndex[i+1] := colIndex[i] + ColCount[i].Сделайте это в цикле for, который работает до RowCount включительно.Итак, в последней записи, colIndex[RowCount], вы сохраняете общее количество элементов.

Теперь установите длину a равной colIndex[RowCount].Это может занять некоторое время, но это будет быстрее, чем вы делали раньше.

Теперь вам нужно написать пару индексаторов.Поместите их в класс или запись.

Получатель выглядит следующим образом:

 function GetItem(row, col: Integer): Word;
 begin
   Result := a[colIndex[row]+col];
 end;

Установщик очевиден.Вы можете встроить эти методы доступа для повышения производительности.Предоставьте их как индексированное свойство для удобства клиентов объекта.

Вы захотите добавить код, чтобы проверить правильность row и col.Вам нужно использовать colIndex для последнего.Вы можете сделать эту проверку необязательной с помощью {$IFOPT R+}, если хотите имитировать проверку диапазона для собственной индексации.

Конечно, это полный старт, если вы хотите изменить любой из ваших столбцов после начальногоконкретизация!