Тема: Обломалася моя задачка
Вирішив я вигадати задачку для форуму по програмуванні, тай задумав таку штуку. Вирішив написати функцію пошуку елемента у числовому масиві. Початкова функція просто проходила усі елементи по порядку в циклі і порівнювала з шуканим числом. У числовому масиві завжди однакова кількість сталих елементів, їх 100 і вони мають значення від 0 до 99. Потім я порахував час пошуку елементів за допомогою наступного коду.
//prepare values to search
$searches = array();
for($i = 0; $i < $countOfSearches; $i++){
$searches[] = rand(0, 99);
}
$startTime = microtime(true);
for($j = 0; $j < $countOfSearches; $j++){
search2($searches[$j]);
}
$endTime = microtime(true);
$diff = (float) $endTime - $startTime;
$average = number_format(($diff/$countOfSearches), 6);
echo "Середня швидкість пошуку одоного елемента ".$average." секунди";
echo " або ".($average * 1000)." мілісекунди або ".($average * 1000000000)." наносекунд";На вихід я завжди отримував сталу середню швидкість пошуку елемента котра була рівною 12000 наносекунд або ~83333 елементів в секунду.
Середня швидкість пошуку одоного елемента 0.000012 секунди або 0.012 мілісекунди або 12000 наносекунд або ~83333 елементів в секунду
Ось доречі сама функція.
function search($n){
$array = array(
0,1,2,3,4,5,6,7,8,9,10,
11,12,13,14,15,16,17,18,19,20,
21,22,23,24,25,26,27,28,29,30,
31,32,33,34,35,36,37,38,39,40,
41,42,43,44,45,46,47,48,49,50,
51,52,53,54,55,56,57,58,59,60,
61,62,63,64,65,66,67,68,69,70,
71,72,73,74,75,76,77,78,79,80,
81,82,83,84,85,86,87,88,89,90,
91,92,93,94,95,96,97,98,99
);
for($i = 0; $i < 100; $i++){
if($array[$i] == $n){
return true;
}
}
return false;
}Потім я подумав що швидкість пошуку напряму залежить від кількості ітерацій у пошуковому циклі і вирішив написати функцію котра буде рівно в два рази швидшою. Таке саме завдання я хотів завдати в умові задачі. Я просто написав функцію котра ділить масив на два відрізки і в кожній робить ітерації робить по 2 спроби знайти елемент. Відповідно середня кількість ітерацій зменшилась в два рази але швидкість пошуку не те що не збільшилася, вона зменшилася і стала рівною 13000 наносекунд для знаходження 1 елемента.
function search2($n){
$array = array(
0,1,2,3,4,5,6,7,8,9,10,
11,12,13,14,15,16,17,18,19,20,
21,22,23,24,25,26,27,28,29,30,
31,32,33,34,35,36,37,38,39,40,
41,42,43,44,45,46,47,48,49,50,
51,52,53,54,55,56,57,58,59,60,
61,62,63,64,65,66,67,68,69,70,
71,72,73,74,75,76,77,78,79,80,
81,82,83,84,85,86,87,88,89,90,
91,92,93,94,95,96,97,98,99
);
$delimiter = count($array)/2;
$j = count($array)-1;
for($i = 0; $i <= $delimiter && $j > $delimiter; $i++){
if($array[$i] == $n){
return true;
}
if($array[$j] == $n){
return true;
}
$j--;
}
return false;
}Середня швидкість пошуку одоного елемента 0.000013 секунди або 0.013 мілісекунди або 13000 наносекунд або ~76923 елементів в секунду
Відповідно моя задачка обломалася і замість швидшої функції я отримав повільнішу. Виявилося що функція котра проходить весь масив не вдаючись до розподілів шукає швидше. Чому?
