Facebook
From phpdev.tech, 6 Months ago, written in PHP.
Embed
Download Paste or View Raw
Hits: 111
  1. <?php
  2.  
  3. function linearSearch(array $haystack, $needle)
  4. {
  5.     $haystackSize = count($haystack);
  6.    
  7.     for ($i = 0; $i < $haystackSize; $i++) {
  8.         if ($haystack[$i] == $needle) {
  9.             return $i;
  10.         }
  11.     }
  12.    
  13.     return -1;
  14. }
  15.  
  16. function linearSearchWithSentinel(array $haystack, $needle)
  17. {
  18.     $haystack[] = $needle;
  19.    
  20.     for ($i = 0; ; $i++) {
  21.         if ($haystack[$i] == $needle) {
  22.             return $i == count($haystack) ? -1 : $i;
  23.         }
  24.     }
  25. }
  26.  
  27. function prepareHaystack(int $n)
  28. {
  29.     $haystack = [];
  30.     for ($i = 0; $i < $n; $i++) {
  31.         $haystack[] = random_int(1, $n * 10);
  32.     }
  33.    
  34.     return $haystack;
  35. }
  36.  
  37. $iterations = 1000;
  38. $linearSearchTime = 0.0;
  39. $linearSearchWithSentinelTime = 0.0;
  40.  
  41. for ($i = 0; $i < $iterations; $i++) {
  42.     $n = random_int(1, 100000);
  43.     $haystack = prepareHaystack($n);
  44.     $needle = random_int(1, $n);
  45.    
  46.     $time_start = microtime(true);
  47.     linearSearch($haystack, $needle);
  48.     $linearSearchTime += (microtime(true) - $time_start);
  49.    
  50.     $time_start = microtime(true);
  51.     linearSearchWithSentinel($haystack, $needle);
  52.     $linearSearchWithSentinelTime += (microtime(true) - $time_start);
  53. }
  54.  
  55. echo 'Linear search avg time : ' . round($linearSearchTime / $iterations, 6) . PHP_EOL;
  56. echo 'Linear search with sentinel avg time : ' . round($linearSearchWithSentinelTime / $iterations, 6) . PHP_EOL;
  57.  
  58.  

Replies to linear search comparasion rss

Title Name Language When
Re: linear search comparasion Abrupt Gorilla php 6 Months ago.