Байланысты деректер құрылымы (арқан деректер құрылымы) Java тіліндегі String сияқты өзгермейтін таңбалар тізбегі болып табылады. Бірақ байланыстыру өзгерістерін тиімді жүзеге асыру оларды String нысандары мен олардың өзгермелі немерелері StringBuffer және StringBuilder-тен айырмашылығы, жолды манипуляциялау жұмыстарын көп орындайтын қолданбалар үшін өте қолайлы етеді, әсіресе көп ағынды орталарда.
Байланыстыруға негізделген деректер құрылымдарына қысқаша кіріспеден кейін бұл мақала оқырманды Java платформасына арналған байланыстыруларды жүзеге асыру үшін Java кітапханасына арналған Ropes таныстырады. Содан кейін ол Java платформасына арналған Ropes for Java кітапханасынан String, StringBuffer сыныптары мен Rope сыныбын салыстырады; жеке өнімділік мәселелері зерттеледі және мақала қолданбада байланыстыруды қашан пайдалану керек және оларды қай кезде пайдаланбау жақсы екенін талқылаумен аяқталады.
Қатысты деректер құрылымдарына қысқаша шолу
Арқан — таңбалардың өзгермейтін тізбегі. Ұзындық — жай реттіліктегі таңбалар саны. Көптеген жолды іске асырулар өздерінің барлық таңбаларын бірінен соң бірі жадта сақтайды. Буманың негізгі қасиеті бұл шектеудің жоқтығы болып табылады, ол десте фрагменттерін дербес сақтауға мүмкіндік береді және оларды біріктіру түйіндерінің көмегімен қосуға мүмкіндік береді. Бұл архитектура String түріндегі Java нысандарына қарағанда жолдарды тезірек біріктіруге мүмкіндік береді. String нысандары үшін біріктіруді іске асыру біріктірілетін жолдардың O(n) күрделілік операциясы болып табылатын жаңа орынға көшірілуін талап етеді. Екінші жағынан, галстук O(1) операциясы болып табылатын жаңа қосылыс түйінін жасайды. (Күрділікті анықтау үшін O-белгісін түсіндіретін ресурстарға сілтемелер үшін Ресурстарды қараңыз.)
1-суретте жолды іске асырудың екі түрі көрсетілген. Сол жақта символдар бірізді жад орындарында орналасқан. Java тіліндегі жолдарды іске асыру осы принципке негізделген. Оң жақта көрсетілген іске асыруда бөлінген жолдар қосқыш түйіндері арқылы біріктіріледі.
Сурет 1. Жолды бейнелеудің екі түрі
Байланыстырылған деректер құрылымын іске асыру көбінесе ішкі жол түйіні сияқты элементті енгізу арқылы күрделі ішкі жол операцияларын есептеуді кейінге қалдырады. Ішкі жолдар үшін түйіндерді пайдалану ұзындығы n ішкі жолды O(n)-дан O(log n)-ге және жиі тіпті O(1)-ге дейін шығаруға кететін уақытты азайтады. Айта кетейік, Java String нысандары өзгермейтін болғандықтан, ішкі жол операцияларына бірдей уақыт жұмсайды, ал StringBuilder нысандарында мұндай тұрақты уақыт сипаттамалары жиі болмайды.
Жалпақ арқанның, жалғаулары немесе ішкі жіптері жоқ арқанның тереңдігі 1. Жалғаулары немесе ішкі жіптері бар арқанның тереңдігі оның ішіндегі ең сыртқы түйіннің тереңдік деңгейінен бір үлкен.
Байланыстырылған деректер құрылымдарында жолды іске асыруды сериализациялаудың екі жанама әсері бар. Біріншісі — белгілі бір таңбаны табу үшін өту керек ішкі жолдарға арналған қосқыш түйіндерінің және түйіндерінің мета-құрылымы. Сонымен қатар, бұл ағаш мета құрылымы өту уақытын азайту үшін мүмкіндігінше теңдестірілген болуы керек, яғни жақсы оқу өнімділігін сақтау үшін қатысты деректер құрылымдарын мерзімді түрде қайта теңестіру қажет. Сілтеме жақсы теңдестірілген болса да, белгілі бір позициядағы таңбаны алу O(log n) операциясы болып табылады, мұнда n — деректер құрылымын құрайтын ішкі жолдар үшін қосқыш түйіндерінің және түйіндерінің саны. (Ыңғайлы болу үшін сілтеменің ұзындығын n-ге ауыстыруға болады, өйткені ұзындық әрқашан ішкі жолдар үшін қосылатын түйіндер мен түйіндердің санынан үлкен болады.)
Бақытымызға орай, буманы теңестіру жылдам және теңдестіру қажет болған кезде автоматты түрде анықтауға болады, мысалы, байлам ұзындығын оның тереңдігімен салыстыру. Сондай-ақ, деректерді өңдеу тапсырмаларының көпшілігінде бұл жинақта сақталған таңбаларға ретті қол жеткізу қажет және бұл жағдайда байланысты деректер құрылымының итераторы O (1) мәніне жақын жалпы қол жеткізу жылдамдығын қамтамасыз ете алады.
1-кесте байланысты деректер құрылымдары үшін және String типті нысандар үшін кейбір стандартты жол операцияларының орындалу уақытын салыстырады.
