Помощь начинабщему №2 (Практикум)

Думал сегодня над "своим" алгоритмом, пришел к выводу, что нулевой элемент массива должен быть равен нулю (если числа натуральные), либо наименьшему числу из массива, либо просто наименьшему... Тогда за пределы массива мы не выйдем, уж точно...
Пробегаться по исходному массиву скучно и долго (это про ссылку insert_sort.php). Я предлагаю другой вариант:

Код (Text):

1.  
2. 1. Упростим задачу: все элементы массива имеют один и тот же тип
3. 2. делаем gettype() первого элемента массива
4. 3. Зная его тип, мы знаем наименьше-возможное число $minim.
5. 4. Делаем в массиве arr_push($arr,$minim),
6. т.е. добавляем его в конец нашего родного массива.
7. 5. Делаем shift() массива, т.е. последний элемент станет первым
8. 6. выполняем сортировку (см код выше)
9. 7. Производим unshift() массива и удаляем последний элемет...

это теория, как будет на практике не знаю... но думаю нотисов не будет *миг Raa

 

Честно говоря, я не понял смысл этих манипуляций. предлагаю тебе изучить ссылочку, которую ты процитировал. Там подробно описан тот метод, который ты используешь, и даже пример кода. Разбери в деталях сам метод, не подглядывая в пример кода, и попробуй переписать заново функцию.

 

2Raa
я ссылочку просмотрел, в код не заглядывал (даже не понял на чем он написан, ну не стал на него обращать внимания %) и в алгоритме (по ссылке) обнаружил нелогичную для php реализацию....

там предлагается
1. сохранить первый элемент массива куда-ть в тмп
2. заменить первый элемент массива на наименьший элемент
3. выполнить сортировку
4. заменить первый элемент массива на тмп
5. пройтись по циклу сортировки еще раз

меня смутил пятый пункт, вместо него я предложил:
1. добавить в конец массива наименьше число
2. сдвинуть массив вправо функцией shift()
3. выполнить сортировку.
4. сдвинуть массив влево функцией unshift()
5. удалить последний элемент массива (наше родимое, наименьшее числ)

причем "наименьшее число" я предложил искать не в массиве (как никак прийдется опять пробежать по всему массиву, а взять наименьшее число из типа элемента массива)

код приведу чуть позже %)

 

Там не предлагается

И если уже описывать алгоритм сортировки, то там не будет пункта "выполнить сортировку". Иначе больше никаких пунктов и не нужно. Такой себе элементраный алгоритм:

1. выполнить сортировку

И все )

Читай внимательно описание алгоритма, сравни его с другими. У меня подозрение, что ты немного не допонял его.

 

2Raa
Ладно, заменить пункт
3. Выполнить цикл по сортировке

 

2topas
Да все равно не понятно, что ты имеешь в виду. Это не описание алгоритма, а какой-то приблизительный набросок действий. Я не могу понять, что ты имеешь в виду под циклом сортировки.

Вот как один из вариантов описания алгоритма.

1. Устанавливаем курсор i на второй элемент массива. Курсор делит массив на две части: левая - отсортированная, правая - неотсортированная.
2. Если i выходит за пределы массива - завершаем выполнение алгоритма.
3. Вставляем i-й элемент в отсортированную часть массива. Для этого:
3.1. Сохраняем i-й элемент во временную переменную t.
3.2. Устанавливаем курсор j = i для нахождеиня места вставки.
3.4. Пока j указывает не на первую ячейку и (j-1)-й элемент больше чем t, сдвигаем (j-1)-й элемент вправо, а крусор j - влево.
3.5. Вставляем t в j-ю ячейку.
4. Сдвигаем i вправо.
5. Возвращаемся к шагу 2.

Это можно назвать алгоритмом, потому что строго руководствуясь этой инструкцией можно отсортировать массив (если я нигде не ошибся). Попробуй вручную отсортировать маленький массивчик по этому алгоритму. А потом попробуй сделать то же самое по своему алгоритму.

 

А вообще внатуре оффтоп такой пошел уже... алгоритмы всякие... ))) На форуме явно не хватает двух разделов: Алгоритмы и Задания для учащихся )

 

ну так... практика так практика

ладно, вот что пытался выразить словами:

PHP:

1. <?
2.     function my_sort(&$arr,$min=0){
3.     $sz = count($arr);
4.     array_unshift($arr);
5.     $count = 0;
6.     for ($i=1; $i < $sz; $i++){  
7.         $count++;
8.         if ($arr[$i-1] > $arr[$i]){
9.            $temp      = $arr[$i-1];
10.            $arr[$i-1] = $arr[$i];
11.            $arr[$i]   = $temp;
12.            $i -= 2;
13.         }
14.     }
15.     array_shift($arr);
16.     return $count;
17. }
18.  
19. $my_arr = array(3,-3,4,1,-49,2,4,5,1,5,5,1,2,4,6,7,3,5,65);
20. print_r($my_arr);
21. $count = my_sort($my_arr,-100);
22. echo "<br>";
23. print_r($my_arr);
24. echo "<br>Размер массива: ".count($my_arr)."; Количество заходов в цикл: ".$count;
25. ?>
26.  

Второй параметр функции: число, которое меньше каждого элемента массива... по умолчание сортируем только натуральные числа... Если у пользователя будет желание, он может указать например -27e10 и будет сортировать отрицательные числа...

результат функции:

Код (Text):

1. Array ( [0] => 3 [1] => -3 [2] => 4 [3] => 1 [4] => -49 [5] => 2 [6] => 4 [7] => 5 [8] => 1 [9] => 5 [10] => 5 [11] => 1 [12] => 2 [13] => 4 [14] => 6 [15] => 7 [16] => 3 [17] => 5 [18] => 65 )
2. Array ( [0] => -3 [1] => 1 [2] => 1 [3] => 1 [4] => 2 [5] => 2 [6] => 3 [7] => 3 [8] => 4 [9] => 4 [10] => 4 [11] => 5 [12] => 5 [13] => 5 [14] => 5 [15] => 6 [16] => 7 [17] => 65 )
3. Длина массива: 18; Количество заходов в цикл: 98

 

Все равно далеко не оптимально. И параметр $min еще зачем-то... Теперь пользователю нужно думать о том, каким образом твоя функция работает? Попробуй перечитать мои посты и описание алгоритма на algolist.manual.ru. До совершенства еще далеко.

 

добавил направление сортировки,
и попытался посчитать какой способ передачи массива оптимальнее по времени исполнения кода использовать:

PHP:

1. <?php
2.     $ar = array (1,12,334,5,66,7,9,0);
3.     echo implode(', ', $ar).'<br>';
4.  
5. function sorting1(&$arr, $direction=0){
6. // This function use "SelectSort" method.
7.     $size = count($arr);
8.     for ($i = 0; $i < $size; $i++) {
9.         $min = $arr[$i];
10.         $key = $i;
11.         for ($j = $i+1; $j < $size; $j++) {
12.             if (($arr[$j] < $min)&&$direction) {
13.                 $key = $j;
14.                 $min = $arr[$j];
15.             } elseif (($arr[$j] > $min)&&!$direction) {
16.                 $key = $j;
17.                 $min = $arr[$j];
18.             }
19.         }
20.         $arr[$key] = $arr[$i];
21.         $arr[$i] = $min;
22.     }
23. }
24.  
25. function sorting2($arr, $direction=0){
26. // This function use "SelectSort" method.
27.     $size = count($arr);
28.     for ($i = 0; $i < $size; $i++) {
29.         $min = $arr[$i];
30.         $key = $i;
31.         for ($j = $i+1; $j < $size; $j++) {
32.             if (($arr[$j] < $min)&&$direction) {
33.                 $key = $j;
34.                 $min = $arr[$j];
35.             } elseif (($arr[$j] > $min)&&!$direction) {
36.                 $key = $j;
37.                 $min = $arr[$j];
38.             }
39.         }
40.         $arr[$key] = $arr[$i];
41.         $arr[$i] = $min;
42.     }
43.     return $arr;
44. }
45.  
46.  
47.  
48.     list($usec1, $sec1) = explode(" ", microtime());
49.     for ($i=0; $i<100000; $i++) {
50.         sorting1($ar,0);
51.     }
52.     list($usec2, $sec2) = explode(" ", microtime());
53.     for ($i=0; $i<100000; $i++) {
54.         sorting2($ar,0);
55.     }
56.     list($usec3, $sec3) = explode(" ", microtime());
57.     echo "\n<br>Time1 = ".($sec2-$sec1)."sec ".($usec2-$usec1)."msec\n<br>";
58.     echo "\n<br>Time2 = ".($sec3-$sec2)."sec ".($usec3-$usec2)."msec\n<br>";
59.     echo implode(', ', $ar).'<br>';
60.  
61. ?>
62.  

Результат в браузере:

Код (Text):

1.  
2. 1, 12, 334, 5, 66, 7, 9, 0
3.  
4. Time1 = 9sec 0.086016msec
5.  
6. Time2 = 9sec 0.068688msec
7. 334, 66, 12, 9, 7, 5, 1, 0

мог напутать с временными функциями
но вывод такой незначительно но второй способ быстрее.

большее количество итераций задать не могу - время скрипта ограничено 30 секундами.

 

Вместо двух условий я б написал бы вот так (намекал на это, но видно непрозрачно )

PHP:

1. <?
2.     if (($arr[$j] < $min == $direction) {
3.         $key = $j;
4.         $min = $arr[$j];
5.     }
6. ?>

Такой незначительностью вполне можно принебречь, и использовать тот метод, который удобнее. Имхо, логичнее ловить измененный массив в качестве возвращаемого значения.

Я думаю, и не надо. 100 тыс. - это и так порядочно. Неплохо было бы попробовать крутануть тест на огромных массивах. Потому что выигрышь второго метода весьма сомнителен. Можно сгенерить рандомом массивчик в несколько тыс элементов, дабы убедиться.

 

мой скрипт на тест захватите плиз... если найдете ему там место конечно

 

как все просто
а я выдумывал такую логическую последовательность:
событие a = ($arr[$j] < $min)
событие b = $direction

(a or b) and !(a and b)
написанное не вместилось в строчку и я понял что с точки зрения времени выполнения не допустимо нагружать скрипт.
видимо если бы я применил пару правил из булевой логики то пришел бы к тому же.:roll:

есть смысл, потому как эксперимент получился не оконченным.

 

Ага! Булева алгебра рулит! )

И topas'а функцию заодно прогони ;-)

 

обязательно прогоню.

вот пока что массив из 100 случайных чисел прокрутил 1000, однако результаты не понятны.

Код (Text):

1. 367044441, 942204300, 660390806, 1257800165, 2128547341, 147892568,
2. ...
3. 625119003, 848404544
4.  
5. Time1 = 10sec 0.299636msec
6.  
7. Time2 = 11sec -0.786106msec
8. 2128547341, 2114299089, 2091218768,
9. ...
10. 147892568, 76271672, 37949143, 10231253, 3593636

или вот еще

Код (Text):

1.  
2.  
3. Time1 = 10sec 0.260226msec
4.  
5. Time2 = 7sec 0.267465msec

а потом еще

Код (Text):

1.  
2. Time1 = 10sec 0.234563msec
3.  
4. Time2 = 8sec -0.678274msec

странновато микросекунды считаются. или милисекунды. я вообщето справедливо пользуюсь microtime(); ?

 

функция microtime () работает странно. зачем ей отрицательные микросекунды выдавать?

а по разнице времени это мой косяк. условие

PHP:

1. <?
2.     if (($arr[$j] < $min == $direction) {
3.         $key = $j;
4.         $min = $arr[$j];
5.     }
6. ?>

исправил только в одной функции. так что 30% это разница подсчета моего варианта и вышеприведенного. не кислая разница. не думал что в реалии все так серьезно.... думал микросекунды ...

теперь :

Код (Text):

1.  
2. Time1 = 8sec -0.659661msec
3.  
4. Time2 = 7sec 0.310508msec

 

PHP:

1. <?php
2.     for ( $i=0; $i <100; $i++) { $ar[] = rand();}
3.     echo implode(', ', $ar).'<br>';
4.  
5. function sorting($arr, $direction=0){
6. // This function use "SelectSort" method.
7.     $size = count($arr);
8.     for ($i = 0; $i < $size; $i++) {
9.         $min = $arr[$i];
10.         $key = $i;
11.         for ($j = $i+1; $j < $size; $j++) {
12.             if (($arr[$j] < $min) == $direction) {
13.                 $key = $j;
14.                 $min = $arr[$j];
15.             }
16.         }
17.         $arr[$key] = $arr[$i];
18.         $arr[$i] = $min;
19.     }
20.     return $arr;
21. }
22.  
23. function my_sort(&$arr,$min=0){
24.     $sz = count($arr);
25.     array_unshift($arr);
26.     for ($i=1; $i < $sz; $i++){  
27.         if ($arr[$i-1] > $arr[$i]){
28.            $temp      = $arr[$i-1];
29.            $arr[$i-1] = $arr[$i];
30.            $arr[$i]   = $temp;
31.            $i -= 2;
32.         }
33.     }
34.     array_shift($arr);
35. }  
36.  
37.     list($usec1, $sec1) = explode(" ", microtime());
38.     for ($i=0; $i<1000; $i++) {
39.         sorting($ar,0);
40.     }
41.     list($usec2, $sec2) = explode(" ", microtime());
42.     for ($i=0; $i<1000; $i++) {
43.           my_sort($ar,-100);
44.     }
45.     list($usec3, $sec3) = explode(" ", microtime());
46.     echo "\n<br>Time1 = ".($sec2-$sec1)."sec ".($usec2-$usec1)."msec\n<br>";
47.     echo "\n<br>Time2 = ".($sec3-$sec2)."sec ".($usec3-$usec2)."msec\n<br>";
48.     echo implode(', ', $ar).'<br>';
49.  
50. ?>
51.  
52.  

многократно выдает ошибку:
Warning: Wrong parameter count for array_unshift() in /usr/home/ac/php/work/sort/4.php on line 25

 

PHP:

1. <?php
2.     for ( $i=0; $i <100; $i++) { $ar[] = rand();}
3.     echo implode(', ', $ar).'<br>';
4.  
5. function sorting($arr, $direction=0){
6. // This function use "SelectSort" method.
7.     $size = count($arr);
8.     for ($i = 0; $i < $size; $i++) {
9.         $min = $arr[$i];
10.         $key = $i;
11.         for ($j = $i+1; $j < $size; $j++) {
12.             if (($arr[$j] < $min) == $direction) {
13.                 $key = $j;
14.                 $min = $arr[$j];
15.             }
16.         }
17.         $arr[$key] = $arr[$i];
18.         $arr[$i] = $min;
19.     }
20.     return $arr;
21. }
22.  
23. function my_sort(&$arr,$min=0){
24.     $sz = count($arr);
25.     array_unshift($arr);
26.     for ($i=1; $i < $sz; $i++){  
27.         if ($arr[$i-1] > $arr[$i]){
28.            $temp      = $arr[$i-1];
29.            $arr[$i-1] = $arr[$i];
30.            $arr[$i]   = $temp;
31.            $i -= 2;
32.         }
33.     }
34.     array_shift($arr);
35. }  
36.  
37.     list($usec1, $sec1) = explode(" ", microtime());
38.     for ($i=0; $i<1000; $i++) {
39.         sorting($ar,0);
40.     }
41.     list($usec2, $sec2) = explode(" ", microtime());
42.     for ($i=0; $i<1000; $i++) {
43.           my_sort($ar,-100);
44.     }
45.     list($usec3, $sec3) = explode(" ", microtime());
46.     echo "\n<br>Time1 = ".($sec2-$sec1)."sec ".($usec2-$usec1)."msec\n<br>";
47.     echo "\n<br>Time2 = ".($sec3-$sec2)."sec ".($usec3-$usec2)."msec\n<br>";
48.     echo implode(', ', $ar).'<br>';
49.  
50. ?>
51.  
52.  

2topas: выше приведен код - многократно выдает ошибку:
Warning: Wrong parameter count for array_unshift() in /usr/home/ac/php/work/sort/4.php on line 25

 

2karatist

Отрицательные микросекунды у тебя потому что отнимаешь отдельно секунды и отдельно микросекунды.

Походу, сложность функций сортировки несопоставима с задачами возвращения значения. Поэтому результаты получаются одинаковые. Я погонял эти две функции и вкривь и вкось - никакой ощутимой разницы. Зато, как и следовало ожидать, разница сразу стала измеряться порядками, когда я сделал функции пустыми и увеличил размер массива до десятка тысяч элементов. Только, вопреки моим ожиданиям, быстрее была функция, возвращающая массив по значению, чем принимающая его по ссылке. Выходит, копирование массива происходит быстрее, чем создание ссылки на массив? Интересно было бы узнать, почему так. Я читал, что работа с ссылками в PHP довольно медленна. Но не думал, что потери растут с увеличением массива, на который передается ссылка. Казалось бы, на больших массивах ссылки должны выигрывать... Кто нить в курсе в чем фокус?

2topas

Я чутка пофиксил твою функцию и запустил их на сравнение.

PHP:

1.  
2. <?php
3. $iArraySize = 100;
4. for ($i = 0; $i < $iArraySize; $i++) $aInitial[] = rand(1, $iArraySize);
5.  
6. echo '<b>Initial array:</b><br />'.implode(', ', $aInitial).'<br /><br />';
7.  
8. $aFuncs = array('karatist', 'topas');
9. $aTimeResults = array();
10. $iCount = 100;
11. for ($i = 1; $i <= $iCount; $i++) {
12.     foreach ($aFuncs as $sFunc) {
13.         if ($i == 1) $aTimeResults[$sFunc] = 0;
14.         $aResult = $aInitial;
15.         $iStartTime = eval('return '.str_replace(' ', '+', microtime()).';');
16.         $aResult = $sFunc($aResult);
17.         $iEndTime = eval('return '.str_replace(' ', '+', microtime()).';');
18.         $aTimeResults[$sFunc] += $iEndTime - $iStartTime;
19.         if ($i == $iCount) {
20.             echo "<b>$sFunc - {$aTimeResults[$sFunc]} sec</b><br />";
21.             echo implode(', ', $aResult).'<br /><br />';
22.         }
23.     }
24. }
25.  
26. function karatist($arr, $direction = 1){
27.     $size = count($arr);
28.     for ($i = 0; $i < $size; $i++) {
29.         $min = $arr[$i];
30.         $key = $i;
31.         for ($j = $i+1; $j < $size; $j++) {
32.             if ($arr[$j] < $min == $direction) {
33.                 $key = $j;
34.                 $min = $arr[$j];
35.             }
36.         }
37.         $arr[$key] = $arr[$i];
38.         $arr[$i] = $min;
39.     }
40.     return $arr;
41. }
42.  
43. function topas($arr){
44.     for ($i=1; $i < count($arr); $i++){  //Проходим все эл-ты массива
45.         if ($arr[$i-1] > $arr[$i]){      //Если текущий эл-т меньше предыдущего, то...
46.            $temp = $arr[$i-1];           //..."Меняем местами ".$arr[$i-1]." и ".$arr[$i]."
47.            $arr[$i-1] = $arr[$i];
48.            $arr[$i]   = $temp;
49.            // Fixed by Raa
50.            $i = $i > 2 ? $i - 2 : 0; //После перепозиционированния проверим текущий
51.                     //элемент еще один раз, но уже с новыми соседями.
52.         }
53.     }
54.     return $arr;
55. }
56.  
57. ?>
58.  

Результат:

Код (Text):

1.  
2. karatist - 0.935048341751 sec
3. topas - 1.92502808571 sec

Как видишь, topas, твоя функция работает в два раза медленнее, несмотря на то, что используемый тобою метод считается более быстрым. Так что, как я уже выссказывал свое мнение, твоя реализация алгоритма далеко не оптимальная. Я даже сказал бы излишняя. Не по кол-ву кода, а по кол-ву выполняемых кодом действий.

 

Ха-ха )

 

и самому стало смешно ну я и чудо!!

а кто-то говорил что блин зачем для изучения пхп изобретать колесо. тут пока алгоритм сортировки реализуешь столько тонкостей познаешь. истину глаголил Vladson вот здесь http://dkflbk.nm.ru/45c48cce2e2d7fbdea1afc51c7c6ad26/
что изучить пхп до конца не возможно.

вот тебе и подтверждение, глубокоуважаемый ALL, что если начинать сразу с изпользования супер пупер сложных библиотек - то в результате получиться продукт типа виндовс, вроде работает но чтобы объяснить что зачем - обратись в службу поддержки - и тебе скажут что ваша бага - это наша фича, или типа модное слово ByDesign. сорри, но это уже очередной оффтоп пошел.

 

(делая невинный вид) а чо такое?

а что такое бинарные деревья??? (нехилоулыбаясь)