ОПТИМАЛЬНИЙ БЛОКОВИЙ ПОШУК У ВИПАДКУ РІВНОМІРНОГО РОЗПОДІЛУ ЙМОВІРНОСТЕЙ ЗВЕРТАННЯ ДО ЗАПИСІВ
OPTIMAL BLOCK SEARCH IN THE CASE OF A UNIFORM DISTRIBUTION OF PROBABILITIES OF ACCESS TO RECORDS
Сторінки: 204-207. Номер: №3, 2019 (273)
Автори:
Л.І. ФУНДАК, Г.Г. ЦЕГЕЛИК
Львівський національний університет імені Івана Франка
L.I. FUNDAK, H.H. TSEHELYK
Ivan Franko Lviv National University
DOI: https://www.doi.org/10.31891/2307-5732-2019-273-3-204-207
Рецензія/Peer review : 15.05.2019 р.
Надрукована/Printed : 02.06.2019 р.
Анотація мовою оригіналу
У роботі розглянутий оптимальний блоковий пошук у випадку рівномірного розподілу ймовірностей звертання до записів, якщо в локалізованому блоці використовується метод двійкового пошуку. Проведено дослідження оптимальної кількості порівнянь, необхідних для пошуку запису у файлі. Показано ефективність методу двійкового пошуку у порівнянні з використанням методу послідовного перегляду для пошуку запису у локалізованому блоці.
Ключові слова: рівномірний розподіл ймовірностей звертання до записів, блоковий пошук, метод двійкового пошуку, метод послідовного перегляду.
Розширена анотація англійською мовою
The purpose of the article is to investigate the effectiveness of the optimal block search in the case of a uniform distribution of the probabilities of access to records if the localized block uses the binary search method. Among the methods for finding information in large databases, the block search method is most effective. The essence of this method is as follows. If file entries ordered in ascending or decreasing values of a key, then it is not necessary to view all records preceding the searched for the record. Entries can be split into blocks and first locate the block containing the desired entry by viewing the latest block records. After the record block is localized, the search for the desired record in the block is continued using one of the methods below. Block search method investigated for different laws of distribution of the probabilities of access to records when used in a localized block to search for the method of sequential viewing. However, in the case of a uniform distribution of probabilities, the block search method can be made much more efficient by using the binary search method in the localized block. This case investigated in the work. The graphs show the dependence of the average number of comparisons between the number of records in the file and the number of blocks on which the file is split. A comparison of the effectiveness of two block search options (with using in block sequential viewing and binary search) is conducted. The average number of comparisons for the different number of records in the file for both methods was calculated and compared. It is shown, that using a binary search method to search for a record in a localized block, you can significantly reduce the average number of comparisons required to search for a record in a file.
Keywords: uniform distribution of probabilities of access to records, block search, binary search method, sequential search.
References
- Tsehelyk H.H. Modeliuvannia ta optymizatsiia dostupu do informatsii failiv baz danykh dlia odnoprotsesornykh i bahatoprotsesornykh system : monohrafiia / H. H. Tsehelyk. – Lviv, 2010. – 192 s.
- Cegelik G. G. Metody avtomaticheskoj obrabotki informacii / G. G. Cegelik. – Lvov, 1981. – 132 s.
- Fundak L. I. Optymalnyi blokovyi poshuk u vypadku rivnomirnoho rozpodilu ymovirnostei zvertannia do zapysiv / L.I. Fundak, H.H. Tsehelyk // Materialy XXIV Vseukr. nauk. konf. “Suchasni problemy prykladnoi matematyky ta informatyky”. – Lviv, 2018. – S. 166–168.
