Funkcja najlepszego sortowania dla krótkich tablic

Question

Pracuję nad algorytmem, który manipuluje obrazami. Zasadniczo zaimplementuję dyfuzję (każdy piksel otrzyma medianę 8 otaczających pikseli + własną wartość).

co mogę zrobić, to stworzyć tablicę liczb całkowitych 9 z wartością, sortowania tablicy i uzyskać wartość mediany w tablicy [4].

ja nadal nie wiem, co używać do problemu, jaki jest najlepszy funkcja sortowania używać do stosunkowo małych tablic? Funkcja sortowania zostanie z grubsza nazwana x razy, gdzie x oznacza liczbę pikseli.

sortowanie przez kopcowanie wydaje się nieco overkill. Quicksort nie sprawdzi się tak dobrze. I nie chcę realizować naprawdę skomplikowanych rzeczy.

Co myślicie?

Answer 1

Jeśli wszystko czego potrzebujesz, to mediana, nie ma potrzeby sortowania w ogóle! (W przypadku długich tablic, patrz http://en.wikipedia.org/wiki/Selection_algorithm dla algorytmu O (n), oczywiście mówimy tu tylko o krótkich tablicach).

Dla mediany 9 liczb, trochę googling ujawnia artykuł Fast median search: an ANSI C implementation N. Devillard, co wskazuje na artykuł Realizacja filtry mediana w XC4000E FPGA przez JL Smith, który zapewnia tę intuicyjną „sieci” do sortowania dostać medianę użyciu 19 porównań:

Pod względem C:

typedef int T; 

void sort2(T* a, T* b); 
void sort3(T* a, T* b, T* c); 
T min3(T a, T b, T c); 
T max3(T a, T b, T c); 

T median9(T p1, T p2, T p3, T p4, T p5, T p6, T p7, T p8, T p9) 
{ 
    sort3(&p1, &p2, &p3); 
    sort3(&p4, &p5, &p6); 
    sort3(&p7, &p8, &p9); 

    p7 = max3(p1, p4, p7); 
    p3 = min3(p3, p6, p9); 

    sort3(&p2, &p5, &p8); 
    sort3(&p3, &p5, &p7); 

    return p5; 
} 

void sort2(T* a, T* b) 
{ 
    if (*a > *b) 
    { 
     T tmp = *b; 
     *b = *a; 
     *a = tmp; 
    } 
} 

void sort3(T* a, T* b, T* c) 
{ 
    sort2(b, c); 
    sort2(a, b); 
    sort2(b, c); 
} 

T min3(T a, T b, T c) 
{ 
    if (a < b) 
     return a < c ? a : c; 
    else 
     return b < c ? b : c; 
} 

T max3(T a, T b, T c) 
{ 
    if (a > b) 
     return a > c ? a : c; 
    else 
     return b > c ? b : c; 
} 

---

Edycja: this file zawiera kod dla uzyskania mediana z 3, 5, 6, 7, 9 i 25 cyfr.

#define PIX_SORT(a,b) { if ((a)>(b)) PIX_SWAP((a),(b)); } 
#define PIX_SWAP(a,b) { pixelvalue temp=(a);(a)=(b);(b)=temp; } 

/*---------------------------------------------------------------------------- 
    Function : opt_med9() 
    In  : pointer to an array of 9 pixelvalues 
    Out  : a pixelvalue 
    Job  : optimized search of the median of 9 pixelvalues 
    Notice : in theory, cannot go faster without assumptions on the 
       signal. 
       Formula from: 
       XILINX XCELL magazine, vol. 23 by John L. Smith 

       The input array is modified in the process 
       The result array is guaranteed to contain the median 
       value 
       in middle position, but other elements are NOT sorted. 
---------------------------------------------------------------------------*/ 

pixelvalue opt_med9(pixelvalue * p) 
{ 
    PIX_SORT(p[1], p[2]) ; PIX_SORT(p[4], p[5]) ; PIX_SORT(p[7], p[8]) ; 
    PIX_SORT(p[0], p[1]) ; PIX_SORT(p[3], p[4]) ; PIX_SORT(p[6], p[7]) ; 
    PIX_SORT(p[1], p[2]) ; PIX_SORT(p[4], p[5]) ; PIX_SORT(p[7], p[8]) ; 
    PIX_SORT(p[0], p[3]) ; PIX_SORT(p[5], p[8]) ; PIX_SORT(p[4], p[7]) ; 
    PIX_SORT(p[3], p[6]) ; PIX_SORT(p[1], p[4]) ; PIX_SORT(p[2], p[5]) ; 
    PIX_SORT(p[4], p[7]) ; PIX_SORT(p[4], p[2]) ; PIX_SORT(p[6], p[4]) ; 
    PIX_SORT(p[4], p[2]) ; return(p[4]) ; 
} 

Answer 2

Wiesz, że „standard” qsort biblioteki C jest zwykle dość zoptymalizowane? Często jest to quicksort + sortowanie z wstawkami dla małych pod-tablic (kiedy dzieli się bardzo dużo na macierz bazową). Na przykład: read the comments tej wersji pobranej z biblioteki gnu c

Answer 3

Teoretycznie rzecz biorąc, chcesz znaleźć medianę, która jest szczególnym przypadkiem selection problem. Można to zrobić w czasie liniowym.

Ale tak jest w teorii. Praktycznie użyłbym "algorytmu selekcji ogólnej opartego na partycjach" (wspomnianego w tym artykule). Średnio działa w czasie liniowym, a ponadto jest praktycznie prosty i szybki.

template <typename T> 
T* SubDivide(T* pB, T* pE) 
{ 
    ASSERT(pB < pE); 

    T* pPivot = --pE; 
    const T pivot = *pPivot; 

    while (pB < pE) 
    { 
     if (*pB > pivot) 
     { 
      --pE; 
      std::swap(*pB, *pE); 
     } else 
      ++pB; 
    } 

    std::swap(*pE, *pPivot); 
    return pE; 
} 

template <typename T> 
void SelectElement(T* pB, T* pE, size_t k) 
{ 
    ASSERT((pE > pB) && (k < unsigned(pE - pB))); 

    while (true) 
    { 
     T* pPivot = SubDivide(pB, pE); 
     size_t n = pPivot - pB; 

     if (n == k) 
      break; 

     if (n > k) 
      pE = pPivot; 
     else 
     { 
      pB = pPivot + 1; 
      k -= (n + 1); 
     } 
    } 
} 

// Usage example 
int pArr[9] = { /* fill with values*/ }; 

// Select the 4th element (which is a median) 
SelectElement(pArr, pArr + 9, 4); 

// pArr[4] now holds the median value