ТОП-10 популярных



Для работы с вещественными числами в MySQL предусмотрено три типа данных - это типы FLOAT, DOUBLE, DECIMAL. Числовой тип FLOAT...

НОУТБУК с блестящим экраном
Eсли выпустившая ноутбук фирма предлагает его в качестве «замены настольному ПК», то это должно подразумевать под собой нечто большее, чем...

БОЛЬШЕ БОЛЬШИХ LCD-мониторов
Процесс вытеснения с рынка мониторов с электронно-лучевой трубкой (CRT) продолжается. О смещении акцентов в пользу LCD-мониторов теперь заявляют даже те...

Больше больших LCD-мониторов
Процесс вытеснения с рынка мониторов с электронно-лучевой трубкой (CRT) продолжается. О смещении акцентов в пользу LCD-мониторов теперь заявляют даже те...

Магнито-оптический дисковод DynaMO
Cейчас, когда традиционные флоппи-дисководы на долгие годы замерли в своем развитии, поиск альтернативных носителей продолжается, и ситуация, казалось бы, разрешилась...

Иди и пиши. TravelMate C100
Планшетный компьютер платформы Tablet PC обязан в первую очередь быть легким, способным достаточно долго работать без подзарядки батарей. Эти требования...

ПОД ЛИТЕРОЙ «N»
Aтаку LCD-мониторов не остановить, а масштабы этого наступления даже немного пугают. Судите сами — многие пользователи только начинают приглядываться к новому для...


Для длинных строк, т.е. строк длиннее 255 символов, в MySQL предусмотрены типы BLOB (Binary Large Object, большой двоичный объект) и...

Размер объему не помеха.
С тех пор как компания Fujitsu отказалась от производства жестких дисков для настольных компьютеров, многие пользователи начали забывать о том,...


Какую только информацию мы не помещаем на компакт-диски: резервные копии важных данных, музыку, фильмы... Многие полагают, что главное - «купить...

PHP. Сортировка, поиск и случайные числа. Часть Четвёртая.


20-05-2015

21.4. Поиск
После сортировки информация приводится к виду, который удобен для поиска нужной информации. Так, при поиске телефонного номера проще всего бегло просмотреть страницы телефонной книги, пока не будет приблизительно найдено место, где должен располагаться искомый номер. Именно этот раздел книги необходимо просмотреть подробнее. И большинство из нас так поступают автоматически.
Если вы хотите воспроизвести этот процесс в рамках PHP-сценария, необходимо позаботиться обо всех шагах. Самым простым способом является начать с начала книги и просматривать каждую запись до тех пор, пока не будет обнаружена искомая запись. И если после выполнения этих действий ничего не найдено, значит, искомая запись не существует. Пожалуй, не надо специально напоминать, что это наихудший метод поиска, но зачастую это единственное, что у нас есть в распоряжении. Если данные не отсортированы, лучшего способа не существует.
Поиск можно значительно усовершенствовать, если прибегнуть к двоичному поиску. При этом требуется, чтобы данные были отсортированы. К счастью, мы уже убедились в том, что это относительно несложно сделать. Двоичный поиск подразумевает поочередное разбиение списка на части, одна из которых не должна содержать искомой информации, а другая - должна. Двоичный поиск следует начинать с середины списка. Если элемент, расположенный посередине, предшествует искомому элементу, можно быть полностью уверенным в том, что искомый элемент располагается после среднего элемента. Теперь нам следует искать только среди половины из всех элементов. Повторяя эти шаги, мы очень быстро найдем искомый элемент. В худшем случае потребуется просмотреть log n элементов просматриваемого списка. Если имеется 128 элементов, для поиска значения потребуется сделать 7 попыток (листинг 21.6).
Листинг 21.6. Двоичный поиск
<?php
// byName
// сравнить служащих по их именам function byName($left, $right)
{
return(strcmp($left[0], $right[0]));
}
// Создать список служащих ( имя, должность, ставка) $employee = array(
array("Mckillop, Jeff", "Executive", 50),
array("Porter, Carl", "Instructor", 45),
array("Marazzani, Rick", "Manager", 35),
array("Dibetta, Bob", "Programmer", 65),
array("Atkinson, Leon", "President", 100)); // отсортировать список usort($employee, "byName"); print("<pre>"); print_r($employee); print("</pre>n"); // Задать искомую запись $Name = "Porter, Carl"; print("Searching for $Name<br>n"); // Задать диапазон поиска $lower_limit = 0;
$upper_limit = count($employee) - 1; //Выбрать середину списка
$index = floor(($lower_limit + $upper_limit)/2); while($lower_limit < $upper_limit)
{
if(strcmp($employee[$index][0], $Name) < 0)
// Выбрать первую половину $lower_limit = $index + 1;
elseif(strcmp($employee[$index][0], $Name) > 0)
// Выбрать вторую половину $upper_limit = $index - 1;
else
//Искомая запись найдена $lower_limit = $index; $upper_limit = $index;

//Выбрать среднюю точку
$index = floor(($lower_limit + $upper_limit)/2);
}
// Распечатать результаты print("Position $index<br>n"); print("{$employee[$index][0]}
{$employee[$index][1]}<br>n");
?>

21.5. Индексирование
Сортировка данных требует определенных временных затрат, но она позволит сэкономить время при последующих операциях поиска. Но на выполнение операции поиска тоже требуется определенное время. Двоичный поиск позволяет ускорить и этот процесс. Когда требуется выполнить сотни операций поиска, может потребоваться усовершенствовать и этот процесс, и здесь поможет создание индекса. Для того чтобы поиск выполнялся достаточно быстро, необходимо провести большую предварительную работу.
Посмотрим, как можно ускорить двоичный поиск из листинга 21.6. Для этого потребуется массив, который при заданном имени возвращает его положение в исходном массиве и позволит, таким образом, создать список соответствий. Обратите внимание на программный код, приведенный в листинге 21.7. Не будем думать о сортировке списка, поскольку это нам не поможет, так как мы собираемся просматривать каждый элемент массива.
По мере просмотра элементов массива создается новый массив. Индекс массива содержит имена служащих компании. Каждый элемент индекса является массивом индексов массива employee. После того как индекс создан, для поиска служащего будет достаточно одного-единственного оператора. По найденному имени в массиве можно найти значения индексов для массива employee.

| Листинг 21.7. Создание индекса_
<?php
// Создать список служащих ( имя, должность, ставка) $employee = array(
array("Mckillop, Jeff", "Executive", 50),
array("Porter, Carl", "Instructor", 45),
array("Marazzani, Rick", "Manager", 35),
array("Dibetta, Bob", "Programmer", 65),
array("Atkinson, Leon", "President", 100)); // создать индекс $employeeIndex = array(); foreach($employee as $id=>$val)
{
$employeeIndex[$val[0]] = $id;
}
//где Карл?
$index = $employeeIndex["Porter, Carl"]; print("Position $index<br>n");
print("{$employee[$index][0]} {$employee[$index][1]}<br>n");
?> 
Этот пример не совсем реалистичен, так как мы выполняем только одну операцию поиска и при каждом запросе потребуется создание индекса. А индекс достаточно создать только один раз, поскольку массив employee не претерпевает изменений. Возможно, пользуясь возможностью трансформации, которую имеет PHP, этот массив можно сохранить в отдельном файле, который можно по необходимости загрузить. Аналогичный программный код был написан автором для индексирования ключевых слов, которые возникают на Web-узле, в ходе выполнения проекта FreeTrade.
Конечно, для обработки данных мощные решения предлагают базы данных. В большинстве случаев хранение больших объемов данных лучше всего возложить на базы данных, поскольку они имеют специальные возможности для поиска и сортировки. Базы данных описываются в главе 23, "Интеграция баз данных".

Понравился материал? Поделитесь с друзьями!



<< Предыдущая статьяСледующая статья >>
PHP. Сортировка, поиск и случайные числа. Часть Третья. PHP. Сортировка, поиск и случайные числа. Часть Пятая.