Ефективн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пфа.Посилання
- 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].
- Martyn, Dzh. (1980). Orhanizatsiya baz dannykh v vychislytel’nykh sistemakh [Database organization in computing systems]. Moscow [in Russian].
- Tsehelyk, H. H. (2010). Modelyuvannya ta optymizatsiya dostupu do informatsiyi fayliv baz danykh dlya odnoprotsesornykh i bahatoprotsesornykh system: monohrafiya. [Modeling and
- optimization of access to information file databases for single-processor and multiprocessor systems]. Lviv [in Ukranian].
- Tsehelyk, H. H. (1987). Orhanyzatsiya i poisk informatsii v bazakh dannykh. [Organization and search of information in databases]. Lviv [in Russian].
- Leipala, T. (1981). On the design of one-level indexed sequential files. Int. J. Comput. Inform., 10(3), 177–186.
- 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 науки та прикладна математика
Ліцензія
Авторське право (c) 2019 Л. І. Фундак, Г. Г. Цегелик, М. І. Глебена
Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License.
Автори залишають за собою право на авторство своєї роботи та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons Attribution License, котра дозволяє іншим особам вільно розповсюджувати опубліковану роботу з обов'язковим посиланням на авторів оригінальної роботи та першу публікацію роботи у цьому журналі.