sortowanie, parsowanie :: 4programmers.net

0

Witam, mam np. takie dane
Jasiu 12
Wacek 22
Misiek 13
Zapisałem je w tablicy:
uzytkownik[1][0]=Jasiu
uzytkownik[1][1]=12
uzytkownik[2][0]=Wacek
uzytkownik[2][1]=22
uzytkownik[2][0]=Misiek
uzytkownik[2][1]=13

W jaki sposób posortować ją według tych liczb?
Próbowałem funkcją multisort ale kompletnie mi to nie idzie.

Drugie moje pytanie dotyczy parsowania, jak dołączyć tą bibliotę, funkcję? (file_get_html)
Przyznam, że utknąłem tutaj na początku bo nie umie jej podłączyć i wywala mi błąd
Fatal error: Call to undefined function file_get_html()

0

Drugie moje pytanie dotyczy parsowania, jak dołączyć tą bibliotę, funkcję? (file_get_html)

No zapewne należy ją pobrać (http://sourceforge.net/projects/simplehtmldom/files/) i dołączyć za pomocą include :|

0

ok, fakt, walnąłem literówkę i nic się nie działo więc myślałem, że to jakoś inaczej się robi, wielkie dzięki.
A co do pierwszego to jakieś sugestie?

0

No najprościej to chyba po swojemu napisać np.sortowanie bąbelkowe i posortować to.

0

aha, no myślałem że jakąś fcją gotową, ale fakt, napisać własną pewnie będzie szybciej zwłaszcza że tam nie będzie dużo danych

0

Patryk27 napisał(a):

No najprościej to chyba po swojemu napisać np.sortowanie bąbelkowe i posortować to.

PHP ma pełno funkcji budowanych a Ty chcesz ręcznie pisać sortowanie, na dodatek niewydajne :D

edit:

Proszę bardzo:

<?php
	$uzytkownik=Array();
	$uzytkownik[1][0]="Jasiu";
	$uzytkownik[1][1]=22;
	$uzytkownik[2][0]="Wacek";
	$uzytkownik[2][1]=21;
	$uzytkownik[3][0]="Misiek";
	$uzytkownik[3][1]=16;
	$uzytkownik[4][0]="Kasia";
	$uzytkownik[4][1]=11;
	
	usort($uzytkownik, function($a, $b){return ($a[1] == $b[1]) ? 0 : ($a[1] < $b[1]) ? -1 : 1;});
	print_r($uzytkownik)
?>

Funkcja podana do usort'a definiuje sposób sortowania elementów tablicy.

0

@Spine porównaj sobie wydajność:

<?php
function quicksort( $array )
{
 $cur = 1;
 $stack[1]['l'] = 0;
 $stack[1]['r'] = count($array)-1;
 
 do 
 {
  $l = $stack[$cur]['l'];
  $r = $stack[$cur]['r'];
  $cur--;
 
  do
  {
   $i = $l;
   $j = $r;
   $tmp = $array[(int)( ($l+$r)/2 )][1];
 
   // partion the array in two parts.
   // left from $tmp are with smaller values,
   // right from $tmp are with bigger ones
   do
   {
    while( $array[$i][1] < $tmp )
     $i++;
 
    while( $tmp < $array[$j][1] ) 
     $j--;
 
    // swap elements from the two sides 
    if( $i <= $j )
    {
     $w = $array[$i];
     $array[$i] = $array[$j];
     $array[$j] = $w;
 
     $i++;
     $j--;
    }
 
   }while( $i <= $j );
 
 
   if( $i < $r )
   {
    $cur++;
    $stack[$cur]['l'] = $i;
    $stack[$cur]['r'] = $r;
   }
   $r = $j;
 
  }while( $l < $r );
 
 }while( $cur != 0 );
 
 return $array;
}

function microtime_float()
{
    list($usec, $sec) = explode(" ", microtime());
    return ((float)$usec + (float)$sec);
}

function set(&$uzytkownik)
{
    $uzytkownik[0][0] = "Jasiu";
	$uzytkownik[0][1] = 22;
	$uzytkownik[1][0] = "Wacek";
	$uzytkownik[1][1] = 21;
	$uzytkownik[2][0] = "Misiek";
	$uzytkownik[2][1] = 16;
	$uzytkownik[3][0] = "Kasia";
	$uzytkownik[3][1] = 11;
}

$time = microtime_float();
for ($i = 0; $i<50000; $i++)
{
	set($uzytkownik);
	usort($uzytkownik, function($a, $b){return ($a[1] == $b[1]) ? 0 : ($a[1] < $b[1]) ? -1 : 1;});
}
$time = microtime_float()-$time;
echo "usort: ".$time."<br>";

$time = microtime_float();
for ($i = 0; $i<50000; $i++)
{
	set($uzytkownik);
	$uzytkownik = quicksort($uzytkownik);
}
$time = microtime_float()-$time;
echo "quicksort: ".$time."<br>";
?>

U mnie wyświetla:

usort: 7.8763520717621
quicksort: 2.9220938682556

Pisanie własnych funkcji (pomimo bogatej biblioteki standardowej PHP) ma sens.

Edit: algorytm wzięty ze strony http://www.algorithmist.com/index.php/Quicksort_non-recursive.php i przystosowany do tego kodu.
Edit2: wygląda na to, że usort korzysta z wielu rdzeni, aby posortować przekazaną tablicę, podczas gdy moja funkcja do sortowania korzysta tylko z jednego, przez co usort jest szybsze w przypadku procesorów wielordzeniowych.

0

U mnie na kompie Twój przykład pokazuje:

usort: 0.16182208061218
quicksort: 0.29244804382324

Linux Mint, PHP 5.3.6-13ubuntu3.8 with Suhosin-Patch (cli) (built: Jun 13 2012 1819)

Kiedy w usort wyciągnę funkcję przed pętlę to osiągam wynik:
usort: 0.14249086380005

Kod:

<?php
	function microtime_float()
	{
		list($usec, $sec) = explode(" ", microtime());
		return ((float)$usec + (float)$sec);
	}
	function set(&$uzytkownik)
	{
		$uzytkownik[0][0] = "Jasiu";
		$uzytkownik[0][1] = 22;
		$uzytkownik[1][0] = "Wacek";
		$uzytkownik[1][1] = 21;
		$uzytkownik[2][0] = "Misiek";
		$uzytkownik[2][1] = 16;
		$uzytkownik[3][0] = "Kasia";
		$uzytkownik[3][1] = 11;
	}
	
	$sort_function = function($a, $b){return ($a[1] == $b[1]) ? 0 : ($a[1] < $b[1]) ? -1 : 1;};
	$time = microtime_float();
	for ($i = 0; $i<50000; $i++) {
		set($uzytkownik);
		usort($uzytkownik, $sort_function);
	}
	$time = microtime_float()-$time;
	echo "usort: ".$time;
?>

Coś słabego kompa masz, albo Ci się przecinek przesunął :D

Edit:

PHP 5.4.4-4~oneiric+1 (cli) (built: Aug 6 2012 1338)
Copyright (c) 1997-2012 The PHP Group
Zend Engine v2.4.0, Copyright (c) 1998-2012 Zend Technologies

Mój usort:
0.11031198501587

Twój kod:

usort: 0.1178719997406
quicksort: 0.2293701171875

Edit (Większy zbiór):

usort: 0.99025988578796
quicksort: 0.90684819221497

Dorzucę jeszcze przy okazji funkcję sorted Pythona:

from datetime import datetime

def set():
	uzytkownik=[]
	uzytkownik.append(("Jasiu",22,))
	uzytkownik.append(("Wacek",21,))
	uzytkownik.append(("Misiek",16,))
	uzytkownik.append(("Kasia",11,))
	return uzytkownik

d1=datetime.now()
for i in xrange(0,50000):
	uzytkownik=set()
	osoby=sorted(uzytkownik, key=lambda a: a[1]) 
d=datetime.now()-d1

print d

Dla małego zbioru:

Python 2.7
0:00:00.099229

Python 3.2
0:00:00.096701

PyPy

pypy --version
Python 2.7.2 (1.9+dfsg-1~~ubuntu11.10.1~~ppa1, Jun 21 2012, 1129)
[PyPy 1.9.0 with GCC 4.6.1])

0:00:00.063299

Dla dużego zbioru:

Python 2.7:
0:00:00.271632

Python 3.2:
0:00:00.247024

PyPy:
0:00:00.226309

Prostsze, szybsze i przyjemniejsze, a ludzie dalej przy PHP siedzą :D

2

Jaja se robicie? Benchmarkujecie sortowanie tablicy 4x2, czy mi się przywidziało? Walczycie o jakieś pierdyliardowe części sekundy, to tak jakby doliczyć sobie do wacka 30mm i oczekiwać wyraźnej poprawy doznań...

@Patryk27, @Spine: Praca domowa na dziś, zrobić porządny benchmark z losowo generowanymi zbiorami i to taki, żeby środowisko testowe bujało się przynajmniej kilka sekund i wyciągnąć sensowne wnioski dotyczące plusów i minusów każdego z algorytmów wynikające z ich różnej złożoności.

1

@Spine, jak już tym Pythonem trollujesz to pisz chociaż jak człowiek, operator.itemgetter zamiast lambdy. Przyrost wydajności gwarantowany.

[dopisano odnośnie komentarza]
@Spine,przewaga wydajności itemgettera jest powszechnie znanym faktem wśród profesjonalnych pythonistów. http://ideone.com/L5V8t i http://ideone.com/BQBpn - nawet kilkukrotne wrzucenie tego samego kodu daje podobne proporcje, wynika to z faktu, że itemgetter, attrgetter itd. są akcesorami zaimplementowanymi w C, pozbawionymi narzutu wynikającego z interpretowania bytekodu.

[dopisano]
Robienie benchmarku, który zamyka się w milisekundach uważam za śmieszny, pracujesz w końcu w systemie wielozadaniowym.

0

Zgodnie z tym, co powiedział @Demonical Monk, zmodyfikowałem kod:
http://pastebin.com/A9WrE9j2

Wynik na Ideone dla 5000 testów, tablica 200 na 2 elementy: http://ideone.com/sR1um

usort: 7.0912258625-1.24990940094=
5.84131646156

quicksort: 4.40364909172-1.24990940094=
3.15373969078

Wynik u mnie dla 5000 testów, tablica 200 na 2 elementy (Intel Core 2 Duo, PHP 5.4.6):

usort: 81.998184919357-2.3150444030762=
79.683140516281

quicksort: 7.9174199104309-2.3150444030762=
5.6023755073547

Różnice są - jak widać - całkiem spore.
Prosiłbym o sprawdzenie kodu, czy nie popełniłem jakiegoś błędu przy obliczeniach oraz sprawdzenie kodu u Was (oczywiście zmieniając także rozmiary tablicy i liczbę elementów; ja mam słaby komputer, więc nie mam zbyt dużego pola popisu ;)).

Edit: ta odejmowana wartość to szacowany czas wypełniania tablicy funkcją set.

0

usort: 3.0660419464111-3.5476684570312=
-0.48162651062012

quicksort: 1.6420059204102-3.5476684570312=
-1.9056625366211

Kodu nie sprawdzałem :D

sortowanie, parsowanie

Patryk27 napisał(a):

1 użytkowników online, w tym zalogowanych: 0, gości: 1

Praca dla programistów

Forum dyskusyjne

Sprawy administracyjne

O nas

Skontaktuj się z nami