Дослідження ефективності деяких детермінованих методів передобробки сортування даних

Simple item page
dc.contributor.authorШинкаренко, Віктор Івановичuk_UA
dc.contributor.authorМакаров, Олексій Вікторович uk_UA
dc.date.accessioned2024-03-12T08:16:39Z
dc.date.available2024-03-12T08:16:39Z
dc.date.issued2023
dc.descriptionВ. Шинкаренко: ORCID 0000-0001-8738-7225; О. Макаров: ORCID 0009-0003-0921-155X uk_UA
dc.description.abstractUKR: Для виконання перевірки гіпотези щодо зменшення часу сортування алгоритмами різної обчислювальної складності проведені експерименти. Опрацьовано декілька ідей з детермінованої передобробки масивів даних для алгоритмів сортування. Запропоновані відповідні алгоритми: швидка передобробка – передбачення індексу елемента у відсортованому масиві і перестановка, передобробка з пам’яттю – передбачення і перестановка із запам’ятовуванням раніше встановлених елементів, передобробка із розворотом – розвертання послідовностей елементів відсортованих у зворотному порядку. Також запропоновані блочні варіації швидкої та передобробки з пам’яттю, які виконуються для частин масиву заданої довжини. Встановлено що більшу ефективність передобробки показують разом із алгоритмами сортування які значно прискорюються на відсортованих (або майже відсортованих) масивах даних. Блочні передобробки можуть виконуватись швидше через можливість уникнути промахів кешу (cache miss), однак показують нижчий відсоток впорядкованості масиву. Проведені експерименти з оцінки ефективності різних алгоритмів сортування після і разом з запропонованими передобробками. uk_UA
dc.description.abstractENG: To verify the hypothesis about decrease in time of sorting by algorithms of different computational complexity experiments have been conducted. Several ideas on deterministic preprocessing of data arrays for sorting algorithms have been tested. The following algorithms are proposed: quick preprocessing – prediction of the index of an element in a sorted array and permutation, preprocessing with memory - prediction and permutation with memorization of previously set elements, preprocessing with reordering – reverting sequences of elements sorted in reverse order. Also proposed block variations of quick and preprocessing with memory, which are performed for parts of the array of a given length. It has been defined that the higher efficiency of preprocessing is achieved by using with sorting algorithms, which are significantly accelerated on sorted (or almost sorted) arrays of data. Block preprocessing methods can be performed faster due to the possibility of avoiding cache misses, but show a lower percentage of array sorting. Experiments were conducted to evaluate the effectiveness of various sorting algorithms after and together with the proposed preprocessing methods.en
dc.identifier.citationШинкаренко В. І., Макаров О. В. Дослідження ефективності деяких детермінованих методів передобробки сортування даних. Проблеми програмування. 2023. № 4. С. 3–14. DOI: 10.15407/pp2023.04.003. uk_UA
dc.identifier.issn1727-4907
dc.identifier.urihttp://doi.org/10.15407/pp2023.04.003
dc.identifier.urihttps://crust.ust.edu.ua/handle/123456789/18254
dc.language.isouk
dc.publisherІнститут програмних систем НАН України, Київ uk_UA
dc.subjectалгоритм сортуванняuk_UA
dc.subjectсортуванняuk_UA
dc.subjectчасова ефективністьuk_UA
dc.subjectкомбінований алгоритмuk_UA
dc.subjectпередобробкаuk_UA
dc.subjectsorting algorithmen
dc.subjectsortingen
dc.subjecttime efficiencyen
dc.subjectcombined algorithmen
dc.subjectpreprocessingen
dc.subjectКІТuk_UA
dc.subject.classificationTECHNOLOGYen
dc.subject.classificationTECHNOLOGY:: Information technology:: Computer scienceen
dc.titleДослідження ефективності деяких детермінованих методів передобробки сортування даних
dc.title.alternativeStudy of the Efficiency of Some Deterministic Preprocessing Methods for Sorting Algoritms
dc.typeArticle
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
Shynkarenko_Makarov.pdf
Size:
1021.87 KB
Format:
Adobe Portable Document Format
Download
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
1.71 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
Статті КІТ