Azərbaycanca AzərbaycancaБеларускі БеларускіDansk DanskDeutsch DeutschEspañola EspañolaFrançais FrançaisIndonesia IndonesiaItaliana Italiana日本語 日本語Қазақ ҚазақLietuvos LietuvosNederlands NederlandsPortuguês PortuguêsРусский Русскийසිංහල සිංහලแบบไทย แบบไทยTürkçe TürkçeУкраїнська Українська中國人 中國人United State United StateAfrikaans Afrikaans
Підтримка
www.wikidata.uk-ua.nina.az

В програмуванні парале льний маси в структура даних для представлення масиву записів котра фізично складається з окремих

Паралельний масив

Паралельний масив

В програмуванні, парале́льний маси́в — структура даних для представлення масиву записів, котра фізично складається з окремих однотипних масивів однакової довжини для кожного з полей запису. Значення елементів з однаковим порядковим номером у кожному масиві, логічно належать до одної структури. Як вказники на структуру використовується загальний індекс в паралельному масиві. Цей підхід відрізняється від традиційного, при якому усі поля структури зберігаються у сусідніх областях пам'яті. Наприклад, можна оголосити масив строкового типу для 100 імен, та масив цілих чисел для 100 віків, та вважати, що кожному імені відповідає вік з таким самим індексом запису.

Приклад реалізації паралельних масивів на C: 

char *first_names[] = {"Joe", "Bob", "Frank", "Hans" }; char *last_names[] = {"Smith", "Seger", "Sinatra", "Schultze"}; int *heights[] = {169, 158, 201, 199 }; for (int i = 0; i < 4; i++) {  printf("Ім'я: %s %s, зріст: %d см \n", first_names[i], last_names[i], heights[i]); }

Приклад реалізації паралельних масивів на (у цій мові відсутня підтримка структур): 

string first_names[] = {"Joe", "Bob", "Frank", "Hans" }; string last_names[] = {"Smith", "Seger", "Sinatra", "Schultze"}; int heights[] = {169, 158, 201, 199 }; int i; for (i = 0; i < 4; i++) {  Print(StringConcatenate("Ім'я: ", first_names[i], " ", last_names[i], ", зріст: ", heights[i], " см")); }

Приклад реалізації на Perl (використано для логічного групування компонентів паралельного масиву): 

my %data = (  first_names => ['Joe', 'Bob', 'Frank', 'Hans' ],  last_names => ['Smith', 'Seger', 'Sinatra', 'Schultze'],  heights => [169, 158, 201, 199 ], ); for $i (0..$#{$data{first_names}}) {  printf "Ім'я: %s %s, зріст: %i см \n", $data{first_names}[$i], $data{last_names}[$i], $data{heights}[$i]; }

Приклад реалізації на Python: 

first_names = ["Joe", "Bob", "Frank", "Hans" ] last_names = ["Smith", "Seger", "Sinatra", "Schultze"] heights = [169, 158, 201, 199 ] for i in range(len(first_names)): print("Ім'я: %s %s, зріст: %d см" % (first_names[i], last_names[i], heights[i]))

Приклад альтернативної реалізації на Python: 

first_names = ["Joe", "Bob", "Frank", "Hans" ] last_names = ["Smith", "Seger", "Sinatra", "Schultze"] heights = [169, 158, 201, 199 ] for (first_name, last_name, height) in zip(first_names, last_names, heights): print("Ім'я: %s %s, зріст: %d см" % (first_name, last_name, height))

Приклад реалізації на bash: 

#!/bin/bash declare -a first_names=('Joe' 'Bob' 'Frank' 'Hans' ); declare -a last_names=('Smith' 'Seger' 'Sinatra' 'Schultze'); declare -a heights=(169 158 201 199 ); declare -i i; for (( i = 0 ; i <= ${#first_names} ; i++ )); do { echo "Ім'я: ${first_names[${i}]} ${last_names[${i}]}, зріст: ${heights[${i}]} см"; }; done


У паралельних масивів є ряд практичних переваг у зрівнянні з класичним підходом:

  • Вони можуть бути використані у мовах, котрі підтримують тільки масиви примітивних типів, але не підтримують масиви записів, чи не підтримують записи взагалі.
  • Паралельні масиви прости для розуміння та використання, та часто використовуються там, де об'ява структури запису надмірна.
  • Вони можуть зберегти відчутний об'єм пам'яті у деяких випадках, так як більш ефективно вирішують питання вирівнювання. Наприклад, одним з полей структури може бути одиничний біт — при звичайному підході, невикористані біти доведеться вирівняти так, що єдиний біт займе повні 8, 16 або 32 біта, тоді як паралельний масив дозволить об'єднати по 32 або по 64 бітових поля у єдиному елементі, у залежності від разрядності архітектури процесора.
  • Якщо кількість елементів невелика, індекси масиву займають суттєво менше простору, чим повноцінні вказники, особливо на архітектурах з великою разрядністю.
  • Послідовне читання єдиного поля кожного запису у масиві дуже швидке на сучасних комп'ютерах, так як це рівноцінно лінейному ітеруванню по єдиному масиву, що дає ідеальні [en] и поведінку кешу.

Незважаючи на це, у паралельних масивів є декілька суттєвих недоліків, котрі пояснюють, чому вони не використовуються повсюдно:

  • У них суттєво гірша локальність при послідовному ітеруванні по записам та читанні деяких полів, що є типовою задачею.
  • Зв'язок між полями одного запису може бути неочевидним та заплутаним.
  • Достатньо мала кількість мов підтримує паралельні масиви, як повноцінні структури — мова та її синтаксис, як правило, не позначують зв'язок між масивами у паралельному масиві.
  • Зміна розміру паралельного масиву — досить затратна операція, так як потребується заново виділити пам'ять під кожен з субмасивів. Многорівневі масиви є частковим вирішенням даної проблеми, але накладають обмеження на продуктивність через введення додаткового шару переспрямувань, щоб знайти потрібний елемент.

Погана локальність є серйозним недоліком, але можна скористуватися наступними підходами, щоб зменшити серйозність проблеми та її вплив на продуктивність:

  • Якщо у записі є окремі набори полів, що, як правило, використовуються разом, можна поділити структуру на декілька, та зробити паралельний масив з таких часткових записів. Цей спосіб дозволяє суттєво збільшити продуктивність доступу до дуже великих структур, зберігаючи їх логічну компоновку. Якщо це допустимо, деякі поля структури можуть бути продубльовані у різних субструктурах, але тоді на програміста лягає задача відстежування змінення записів, що дублюються, та оновлення усіх екземплярів.
  • Замість індексів масивів можна використовувати посилання, але результуюча продуктивність сильно залежить від мови, компілятора та архітектури процесора — подібне рішення може бути неефективним як по часу виконання, так і по об'єму використаної пам'яті.
  • Ще одним варіантом є об'єднання полей сумісних типів у єдиний одномірний масив так, щоб поля, що належать до одної структури, були записані послідовно. Наприклад, є паралельний масив з записів для зросту, ваги та віку — замість трьох роздільних масивів можна створити один, у якому записи будуть мати наступний вигляд: [зріст1, вага1, вік1, зріст2, вага2, вік2, ...], таким чином, для отримання J-ного поля (з M) у I-тому записі (з N), треба звернутися до елементу з індексом (M * I + J). Деякі компілятори автоматично здатні застосовувати подібну оптимізацію для розгортання масивів структур для адаптації під векторні процесори та SIMD-інструкції.
  • В пакеті pandas для мови програмування python використовуєьтся цей підход. Основна структура DataFrame розглядається як список колонок Series, кожна з яких складається з однотипних даних.

Див. також

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет

V programuvanni parale lnij masi v struktura danih dlya predstavlennya masivu zapisiv kotra fizichno skladayetsya z okremih odnotipnih masiviv odnakovoyi dovzhini dlya kozhnogo z polej zapisu Znachennya elementiv z odnakovim poryadkovim nomerom u kozhnomu masivi logichno nalezhat do odnoyi strukturi Yak vkazniki na strukturu vikoristovuyetsya zagalnij indeks v paralelnomu masivi Cej pidhid vidriznyayetsya vid tradicijnogo pri yakomu usi polya strukturi zberigayutsya u susidnih oblastyah pam yati Napriklad mozhna ogolositi masiv strokovogo tipu dlya 100 imen ta masiv cilih chisel dlya 100 vikiv ta vvazhati sho kozhnomu imeni vidpovidaye vik z takim samim indeksom zapisu Priklad realizaciyi paralelnih masiviv na C char first names Joe Bob Frank Hans char last names Smith Seger Sinatra Schultze int heights 169 158 201 199 for int i 0 i lt 4 i printf Im ya s s zrist d sm n first names i last names i heights i Priklad realizaciyi paralelnih masiviv na u cij movi vidsutnya pidtrimka struktur string first names Joe Bob Frank Hans string last names Smith Seger Sinatra Schultze int heights 169 158 201 199 int i for i 0 i lt 4 i Print StringConcatenate Im ya first names i last names i zrist heights i sm Priklad realizaciyi na Perl vikoristano dlya logichnogo grupuvannya komponentiv paralelnogo masivu my data first names gt Joe Bob Frank Hans last names gt Smith Seger Sinatra Schultze heights gt 169 158 201 199 for i 0 data first names printf Im ya s s zrist i sm n data first names i data last names i data heights i Priklad realizaciyi na Python first names Joe Bob Frank Hans last names Smith Seger Sinatra Schultze heights 169 158 201 199 for i in range len first names print Im ya s s zrist d sm first names i last names i heights i Priklad alternativnoyi realizaciyi na Python first names Joe Bob Frank Hans last names Smith Seger Sinatra Schultze heights 169 158 201 199 for first name last name height in zip first names last names heights print Im ya s s zrist d sm first name last name height Priklad realizaciyi na bash bin bash declare a first names Joe Bob Frank Hans declare a last names Smith Seger Sinatra Schultze declare a heights 169 158 201 199 declare i i for i 0 i lt first names i do echo Im ya first names i last names i zrist heights i sm done U paralelnih masiviv ye ryad praktichnih perevag u zrivnyanni z klasichnim pidhodom Voni mozhut buti vikoristani u movah kotri pidtrimuyut tilki masivi primitivnih tipiv ale ne pidtrimuyut masivi zapisiv chi ne pidtrimuyut zapisi vzagali Paralelni masivi prosti dlya rozuminnya ta vikoristannya ta chasto vikoristovuyutsya tam de ob yava strukturi zapisu nadmirna Voni mozhut zberegti vidchutnij ob yem pam yati u deyakih vipadkah tak yak bilsh efektivno virishuyut pitannya virivnyuvannya Napriklad odnim z polej strukturi mozhe buti odinichnij bit pri zvichajnomu pidhodi nevikoristani biti dovedetsya virivnyati tak sho yedinij bit zajme povni 8 16 abo 32 bita todi yak paralelnij masiv dozvolit ob yednati po 32 abo po 64 bitovih polya u yedinomu elementi u zalezhnosti vid razryadnosti arhitekturi procesora Yaksho kilkist elementiv nevelika indeksi masivu zajmayut suttyevo menshe prostoru chim povnocinni vkazniki osoblivo na arhitekturah z velikoyu razryadnistyu Poslidovne chitannya yedinogo polya kozhnogo zapisu u masivi duzhe shvidke na suchasnih komp yuterah tak yak ce rivnocinno linejnomu iteruvannyu po yedinomu masivu sho daye idealni en i povedinku keshu Nezvazhayuchi na ce u paralelnih masiviv ye dekilka suttyevih nedolikiv kotri poyasnyuyut chomu voni ne vikoristovuyutsya povsyudno U nih suttyevo girsha lokalnist pri poslidovnomu iteruvanni po zapisam ta chitanni deyakih poliv sho ye tipovoyu zadacheyu Zv yazok mizh polyami odnogo zapisu mozhe buti neochevidnim ta zaplutanim Dostatno mala kilkist mov pidtrimuye paralelni masivi yak povnocinni strukturi mova ta yiyi sintaksis yak pravilo ne poznachuyut zv yazok mizh masivami u paralelnomu masivi Zmina rozmiru paralelnogo masivu dosit zatratna operaciya tak yak potrebuyetsya zanovo vidiliti pam yat pid kozhen z submasiviv Mnogorivnevi masivi ye chastkovim virishennyam danoyi problemi ale nakladayut obmezhennya na produktivnist cherez vvedennya dodatkovogo sharu perespryamuvan shob znajti potribnij element Pogana lokalnist ye serjoznim nedolikom ale mozhna skoristuvatisya nastupnimi pidhodami shob zmenshiti serjoznist problemi ta yiyi vpliv na produktivnist Yaksho u zapisi ye okremi nabori poliv sho yak pravilo vikoristovuyutsya razom mozhna podiliti strukturu na dekilka ta zrobiti paralelnij masiv z takih chastkovih zapisiv Cej sposib dozvolyaye suttyevo zbilshiti produktivnist dostupu do duzhe velikih struktur zberigayuchi yih logichnu komponovku Yaksho ce dopustimo deyaki polya strukturi mozhut buti produblovani u riznih substrukturah ale todi na programista lyagaye zadacha vidstezhuvannya zminennya zapisiv sho dublyuyutsya ta onovlennya usih ekzemplyariv Zamist indeksiv masiviv mozhna vikoristovuvati posilannya ale rezultuyucha produktivnist silno zalezhit vid movi kompilyatora ta arhitekturi procesora podibne rishennya mozhe buti neefektivnim yak po chasu vikonannya tak i po ob yemu vikoristanoyi pam yati She odnim variantom ye ob yednannya polej sumisnih tipiv u yedinij odnomirnij masiv tak shob polya sho nalezhat do odnoyi strukturi buli zapisani poslidovno Napriklad ye paralelnij masiv z zapisiv dlya zrostu vagi ta viku zamist troh rozdilnih masiviv mozhna stvoriti odin u yakomu zapisi budut mati nastupnij viglyad zrist1 vaga1 vik1 zrist2 vaga2 vik2 takim chinom dlya otrimannya J nogo polya z M u I tomu zapisi z N treba zvernutisya do elementu z indeksom M I J Deyaki kompilyatori avtomatichno zdatni zastosovuvati podibnu optimizaciyu dlya rozgortannya masiviv struktur dlya adaptaciyi pid vektorni procesori ta SIMD instrukciyi V paketi pandas dlya movi programuvannya python vikoristovuyetsya cej pidhod Osnovna struktura DataFrame rozglyadayetsya yak spisok kolonok Series kozhna z yakih skladayetsya z odnotipnih danih Div takozhPriklad u anglijskij statti pro svyaznij spisok en nezvichnij tip BD sho vikoristovuye koncepciyu paralelnyh masiviv dlya organizaciyi danih Asociativnij masiv Dinamichnij masiv

Дата публікації:
Топ