Құралымдық іздеу алгоритмі: реттелген сандық мәндердегі кілтті табу әдісі. 1957 ж. У.У. Петерсон сипаттаған. Телефон анықтамасындағы іздеуге ұқсас, тиімді әдіс.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Іздеу алгоритмі
Searching algorithm
Интерполяциялық іздеу – кілттерге тағайындалған сандық мәндер бойынша реттелген массивте кілтті іздеуге арналған алгоритм (кілт мәндері). Оны алғаш рет 1957 жылы В.В. Петерсон сипаттады. Интерполяциялық іздеу адамдардың телефондық анықтамалықта есімді іздеу әдісіне ұқсас (кітаптағы жазбалар реттелген кілт мәні бойынша): әр қадамда алгоритм іздеу кеңістігінің шекараларындағы кілт мәндері мен ізделіп жатқан кілт мәніне сүйене отырып, іздеу кеңістігінің қалған бөлігінде ізделіп жатқан нысан қайда болуы мүмкін екенін есептейді, әдетте сызықтық интерполяция арқылы. Осы шамаланған орында нақты табылған кілт мәні ізделіп жатқан кілт мәнімен салыстырылады. Егер ол тең болмаса, салыстыру нәтижесіне байланысты қалған іздеу кеңістігі шамаланған орынның алдындағы немесе кейінгі бөлігіне дейін қысқартылады. Бұл әдіс тек кілт мәндері арасындағы айырмашылықтардың мөлшерін есептеу мағыналы болған жағдайда ғана жұмыс істейді. Екілік іздеуге қарағанда, ол әрқашан қалған іздеу кеңістігінің ортасын таңдайды, кілттің шамаланған орнында табылған кілт пен ізделіп жатқан кілт арасындағы салыстыруға байланысты бір жартысын немесе екінші жартысын жоққа шығарады. Ол кілттер үшін сандық мәндерді қажет етпейді, тек олардың жалпы ретін ғана қажет етеді. Қалған іздеу кеңістігі шамаланған орыннан алдыңғы немесе кейінгі бөлікке дейін қысқартылады. Сызықтық іздеу тек бастапқыдан элементтерді бірінен соң бірін салыстыра отырып, теңдікті ғана пайдаланады және кез келген сұрыптауды ескермейді. Орташа есепте интерполяциялық іздеу элементтер біркелкі таратылған жағдайда log(log(n)) шамасында салыстыру жасайды, мұнда n іздеуге арналған элементтердің саны. Ең нашар жағдайда (мысалы, кілттердің сандық мәндері экспоненциалды түрде өскенде) ол O(n) дейін салыстырулар жасауы мүмкін. Интерполяциялық тізбекті іздеуде интерполяция ізделіп жатқан нысанға жақын нысанды табу үшін қолданылады, содан кейін сызықтық іздеу дәл нысанды табу үшін қолданылады.
Interpolation search is an algorithm for searching for a key in an array that has been ordered by numerical values assigned to the keys (key values). It was first described by W. W. Peterson in 1957. Interpolation search resembles the method by which people search a telephone directory for a name (the key value by which the book's entries are ordered): in each step the algorithm calculates where in the remaining search space the sought item might be, based on the key values at the bounds of the search space and the value of the sought key, usually via a linear interpolation. The key value actually found at this estimated position is then compared to the key value being sought. If it is not equal, then depending on the comparison, the remaining search space is reduced to the part before or after the estimated position. This method will only work if calculations on the size of differences between key values are sensible. By comparison, binary search always chooses the middle of the remaining search space, discarding one half or the other, depending on the comparison between the key found at the estimated position and the key sought — it does not require numerical values for the keys, just a total order on them. The remaining search space is reduced to the part before or after the estimated position. The linear search uses equality only as it compares elements one by one from the start, ignoring any sorting. On average the interpolation search makes about log(log(n)) comparisons (if the elements are uniformly distributed), where n is the number of elements to be searched. In the worst case (for instance where the numerical values of the keys increase exponentially) it can make up to O(n) comparisons. In interpolation sequential search, interpolation is used to find an item near the one being searched for, then linear search is used to find the exact item.
Өнер көрсету
Үлкен O белгісін қолдану арқылы, n өлшемді деректер жиынтығында интерполяция алгоритмінің жұмысы O(n) болады; алайда, интерполяцияға қолданылатын сызықтық шкаладағы деректердің біркелкі таралуын ескерсек, оның жұмысы O(log log n) екенін көрсетуге болады. Бірақ, жаңа дерек құрылымын пайдаланып, динамикалық интерполяциялық іздеуді o(log log n) уақытында жүргізуге болады. Интерполяциялық іздеудің нақты тиімділігі, азайтылған зондтар саны әр зонд үшін қажетті күрделі есептеулерден басып өтетін-өтпейтініне байланысты. Бұл, әсіресе дисктегі үлкен сұрыпталған файлда жазбаны табу үшін пайдалы болуы мүмкін, онда әр зонд дискіде іздеуді қамтиды және интерполяциялық есептеулерден әлдеқайда баяу. B-ағаштары сияқты индекстік құрылымдар дискіге қол жеткізу санын азайтады және дискідегі деректерді индекстеу үшін көбінесе қолданылады, себебі олар көптеген дерек түрлерін индекстеуге және онлайн режимінде жаңартуға мүмкіндік береді. Дегенмен, интерполяциялық іздеу, сұрыпталған, бірақ индекстелмеген дискідегі деректер жиынтығында іздеуге мәжбүр болған жағдайда тиімді болуы мүмкін.
Using big O notation, the performance of the interpolation algorithm on a data set of size n is O(n); however under the assumption of a uniform distribution of the data on the linear scale used for interpolation, the performance can be shown to be O(log log n). However, Dynamic Interpolation Search is possible in o(log log n) time using a novel data structure. Practical performance of interpolation search depends on whether the reduced number of probes is outweighed by the more complicated calculations needed for each probe. It can be useful for locating a record in a large sorted file on disk, where each probe involves a disk seek and is much slower than the interpolation arithmetic. Index structures like B trees also reduce the number of disk accesses, and are more often used to index on disk data in part because they can index many types of data and can be updated online. Still, interpolation search may be useful when one is forced to search certain sorted but unindexed on disk datasets.
Әртүрлі деректер жиынтығына бейімделу
Деректер жиынтығының сұрыптау кілттері біркелкі таратылған сандар болғанда, сызықтық интерполяцияны іске асыру оңай және ізделіп отырған мәнге өте жақын индексті табады. Ал, есімдері бойынша сұрыпталған телефон кітапшасында интерполяциялық іздеудің қарапайым тәсілі қолданылмайды. Дегенмен, жоғары деңгейдегі ұқсас қағидалар сақталады: есімдердегі әріптердің салыстырмалы жиілігін пайдаланып телефон кітапшасындағы есімнің орнын шамалауға болады және оны іздеу орны ретінде қолдануға болады. Кейбір интерполяциялық іздеулер тең кілт мәндерінің тізбегі болғанда күтілгендей жұмыс істемей қалуы мүмкін. Интерполяциялық іздеудің ең қарапайым түрі міндетті түрде мұндай тізбектің бірінші (немесе соңғы) мүшесін таңдамайды.
When sort keys for a dataset are uniformly distributed numbers, linear interpolation is straightforward to implement and will find an index very near the sought value. On the other hand, for a phone book sorted by name, the straightforward approach to interpolation search does not apply. The same high level principles can still apply, though: one can estimate a name's position in the phone book using the relative frequencies of letters in names and use that as a probe location. Some interpolation search implementations may not work as expected when a run of equal key values exists. The simplest implementation of interpolation search won't necessarily select the first (or last) element of such a run.
Кітаптар бойынша іздеу
Телефон кітапшасындағы есімдерді қандай да бір санға түрлендіру, есімдерді сұрыптап, оларды №1, №2 және т.б. деп атау сияқты үлкен еңбекті жұмсамайынша, біркелкі таралымды сандарды қамтамасыз етпейді. Сонымен қатар, кейбір есімдер басқаларына қарағанда әлдеқайда жиі кездеседі (мысалы, Смит, Джонс). Сөздіктерде де жағдай осылай – кейбір әріптермен басталатын сөздер басқаларына қарағанда көп болады. Кейбір баспагерлер әр әріптің орнын көрсету үшін шетке түсіндірмелер жазуға, тіпті беттердің жиегін кесіп, маркерлер жасауға бейімделген, осылайша бір көз тастағанда сегменттелген интерполяция жасауға мүмкіндік туады.
The conversion of names in a telephone book to some sort of number clearly will not provide numbers having a uniform distribution (except via immense effort such as sorting the names and calling them name #1, name #2, etc.) and further, it is well known that some names are much more common than others (Smith, Jones,) Similarly with dictionaries, where there are many more words starting with some letters than others. Some publishers go to the effort of preparing marginal annotations or even cutting into the side of the pages to show markers for each letter so that at a glance a segmented interpolation can be performed.