Використання вільної пам'яті, Детальна інформація

function delr ( a : integer; lp : Plist ) : Plist;

begin

if lp = nil then delr := nil

else

if lp^.v = a then

{ обробка голови }

begin

delr := lp^.subl; dispose ( lp )

end

else

{ рекурсивно вилучити елемент із підсписку }

begin

lp^.subl := delr ( a, lp^.subl ); delr := lp

end

end

Як бачимо, наведені рекурсивні підпрограми простіші для розуміння та коротші від їх нерекурсивних аналогів з попереднього підрозділу. Проте вони виконуються практично вдвічі довше за рахунок заглиблення в рекурсію та повернення з неї. Крім того, для виконання кожного рекурсивного виклику потрібна нова ділянка автоматичної пам'яті. Але ця пам'ять обмежена, а її "переповнення" веде до аварійного завершення виконання програми. Таким чином, може статися, що максимальна глибина рекурсії залежить зовсім не від довжини списку, а від розмірів автоматичної пам'яті.

Отже, наведені алгоритми мають скоріше теоретичний, ніж практичний інтерес. Принаймні, ми не можемо рекомендувати їх до практичного застосування.

5. Великі масиви у вільній пам'яті

Подання послідовностей даних списками є досить гнучким. Особливо зручним воно є у випадках, коли дані додаються та вилучаються в процесі виконання програми. Але воно призводить до неефективного використання пам'яті, особливо коли дані, записані в елементах списку, невеликі за розміром. Справді, кожний елемент послідовності потребує додатково 4 байти під вказівник, або навіть 8, коли список двозв'язаний. Крім того, доступність елемента залежить від його розташування в списку. Відсутність прямого доступу до елементів створює незручності програмування і в багатьох випадках веде до того, що при виконанні програми пошук елемента стає занадто довгим.

Існує багато задач, в яких вимагається швидкий пошук значень і не потрібна гнучкість спискового подання. Прикладами є задачі наступних розділів. Там, як правило, не треба додавати чи вилучати довільні елементи з послідовності. Використання масивів там набагато зручніше.

Система Турбо Паскаль має обмеження на розміри як статичної, так і автоматичної пам'яті, що надається програмі. Тому у випадках, коли потрібні масиви розміром, наприклад, у сотні тисяч байтів, слід зберігати їх у вільній пам'яті, адже її обсяг залежить головним чином від обсягу наявної оперативної пам'яті комп'ютера.

Розглянемо засоби системи Турбо Паскаль, за допомогою яких зручно задавати обробку масивів у вільній пам'яті.

По-перше, корисними є функції MEMAVAIL і MAXAVAIL, з яких повертається загальний розмір незайнятої частини купи та найбільший розмір суцільної незайнятої ділянки (у байтах, типу Longint).

Масив у купі повинен ідентифікуватися вказівником, установленим на його перший елемент. В означенні типу масиву головне – задати індекс і тип його першого елемента. Наприклад, type Arl=array[0..0]of longint. Далі означимо тип вказівника на такий масив: Parl=^Arl. Вказівник, який встановлюється на масив у купі, означається як безтиповий– він може мати значеннями адреси даних будь-яких типів і розмірів. Для цього в Турбо Паскаль є тип з іменем Pointer.

"Захоплення" ділянки вільної пам'яті заданого розміру та встановлення безтипового вказівника на її перший байт задається процедурою GETMEM. Першим аргументом у її виклику є ім'я вказівника, другим – вираз типу Longint, що задає довжину ділянки в байтах. Наприклад, якщо

var p : Pointer; num : word = 16383;

то за виконання виклику

getmem(p, num*sizeof(Longint))

вказівник p встановлюється на ділянку вільної пам'яті розміром у

num*sizeof(Longint) = 16383*4 = 65532