КЛАСИФІКАЦІЙНИЙ АНАЛІЗ МЕТОДІВ СОРТУВАННЯ
DOI:
https://doi.org/10.31649/1997-9266-2023-168-3-77-83Ключові слова:
сортування, ранжування, числовий масив, часова залежністьАнотація
Основною процедурою у багатьох пошукових системах є асоціативне оброблення, а саме процеси сортування, ранжування та вибірки за ключем. Ці процеси є важливими через необхідність прискорення роботи відповідних алгоритмів, де потрібно часто звертатися до певних елементів масиву даних. Потреба у паралельних методах та засобах асоціативного оброблення значних масивів даних пов’язана також з областю їхнього ефективного застосування, наприклад, у реляційних базах даних, базах знань, експертних системах, у разі аналізу семантичних мереж.
У роботі проаналізовано функціональні та реалізаційні можливості процесу сортування за відомими та альтернативними методами з урахуванням часових залежностей. Розглянуто прикладний аспект застосування операцій сортування і ранжування в таких областях як: медіанна фільтрація з попереднім обробленням сигналів і зображень, нейромережна класифікація об’єктів, підсистема підтримки прийняття рішень в експертних системах. Запропоновано класифікаційну модель методів сортування одновимірного масиву, які поділяються на дві групи за такими ознаками: застосування операції попарного порівняння та перекомутація елементів числового масиву. Першу групу складають класичні методи сортування, а друга група містить альтернативні методи сортування з позрізовим обробленням. У таблиці характеристики методів сортування першої групи розглянуто за такими ознаками, як загальна кількість порівнянь і середня кількість переміщень, які корелюють відповідно з часовими та апаратними витратами на їхню реалізацію. Наведено функціональну структуру вертикально-паралельного оброблення одновимірного масиву чисел з використанням операцій декремента і інкремента як приклад методу сортування другої групи. Водночас показано, що використання швидкісних операцій інкремента і декремента в результаті дає можливість визначити максимальний, мінімальний і середній елемент масиву за величиною. Порівняння наведених часових залежностей двох груп алгоритмів свідчить про те, що методи сортування другої групи мають більшу швидкодію або швидкодію, що не залежить від кількості елементів масиву, що сортується. При цьому, апаратна реалізація методів сортування обох груп у більшості випадків реалізується на засобах з достатнім рівнем регулярності структури, але з різним ступенем апаратних витрат.
Посилання
Р. Седжвик, Фундаментальные алгоритмы на С++. Анализ. Структура данных. Сортировка. Поиск. СПб.: ООО «ДиаСофтЮП», 2002, 688 с.
Е. А. Яценко, «Регулярные схемы алгоритмов адресной сортировки и поиска,» Управляющие системы и машины, № 5, с. 61-66, 2004.
D. E. Knuth, The Art of Computer Programming. V.3, Sorting and Searching. Reading: Addison-Wesley Longman, Inc., 1998, 800 p.
І. Г. Цмоць, Інформаційні технології та спеціалізовані засоби обробки сигналів і зображень у реальному часі, моногр. Львів, Україна: Видавництво УАД, 2005, 228 с.
І. Г. Цмоць, і В. Я. Антонів, «Апаратні засоби сортування даних методом злиття в реальному часі,» Інформаційні системи та мережі, № 814, с. 171-185, 2015. https://ena.lpnu.ua/handle/ntb/29774 .
І. Г. Цмоць, і В. Я. Антонів, «Алгоритми та паралельні структури сортування даних методом вставки,» Науковий вісник НЛТУ України, вип. 26.1, с. 340-350, 2016. https://doi.org/10.15421/40260153 .
Г. Е. Цейтлин, «Распараллеливание алгоритмов сортировки,» Кибернетика, т. 24, № 6, с. 67-74, 1989.
В. П. Кожемяко, Т. Б. Мартынюк, и В. В. Хомюк, «Особенности структурного программирования синхронных алгоритмов сортировки,» Кибернетика и системный анализ, № 5, с. 122-133, 2006.
Т. Б. Мартинюк, і Б. І. Круківський, «Модель паралельного сортувальника масиву чисел,» Вісник Вінницького політехнічного інституту, № 5 (152), с. 49-55, 2020. https://doi.org/10.31649/1997-9266-2020-152-5-49-55
Т. Б. Мартинюк, і Б. І. Круківський, «Особливості паралельного алгоритму сортування з формуванням рангів,» Кібернетика та системний аналіз, т. 58, № 1, с. 31-36, 2022.
Т. Б. Мартинюк, О. І. Черняк, Б. І. Круківський, і Мохамед Салем Нассер Мохамед, «Обчислювальна складність мережевої моделі сортування лінійного масиву чисел,» Інформаційні технології та комп’ютерна інженерія, № 2, с. 64-71, 2019. http://ir.lib.vntu.edu.ua//handle/123456789/30531 .
Т. Б. Мартинюк, Мохамед Салем Нассер, і В. В. Власійчук, «Модель сортувальної мережі,» Інформаційні технології та комп’ютерна інженерія, № 3, с. 217-220, 2005.
Г. М. Гнатієнко, і В. Є. Снитюк, Експертні технології прийняття рішень, моногр. Київ, Україна: ТОВ «Маклаут», 2008, 444 с.
А. Ш. Непомнящая, и М. А. Владыко, «Сравнение моделей ассоциативного вычислителя,» Программирование, № 6, с. 41-50, 1995.
T. Kohonen, Content-Addressable Memories. Springer-Verlag Berlin Heidelberg, 1987, 388 р.
H. Lorin, Sorting and Sort Systems. Mass.: Addison-Wesley Publishing Company, 1975, 373 р.
W. K. Pratt, Introduction to Digital image Processing. Reading: Taylor and Francis Group, Inc, 2014. 371 р.
T. B. Martyniuk, et all, «Neural network approach to numeric array sorting,» Photonics Applications in Astronomy, Communications, Industry, and High-Energy Physics Experiments: Proceedings of SPIE 11176, 111761N (6 November), 2019. https://doi.org/10.1117/12.2535916 .
А. В. Палагин, и В. Н. Опанасенко, Реконфигурируемые вычислительные системы. Киев, Украина: Просвіта, 2006, 295 с.
В. И. Осинский, Т. Б. Мартынюк, А. А. Козлов, и Мохамед Салем Нассер Мохамед, «Особенности оптоэлектронной реализации сортирующей нейросети,» Оптико-електронні інформаційно-енергетичні технології, т. 18, № 2, с. 58-67, 2009.
V. P. Kozhemyako, T. B. Martyniuk, R. A. Rasenko, and L. L. Pekhan, «Structure of optoelectronic sorting memory,» Оптико-електронні інформаційно-енергетичні технології, № 1 (3), с. 26-30, 2002.
В. Р. Григорьев, и С. П. Наумов, «Нейросетевая организация алгоритма сортировки на трехмерном оптическом нейрочипе,» Автометрия, № 3, с. 28-37, 1993.
Т. Б. Мартинюк, Н. О. Денисюк, і Б. І. Круківський, «Асоціативні процесори з паралельно-послідовною обробкою даних,» Інформаційні технології та комп’ютерна інженерія, № 1 (44), с. 27-36, 2019. https://doi.org/10.31649/1999-9941-2019-44-1-27-36 .
Т. Б. Мартинюк, Л. В. Крупельницький, і Б. І. Круківський, «Регулярна обчислювальна структура для ранжування даних,» Інформаційні технології та комп’ютерна інженерія, № 3 (52), с. 70-76, 2021. https://doi.org/10.31649/1999-9941-2021-52-3-70-76
Т. Б. Мартинюк, Б. І. Круківський, і О. А. М’якішев, «Особливості моделей нейромережного класифікатора для розпізнавання об’єктів,» Вісник Вінницького політехнічного інституту, № 4 (163), с. 56-63, 2022. https://doi.org/10.31649/1997-9266-2022-163-4-56-63 .
T. B. Martyniuk, B. I. Krukivsyi, L. M. Kupershtein, and V. V. Lukichov, «Neural network model of heteroassociative memory for the classification task,» Radioelectronic and Computer Systems, № 2 (102), pp. 108-114, 2022. https://doi.org/10.32620/reks.2022.2.09 .
] А. Ш. Непомнящая, «Сравнение алгоритмов Прима-Дейкстры и Краскала с помощью ассоциативного параллельного процессора,» Кибернетика и системный анализ, т. 36, № 2, с. 19-27, 2000.
] Т. Б. Мартынюк, и В. В. Хомюк, «Особенности математической модели дискретного SM-преобразования,» Математичні машини і системи, № 4, с. 145-155, 2010. http://dspace.nbuv.gov.ua/handle/123456789/83330 .
] Т. Б. Мартинюк, А. В. Кожем’яко, Б. І. Круківський, і А. Г. Буда, «Асоціативні операції на базі різницево-зрізової обробки даних», Вісник Хмельницького національного університету, № 4 (311), с. 159-163, 2022. https://doi.org/10.31891/2307-5732-2022-311-4-159-163 .
Т. Б. Мартинюк, Д. О. Каташинський, М. В. Микитюк, і М. О. Зайцев, «Особливості обчислювальних процесів на базі SM-перетворення,» Оптико-електронні та інформаційно-енергетичні технології, № 2 (44), с. 32-37, 2022. https://doi.org/10.31649/1681-7893-2022-44-2-32-37 .
В. Ф. Гузик, В. Е. Золотовский, и С. А. Чиненков, «Организация различных методов сортировки в вычислительных системах,» Электронное моделирование, № 3 (14), с. 25-28, 1992.
А. С. Мельничук, С. П. Луценко, Д. С. Громовий, і М. В. Трофимова, «Аналіз методів сортування масиву чисел,» Технологический аудит и резервы производства, № 4/1 (12), с. 37-40, 2013.
Т. Б. Мартинюк, А. В. Кожем’яко, А. І. Колівошко, і О. В. Карась, «Дослідження ефективності кільцевої сортувальної мережі,» Інформаційні технології та комп’ютерна інженерія, № 1, с. 68-71, 2015.
Т. Б. Мартынюк, Л. И. Тимченко, А. В. Кожемяко, и Л. М. Куперштейн, «Эффективность посрезовой обработки векторных массивов данных,» Математичні машини і системи, № 2, с. 60-67, 2017.
http://dspace.nbuv.gov.ua/handle/123456789/125561 .
Т. Б. Мартынюк, «Организация ассоциативного процессора с поразрядно-последовательной обработкой информации», Электронное моделирование, т. 18, № 3, с. 28-31, 1996.
T. Martyniuk, T. Vasilyeva, V. Suprigan, and M. AL-Heyari, «Features of sorting memory realization», Proceedings of SPIE-The International Society for Optical Engineering, vol. 4425, pp. 89-91, 2001.
Т. Б. Мартынюк, А. В. Кожемяко, и В. В. Хомюк, «Модели систолических массивов для обработки векторных данных по разностным срезам», Управляющие системы и машины, № 5, с. 46-55, 2009.
##submission.downloads##
-
PDF
Завантажень: 128
Опубліковано
Як цитувати
Номер
Розділ
Ліцензія
Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License.
Автори, які публікуються у цьому журналі, згодні з такими умовами:
- Автори зберігають авторське право і надають журналу право першої публікації.
- Автори можуть укладати окремі, додаткові договірні угоди з неексклюзивного поширення опублікованої журналом версії статті (наприклад, розмістити її в інститутському репозиторії або опублікувати її в книзі), з визнанням її первісної публікації в цьому журналі.
- Авторам дозволяється і рекомендується розміщувати їхню роботу в Інтернеті (наприклад, в інституційних сховищах або на їхньому сайті) до і під час процесу подачі, оскільки це сприяє продуктивним обмінам, а також швидшому і ширшому цитуванню опублікованих робіт (див. вплив відкритого доступу).
