fork download
copy 
  1. <?php
  2. /********** Generating array (because use of range() was to simple :)): *************/
  3.  
  4. function generateSortedArray($start = 300000, $elementsNum = 10000, $dev = 30){
  5. 	$arr = array();
  6. 	for($i = 1; $i <= $elementsNum; $i++){
  7. 		$rand = mt_rand(1, $dev);
  8. 		$start -= $rand;
  9. 		$arr[] = $start; 
  10. 	}
  11. 	return $arr;
  12. }
  13.  
  14. /********************** Four insert functions: **************************/
  15.  
  16. // for loop, and array copying
  17. function insert1(&$arr, $elem){
  18. 	if(empty($arr)){
  19. 		$arr[] = $elem;
  20. 		return true;
  21. 	}
  22. 	$c = count($arr);
  23. 	$lastIndex = $c - 1;
  24. 	$tmp = array();
  25. 	$inserted = false;
  26. 	for($i = 0; $i < $c; $i++){
  27. 		if(!$inserted && $arr[$i] <= $elem){
  28. 			$tmp[] = $elem;
  29. 			$inserted = true;
  30. 		}
  31. 		$tmp[] = $arr[$i];
  32. 		if($lastIndex == $i && !$inserted) $tmp[] = $elem;
  33. 	}
  34. 	$arr = $tmp;
  35. 	return true;
  36. }
  37.  
  38. // new element inserted at the end of array 
  39. // and moved up until correct place
  40. function insert2(&$arr, $elem){
  41. 	$c = count($arr);
  42. 	array_push($arr, $elem);
  43. 	for($i = $c; $i > 0; $i--){
  44. 		if($arr[$i - 1] >= $arr[$i]) break;
  45. 		$tmp = $arr[$i - 1];
  46. 		$arr[$i - 1] = $arr[$i];
  47. 		$arr[$i] = $tmp;
  48. 	}
  49. 	return true;
  50. }
  51.  
  52. // binary search for correct place + array_splice() to insert element
  53. function insert3(&$arr, $elem){
  54. 	$startIndex = 0;
  55. 	$stopIndex = count($arr) - 1;
  56. 	$middle = 0;
  57. 	while($startIndex < $stopIndex){
  58. 		$middle = ceil(($stopIndex + $startIndex) / 2);
  59. 		if($elem > $arr[$middle]){
  60. 			$stopIndex = $middle - 1;
  61. 		}else if($elem <= $arr[$middle]){
  62. 			$startIndex = $middle;
  63. 		}
  64. 	}
  65. 	$offset = $elem >= $arr[$startIndex] ? $startIndex : $startIndex + 1; 
  66. 	array_splice($arr, $offset, 0, array($elem));
  67. }
  68.  
  69. // for loop to find correct place + array_splice() to insert
  70. function insert4(&$arr, $elem){
  71. 	$c = count($arr);
  72. 	$inserted = false;
  73. 	for($i = 0; $i < $c; $i++){
  74. 		if($elem >= $arr[$i]){
  75. 			array_splice($arr, $i, 0, array($elem));
  76. 			$inserted = true;
  77. 			break;
  78. 		}
  79. 	}
  80. 	if(!$inserted) $arr[] = $elem;
  81. 	return true;
  82. }
  83.  
  84. /*********************** Speed tests: *************************/
  85.  
  86. // check if array is sorted descending
  87. function checkIfArrayCorrect($arr, $expectedCount = null){
  88. 	$c = count($arr);
  89. 	if(isset($expectedCount) && $c != $expectedCount) return false;
  90. 	$correct = true;
  91. 	for($i = 0; $i < $c - 1; $i++){
  92. 		if(!isset($arr[$i + 1]) || $arr[$i] < $arr[$i + 1]){
  93. 			$correct = false;
  94. 			break;
  95. 		}
  96. 	}
  97. 	return $correct;
  98. }
  99. // claculates microtimetime diff
  100. function timeDiff($startTime){
  101. 	$diff = microtime(true) - $startTime;
  102. 	return $diff;
  103. }
  104. // prints formatted execution time info
  105. function showTime($func, $time){
  106. 	printf("Execution time of %s(): %01.7f s\n", $func, $time);
  107. }
  108. // generated elements num
  109. $elementsNum = 10000;
  110. // generate starting point
  111. $start = 300000;
  112. // generated elements random range  1 - $dev
  113. $dev = 50;
  114.  
  115.  
  116. echo "Generating array with descending order, $elementsNum elements, begining from $start\n";
  117. $startTime = microtime(true);
  118. $arr = generateSortedArray($start, $elementsNum, $dev);
  119. showTime('generateSortedArray', timeDiff($startTime));
  120.  
  121. $step = 2;
  122. echo "Generating second array using range range(), $elementsNum elements, begining from $start, step $step\n";
  123. $startTime = microtime(true);
  124. $arr2 = range($start, $start - $elementsNum * $step, $step);
  125. showTime('range', timeDiff($startTime));
  126.  
  127. echo "Checking if array is correct\n";
  128. $startTime = microtime(true);
  129. $sorted = checkIfArrayCorrect($arr, $elementsNum);
  130. showTime('checkIfArrayCorrect', timeDiff($startTime));
  131.  
  132. if(!$sorted) die("Array is not in descending order!\n");
  133. echo "Array OK\n";
  134.  
  135. $toInsert = array();
  136.  
  137. // number of elements to insert from every range
  138. $randElementNum = 20;
  139.  
  140. // some ranges of elements to insert near begining, middle and end of generated array
  141. // start value => end value
  142. $ranges = array(
  143. 	300000 => 280000,
  144. 	160000 => 140000,
  145. 	30000 => 0,
  146. );
  147. foreach($ranges as $from => $to){
  148. 	$values = array();
  149. 	echo "Generating $randElementNum random elements from range [$from - $to] to insert\n";
  150. 	while(count($values) < $randElementNum){
  151. 		$values[mt_rand($from, $to)] = 1;
  152. 	}
  153. 	$toInsert = array_merge($toInsert, array_keys($values));
  154. }
  155. // some elements to insert on begining and end of array
  156. array_push($toInsert, 310000);
  157. array_push($toInsert, -1000);
  158.  
  159. echo "Generated elements: \n";
  160. for($i = 0; $i < count($toInsert); $i++){
  161. 	if($i > 0 && $i % 5 == 0) echo "\n";
  162. 	printf("%8d, ", $toInsert[$i]);
  163. 	if($i == count($toInsert) - 1) echo "\n";
  164. }
  165. // functions to test
  166. $toTest = array('insert1' => null, 'insert2' => null, 'insert3' => null, 'insert4' => null);
  167. foreach($toTest as $func => &$time){
  168. 	echo "\n\n================== Testing speed of $func() ======================\n\n";
  169. 	$tmpArr = $arr;
  170. 	$startTime = microtime(true);
  171. 	for($i = 0; $i < count($toInsert); $i++){
  172. 		$func($tmpArr, $toInsert[$i]);
  173. 	}
  174. 	$time = timeDiff($startTime, 'checkIfArraySorted');
  175. 	showTime($func, $time);
  176. 	echo "Checking if after using $func() array is still correct: \n";
  177. 	if(!checkIfArrayCorrect($tmpArr, count($arr) + count($toInsert))){
  178. 		echo "Array INCORRECT!\n\n";
  179. 	}else{
  180. 		echo "Array OK!\n\n";
  181. 	}
  182. 	echo "Few elements from begining of array:\n";
  183. 	print_r(array_slice($tmpArr, 0, 5));
  184.  
  185. 	echo "Few elements from end of array:\n";
  186. 	print_r(array_slice($tmpArr, -5));
  187.  
  188. 	//echo "\n================== Finished testing $func() ======================\n\n";
  189. }
  190. echo "\n\n================== Functions time summary  ======================\n\n";
  191. print_r($toTest);
Success #stdin #stdout 1.41s 13112KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Generating array with descending order, 10000 elements, begining from 300000
Execution time of generateSortedArray(): 0.0086179 s
Generating second array using range range(), 10000 elements, begining from 300000, step 2
Execution time of range(): 0.0028510 s
Checking if array is correct
Execution time of checkIfArrayCorrect(): 0.0055759 s
Array OK
Generating 20 random elements from range [300000 - 280000] to insert
Generating 20 random elements from range [160000 - 140000] to insert
Generating 20 random elements from range [30000 - 0] to insert
Generated elements: 
  290255,   294911,   293677,   286876,   280342, 
  287995,   293735,   292697,   299842,   284768, 
  282965,   287219,   297657,   294414,   297306, 
  281756,   288477,   281002,   285585,   283227, 
  147570,   142458,   155661,   141752,   141173, 
  153437,   155050,   141765,   147127,   156783, 
  150198,   147377,   154378,   159260,   153550, 
  145251,   148831,   140505,   157355,   150214, 
    8833,      676,    23598,     4809,     5777, 
   16089,     5530,    17560,    13849,      622, 
   23912,    29811,    23176,    13363,    25908, 
     318,    17577,    22735,    23453,    19592, 
  310000,    -1000, 


================== Testing speed of insert1() ======================

Execution time of insert1(): 0.6082120 s
Checking if after using insert1() array is still correct: 
Array OK!

Few elements from begining of array:
Array
(
    [0] => 310000
    [1] => 299985
    [2] => 299975
    [3] => 299972
    [4] => 299924
)
Few elements from end of array:
Array
(
    [0] => 4809
    [1] => 676
    [2] => 622
    [3] => 318
    [4] => -1000
)


================== Testing speed of insert2() ======================

Execution time of insert2(): 0.2938130 s
Checking if after using insert2() array is still correct: 
Array OK!

Few elements from begining of array:
Array
(
    [0] => 310000
    [1] => 299985
    [2] => 299975
    [3] => 299972
    [4] => 299924
)
Few elements from end of array:
Array
(
    [0] => 4809
    [1] => 676
    [2] => 622
    [3] => 318
    [4] => -1000
)


================== Testing speed of insert3() ======================

Execution time of insert3(): 0.1914899 s
Checking if after using insert3() array is still correct: 
Array OK!

Few elements from begining of array:
Array
(
    [0] => 310000
    [1] => 299985
    [2] => 299975
    [3] => 299972
    [4] => 299924
)
Few elements from end of array:
Array
(
    [0] => 4809
    [1] => 676
    [2] => 622
    [3] => 318
    [4] => -1000
)


================== Testing speed of insert4() ======================

Execution time of insert4(): 0.2639391 s
Checking if after using insert4() array is still correct: 
Array OK!

Few elements from begining of array:
Array
(
    [0] => 310000
    [1] => 299985
    [2] => 299975
    [3] => 299972
    [4] => 299924
)
Few elements from end of array:
Array
(
    [0] => 4809
    [1] => 676
    [2] => 622
    [3] => 318
    [4] => -1000
)


================== Functions time summary  ======================

Array
(
    [insert1] => 0.608211994171
    [insert2] => 0.293812990189
    [insert3] => 0.191489934921
    [insert4] => 0.263939142227
)
https://ideone.com/1xQ3T
language:
PHP (php 7.3.5)
created:
12 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!