fusion en place sans stockage externe

Question

Je veux fusionner deux tableaux avec des valeurs triées en un seul. Puisque les deux réseaux de sources sont stockées en tant que parties d'un grand réseau suivant, je me demande, si vous connaissez un moyen de les fusionner dans le grand stockage. Signification fusion enplace.

Toutes les méthodes que j'ai trouvé, besoin d'un peu de stockage externe. Ils nécessitent souvent des réseaux de temp sqrt (n). Y at-il un moyen efficace sans elle?

Je suis en utilisant C #. D'autres langues accueillent également. Merci à l'avance!

Answer 1

AFAIK, la fusion de deux ne fonctionne pas (même) triées tableaux inplace sans augmenter considérablement le nombre nécessaire de comparaisons et mouvements d'éléments. Voir: tri par fusion . Toutefois, des variantes existent bloquées, qui sont capables de trier une liste de longueur n en utilisant une longueur de tableaux temporaires sqrt (n) - que vous avez écrit - en gardant toujours le nombre d'opérations très bas .. Pas mal - mais aussi son pas « rien » et, évidemment, le mieux que vous pouvez obtenir.

Pour les situations pratiques et si vous pouvez vous le permettre, vous utilisez mieux un tableau temporaire pour fusionner vos listes.

Answer 2

Si les valeurs sont stockées en tant que parties d'un éventail plus large réussir, vous voulez juste pour trier le tableau, puis supprimer les valeurs consécutives qui sont égales.

void  SortAndDedupe(Array<T> a)
{
    // Do an efficient in-place sort
    a.Sort();
    // Now deduplicate
    int lwm = 0; // low water mark
    int hwm = 1; // High water mark
    while(hwm < a.length)
    {
        // If the lwm and hwm elements are the same, it is a duplicate entry.
        if(a[lwm] == a[hwm])
        {
            hwm++;
        }else{
            // Not a duplicate entry - move the lwm up
            // and copy down the hwm element over the gap.
            lwm++;
            if(lwm < hwm){
                a[lwm] = a[hwm];
            }
            hwm++;
        }
    }
    // New length is lwm
    // number of elements removed is (hwm-lwm-1)
}

Avant de conclure que ce sera trop lent, la mise en œuvre et le profil il. Cela devrait prendre environ dix minutes.

Modifier Cela peut bien sûr être amélioré en utilisant un autre type plutôt que le haut-tri, par exemple Quicksort, Heapsort ou smoothsort, selon la donne de meilleures performances dans la pratique. Notez que les questions d'architecture matérielle signifient que les comparaisons de performances pratiques peuvent très bien être très différents des résultats de grande analyse O.

Vraiment, vous devez le profil avec différents algorithmes de tri sur votre plate-forme matérielle / OS réelle.

Remarque:. Je ne cherche pas dans cette réponse à donner une réponse académique, je suis en train de donner une pratique, en supposant que vous essayez de résoudre un vrai problème

Answer 3

soins sur le stockage externe Dont. sqrt (n) ou encore plus ne devrait pas nuire à votre performance. Vous aurez juste à vous assurer, le stockage est mis en commun. Surtout pour les gros volumes de données. Surtout pour les fusionner en boucles. Dans le cas contraire, le GC est stressé et manger une grande partie de votre temps CPU / bande passante mémoire.