ftx_cleartel_test
bearbeitet von Christian KruseHallo 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
<?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);
for($i = 0; $i < $len; ++$i) {
if($array[$i] == $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.
--
[CK kennt Wayne](http://ck.kennt-wayne.de/)
ftx_cleartel_test
bearbeitet von Christian KruseHallo 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 ein Aufwand O(n) mit O(log n) nicht mehr mithalten. Einfacher Test:
~~~php
<?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);
for($i = 0; $i < $len; ++$i) {
if($array[$i] == $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";
# no 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.
--
[CK kennt Wayne](http://ck.kennt-wayne.de/)
ftx_cleartel_test
bearbeitet von Christian KruseHallo 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 ein Aufwand O(n) mit O(log n) nicht mehr mithalten. Einfacher Test:
~~~php
<?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);
for($i = 0; $i < $len; ++$i) {
if($array[$i] == $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";
# no 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
--
[CK kennt Wayne](http://ck.kennt-wayne.de/)