Дослідження ефективності деяких детермінованих методів передобробки сортування даних
Loading...
Date
2023
Journal Title
Journal ISSN
Volume Title
Publisher
Інститут програмних систем НАН України, Київ
Abstract
UKR: Для виконання перевірки гіпотези щодо зменшення часу сортування алгоритмами різної обчислювальної складності проведені експерименти. Опрацьовано декілька ідей з детермінованої передобробки масивів даних для алгоритмів сортування. Запропоновані відповідні алгоритми: швидка передобробка – передбачення індексу елемента у відсортованому масиві і перестановка, передобробка з пам’яттю – передбачення і перестановка із запам’ятовуванням раніше встановлених елементів, передобробка із розворотом – розвертання послідовностей елементів відсортованих у зворотному порядку. Також запропоновані блочні варіації швидкої та передобробки з пам’яттю, які виконуються для частин масиву заданої довжини. Встановлено що більшу ефективність передобробки показують разом із алгоритмами сортування які значно прискорюються на відсортованих (або майже відсортованих) масивах даних. Блочні передобробки можуть виконуватись швидше через можливість уникнути промахів кешу (cache miss), однак показують нижчий відсоток впорядкованості масиву. Проведені експерименти з оцінки ефективності різних алгоритмів сортування після і разом з запропонованими передобробками.
ENG: 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.
ENG: 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.
Description
В. Шинкаренко: ORCID 0000-0001-8738-7225;
О. Макаров: ORCID 0009-0003-0921-155X
Keywords
алгоритм сортування, сортування, часова ефективність, комбінований алгоритм, передобробка, sorting algorithm, sorting, time efficiency, combined algorithm, preprocessing, КІТ
Citation
Шинкаренко В. І., Макаров О. В. Дослідження ефективності деяких детермінованих методів передобробки сортування даних. Проблеми програмування. 2023. № 4. С. 3–14. DOI: 10.15407/pp2023.04.003.