1

Тема: Обломалася моя задачка

Вирішив я вигадати задачку для форуму по програмуванні, тай задумав таку штуку. Вирішив написати функцію пошуку елемента у числовому масиві. Початкова функція просто проходила усі елементи по порядку в циклі і порівнювала з шуканим числом. У числовому масиві завжди однакова кількість сталих елементів, їх 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 елементів в секунду

Відповідно моя задачка обломалася і замість швидшої функції я отримав повільнішу. Виявилося що функція котра проходить весь масив не вдаючись до розподілів шукає швидше. Чому?

Щоб зрозуміти рекурсію потрібно спочатку зрозуміти рекурсію.
int fac(int n) { return n < 2 ? 1 : n*fac(n-1); }

2

Re: Обломалася моя задачка

Якщо розмістити масив глобально і взяти доступ до нього через $GLOBALS, то швидкість виростає на 50%!!!

$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
        );
        
    function search($n){        
        for($i = 0; $i < 100; $i++){
            if($GLOBALS["array"][$i] == $n){
                return true;
            }
        }
        return false;
    }

Середня швидкість пошуку одоного елемента 0.000008 секунди або 0.008 мілісекунди або 8000 наносекунд або ~125000 елементів в секунду

Якщо передати масив по адресу то швидкість виростає на 300%!!!

$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
        );
        
    function search($n, &$array){        
        for($i = 0; $i < 100; $i++){
            if($array[$i] == $n){
                return true;
            }
        }
        return false;
    }

Середня швидкість пошуку одоного елемента 0.000004 секунди або 0.004 мілісекунди або 4000 наносекунд або ~250000 елементів в секунду

Щоб зрозуміти рекурсію потрібно спочатку зрозуміти рекурсію.
int fac(int n) { return n < 2 ? 1 : n*fac(n-1); }

3

Re: Обломалася моя задачка

Мої думки

Patron написав:

Відповідно моя задачка обломалася і замість швидшої функції я отримав повільнішу. Виявилося що функція котра проходить весь масив не вдаючись до розподілів шукає швидше. Чому?

В тілі циклу одна додаткова перевірка, в умові також додаткова перевірка.
Ймовірність знайти шуканий елемент на позиціях i, i+1 дорівнює ймовірності знайти елемент на позицях i, n-i, тому це нічого не вирішує.


Patron написав:

Якщо розмістити масив глобально і взяти доступ до нього через $GLOBALS, то швидкість виростає на 50%!!!

Час на створення масиву всередині функції при кожному виклику не витрачається.


Patron написав:

Якщо передати масив по адресу то швидкість виростає на 300%!!!

У випадку Globals йде звертання одразу до двох індексів, спочатку 'array', а потім $i

4

Re: Обломалася моя задачка

Ідея була в тому щоб зменшити кількість ітерацій у два рази і відповідно отримати у два рази більшу швидкість. Мене здивувало те що системі простіше зробити більше ітерацій ніж витрачати час на додаткові умови у кожній ітерації.

Час на створення масиву всередині функції при кожному виклику не витрачається.

це я знав, просто ніколи не доводилося тестувати такий спосіб передачі параметрів на php.

Щоб зрозуміти рекурсію потрібно спочатку зрозуміти рекурсію.
int fac(int n) { return n < 2 ? 1 : n*fac(n-1); }

5

Re: Обломалася моя задачка

2 функцію можна переписати і досягти такого ж часу як і в 1-й ;)

6

Re: Обломалася моя задачка

Replace написав:

2 функцію можна переписати і досягти такого ж часу як і в 1-й ;)

Напиши як придумав)

Щоб зрозуміти рекурсію потрібно спочатку зрозуміти рекурсію.
int fac(int n) { return n < 2 ? 1 : n*fac(n-1); }

7

Re: Обломалася моя задачка

 for($i = 0, $j = 99;  $i < $j; $i++, $j--){
            if($array[$i] == $n){
                return true;
            } else if($array[$j] == $n){
                return true;
            }
        }

8

Re: Обломалася моя задачка

for($i = 0;  $i <= $delimiter;){
            if($array[$i] == $n){
                return true;
            }
            if($array[$j] == $n){
                return true;
            }
            $i++;
            $j--;
        }

12000 тисяч наносекунд на елемент.

Щоб зрозуміти рекурсію потрібно спочатку зрозуміти рекурсію.
int fac(int n) { return n < 2 ? 1 : n*fac(n-1); }

9

Re: Обломалася моя задачка

function search2($n, &$iterations){        
        $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
        );
        
        
        $quarter = count($array)/4;
        $j = count($array)-1;
        for($a = 0, $b = $a+$quarter, $c = $b+$quarter, $d = $c+$quarter;  $a < $b;){
            if($array[$a] == $n){
                return true;
            }
            if($array[$b] == $n){
                return true;
            }
            
            if($array[$c] == $n){
                return true;
            }
            if($array[$d] == $n){
                return true;
            }
            $a++;
            $b++;
            $c++;
            $d++;
            $iterations++;
        }
        return false;
    }

Максимально можлива кількість ітерацій 25 але швидкість не збільшилася))) Перша функція іноді робить понад 90 ітерацій і в результаті дає таку саму швидкість.)

Щоб зрозуміти рекурсію потрібно спочатку зрозуміти рекурсію.
int fac(int n) { return n < 2 ? 1 : n*fac(n-1); }

10 Востаннє редагувалося Replace (23.11.2012 01:21:03)

Re: Обломалася моя задачка

Друга трішки швидше :)

<?php

    $countOfSearches = 100000;
    $max = 1000;
    $searches = array();
    for($i = 0; $i < $countOfSearches; $i++){
        $searches[] = $i;
    } 
    
    $array = array();
    for ($i = 0; $i < $max; $i++) {
        $array[$i] = $i;
    }
    
    test('search', $countOfSearches, $array);
    test('search2', $countOfSearches, $array);
    
    function test($search, $countOfSearches, &$array) {
        
        global $max;
        
        $startTime = microtime(true);
        
        for ($i = 0; $i < $countOfSearches; $i++) {
            $n = rand(0, $max);
            $search($array, $n);
        }
        
        $endTime = microtime(true);
        $diff = (float) $endTime - $startTime;
 
        $average = number_format(($diff/$countOfSearches), 6);
        echo "$search - ".$average." секунди\n";   
    }
    
    
      function search(&$array, $n){
           $size = count($array);
        for($i = 0; $i < $size - 1; $i++){
            if($array[$i] == $n){
                return true;
            }
        }
        return false;
    }
    
    function search2(&$array, $n){
        $size = count($array);
        for($i = 0, $j = $size - 1;  $i < $j; $i++, $j--){
            if($array[$i] == $n){
                return true;
            } else if($array[$j] == $n){
                return true;
            }
        }
        return false;
    }
    
    

Результати:

Leonids-MacBook-Pro:~ leo$ php php.php
search - 0.000098 секунди
search2 - 0.000093 секунди
Leonids-MacBook-Pro:~ leo$ php php.php
search - 0.000098 секунди
search2 - 0.000092 секунди
Leonids-MacBook-Pro:~ leo$ php php.php
search - 0.000098 секунди
search2 - 0.000093 секунди

На сервері:

search - 0.000073 секунди
search2 - 0.000071 секунди

search - 0.000074 секунди
search2 - 0.000072 секунди

11

Re: Обломалася моя задачка

function search(&$array, $n){
           $size = count($array);
        for($i = 0; $i < $size - 1; $i++){ // помилка, ти схитрив на 1 ітерацію) $i < $size;
Щоб зрозуміти рекурсію потрібно спочатку зрозуміти рекурсію.
int fac(int n) { return n < 2 ? 1 : n*fac(n-1); }
Подякували: Replace1

12

Re: Обломалася моя задачка

Так що виходить що при великих масивах 2 функція обганяє першу? Треба спробувати з масивом на 10000 елементів.))

Щоб зрозуміти рекурсію потрібно спочатку зрозуміти рекурсію.
int fac(int n) { return n < 2 ? 1 : n*fac(n-1); }

13

Re: Обломалася моя задачка

Запустив на 10тис елементів.
Чекав хвилин 10.
Ось такі результати:

search - 0.001281 секунди
search2 - 0.001295 секунди

Тобто, можна сказати, що алгоритми мають приблизно однакову ефективність.

Подякували: Patron1

14

Re: Обломалася моя задачка

Якщо знати що масив впорядкований, то там є варіанти