ftx_cleartel_test

[Christian Kruse]

Hallo Camping_RIDER,

Aber nur dann, wenn O(log n) wirklich zutrifft und nicht durch Overhead des Arrayzugriffs zunichte gemacht wird.

Der wird bei grösseren Datenmengen immer irrelevanter. Je nachdem, wie aufwendig ein Array-Zugriff ist verschiebt sich das nach hinten, aber früher oder später kann eine Komplexität O(n) mit O(log n) nicht mehr mithalten. Einfacher Test:

<?php

$data = [];
$no_elements = 10000000;
$test_runs = 1000;

for($i = 0; $i < $no_elements; ++$i) {
  $data[] = $i;
}

function bsearch($elem, $array) {
  $upper = sizeof($array) - 1;
  $lower = 0;

  while($upper >= $lower) {
    $pos = floor(($upper + $lower) / 2);

    if ($array[$pos] < $elem) {
      $lower = $pos + 1;
    }
    elseif($array[$pos] > $elem) {
      $upper = $pos - 1;
    }
    else {
      return true; // element found
    }
  }

  // nothing found
  return false;
}

function linear_search($elem, $array) {
  $len = sizeof($array);

  foreach($array as $element) {
    if($element == $elem) {
      return true;
    }
  }

  return false;
}

echo "test data generated, beginning with searching...\n";

# first test binary search
$start = microtime(true);

for($i = 0; $i < $test_runs; ++$i) {
  bsearch(rand(0, $no_elements - 1), $data);
}

$end = microtime(true);

echo "bsearch: $test_runs test runs: ", $end - $start, "ms\n";


# now lets test linear search
$start = microtime(true);

for($i = 0; $i < $test_runs; ++$i) {
  linear_search(rand(0, $no_elements - 1), $data);
}

$end = microtime(true);

echo "linear search: $test_runs test runs: ", $end - $start, "ms\n";

# eof

Allerdings treten solche Unterschiede halt erst bei ausreichend grossen Datenmengen auf. 5k Daten ist nicht viel, deshalb siehst du da nichts ;-) bei 10 Mio Daten allerdings macht das schon einen Unterschied. Output meines Scripts:

test data generated, beginning with searching...
bsearch: 1000 test runs: 0.0059850215911865ms
linear search: 1000 test runs: 157.40451312065ms

Falls dich sowas interessiert: solche Grundsätze lernt man in der Vorlesung Algorithmen und Datenstrukturen 1 (soweit ich weiss studierst du ja gerade Mathematik?). Das ist es auch, was Dedlfix mit „YAGNI“ meinte.

LG,
CK

EDIT: ich muss eins nochmal klarstellen:

Aber nur dann, wenn O(log n) wirklich zutrifft und nicht durch Overhead des Arrayzugriffs zunichte gemacht wird.

Der Aufwand für einen Array-Zugriff ist, unabhängig von den Kosten, konstant. Die Komplexität für das binary search ist also weiterhin O(log n), auch wenn die Kosten für einen Arrayzugriff grösser würden.

EDIT 2: huch, falsche File gepasted. Jetzt ist es der richtige Source.