Median Function in C Math Library?

Question

Esiste qualche funzione matematica nella libreria C per calcolare MEDIAN dei numeri "n"?

Answer 1

per ottenere la mediana è possibile ordinare la serie di numeri e prendere:

1) nel caso in cui il numero di elementi è strano - il numero in mezzo

2) nel caso in cui il numero di elementi è pari - la media di due numeri nel mezzo

Answer 2

Here you go.

Answer 3

No, non esiste alcuna funzione mediana nella libreria C standard.

Answer 4

No, non esiste tale funzione nella libreria C standard.

Tuttavia, è possibile implementare uno (o sicuramente trovare il codice online). Un algoritmo O (n) efficiente per trovare una mediana è chiamato "algoritmo di selezione" ed è correlato a quicksort. Leggi tutto su di esso here.

Answer 5

Per calcolare la mediana utilizzando la libreria C standard, utilizzare la funzione di libreria standard qsort() e quindi prendere l'elemento centrale. Se l'array è a e ha n elementi, quindi:

qsort(a, n, sizeof(a[0]), compare); 
return a[n/2]; 

Devi scrivere il proprio compare funzione che dipende dal tipo di un elemento di matrice. Per i dettagli consulta la pagina man per qsort o cerca nell'indice di Kernighan e Ritchie.

Answer 6

convenzionale Metodo: (non consigliato se si sta lavorando su di elaborazione delle immagini)

/* median through qsort example */ 
#include <stdio.h> 
#include <stdlib.h> 

#define ELEMENTS 6 

int values[] = { 40, 10, 100, 90, 20, 25 }; 

int compare (const void * a, const void * b) 
{ 
    return (*(int*)a - *(int*)b); 
} 

int main() 
{ 
    int n; 
    qsort (values, ELEMENTS, sizeof(int), compare); 
    for (n=0; n<ELEMENTS; n++) 
    { printf ("%d ",values[n]); } 
    printf ("median=%d ",values[ELEMENTS/2]); 
    return 0; 
} 

Tuttavia, sono due funzioni per calcolare mediana il modo più veloce senza ordinare la matrice dei candidati. Quanto segue è almeno il 600% più veloce rispetto ai metodi convenzionali per calcolare la mediana. Sfortunatamente non fanno parte di C standard Library o C++ STL.

metodi più veloci:

//===================== Method 1: ============================================= 
//Algorithm from N. Wirth’s book Algorithms + data structures = programs of 1976  

typedef int_fast16_t elem_type ; 

#ifndef ELEM_SWAP(a,b) 
#define ELEM_SWAP(a,b) { register elem_type t=(a);(a)=(b);(b)=t; } 

elem_type kth_smallest(elem_type a[], uint16_t n, uint16_t k) 
{ 
    uint64_t i,j,l,m ; 
    elem_type x ; 
    l=0 ; m=n-1 ; 
    while (l<m) { 
    x=a[k] ; 
    i=l ; 
    j=m ; 
    do { 
    while (a[i]<x) i++ ; 
    while (x<a[j]) j-- ; 
    if (i<=j) { 
    ELEM_SWAP(a[i],a[j]) ; 
    i++ ; j-- ; 
    } 
    } while (i<=j) ; 
    if (j<k) l=i ; 
    if (k<i) m=j ; 
    } 
    return a[k] ; 
} 

    #define wirth_median(a,n) kth_smallest(a,n,(((n)&1)?((n)/2):(((n)/2)-1))) 

//===================== Method 2: ============================================= 
//This is the faster median determination method. 
//Algorithm from Numerical recipes in C of 1992 

elem_type quick_select_median(elem_type arr[], uint16_t n) 
{ 
    uint16_t low, high ; 
    uint16_t median; 
    uint16_t middle, ll, hh; 
    low = 0 ; high = n-1 ; median = (low + high)/2; 
    for (;;) { 
    if (high <= low) /* One element only */ 
    return arr[median] ; 
    if (high == low + 1) { /* Two elements only */ 
    if (arr[low] > arr[high]) 
    ELEM_SWAP(arr[low], arr[high]) ; 
    return arr[median] ; 
    } 
    /* Find median of low, middle and high items; swap into position low */ 
    middle = (low + high)/2; 
    if (arr[middle] > arr[high]) 
    ELEM_SWAP(arr[middle], arr[high]) ; 
    if (arr[low] > arr[high]) 
    ELEM_SWAP(arr[low], arr[high]) ; 
    if (arr[middle] > arr[low]) 
    ELEM_SWAP(arr[middle], arr[low]) ; 
    /* Swap low item (now in position middle) into position (low+1) */ 
    ELEM_SWAP(arr[middle], arr[low+1]) ; 
    /* Nibble from each end towards middle, swapping items when stuck */ 
    ll = low + 1; 
    hh = high; 
    for (;;) { 
    do ll++; while (arr[low] > arr[ll]) ; 
    do hh--; while (arr[hh] > arr[low]) ; 
    if (hh < ll) 
    break; 
    ELEM_SWAP(arr[ll], arr[hh]) ; 
    } 
    /* Swap middle item (in position low) back into correct position */ 
    ELEM_SWAP(arr[low], arr[hh]) ; 
    /* Re-set active partition */ 
    if (hh <= median) 
    low = ll; 
    if (hh >= median) 
    high = hh - 1; 
    } 
    return arr[median] ; 
} 
#endif 

In C++ che rendono queste funzioni templated e se i numeri sono in aumento o in diminuzione (una direzione) per tali funzioni utilizzare int8_fast_t; int16_fast_t; int32_fast_t; int64_fast_t; uint8_fast_t; uint16_fast_t; tipi invece di tipi regolari [stdint.h] (ad esempio uint16_t; uint32_t, ecc.)

Answer 7

Che dire di std::nth_element? Se sto capendo correttamente la natura della mediana, questo ti darebbe uno per il numero dispari di elementi.