Ефективнiсть методу двiйкового пошуку записiв у файлах баз даних у випадку розподiлу ймовiрностей звертання до записiв за законом Зiпфа

Автор(и)

DOI:

https://doi.org/10.24144/2616-7700.2019.1(34).102-107

Ключові слова:

розподiл ймовiрностей звертання до записiв за законом Зiпфа, метод двiйкового пошуку, математичне сподiвання

Анотація

Основний акцент пiд час розв’язування рiзноманiтних задач з використанням концепцiї баз даних переноситься з процедур опрацювання iнформацiї на процедури органiзацiї збереження та пошуку iнформацiї в базах даних. Тому продуктивнiсть обчислювальних систем, орiєнтованих на опрацювання iнформацiї у великих базах даних, головним чином визначається ефективнiстю методiв пошуку iнформацiї у файлах баз даних. Оскiльки в бiльшостi систем опрацювання iнформацiї типовими є випадки нерiвномiрного розподiлу ймовiрностей звертання до записiв файлiв, то дослiдження ефективностi методiв пошуку проводиться для таких типових законiв нерiвномiрного розподiлу ймовiрностей як бiнарний, закон Зiпфа, узагальнений закон. За критерiй ефективностi методiв приймається математичне сподiвання кiлькостi порiвнянь, необхiдних для пошуку запису у файлi. Деякi частковi результати дослiдження ефективностi методiв пошуку одержанi зарубiжними авторами, зокрема вони вiдображенi у монографiях Д. Кнута i Дж. Мартiна. Бiльш повнi дослiдження проведенi в працях Цегелика Г.Г. Для пошуку запису у файлi можна використати рiзнi методи: послiдовний перегляд; однорiвневий чи багаторiвневий блоковий пошук; двiйковий пошук; метод пошуку, що враховує розподiл ймовiрностей звертання до записiв; методи пошуку, що використовують iндекси тощо. Ефективнiсть цих методiв для рiзних законiв розподiлу ймовiрностей звертання до записiв є рiзною. Вважатимемо, що файл бази даних упорядкований за зростанням значень ключа. У статтi виведено формулу для обчислення математичного сподiвання кiлькостi порiвнянь, необхiдних для пошуку запису у файлi, у випадку розподiлу ймовiрностей звертання до записiв за законом Зiпфа. Зроблено порiвняння ефективностi методу послiдовного перегляду та методу двiйкового пошуку у цьому випадку, а також порiвняння ефективностi двiйкового пошуку у випадку рiвномiрного розподiлу ймовiрностей i розподiлу за законом Зiпфа. На графiках показана залежнiсть математичного сподiвання кiлькостi порiвнянь вiд кiлькостi записiв у файлi у випадку розподiлу ймовiрностей звертання до записiв за законом Зiпфа.

Біографії авторів

Л. І. Фундак, Львiвський нацiональний унiверситет iм. I. Франка, Львiв

асистент кафедри математичного моделювання соцiально-економiчних процесiв

Г. Г. Цегелик, Львiвський нацiональний унiверситет iм. I. Франка, Львiв

професор кафедри математичного моделювання соцiально-економiчних процесiв, доктор фiзико-математичних наук

М. І. Глебена, ДВНЗ «Ужгородський нацiональний унiверситет», Ужгород

доцент кафедри системного аналiзу i теорiї оптимiзацiї, кандидат фiзико-математичних наук

Посилання

  1. Knut, D. (2000). Iskusstvo prohrammirovaniya dlya EV M ´ . T. 3. Sortirovka y poisk. [The art of programming for computers. Vol. 3. Sort and search]. Moscow [in Russian].
  2. Martyn, Dzh. (1980). Orhanizatsiya baz dannykh v vychislytel’nykh sistemakh [Database organization in computing systems]. Moscow [in Russian].
  3. Tsehelyk, H. H. (2010). Modelyuvannya ta optymizatsiya dostupu do informatsiyi fayliv baz danykh dlya odnoprotsesornykh i bahatoprotsesornykh system: monohrafiya. [Modeling and
  4. optimization of access to information file databases for single-processor and multiprocessor systems]. Lviv [in Ukranian].
  5. Tsehelyk, H. H. (1987). Orhanyzatsiya i poisk informatsii v bazakh dannykh. [Organization and search of information in databases]. Lviv [in Russian].
  6. Leipala, T. (1981). On the design of one-level indexed sequential files. Int. J. Comput. Inform., 10(3), 177–186.
  7. Leipala, T. (1982). On optimal multilevel indexed sequential files. Inform. Process. Lett., 15(5), 191–195.

##submission.downloads##

Опубліковано

2019-07-02

Як цитувати

Фундак, Л. І., Цегелик, Г. Г., & Глебена, М. І. (2019). Ефективнiсть методу двiйкового пошуку записiв у файлах баз даних у випадку розподiлу ймовiрностей звертання до записiв за законом Зiпфа. Науковий вісник Ужгородського університету. Серія «Математика і інформатика», 1(34), 102–107. https://doi.org/10.24144/2616-7700.2019.1(34).102-107

Номер

Розділ

Iнформатика, комп’ютернi науки та прикладна математика