Médiane des médianes en Java

Je ne sais pas si vous avez encore besoin de résoudre ce problème, mais http://www.ics.uci.edu/~eppstein/161/960130.html a un algorithme:

select(L,k)
{
    if (L has 10 or fewer elements)
    {
        sort L
        return the element in the kth position
    }

    partition L into subsets S[i] of five elements each
        (there will be n/5 subsets total).

    for (i = 1 to n/5) do
        x[i] = select(S[i],3)

    M = select({x[i]}, n/10)

    partition L into L1<M, L2=M, L3>M
    if (k <= length(L1))
        return select(L1,k)
    else if (k > length(L1)+length(L2))
        return select(L3,k-length(L1)-length(L2))
    else return M
}

bonne chance!

la question posée pour Java, donc voici

import java.util.*;

public class MedianOfMedians {
    private MedianOfMedians() {

    }

    /**
     * Returns median of list in linear time.
     * 
     * @param list list to search, which may be reordered on return
     * @return median of array in linear time.
     */
    public static Comparable getMedian(ArrayList<Comparable> list) {
        int s = list.size();
        if (s < 1)
            throw new IllegalArgumentException();
        int pos = select(list, 0, s, s / 2);
        return list.get(pos);
    }

    /**
     * Returns position of k'th largest element of sub-list.
     * 
     * @param list list to search, whose sub-list may be shuffled before
     *            returning
     * @param lo first element of sub-list in list
     * @param hi just after last element of sub-list in list
     * @param k
     * @return position of k'th largest element of (possibly shuffled) sub-list.
     */
    public static int select(ArrayList<Comparable> list, int lo, int hi, int k) {
        if (lo >= hi || k < 0 || lo + k >= hi)
            throw new IllegalArgumentException();
        if (hi - lo < 10) {
            Collections.sort(list.subList(lo, hi));
            return lo + k;
        }
        int s = hi - lo;
        int np = s / 5; // Number of partitions
        for (int i = 0; i < np; i++) {
            // For each partition, move its median to front of our sublist
            int lo2 = lo + i * 5;
            int hi2 = (i + 1 == np) ? hi : (lo2 + 5);
            int pos = select(list, lo2, hi2, 2);
            Collections.swap(list, pos, lo + i);
        }

        // Partition medians were moved to front, so we can recurse without making another list.
        int pos = select(list, lo, lo + np, np / 2);

        // Re-partition list to [<pivot][pivot][>pivot]
        int m = triage(list, lo, hi, pos);
        int cmp = lo + k - m;
        if (cmp > 0)
            return select(list, m + 1, hi, k - (m - lo) - 1);
        else if (cmp < 0)
            return select(list, lo, m, k);
        return lo + k;
    }

    /**
     * Partition sub-list into 3 parts [<pivot][pivot][>pivot].
     * 
     * @param list
     * @param lo
     * @param hi
     * @param pos input position of pivot value
     * @return output position of pivot value
     */
    private static int triage(ArrayList<Comparable> list, int lo, int hi,
            int pos) {
        Comparable pivot = list.get(pos);
        int lo3 = lo;
        int hi3 = hi;
        while (lo3 < hi3) {
            Comparable e = list.get(lo3);
            int cmp = e.compareTo(pivot);
            if (cmp < 0)
                lo3++;
            else if (cmp > 0)
                Collections.swap(list, lo3, --hi3);
            else {
                while (hi3 > lo3 + 1) {
                    assert (list.get(lo3).compareTo(pivot) == 0);
                    e = list.get(--hi3);
                    cmp = e.compareTo(pivot);
                    if (cmp <= 0) {
                        if (lo3 + 1 == hi3) {
                            Collections.swap(list, lo3, lo3 + 1);
                            lo3++;
                            break;
                        }
                        Collections.swap(list, lo3, lo3 + 1);
                        assert (list.get(lo3 + 1).compareTo(pivot) == 0);
                        Collections.swap(list, lo3, hi3);
                        lo3++;
                        hi3++;
                    }
                }
                break;
            }
        }
        assert (list.get(lo3).compareTo(pivot) == 0);
        return lo3;
    }

}

voici un test unitaire pour vérifier qu'il fonctionne...

import java.util.*;

import junit.framework.TestCase;

public class MedianOfMedianTest extends TestCase {
    public void testMedianOfMedianTest() {
        Random r = new Random(1);
        int n = 87;
        for (int trial = 0; trial < 1000; trial++) {
            ArrayList list = new ArrayList();
            int[] a = new int[n];
            for (int i = 0; i < n; i++) {
                int v = r.nextInt(256);
                a[i] = v;
                list.add(v);
            }
            int m1 = (Integer)MedianOfMedians.getMedian(list);
            Arrays.sort(a);
            int m2 = a[n/2];
            assertEquals(m1, m2);
        }
    }
}

cependant, le code ci-dessus est trop lent pour une utilisation pratique.

Voici une façon plus simple d'obtenir le k'ème élément qui ne garantit pas la performance, mais est beaucoup plus rapide dans la pratique:

/**
 * Returns position of k'th largest element of sub-list.
 * 
 * @param list list to search, whose sub-list may be shuffled before
 *            returning
 * @param lo first element of sub-list in list
 * @param hi just after last element of sub-list in list
 * @param k
 * @return position of k'th largest element of (possibly shuffled) sub-list.
 */
static int select(double[] list, int lo, int hi, int k) {
    int n = hi - lo;
    if (n < 2)
        return lo;

    double pivot = list[lo + (k * 7919) % n]; // Pick a random pivot

    // Triage list to [<pivot][=pivot][>pivot]
    int nLess = 0, nSame = 0, nMore = 0;
    int lo3 = lo;
    int hi3 = hi;
    while (lo3 < hi3) {
        double e = list[lo3];
        int cmp = compare(e, pivot);
        if (cmp < 0) {
            nLess++;
            lo3++;
        } else if (cmp > 0) {
            swap(list, lo3, --hi3);
            if (nSame > 0)
                swap(list, hi3, hi3 + nSame);
            nMore++;
        } else {
            nSame++;
            swap(list, lo3, --hi3);
        }
    }
    assert (nSame > 0);
    assert (nLess + nSame + nMore == n);
    assert (list[lo + nLess] == pivot);
    assert (list[hi - nMore - 1] == pivot);
    if (k >= n - nMore)
        return select(list, hi - nMore, hi, k - nLess - nSame);
    else if (k < nLess)
        return select(list, lo, lo + nLess, k);
    return lo + k;
}

je suis d'accord avec la réponse/solution de Chip Uni. Je vais juste commenter la partie de tri et fournir quelques explications supplémentaires:

vous n'avez pas besoin d'algorithme de tri. L'algorithme est similaire à quicksort, avec la différence qu'une seule partition est résolu (gauche ou droite). Nous avons juste besoin de trouver un pivot optimal pour que les parties gauche et droite soient aussi égales que possible, ce qui signifierait N/2 + N/4 + N/8 ... = 2N itérations, et donc la complexité temporelle de O (N). Les algorithmes ci-dessus, appelé médiane des médianes, calcule la médiane des médianes de 5, qui s'avère pour donner la complexité linéaire du temps de l'algorithme.

cependant, l'algorithme de tri est utilisé lorsque la plage recherchée pour le nième élément le plus petit / le plus grand (que je suppose que vous mettez en œuvre avec cet algorithme) afin d'accélérer l'algorithme. Le tri d'Insertion est particulièrement rapide sur les petits tableaux jusqu'à 7 à 10 éléments.

Note D'application:

M = select({x[i]}, n/10)

signifie en fait prendre la médiane de tous les médianes des groupes à 5 éléments. Vous pouvez accomplir cela en créant un autre tableau de taille (n - 1)/5 + 1 et appeler le même algorithme de façon récursive pour trouver l'élément n/10-th (qui est la médiane du tableau nouvellement créé).

@android développeur :

for (i = 1 to n/5) do
    x[i] = select(S[i],3)

est vraiment

for (i = 1 to ceiling(n/5) do
    x[i] = select(S[i],3)

avec une fonction de plafond appropriée pour vos données(par exemple en java 2 doubles) Cela affecte également la médiane wrt en prenant simplement n / 10, mais nous trouvons plus proche de la moyenne qui se produit dans le tableau, pas la vraie moyenne. Une autre note est que S[i] peut avoir moins de 3 éléments, donc nous voulons trouver la médiane par rapport à la longueur; la passer dans select avec k=3 ne sera pas toujours travail.( par exemple, n =11, nous avons 3 sous-groupes 2 5 w, 1 w 1 élément)

je sais que c'est un poste très ancien et vous pourriez ne plus vous en souvenir. Mais je me demande si vous avez mesuré la durée de votre implémentation quand vous l'avez implémentée?

j'ai essayé cet algorithme et de le comparer avec l'approche simple en utilisant la méthode de tri java (tableaux.sort ()), puis sélectionne l'élément kth dans le tableau trié. Le résultat que j'ai reçu est que cet algorithme ne surpasse l'algorithme de tri java que lorsque la taille du tableau est d'environ cent mille éléments ou plus. Et c'est seulement environ 2 ou 3 fois plus rapide, ce qui n'est évidemment pas log(n) temps plus rapide.

avez-vous un commentaire à ce sujet?