Ағаш тізімі - Conc-tree list

Шатастыруға болмайды минус.

A ағаш [1][2] - бұл элементтер тізбегін сақтайтын және амортизацияланған мәліметтер құрылымы O (1) уақытты қосу және алдын-ала орындау, O (log n) уақытты енгізу және жою және O (log n) уақытты біріктіру. Бұл деректер құрылымы функционалды-параллельді және параллельді параллельді бағдарламалау үшін өміршең болып табылады, және басқа асимптотикалық күрделілігі бар басқа деректер құрылымдарымен салыстырғанда қарапайым.[1] Консольдар дәйекті солдан оңға қарай қайталауды қажет етпейтін мәліметтерге параллель операциялардың тиімділігін арттыруға арналған,[3] және деректердің қажетсіз көшірмелерін болдырмау арқылы осы операциялардағы тұрақты факторларды жақсарту.[2] Ортогональды түрде олар функционалды стильдегі деректерді тиімді жинақтау үшін қолданылады параллельді алгоритмдер, деректерді консистентті дерексіздендіруді жүзеге асыру ретінде.[4] Conc-list - параллель бағдарламалау аналогы функционалдық жағымсыз тізімдер, және бастапқыда енгізілген Бекініс тілі.

Операциялар

Ағаш ағашының негізгі жұмысы - біріктіру. Ағаштар келесі негізгі типтер бойынша жұмыс істейді:

қасиет Тұжырымдама[Т] {  деф сол: Тұжырымдама[Т]  деф дұрыс: Тұжырымдама[Т]  деф деңгей: Int  деф өлшемі: Int}іс сынып Бос[Т] ұзарады Тұжырымдама[Т] {  деф деңгей = 0  деф өлшемі = 0}іс сынып Бойдақ[Т](елем: Т) ұзарады Тұжырымдама[Т] {  деф деңгей = 0  деф өлшемі = 1}іс сынып <>[Т](сол: Тұжырымдама[Т], дұрыс: Тұжырымдама[Т]) ұзарады Тұжырымдама[Т] {  вал деңгей = 1 + математика.макс(сол.деңгей, дұрыс.деңгей)  вал өлшемі = сол.өлшемі + дұрыс.өлшемі}

The <> тип ішкі түйіндерді білдіреді және айтылады конц, шабыт :: ( минус тип) функционалды тізімдерде, дәйекті бағдарламалау үшін қолданылады.

Содан кейін O (log n) уақыттағы сабақтастық кез келген екі бауырлас ағаштар арасындағы деңгейлердің (яғни биіктіктердің) айырмашылығы бір немесе одан аз болатынына көз жеткізіп, инварианттарға ұқсас болады. AVL ағаштары. Бұл инвариант ағаштың биіктігінің (тамырдан кейбір жапыраққа дейінгі ең ұзын жолдың) әрқашан ағаштағы элементтер саны бойынша логарифмдік болуын қамтамасыз етеді. Біріктіру келесідей жүзеге асырылады:

деф консоль(xs: Тұжырымдама[Т], ys: Тұжырымдама[Т]) {  вал айырмашылық = ys.деңгей - xs.деңгей  егер (математика.абс(айырмашылық) <= 1) жаңа <>(xs, ys)  басқа егер (айырмашылық < -1) {    егер (xs.сол.деңгей >= xs.дұрыс.деңгей) {      вал nr = консоль(xs.дұрыс, ys)      жаңа <>(xs.сол, nr)    } басқа {      вал nrr = консоль(xs.дұрыс.дұрыс, ys)      егер (nrr.деңгей == xs.деңгей - 3) {        вал nr = жаңа <>(xs.дұрыс.сол, nrr)        жаңа <>(xs.сол, nr)      } басқа {        вал nl = жаңа <>(xs.сол, xs.дұрыс.сол)        жаңа <>(nl, nrr)      }    }  } басқа {    // симметриялы жағдай  }}

Амортизацияланған O (1) уақыт қосымшаларына (немесе алдын-ала) жаңа ішкі түйін түрін енгізу арқылы қол жеткізіледі Қосыңызжәне оның көмегімен биіктігі қатаң төмендейтін консольдардың логарифмдік тізімін кодтайды. Әрқайсысы Қосыңыз түйін ап келесі инварианттарды қанағаттандыруы керек:

1. деңгей оңға деңгейінен әрдайым үлкенірек болады дұрыс.

2. Ағаш дұрыс ешқашан болмайды Қосыңыз түйіндер (яғни ол тек қалыптанған түрінде болады, тек <>, Бойдақ және Бос).

Бұл инварианттардың көмегімен екілік санды қосуға изоморфты болып табылады - биіктігі бірдей екі іргелес ағашты тұрақты уақыт бойынша байланыстыруға болады, ең көбі логарифмдік тасымалдау амалдары болады. Бұл келесі суретте көрсетілген, мұнда элемент екілік санға сәйкес келетін консольға қосылады:

Қосымша ағаштардың жұмысы

Бұл екілік санның көрінісі ұқсастыққа ұқсас таза функционалды кездейсоқ қол жеткізу тізімдері авторы Окасаки,[5] айырмашылықпен кездейсоқ қол жеткізу тізімдері барлық ағаштардың болуын талап етеді толық екілік ағаштар, ал қарағайлар босаңсыған және теңдестірілген ағаштарды қажет етеді. Бұл біршама босаңсыған инварианттар ағаштардың логарифмдік уақыт тізбегін сақтауға мүмкіндік береді, ал кездейсоқ қол жеткізу тізімдері тек O (n) біріктіруге мүмкіндік береді.

Төменде қосу ең нашар әдіс O (log n) уақыт және амортизацияланған O (1) уақыт:

іс сынып Қосыңыз[Т](сол: Тұжырымдама[Т], дұрыс: Тұжырымдама[Т]) ұзарады Тұжырымдама[Т] {  вал деңгей = 1 + математика.макс(сол.деңгей, дұрыс.деңгей)  вал өлшемі = сол.өлшемі + дұрыс.өлшемі}жеке деф қосу[Т](xs: Қосыңыз[Т], ys: Тұжырымдама[Т]) =  егер (xs.дұрыс.деңгей > ys.деңгей) жаңа Қосыңыз(xs, ys)  басқа {    вал zs = жаңа <>(xs.дұрыс, ys)    xs.сол матч {      іс ws @ Қосыңыз(_, _) => қосу(ws, zs)      іс ws => егер (ws.деңгей <= xs.деңгей) консоль(ws, zs) басқа жаңа Қосыңыз(ws, zs)    }  }}

Осылай салынған ағаш ағашында ешқашан O (log n) артық болмайды Қосыңыз түйіндерді қалпына келтіріп, қалыпқа келтіруге болады (тек қана қолдана отырып) <>, Бойдақ және Бос түйіндер) O (log n) уақытында.

Осы операциялардың егжей-тегжейлі көрсетілімін интернет-ресурстардан табуға болады,[6][7] немесе түпнұсқа ағаш қағазда.[1] Осы негізгі операцияларды ең нашар жағдайды қолдау үшін кеңейтуге болатындығы көрсетілген (1) дек операциялар,[2] барлық операциялардың тұрақты факторларын көбейту есебінен O (log n) тізбектелген уақытты сақтай отырып.

Пайдаланылған әдебиеттер

  1. ^ а б c Prokopec, A. және басқалар. (2015) Функционалды және параллель бағдарламалауға арналған ағаштар. Ғылыми еңбек, 2015
  2. ^ а б c Prokopec A. (2014) Мәліметтер құрылымы және басқарылатын жұмыс уақытында параллельді есептеу алгоритмдері. Докторлық диссертация, 2014 ж
  3. ^ Стил, Г. (2009) [1] Параллельді орындау үшін функционалды кодты ұйымдастыру; немесе, бүктеу және бүктеу сәл зиянды деп саналады
  4. ^ Steel, G. (2011) [2] Параллель бағдарламалау туралы қалай ойлауға болады: Жоқ!
  5. ^ Okasaki, C. (1995)[3] Таза функционалды кездейсоқ қол жеткізу тізімдері
  6. ^ Ағаш ағашының презентациясы
  7. ^ EPFL-де параллель бағдарламалау дәрісі