Matematické Fórum

PeterSheldon

Chtěl bych se Vás zeptat, jak byste implementovali a optimalizovali algoritmus pro quicksort.. V PHP je velká sada již zavedených funkcí - uveďme nejzákladnější funkci sort. Když jsem si napsal sám vlastní Quicksort (poměrně čistý kod) tak přesto pro velká pole je o cca 0,2 sekundy pomalejší než funkce sort. U velkých polí obsahující až někollik milionu hodnot je rozdíl v rámci 1,5 vteřiny. Chtěl bych se zeptat jestli hlavní faktor může být ten, že funkce sort je v PHP napsána přímo v C, nebo i také tím, že se nejedná o čistý Quicksort z jejich strany. V KSP si pamatuji, se psalo, že čistý Quicksort se pro funkce řazení až tak nepoužívá (viz. v knihovně .NET - řazení pole), ale převážně se objevuje "hybrid" mezi Quicksortem a jiným algoritmem, který se spustí až tehdy kdy je výhodnější ho použít než Quicksort, protože Qsort je výhodný jen pro velmi velká pole.

Napadá Vás jak Qsort napsat efektivně (tj. lépe než v kuchařkách volně dostupných na netu?)

Lumikodlak · 04. 12. 2010 15:47

Ten rozdil napriklad 1,5 vteriny to je treba rozdil mezi 0,2 a 1,7 (coz je hodne), a nebo treba jako mezi 10 a 11,5 (coz je malo)?

Muj osobni tip je, ze hlavni problem je v tom, ze PHP je pomale (Co jsem videl na internetu srovnani tak asi 10 krat az 50 krat pomalejsi nez C. Mozna je to ale jinak).

Co se tyce Quicksortu, tak na Wikipedii se da neco najit - v te casti "Implementation issues".

Kazdopadne jestli se chces priblizit v rychlosti knihovni funkci, pravdepodobne to nebude jednoduche :-)
(Muzes zkusit upravit ten vyber pivota, a tridit ty male casti pomoci vkladani, ale porad bych se bal, ze tam bude problem PHP versus C)

PeterSheldon · 04. 12. 2010 16:01

↑ Lumikodlak:

je mi jasné, že to nemůže PHP překonat C, ale jde mi jen o optimalizaci. Je mi jasné, že je to jeden z hlavních důvodů , proč to jede tak pomalu , protože stejný kod jsem napsal v C a napsal vlatní benchmark, abych změřil čas a výsledný čas byl mnohem kratší než u PHP:)

Lumikodlak · 04. 12. 2010 16:17

Ok, chapu.

No pak tedy me napada predelat to tak, ze kdyz zbyde nejaka mala cast pro trideni, tak tu malou cast setridit vkladanim, misto quicksortem. (Jak jsem psal predtim, co je na te wikipedii, a vlastne jsi to psal i v tom puvodnim prispevku)
A take zkusit vybirat pivota jako prumer prvniho a posledniho cisla. Jsou i jine moznosti.

(Nebo muzes zkusit jine trideni nez quicksort, ale predpokladam, ze chces quicksort)

Zkousel jsi merit rozdil mezi tvym kodem v C a tou funkci sort, co je v PHP?

PeterSheldon

↑ Lumikodlak:

zkoušel a výsledky jsou více méně srovnatelné (odchylka je +- 0,003 vteřiny)

Lumikodlak · 06. 12. 2010 15:16

Zkousel jsi to pridat trideni vkladanim? Kdyz ten quicksort by vypadal takhle:
(Nasel jsem to jako priklad na internetu, jeste je tam ta procedura partition)

Code:

void quickSort(int a[], int p, int r) {
  if (p < r) {
    int q = partition(a, p, r);
    quickSort(a, p, q - 1);
    quickSort(a, q + 1, r);
  }
}

Tak to upravit podobne:

Code:

void quickSort(int a[], int p, int r) {
  if (p < r) {
    int q = partition(a, p, r);
    if (q - p < limit) insertionSort (a, p, q - 1);
    else  quickSort(a, p, q - 1);
    if (r - q < limit) insertionSort (a, q + 1, r);
    else quickSort(a, q + 1, r);
  }
}

Ten limit zvolit nejake cislo, asi najit ho experimentalne (otestovat to a vzit takove, pro ktere to bude nejrychlejsi, tipoval bych, ze ne vic jak 10). Jeste je treba napsat ten insertionSort.

PeterSheldon · 06. 12. 2010 19:07

↑ Lumikodlak:

díky insertion sort mám napsanej.. otázka zná , co dělá procedura partition?

Lumikodlak · 06. 12. 2010 20:24

Chtel jsem rychle najit nejaky kod quicksortu, a nasel ho na teto strance. Ta procedure partition vezme prvky od 'p' do 'r', a rozdeli je na dve casti podle pivota. V jedne z tech casti jsou cisla mensi a ve druhe vetsi nez pivot. To samote trideni vlastne provadi ta procedura partition, dal je tam pak to rekurzivni volani quicksortu pro ty rozdelene casti. Ten kod vypada takhle:

Code:

int partition(int a[], int p, int r) {
  int x = a[r];
  int j = p - 1;
  for (int i = p; i < r; i++) {

    if (x <= a[i]) {
      j = j + 1;
      int temp = a[j];
      a[j] = a[i];
      a[i] = temp;
    }
  }
  a[r] = a[j + 1];
  a[j + 1] = x;

  return (j + 1);
}

Jinak sam jsem zvedavy a doufam, ze to pomuze. Z optimalizaci na PHP nemam vubec zkusenosti :-) a urcite ta rychlost zavisi na jinych vecech nez v C.

pizet · 23. 01. 2011 14:11

Viem, že táto téma je stará. Ale ja som sa nechal inšpirovať a spravil som quicksort nejak takto a podla mojich časových testov som veľmi blízko funkcí sort() z hlavičky <algorithm>. Triedil som polia v rozsahu 500000 až 1000000 a triedené hodnoty boli náhodne vygenerované do súboru, následne z neho načítané, vytriedené a vypísané do v vzostupnom poradí naspäť do súboru.

Code:

void insertsort (int p[],int l,int r) {
    int j,x;
    for (int i=l+1;i<=r;i++) {
        x=p[i];j=i-1;
        while (j>l-1 && x<p[j]) {
            p[j+1]=p[j];j--;
        }
        p[j+1]=x;
    }
}

void quicksort(int p[],int l,int r) {
    int pivot = p[(l+r)/2],i=l,j=r;
    while (i<=j) {
        while (p[i]<pivot) i++;
        while (p[j]>pivot) j--;
        if (i<j) { int d=p[i];p[i]=p[j];p[j]=d;i++;j--; }
        else if (i==j) { i++;j--; }
    }
    if (j-l<10) insertsort(p,l,j);
    else quicksort(p,l,j);
    if (r-i<10) insertsort(p,i,r);
    else quicksort(p,i,r);
}

Matematické Fórum

#1 04. 12. 2010 12:57 — Editoval PeterSheldon (04. 12. 2010 13:12)

Quicksort

#2 04. 12. 2010 15:47

Re: Quicksort

#3 04. 12. 2010 16:01

Re: Quicksort

#4 04. 12. 2010 16:17

Re: Quicksort

#5 04. 12. 2010 16:29 — Editoval PeterSheldon (04. 12. 2010 16:29)

Re: Quicksort

#6 06. 12. 2010 15:16

Re: Quicksort

Code:

Code:

#7 06. 12. 2010 19:07

Re: Quicksort

#8 06. 12. 2010 20:24

Re: Quicksort

Code:

#9 23. 01. 2011 14:11

Re: Quicksort

Code:

Zápatí