fork download
copy 
  1. <?php
  2. /********** Generating sorted structure (array / SplMaxHeap): *************/
  3.  
  4. function generateSorted($start = 300000, $elementsNum = 10000, $dev = 30, $heap = false){
  5. 	$sorted = $heap ? new SplMaxHeap() : array();
  6. 	for($i = 1; $i <= $elementsNum; $i++){
  7. 		$rand = mt_rand(1, $dev);
  8. 		$start -= $rand;
  9. 		if(!$heap){
  10. 			$sorted[] = $start;
  11. 		}else{
  12. 			$sorted->insert($start); 
  13. 		}
  14. 	}
  15. 	return $sorted;
  16. }
  17.  
  18. /********************** Four insert functions: **************************/
  19.  
  20. // for loop, and array copying
  21. function insert1(&$arr, $elem){
  22. 	if(empty($arr)){
  23. 		$arr[] = $elem;
  24. 		return true;
  25. 	}
  26. 	$c = count($arr);
  27. 	$lastIndex = $c - 1;
  28. 	$tmp = array();
  29. 	$inserted = false;
  30. 	for($i = 0; $i < $c; $i++){
  31. 		if(!$inserted && $arr[$i] <= $elem){
  32. 			$tmp[] = $elem;
  33. 			$inserted = true;
  34. 		}
  35. 		$tmp[] = $arr[$i];
  36. 		if($lastIndex == $i && !$inserted) $tmp[] = $elem;
  37. 	}
  38. 	$arr = $tmp;
  39. 	return true;
  40. }
  41.  
  42. // new element inserted at the end of array 
  43. // and moved up until correct place
  44. function insert2(&$arr, $elem){
  45. 	$c = count($arr);
  46. 	array_push($arr, $elem);
  47. 	for($i = $c; $i > 0; $i--){
  48. 		if($arr[$i - 1] >= $arr[$i]) break;
  49. 		$tmp = $arr[$i - 1];
  50. 		$arr[$i - 1] = $arr[$i];
  51. 		$arr[$i] = $tmp;
  52. 	}
  53. 	return true;
  54. }
  55.  
  56. // binary search for correct place + array_splice() to insert element
  57. function insert3(&$arr, $elem){
  58. 	$startIndex = 0;
  59. 	$stopIndex = count($arr) - 1;
  60. 	$middle = 0;
  61. 	while($startIndex < $stopIndex){
  62. 		$middle = ceil(($stopIndex + $startIndex) / 2);
  63. 		if($elem > $arr[$middle]){
  64. 			$stopIndex = $middle - 1;
  65. 		}else if($elem <= $arr[$middle]){
  66. 			$startIndex = $middle;
  67. 		}
  68. 	}
  69. 	$offset = $elem >= $arr[$startIndex] ? $startIndex : $startIndex + 1; 
  70. 	array_splice($arr, $offset, 0, array($elem));
  71. }
  72.  
  73. // for loop to find correct place + array_splice() to insert
  74. function insert4(&$arr, $elem){
  75. 	$c = count($arr);
  76. 	$inserted = false;
  77. 	for($i = 0; $i < $c; $i++){
  78. 		if($elem >= $arr[$i]){
  79. 			array_splice($arr, $i, 0, array($elem));
  80. 			$inserted = true;
  81. 			break;
  82. 		}
  83. 	}
  84. 	if(!$inserted) $arr[] = $elem;
  85. 	return true;
  86. }
  87.  
  88. /*********************** Speed tests: *************************/
  89.  
  90. // check if array is sorted descending
  91. function checkIfArrayCorrect($arr, $expectedCount = null){
  92. 	$c = count($arr);
  93. 	if(isset($expectedCount) && $c != $expectedCount) return false;
  94. 	$correct = true;
  95. 	for($i = 0; $i < $c - 1; $i++){
  96. 		if(!isset($arr[$i + 1]) || $arr[$i] < $arr[$i + 1]){
  97. 			$correct = false;
  98. 			break;
  99. 		}
  100. 	}
  101. 	return $correct;
  102. }
  103. // claculates microtimetime diff
  104. function timeDiff($startTime){
  105. 	$diff = microtime(true) - $startTime;
  106. 	return $diff;
  107. }
  108. // prints formatted execution time info
  109. function showTime($func, $time){
  110. 	printf("Execution time of %s(): %f s\n", $func, $time);
  111. }
  112. // generated elements num
  113. $elementsNum = 10000;
  114. // generate starting point
  115. $start = 300000;
  116. // generated elements random range  1 - $dev
  117. $dev = 50;
  118.  
  119.  
  120. echo "Generating array with descending order, $elementsNum elements, begining from $start\n";
  121. $startTime = microtime(true);
  122. $arr = generateSorted($start, $elementsNum, $dev);
  123. showTime('generateSorted', timeDiff($startTime));
  124.  
  125. $step = 2;
  126. echo "Generating second array using range range(), $elementsNum elements, begining from $start, step $step\n";
  127. $startTime = microtime(true);
  128. $arr2 = range($start, $start - $elementsNum * $step, $step);
  129. showTime('range', timeDiff($startTime));
  130.  
  131. echo "Generating SplMaxHeap, $elementsNum elements, begining from $start\n";
  132. $startTime = microtime(true);
  133. $heap = generateSorted($start, $elementsNum, $dev, true);
  134. showTime('SplMaxHeap', timeDiff($startTime));
  135.  
  136. echo "Checking if array is correct\n";
  137. $startTime = microtime(true);
  138. $sorted = checkIfArrayCorrect($arr, $elementsNum);
  139. showTime('checkIfArrayCorrect', timeDiff($startTime));
  140.  
  141. if(!$sorted) die("Array is not in descending order!\n");
  142. echo "Array OK\n";
  143.  
  144. $toInsert = array();
  145.  
  146. // number of elements to insert from every range
  147. $randElementNum = 20;
  148.  
  149. // some ranges of elements to insert near begining, middle and end of generated array
  150. // start value => end value
  151. $ranges = array(
  152. 	300000 => 280000,
  153. 	160000 => 140000,
  154. 	30000 => 0,
  155. );
  156. foreach($ranges as $from => $to){
  157. 	$values = array();
  158. 	echo "Generating $randElementNum random elements from range [$from - $to] to insert\n";
  159. 	while(count($values) < $randElementNum){
  160. 		$values[mt_rand($from, $to)] = 1;
  161. 	}
  162. 	$toInsert = array_merge($toInsert, array_keys($values));
  163. }
  164. // some elements to insert on begining and end of array
  165. array_push($toInsert, 310000);
  166. array_push($toInsert, -1000);
  167.  
  168. echo "Generated elements: \n";
  169. for($i = 0; $i < count($toInsert); $i++){
  170. 	if($i > 0 && $i % 5 == 0) echo "\n";
  171. 	printf("%8d, ", $toInsert[$i]);
  172. 	if($i == count($toInsert) - 1) echo "\n";
  173. }
  174. // functions to test
  175. $toTest = array('insert1' => null, 'insert2' => null, 'insert3' => null, 'insert4' => null);
  176. foreach($toTest as $func => &$time){
  177. 	echo "\n\n================== Testing speed of $func() ======================\n\n";
  178. 	$tmpArr = $arr;
  179. 	$startTime = microtime(true);
  180. 	for($i = 0; $i < count($toInsert); $i++){
  181. 		$func($tmpArr, $toInsert[$i]);
  182. 	}
  183. 	$time = timeDiff($startTime);
  184. 	showTime($func, $time);
  185. 	echo "Checking if after using $func() array is still correct: \n";
  186. 	if(!checkIfArrayCorrect($tmpArr, count($arr) + count($toInsert))){
  187. 		echo "Array INCORRECT!\n\n";
  188. 	}else{
  189. 		echo "Array OK!\n\n";
  190. 	}
  191. 	//echo "Few elements from begining of array:\n";
  192. 	//print_r(array_slice($tmpArr, 0, 5));
  193.  
  194. 	//echo "Few elements from end of array:\n";
  195. 	//print_r(array_slice($tmpArr, -5));
  196.  
  197. 	//echo "\n================== Finished testing $func() ======================\n\n";
  198. }
  199.  
  200. echo "\n\n================== Testing speed of SplMaxHeap::insert() ======================\n\n";
  201. $startTime = microtime(true);
  202. for($i = 0; $i < count($toInsert); $i++){
  203. 	$heap->insert($toInsert[$i]);
  204. }
  205. $time = timeDiff($startTime);
  206. showTime('SplMaxHeap::insert', $time);
  207. $toTest['SplMaxHeap::insert'] = $time;
  208. echo "\n\n================== Functions time summary  ======================\n\n";
  209. foreach($toTest as $func => $time){
  210. 	printf("%18s() => %.10f\n", $func, $time);
  211. }
Runtime error #stdin #stdout 0.03s 13112KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Generating array with descending order, 10000 elements, begining from 300000
Execution time of generateSorted(): 0.008960 s
Generating second array using range range(), 10000 elements, begining from 300000, step 2
Execution time of range(): 0.002125 s
Generating SplMaxHeap, 10000 elements, begining from 300000

Fatal error: Class 'SplMaxHeap' not found in /home/sTMdwR/prog.php on line 5
https://ideone.com/vfX98
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!