Witam..
mam taki mało spotykany problem (google nie dał rady =/).. otóż tworzę sobie tabelkę różnych metod sortowania tablic (bąbelkowe, quick, wstawianie itd.) i chcę obliczyć czas posortowania rosnąco, losowo i malejąco dla próby 1k, 10k i 100k liczb. Wszystko wychodzi ładnie pięknie, tzn. skrypt dla każdej komórki tworzy odpowiednio dużą tablicę i odpowiednio ją wypełnia liczbami. Następnie sprawdzany jest microtime, dokonywane sortowanie i obliczana różnica microtime na końcu.

Wyniki są jednak nader dziwne, bo wg przedstawionych obliczeń tablice z 1k elementów sortują się o kilka ms dłużej niż tablice 10k (dalej, tj. porównując 10k i 100k jest odwrotnie, ale to akurat nic dziwnego, że większą tablicę sortuje dłużej).

Jedyny pomysł, jaki przychodzi mi na myśl to to, że PHP tworzy sobie cache interpretera (istnieje taki wbudowany w standardowy php? 0o), ale czuję, że ta opcja odpada, bo porównując liczby przy każdym odświeżeniu zwykle nie są identyczne.

Ostatnia rzecz (choć nie wydaje mi się, żeby miała tu znaczenie) - funkcje sortowania ładowane są z zewnętrznych plików (oddzieliłem logikę samego sortowania od tworzenia tablic testowych i obliczeń czasowych).

Skąd rodzi się moje pytanie - czy byłby ktoś w stanie wyjaśnić mi te dziwne anomalie w czasach sortowania tablic?

A moze poprostu źle mierzysz czas?

1. Pokaż swój kod.
2. Średnią z ilu sortowań wybierasz?

[PHP] pobierz, plaintext 
(...)
public function getTime() {
	$time = -microtime(true) *1000 *1000;
 
	$this->mySort($this->a);		// tabela jest pobierana do klasy wcześniej i znajduje się w zmiennej $a
						// natomiast funkcja mySort odpowiada za sortowanie w określony sposób
	$time += microtime(true) *1000 *1000;
	return number_format($time, 0, '.', '');
}
(...)
[PHP] pobierz, plaintext 

W ten sposób uzyskuję różnicę czasu sprzed i po sortowaniu w milisekundach. Sprawdzałem także różnice w mikrosekundach, bez formatowania liczby (myślałem, że to problem z zaokrąglaniem), ale ciągle występuje ten sam błąd - tablica z mniejszą ilością elementów (tak, count'owałem je, a nawet var_dumpowałem i pobieżnie przeglądałem ich ilość i wartości) sortowana jest wg powyższego skryptu wolniej niż jej odpowiednik o rząd, dwa rzędy większy..


1. Jak powyżej.. mogę wrzucić całość, ale ciut tego będzie - wszystko odbywa się przez ajax (wciskam przycisk i symetrycznie odpytuję serwer, wypełniając pola tabeli).. jednak odpytywanie bez tej technologii (wpisując po prostu w URL z GETem) daje takie same wyniki.
2. Być może to trochę naprowadzi na właściwy tor, ale walnąłem funkcję sortowania w pętli i zauważyłem, że mniejsze tablice sortuje szybciej. Tj. dla wbudowanego w php quicksorta 1000 pętli tablicy rosnącej wykonuje się 661ms (1k pól w tablicy), 651ms (10k), 442ms (100k).. 0o

Pokaż SSCCE, z którym przynajmniej u Ciebie występuje "błąd". Sam stworzyłem bardzo prosty test:

[PHP] pobierz, plaintext 
<?php
 
function randomArray($count) {
    $arr = array();
 
    for ($i = 0; $i < $count; $i++) {
        $arr[] = mt_rand();
    }
 
    return $arr;
}
 
$arr = randomArray(1000);
$time = -microtime(true) *1000 *1000;
sort($arr);
$time += microtime(true) *1000 *1000;
echo number_format($time, 0, '.', '') . PHP_EOL;
 
$arr = randomArray(10000);
$time = -microtime(true) *1000 *1000;
sort($arr);
$time += microtime(true) *1000 *1000;
echo number_format($time, 0, '.', '') . PHP_EOL;
 
$arr = randomArray(1000);
$start = microtime(true);
sort($arr);
$elapsedTime = microtime(true) - $start;
echo $elapsedTime . PHP_EOL;
 
$arr = randomArray(10000);
$start = microtime(true);
sort($arr);
$elapsedTime = microtime(true) - $start;
echo $elapsedTime . PHP_EOL;
[PHP] pobierz, plaintext 

Wyniki za każdym razem są "odpowiednie", tj. mniejsza tablica sortuje się odpowiednio szybciej (rząd wielkości).

No dobrze.. więc jak wspomniałem mój skrypt ładowany jest dynamicznie przez Ajax do tabelki. Ładuję go sychronicznie, przez co każde kolejne sortowanie nie zamula serwera i - przynajmniej mam nadzieję - eliminuję częściowo fałszowanie wyników. Sam skrypt myślę, że jest poprawny (a przynajmniej to nie tu tkwi problem), bo przy wysyłaniu GETem w URLu z palca wpisanych wartości wyniki są takie same.

Do skryptu wysyłam 3 zmienne: type, będący określeniem rodzaju sortowania (dla prostoty tutaj dodam tylko wbudowany qsort), sort, mówiący w jaki sposób będzie wstępnie posortowana tablica testowa (inc - rosnąco, rnd - losowo, dec - malejąco) oraz val, czyli ilość tysięcy pól w tablicy. Tak wygląda plik, który otrzymuje te dane (na samym dole przykład online):

[PHP] pobierz, plaintext 
	$type = htmlspecialchars($_GET['type']);
	$sort = htmlspecialchars($_GET['sort']);
	$val = (int)htmlspecialchars($_GET['val']);
 
	if ($val <= 0) die('err');	// dla sprawdzenia, czy aby na pewno będzie co liczyć w tabeli testowej
 
	$val *= 1000;
	$arr = array();
	$min = 0;
	$max = $val;
 
	switch($sort) {	// tworzymy odpowiednią tabelę testową
		case 'inc':
			for ($i=0; $i<$val; $i++)
				$arr[$i] = $i;
			break;
		case 'rnd':
			for ($i=0; $i<$val; $i++)
				$arr[$i] = mt_rand($min, $max);
			break;
		case 'dec':
			for ($i=$val-1; $i>=0; $i--)
				$arr[$i] = $i;
			break;
		default: die('err');
	}
	$file = 'sort/'.$type.'.php';
 
	if (file_exists($file)) {	// ładujemy plik ze skryptem do sortowania
		require_once($file);
		$sort = new SortTest($arr);
		die($sort->start().' ms');
	}
	else
		die('err');
[PHP] pobierz, plaintext 

Plik do sortowania znajduje się, jak pisałem, w osobnym pliku i wygląda następująco:

[PHP] pobierz, plaintext 
class SortTest {
	private $a = array();
 
	public function __constructor($array) {
		$this->a = $array;
	}
 
	public function start() {
		$time = -microtime(true) *1000 *1000;
 
		for ($i=0; $i<1000; $i++)	// pętla for, w celu 'uwypuklenia' dziwnych czasów wykonywania sortowań
			$this->mySort($this->a);
 
		$time += microtime(true) *1000 *1000;
		return number_format($time, 1, '.', '');	// formatujemy ms z jednym przecinkiem (sprawdzenie, czy nie ma błędu przy zaokrąglaniu przy mniejszych liczbach)
	}
 
	public function mySort($a) {
		sort($a);
	}
}
[PHP] pobierz, plaintext 

Po przepisaniu tego w przykład online wygląda tak: http://ideone.com/Z4tTUV (wyniki mogą być trochę zakłamane ze względu na to, że nie wiem jak wygląda środowisko na którym to jest uruchamiane, ale tego rodzaju rozrzut obliczeń mam właśnie u siebie)

for ($i=0; $i<1000; $i++) // pętla for, w celu 'uwypuklenia' dziwnych czasów wykonywania sortowań
$this->mySort($this->a);

Ta petla jest totalnie bezsensu, gdyz po pierwszym obrocie masz juz posortowaną tablicę i w kazdym kolejnym obrocie sortujesz posortowane juz dane.

Połowicznie masz rację.. tj. jest o tyle bez sensu, że tablica jest posortowana, ale wciąż trzeba przez nią przelecieć, żeby to sprawdzić =p
W przykładzie online (http://ideone.com/Z4tTUV) już poprawiłem tworząc tymczasową tablicę z testowej, tylko do obliczeń..

EDIT: przy tworzeniu tablic zobaczyłem także, że niepotrzebnie podaję indeks dla nowych elementów, szczególnie przy losowej tablicy ($arr[$i] = $i). Zmieniłem na pusha, żeby indeksy same się inkrementowały.

znajdź różnice

[PHP] pobierz, plaintext 
public function __constructor($array) {
[PHP] pobierz, plaintext 

[PHP] pobierz, plaintext 
public function __construct($array) {
[PHP] pobierz, plaintext 

Jak już napiszę książkę 'O tym jak literówka zmarnowała mi kilka dni życia' to przyślę Ci egzemplarz z podpisem -.-

Faktycznie to tutaj wkradł się błąd.. dzięki za wytknięcie go.. masakra.. chyba słusznie wrzuciłem to do przedszkola 0o

Chętnie przeczytam książkę Po śmierci będziesz sławny.