А почему по расчётам получается 4096 МБ? А на x64 будет работать?
Потому, что диапазон 2^32 - это числа от 0 до 2^32-1 для беззнаковых чисел и -2^31 … 2^31-1 при поддержке знака в старшем бите.
Ну какое отношение указатель имеет к счетчику элементов? Я не знаю, как там все внутри устроено, да и неважно это, если говорится о технических ограничениях - изменить мы их все равно не можем. Но большинство программных средств под Windows имеют ограничения в 1-2-4 миллиарда неважно чего - элементов, отводимой памяти и т.п. Это зависит от количества выделяемых служебных битов или байтов.
Аааа, понял. Счётчик имеет тип Int32. Ясно. Вопрос закрыт.
Какой способ лучше использовать для удаления (вставки) строк (столбцов) в динамических матрицах? Если например взять удаление строки и сдвинуть столбцы на 1 элемент а потом SetLength(a,m-1,n,) выделить новую память вроде так можно технически, но это даже хуже, чем со статической матрицей, которой всего то нужно уменьшить число строк и не нужно переопределять новую память. Есть ли какие-то другие способы для динамических матриц? Такие, как если бы был такой расширяемый тип матриц у которой строки и стобцы были бы типами List? Если в строки еще можно вставить те же списки (List), например, определив массив списков, и потом можно удалять столбцы и даже несколько столбцов методами для List, то вот со строками не понятно получается, да и как удалить элемент массива списков - список, чтобы не выделять потом новую память? Или для таких задач лучше пользоваться статическими матрицами?
Можете привести пример? Ну или объяснить подробнее?
Всё, понял. Нет, так не получится сделать. Даже List построен на базе динамического массива, поэтому удаление элемента с последующим смещением так же потребует память.
Да, как-то не очень понятно, наверное написал, но как уж получилось. Пример, удаление k-й строки в динамической матрице:
begin
var m := 5;
var n := 6;
var a := MatrRandom(m, n, 0, 100); a.Println;
var k := 0;
for var i := k to m - 2 do
for var j := 0 to n - 1 do
a[i, j] := a[i + 1, j];
SetLength(a, m - 1, n);
Println;
a.Println;
end.
Мне не нравится, что нужно выделять новую память после удаления строки, какие есть еще способы?
Чисто теоретически, это возможно, по практически о таком я не слышал. По идее, можно использовать не Array[,], а Array of Array. В таком случае, в корневом массиве будет храниться не содержимое строк, а ссылки на строки, занимающие 4 байта. В таком случае, Вы можете создать новый массив массивов и присваивать его элементам ссылки на нужные строки. Что-то типа того:
Uses System;
Procedure SetLength<T>(var arr: array of T, length: Int32);
Begin
arr := new T[length];
End;
Begin
var a: array of array of Int32;
SetLength(a, 10); // 10 строк
For Var i := 0 to a.Length - 1 do
a[i] := new Int32[9]; // 10 столбцов
var newA: array of array of Int32;
SetLength(newA, 9); // 9 строк. Последнюю удаляем.
newA[0] := a[0];
newA[1] := a[1];
newA[2] := a[2];
newA[3] := a[3];
newA[4] := a[4];
newA[5] := a[5];
newA[6] := a[6];
newA[7] := a[7];
newA[8] := a[8];
a := newA;
End.
1 лайк
Если вам надо быстро вставлять/удалять элементы - надо использоваться связные списки. Хотя для многомерных придётся свои написать.
Если же надо просто матрицу у которой можно быстро менять размер - реализуйте свой прямоугольный список на матрице, так же как List основано на массиве.
Если использовать массив массивов такой var a := new List<integer>[5] то можно удалять столбцы в таком массиве методами для List, и вставлять тоже можно без переопределения памяти. А вот со строками как в этом случае быть я не знаю.
Привёл код выше.
Дело тут не в скорости, а в затрате памяти. Самая быстрая конструкция - чистый массив. Всё остальное будет уступать по производительности. Листы и словари - это лишь высокоуровневые оболочки обычного массива, предоставляющие всевозможный сахар.
Да, но не недооценивайте их. Списки хранят у себя массив большего чем надо размера, с запасом, чтоб позволяет быстро добавлять элементы. И при этом не надо выделять каждый раз новую память, чтоб изменить количество элементов, это самое важное, почему я их рекомендую.
И связные списки, кстати, не основаны на массиве. И скорость добавления элементов у них больше чем у чего либо другого, а памяти выделяется лишь чуть больше чем надо и только когда надо.
так это выходит каждый раз когда нужно изменить исходный массив массивов придется создавать дополнительный массив массивов подходящей длины и туда копировать ссылки, а после этого копировать ссылку на него в исходный? И в чем тут профит, если все равно нужна еще одна память под дополнительный массив?
до связных списков я еще не добрался, а вот насчет реализовать прямоугольный списо на матрице… я даже не представляю как это выглядит, не говоря уже за реализацию =)
Осторожно: очень много костылей! Это лишь чтоб показать идею.
type
RectList<T> = class
private mtx:array[,] of T;
private l1,l2:integer;
private function GetItem(i1,i2:integer):T;
begin
if cardinal(i1) > cardinal(l1) then raise new System.IndexOutOfRangeException('i1 неправильный') else
if cardinal(i2) > cardinal(l2) then raise new System.IndexOutOfRangeException('i2 неправильный') else
Result := mtx[i1,i2];
end;
private procedure SetItem(i1,i2:integer; o:T) :=
if cardinal(i1) > cardinal(l1) then raise new System.IndexOutOfRangeException('i1 неправильный') else
if cardinal(i2) > cardinal(l2) then raise new System.IndexOutOfRangeException('i2 неправильный') else
mtx[i1,i2] := o;
public constructor;
begin
mtx := new T[4,4];
end;
public procedure Resize(nl1,nl2:integer);
begin
var res := new T[nl1,nl2];
//ToDo реализовать через System.Array.Copy, так быстрее
//Только копировать придётся построчно, иначе не сработает
for var i1 := 0 to Min(Cap1,nl1)-1 do
for var i2 := 0 to Min(Cap2,nl2)-1 do
res[i1,i2] := mtx[i1,i2];
mtx := res;
end;
public property Length1:integer read l1;
public property Length2:integer read l2;
public property Cap1:integer read mtx.GetLength(0) write Resize(value,Cap2);
public property Cap2:integer read mtx.GetLength(1) write Resize(Cap1,value);
public property Item[i1,i2:integer]:T read GetItem write SetItem; default;
public procedure Add1(o:ICollection<T>; at:integer);
begin
if cardinal(at) > cardinal(l1) then raise new System.IndexOutOfRangeException('at неправильный');
var ol := o.Count;
if ol > l2 then raise new System.IndexOutOfRangeException('o.Count неправильный');
if l1 = Cap1 then Resize(Cap1*2, Cap2);
//ToDo опять же, через Array.Copy надо
for var i1 := l1-1 downto at do
for var i2 := 0 to l2-1 do
mtx[i1+1,i2] := mtx[i1,i2];
var i2 := 0;
foreach var a in o do
begin
mtx[at, i2] := a;
i2 += 1;
end;
l1 += 1;
end;
public procedure Add2(o:ICollection<T>; at:integer);
begin
if cardinal(at) > cardinal(l2) then raise new System.IndexOutOfRangeException('at неправильный');
var ol := o.Count;
if ol > l1 then raise new System.IndexOutOfRangeException('o.Count неправильный');
if l2 = Cap2 then Resize(Cap1, Cap2*2);
//ToDo опять же, через Array.Copy надо
for var i2 := l2-1 downto at do
for var i1 := 0 to l1-1 do
mtx[i1,i2+1] := mtx[i1,i2];
var i1 := 0;
foreach var a in o do
begin
mtx[i1, at] := a;
i1 += 1;
end;
l2 += 1;
end;
public procedure Remove1(at:integer);
begin
if cardinal(at) > cardinal(l1) then raise new System.IndexOutOfRangeException('at неправильный');
//ToDo опять же, через Array.Copy надо
for var i1 := at to l1-1 do
for var i2 := 0 to l2-1 do
mtx[i1,i2] := mtx[i1+1,i2];
l1 -= 1;
end;
public procedure Remove2(at:integer);
begin
if cardinal(at) > cardinal(l2) then raise new System.IndexOutOfRangeException('at неправильный');
//ToDo опять же, через Array.Copy надо
for var i2 := at to l2-1 do
for var i1 := 0 to l1-1 do
mtx[i1,i2] := mtx[i1,i2+1];
l2 -= 1;
end;
class function operator implicit(a: RectList<T>): array[,] of T;
begin
Result := new T[a.l1,a.l2];
//ToDo опять же, через Array.Copy надо
for var i1 := 0 to a.l1-1 do
for var i2 := 0 to a.l2-1 do
Result[i1,i2] := a.mtx[i1,i2];
end;
end;
begin
var mtx := new RectList<byte>;
mtx.Resize(3,3);
mtx.l2 := 3;//так вообще не даст сделать в нормальном коде, надо как то лучше реализовать.
mtx.Add1(new byte[](10,11,12),0);
mtx.Add1(new byte[](13,14,15),1);
mtx.Add1(new byte[](16,17,18),2);
var res: array[,] of byte := mtx;
res.Println;
writeln;
mtx.Add1(new byte[](21,22,23),1);
mtx.Add2(new byte[](31,32,33,34),1);
res := mtx;
res.Println;
end.
Примерно так же реализован обычный список.
А связный список - этот тот, в котором после каждого элемента идёт ссылка на следующий. Таким образом прямо в его центр можно вставить что то, без особых проблем. Хотя, конечно, получение элемента по индексу - ужасно медленное, из за того, сколько указателей придётся разыменовывать. Он полезен только если надо вставить много элементов в разные места. Тогда надо сначала преобразовать массив к связному списку, потому добавить/убрать всё что надо, а потом преобразовать назад в массив.
2 лайка
Институт математики, механики и компьютерных наук ЮФУ, 2005–2021