String triant plus rapide avec un préfixe commun?

Je soupçonnerais que le temps de traitement que vous passez à essayer d'exploiter des préfixes communs sur l'ordre de 10 caractères par URL ne paie même pas lui-même lorsque vous envisagez la longueur moyenne des URL.

Essayez simplement un type complètement standard. Si ce n'est pas assez rapide, regardez la paralLement ou la distribution d'un type complètement standard. C'est une approche simple qui fonctionnera.

Si vous découvrez les valeurs minimales et maximales dans le vecteur avant de démarrer QuickSorting, vous connaissez toujours la plage de valeurs pour chaque appel à partition (), puisque la valeur de partition est soit au minimum ou au maximum (ou à moins près du minimum / maximum) de chaque sous-bande et le minimum de la partition contenant la partition et le maximum sont l'autre extrémité de chaque sous-bande.

Si le minimum et le maximum d'une sous-groupe partagent un préfixe commune, vous pouvez faire toutes les comparaisons de partition à partir de la position de caractères suivant le préfixe commune. Comme le progresse QuicksTort, les gammes deviennent plus petites et plus petites, de sorte que leurs préfixes communs devraient devenir plus longues et plus longues et les ignorer pour que les comparaisons économiseront de plus en plus de temps. Combien, je ne sais pas; Vous devriez comparer cela pour voir s'il aide réellement.

En tout état de cause, les frais généraux supplémentaires sont assez petits; On passe à travers le vecteur pour trouver la chaîne minimale et maximale, coûtant 1,5 comparaisons par chaîne (*), puis une seule vérification de chaque partition pour trouver le préfixe partagé maximum pour la partition; Le chèque est équivalent à une comparaison et peut commencer à partir du préfixe partagé maximal du préfixe contenant, de sorte qu'il n'est même pas une comparaison complète de chaînes.

• L'algorithme min / max: scannez le vecteur deux éléments à la fois. Pour chaque paire, comparez-les d'abord les uns avec les autres, puis comparez le plus petit avec le minimum de fonctionnement et le plus grand avec le maximum de fonctionnement. Résultat: trois comparaisons pour deux éléments ou 1,5 comparaisons par élément.

enfin, j'ai trouvé un Ternary Quick Trict Sort Strong> fonctionne bien. J'ai trouvé l'algorithme à www.larsson.dogma.net/qsufsort.c .

Voici mon implémentation modifiée, avec une interface similaire à STD :: Trier. Il est environ 40% plus rapide que STD :: Trier sur ma machine et ensemble de données. P>

#include <iterator>

template<class RandIt> static inline void multiway_qsort(RandIt beg, RandIt end, size_t depth = 0, size_t step_len = 6) {
    if(beg + 1 >= end) {
        return;
    }

    struct { /* implement bounded comparing */
        inline int operator() (
                const typename std::iterator_traits<RandIt>::value_type& a,
                const typename std::iterator_traits<RandIt>::value_type& b, size_t depth, size_t step_len) {

            for(size_t i = 0; i < step_len; i++) {
                if(a[depth + i] == b[depth + i] && a[depth + i] == 0) return 0;
                if(a[depth + i] <  b[depth + i]) return +1;
                if(a[depth + i] >  b[depth + i]) return -1;
            }
            return 0;
        }
    } bounded_cmp;

    RandIt i = beg;
    RandIt j = beg + std::distance(beg, end) / 2;
    RandIt k = end - 1;

    typename std::iterator_traits<RandIt>::value_type key = ( /* median of l,m,r */
            bounded_cmp(*i, *j, depth, step_len) > 0 ?
            (bounded_cmp(*i, *k, depth, step_len) > 0 ? (bounded_cmp(*j, *k, depth, step_len) > 0 ? *j : *k) : *i) :
            (bounded_cmp(*i, *k, depth, step_len) < 0 ? (bounded_cmp(*j, *k, depth, step_len) < 0 ? *j : *k) : *i));

    /* 3-way partition */
    for(j = i; j <= k; ++j) {
        switch(bounded_cmp(*j, key, depth, step_len)) {
            case +1: std::iter_swap(i, j); ++i;      break;
            case -1: std::iter_swap(k, j); --k; --j; break;
        }
    }
    ++k;

    if(beg + 1 < i) multiway_qsort(beg, i, depth, step_len); /* recursively sort [x > pivot] subset */
    if(end + 1 > k) multiway_qsort(k, end, depth, step_len); /* recursively sort [x < pivot] subset */

    /* recursively sort [x == pivot] subset with higher depth */
    if(i < k && (*i)[depth] != 0) {
        multiway_qsort(i, k, depth + step_len, step_len);
    }
    return;
}

Le document ingénierie parallèle chaîne tri a, de façon surprenante, les repères d'un grand nombre de monothread algorithmes sur un ensemble de données d'URL (voir page 29). La variante de Rantala de multitouche quicksort mise en cache est en avance; vous pouvez tester multikey_cache8 ce référentiel cité dans le papier.

Je l'ai testé l'ensemble de données dans ce document, et si elle est une indication que vous voyez à peine un peu d'entropie dans les premiers caractères dix et préfixes distinguer dans la gamme de 100 caractères. Faire 100 passes de tri radix débattront le cache avec peu d'avantages, par exemple le tri d'un million de moyens urls que vous cherchez ~ 20 bits distinctifs de chaque clé à un coût de défauts de cache ~ 100.

Alors qu'en général, sorte radix ne peut pas bien sur les longues chaînes, les optimisations qui Kärkkäinen et Rantala décrivent Ingénierie Radix Trier pour cordes suffisent pour l'ensemble de données d'URL. En particulier, ils lisent avant 8 caractères et les mettre en cache avec les pointeurs de chaîne; le tri sur ces valeurs mises en cache donne suffisamment d'entropie pour dépasser le problème cache-miss.

Pour les chaînes essayer certains des algorithmes basés sur LCP-dans ce dépôt; dans mon expérience l'ensemble de données d'URL est sur le point au point de rupture même entre sortes radix de type hautement optimisés et des algorithmes à base de LCP qui ne asymptotiquement mieux sur des chaînes plus longues.