Внешний поиск a



Download 0,91 Mb.
bet1/16
Sana24.02.2022
Hajmi0,91 Mb.
#241523
TuriЛекция
  1   2   3   4   5   6   7   8   9   ...   16
Bog'liq
16.Внешний поиск


Лекция 16: 
Внешний поиск
A

версия для печати
< Лекция 15 || Лекция 161234567 || Лекция 17 >
Ключевые слова: значениепоискмеханизмымножествадоступоперацииотношениепроизводительностьопределениемассивdatabaseравенствобазы данных
Алгоритмы поиска, которые могут выбирать элементы из больших файлов, имеют огромное практическое значениеПоиск — это основная операция для больших наборов данных, которая, безусловно, задействует значительную часть ресурсов, используемых во многих вычислительных средах. С появлением глобальных сетей появилась возможность выбирать практически любую информацию, хоть как-то относящуюся к какой-либо задаче — проблема заключается только в возможности эффективного поиска. В этой главе рассматриваются базовые механизмы, которые могут поддерживать эффективный поиск в настолько больших таблицах символов, насколько можно себе представить.
Подобно алгоритмам из "Специальные методы сортировки" , алгоритмы, рассматриваемые в этой главе, пригодны для множества различных типов аппаратных и программных сред. Поэтому мы будем стремиться к формулировке алгоритмов на более абстрактном уровне, чем программы на языке C++. Однако приведенные далее алгоритмы также непосредственно обобщают знакомые методы поиска, и их удобно записывать в виде С++-программ, полезных во многих ситуациях. Эта глава будет не похожа на "Специальные методы сортировки" : мы тщательно разработаем конкретные реализации, рассмотрим их основные характеристики производительности, а затем обсудим способы применения базовых алгоритмов в реальных ситуациях. Вообще-то название этой главы не совсем верно, поскольку в ней алгоритмы будут представлены в виде С++-программ, взаимозаменяемых с другими реализациями таблиц символов, которые были рассмотрены в лекциях 12—15. В таком виде они вообще не являются " внешними " методами. Тем не менее, они построены в соответствии с простой абстрактной моделью, что превращает их в подробное описание того, как можно строить методы поиска для конкретных внешних устройств.
В основном нас будут интересовать методы поиска в очень больших файлах, хранящихся на внешних устройствах наподобие дисков, которые обеспечивают быстрый доступ к произвольным блокам данных. Для устройств типа ленточных накопителей, где возможен только последовательный доступ (такая модель была рассмотрена в "Специальные методы сортировки" ), поиск вырождается до тривиального (и медленного) метода считывания от начала файла до завершения поиска. С дисковыми устройствами дело обстоит намного лучше: как ни удивительно, методы, которые мы изучим, могут поддерживать операции найти и вставить в таблицах символов, содержащих миллиарды и триллионы элементов, используя всего три-четыре обращения к блокам данных на диске. Такие системные параметры, как размер блока и отношение затрат на доступ к новому блоку к затратам на доступ к элементам внутри блока, влияют на производительность, но методы можно считать относительно не зависящими от значений этих параметров (в тех пределах, которые, скорее всего, будут встречаться на практике). А большинство важных шагов, необходимых для подгонки этих методов под конкретные реальные ситуации, достаточно просты.
Поиск — это фундаментальная операция для дисковых устройств. Как правило, файлы организованы так, чтобы можно было воспользоваться преимуществами конкретного устройства для максимально эффективного доступа к информации. Короче говоря, вполне можно предположить, что устройства, используемые для хранения очень больших объемов информации, построены именно для поддержки простых и эффективных реализаций операции найти. В этой главе мы рассмотрим алгоритмы, которые построены на несколько более высоком уровне абстракции, нежели базовые операции, обеспечиваемые дисковыми устройствами, и которые могут поддерживать операцию вставить и другие динамические операции для таблиц символов. Эти методы дают такие же преимущества по сравнению с прямыми методами поиска, как и деревья бинарного поиска и хеш-таблицы по сравнению с бинарным и последовательным поиском.
Во многих вычислительных средах возможна непосредственная работа в очень большой виртуальной памяти, и мы можем предоставить системе определение эффективных способов обработки запросов данных любой программы. Рассматриваемые алгоритмы также могут служить эффективными решениями задачи реализации таблицы символов в таких средах.
Массив информации, которая должна обрабатываться компьютером, называется базой данных (database). Методам построения, сопровождения и использования баз данных посвящены многочисленные исследования. Большая часть этой работы проводится в области разработки абстрактных моделей и реализаций для поддержки операций найти с более сложным критерием, чем рассмотренное простое " равенство отдельному ключу " . В базе данных поиски могут основываться на критерии частичного соответствия, который может содержать несколько ключей и возвращать большое количество элементов. Методы этого типа будут рассмотрены в частях V и VI. Запросы на поиск общего вида достаточно сложны, поэтому зачастую приходится выполнять последовательный поиск по всей базе данных, проверяя каждый элемент на соответствие критерию. И все же быстрый поиск в огромном файле крошечных фрагментов данных, удовлетворяющих заданному критерию — основная возможность в любой системе управления базами данных, и многие современные базы данных построены на основе описанных в этой главе механизмов.
Правила игры
Как и в "Специальные методы сортировки" , мы будем считать, что последовательный доступ к данным требует значительно меньших затрат, чем не последовательный. Рабочей моделью будет любое запоминающее устройство, которое можно применить для реализации таблицы символов, разбитой на страницы (page) — непрерывные блоки информации, к которым возможен эффективный доступ дисковых устройств. Каждая страница обычно содержит множество элементов, и задача заключается в организации элементов внутри страниц таким образом, чтобы к любому элементу можно было обратиться, прочитав всего нескольких страниц. Мы будем предполагать, что время ввода/вывода, требуемое для считывания страницы, значительно больше времени, требуемого для доступа к конкретным элементам или для выполнения любых других вычислений в пределах этой страницы. Во многих отношениях эта модель слишком упрощена, но она сохраняет характеристики внешних запоминающих устройств, необходимые для рассмотрения фундаментальных методов.

Download 0,91 Mb.

Do'stlaringiz bilan baham:
  1   2   3   4   5   6   7   8   9   ...   16




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish