Counting Sort - Implementierung und Zählen von Array-Zugriffen

Mat

Mat

Aktives Mitglied
Ich versuche im Moment, einige Sortier-Algorithmen aus dem Gedächtnis zu implementieren. Und am Ende vergleiche ich meine Lösung mit einer Version in einem Buch.

Bei CountingSort weicht die Buchlösung stark von meinem Ansatz ab. Ich habe aus Versehen etwas anderes implementiert:

Meine Version
Javascript: 
function sort(A, k) {
    let C = new Array(k + 1).fill(0); // Zählarray mit 0en initialisieren
    for (let i = 0; i < A.length; i++) {
        C[A[i]]++;
    }

    let pos = 0;
    for (let i = 0; i < C.length; i++) {
        while (C[i] > 0) {
            A[pos++] = i;
            C[i]--;
            arrayW += 2;
        }
    }
}

Buchversion (angepasst)
Javascript: 
function sort(A, B, k) {
    let C = new Array(k + 1);
    for (let i = 0; i <= k; i++) C[i] = 0;

    for (let j = 1; j < A.length; j++) C[A[j]]++;

    for (let i = 1; i <= k; i++) C[i] += C[i - 1];

    for (let j = A.length - 1; j >= 1; j--) {
        let item = A[j];
        let pos = C[item];
        B[pos] = item;
        C[item]--;
    }
}

Analyse
Ich wollte sehen, wie die so im Vergleich laufen und habe mir den Ablauf protokollieren lassen:
Sort'a Counting: 
A=[ 2, 5, 3, 0, 2, 3, 0, 3 ] Starting CountingSort - intuitive version: n=8, k=5
    0  1  2  3  4  5
C=[ 0, 0, 0, 0, 0, 0 ]    6 OPS (0xR + 6xW)    -- Done initialising
C=[ 2, 0, 2, 3, 0, 1 ]    22 OPS (8xR + 14xW)    -- Done counting
C=[ 1, 0, 2, 3, 0, 1 ]    25 OPS (9xR + 16xW)    -- 0 >> A[0] : [ 0, 5, 3, 0, 2, 3, 0, 3 ]
C=[ 0, 0, 2, 3, 0, 1 ]    28 OPS (10xR + 18xW)    -- 0 >> A[1] : [ 0, 0, 3, 0, 2, 3, 0, 3 ]
C=[ 0, 0, 1, 3, 0, 1 ]    31 OPS (11xR + 20xW)    -- 2 >> A[2] : [ 0, 0, 2, 0, 2, 3, 0, 3 ]
C=[ 0, 0, 0, 3, 0, 1 ]    34 OPS (12xR + 22xW)    -- 2 >> A[3] : [ 0, 0, 2, 2, 2, 3, 0, 3 ]
C=[ 0, 0, 0, 2, 0, 1 ]    37 OPS (13xR + 24xW)    -- 3 >> A[4] : [ 0, 0, 2, 2, 3, 3, 0, 3 ]
C=[ 0, 0, 0, 1, 0, 1 ]    40 OPS (14xR + 26xW)    -- 3 >> A[5] : [ 0, 0, 2, 2, 3, 3, 0, 3 ]
C=[ 0, 0, 0, 0, 0, 1 ]    43 OPS (15xR + 28xW)    -- 3 >> A[6] : [ 0, 0, 2, 2, 3, 3, 3, 3 ]
C=[ 0, 0, 0, 0, 0, 0 ]    46 OPS (16xR + 30xW)    -- 5 >> A[7] : [ 0, 0, 2, 2, 3, 3, 3, 5 ]
A=[ 0, 0, 2, 2, 3, 3, 3, 5 ]
Done sorting. n=8, k=5. ArrayOperations: 46 (16xR + 30xW)

Buch: 
A=[  , 2, 5, 3, 0, 2, 3, 0, 3 ] Starting CountingSort - book version: n=8, k=5
    0  1  2  3  4  5
C=[ 0, 0, 0, 0, 0, 0 ]    6 OPS (0xR + 6xW)    -- Done initialising
C=[ 2, 0, 2, 3, 0, 1 ]    22 OPS (8xR + 14xW)    -- Done counting
C=[ 2, 2, 4, 7, 7, 8 ]    32 OPS (13xR + 19xW)    -- Done adding neighbours
C=[ 2, 2, 4, 6, 7, 8 ]    36 OPS (15xR + 21xW)    -- 3 >> B[7] : [  ,  ,  ,  ,  ,  ,  , 3,   ]
C=[ 1, 2, 4, 6, 7, 8 ]    40 OPS (17xR + 23xW)    -- 0 >> B[2] : [  ,  , 0,  ,  ,  ,  , 3,   ]
C=[ 1, 2, 4, 5, 7, 8 ]    44 OPS (19xR + 25xW)    -- 3 >> B[6] : [  ,  , 0,  ,  ,  , 3, 3,   ]
C=[ 1, 2, 3, 5, 7, 8 ]    48 OPS (21xR + 27xW)    -- 2 >> B[4] : [  ,  , 0,  , 2,  , 3, 3,   ]
C=[ 0, 2, 3, 5, 7, 8 ]    52 OPS (23xR + 29xW)    -- 0 >> B[1] : [  , 0, 0,  , 2,  , 3, 3,   ]
C=[ 0, 2, 3, 4, 7, 8 ]    56 OPS (25xR + 31xW)    -- 3 >> B[5] : [  , 0, 0,  , 2, 3, 3, 3,   ]
C=[ 0, 2, 3, 4, 7, 7 ]    60 OPS (27xR + 33xW)    -- 5 >> B[8] : [  , 0, 0,  , 2, 3, 3, 3, 5 ]
C=[ 0, 2, 2, 4, 7, 7 ]    64 OPS (29xR + 35xW)    -- 2 >> B[3] : [  , 0, 0, 2, 2, 3, 3, 3, 5 ]
B=[  , 0, 0, 2, 2, 3, 3, 3, 5 ]
Done sorting. n=8, k=5. ArrayOperations: 64 (29xR + 35xW)

Fragen
  1. Gibts einen Namen dafür? Ich sehe auf den 1. Blick keinen Nachteil gegenüber der Version aus dem Buch und ich finde es leichter zu implementieren. Außerdem geht es in situ / inplace. Aber kann auch gut sein, dass ich aufgrund von Müdigkeit Tomaten auf den geistigen Augen hab.
  2. Habe ich die Lese- und Schreibzugriffe richtig gezählt? (siehe vollständigen Code ganz unten für Details)

Hinweis
Habe die Variablennamen meiner Version an das Buch angepasst, damit die Codes leichter zu vergleichen sind. Die Buchversion lässt index 0 in Input und Output frei, für Javascript habe ich das explizit mit null belegt. Die Version aus dem Buch hat in der Originalfassung mehr Lesezugriffe auf Arrays (wahrscheinlich um weniger Zeilen Code zu haben). Habe für einen aussagekräftigeren Vergleich bei wiederholten Lesezugriffen die Werte in Variablen zwischengespeichert. Meine Version und die Version aus dem Buch arbeiten nur mit einem einfachen Zahlenbeispiel. Mit einem Referenz-Array und Zuweisung von durchgängigen Integer-Werten könnte man damit aber alles stabil verarbeiten, nicht nur Zahlen. Also den Abstraktionsschritt kann man sich einfach dazu denken.

Vollständiger Quellcode:
Javascript: 
'use strict';

import DTHelper from '../datatypes/DTHelper.js';

export default class CountingSort {
    /**
     * @param A {Number[]|String[]}
     * @param k {Number}
     */
    static sortIntuitiveVerbose(A, k) {
        console.log(`A=${DTHelper.asPrettyString(A)}`);
        console.log(`Starting CountingSort - intuitive version: n=${A.length}, k=${k}`);

        let indices = new Array(k + 1);
        for (let i = 0; i <= k; i++) indices[i] = i;
        console.log(`  ${DTHelper.asPrettyString(indices, { brackets: false, comma: false })}`);

        let arrayR = 0;
        let arrayW = 0;
        let C = new Array(k + 1).fill(0);
        arrayW += C.length;
        console.log(
            `C=${DTHelper.asPrettyString(C)}\t${arrayR + arrayW} OPS (${arrayR}xR + ${arrayW}xW)\t-- Done initialising`
        );

        for (let i = 0; i < A.length; i++) {
            C[A[i]]++;
            arrayR++;
            arrayW++;
        }
        console.log(
            `C=${DTHelper.asPrettyString(C)}\t${arrayR + arrayW} OPS (${arrayR}xR + ${arrayW}xW)\t-- Done counting`
        );

        let pos = 0;
        for (let i = 0; i < C.length; i++) {
            while (C[i] > 0) {
                arrayR++;
                A[pos++] = i;
                arrayW++;
                C[i]--;
                arrayW++;
                console.log(
                    `C=${DTHelper.asPrettyString(C)}\t${
                        arrayR + arrayW
                    } OPS (${arrayR}xR + ${arrayW}xW)\t-- ${i} >> A[${pos - 1}] : ${DTHelper.asPrettyString(A)}`
                );
            }
        }

        console.log(`A=${DTHelper.asPrettyString(A)}`);
        console.log(
            `Done sorting. n=${A.length}, k=${k}. ArrayOperations: ${arrayR + arrayW} (${arrayR}xR + ${arrayW}xW)`
        );
    }

    /**
     * Original Version
     * @param A {Number[]}
     * @param B {Number[]}
     * @param k {Number}
     */
    static sortVerbose(A, B, k) {
        console.log(`A=${DTHelper.asPrettyString(A)}`);
        console.log(`Starting CountingSort - book version: n=${A.length - 1}, k=${k}`);

        let indices = new Array(k + 1);
        for (let i = 0; i <= k; i++) indices[i] = i;
        console.log(`  ${DTHelper.asPrettyString(indices, { brackets: false, comma: false })}`);

        let arrayR = 0;
        let arrayW = 0;
        let C = new Array(k + 1);
        for (let i = 0; i <= k; i++) {
            C[i] = 0;
            arrayW++;
        }
        console.log(
            `C=${DTHelper.asPrettyString(C)}\t${arrayR + arrayW} OPS (${arrayR}xR + ${arrayW}xW)\t-- Done initialising`
        );

        for (let j = 1; j < A.length; j++) {
            C[A[j]]++;
            arrayR++;
            arrayW++;
        }
        console.log(
            `C=${DTHelper.asPrettyString(C)}\t${arrayR + arrayW} OPS (${arrayR}xR + ${arrayW}xW)\t-- Done counting`
        );

        for (let i = 1; i <= k; i++) {
            C[i] += C[i - 1];
            arrayR++;
            arrayW++;
        }
        console.log(
            `C=${DTHelper.asPrettyString(C)}\t${
                arrayR + arrayW
            } OPS (${arrayR}xR + ${arrayW}xW)\t-- Done adding neighbours`
        );

        for (let j = A.length - 1; j >= 1; j--) {
            let item = A[j];
            arrayR++;
            let pos = C[item];
            arrayR++;
            B[pos] = item;
            arrayW++;
            C[item]--;
            arrayW++;
            console.log(
                `C=${DTHelper.asPrettyString(C)}\t${
                    arrayR + arrayW
                } OPS (${arrayR}xR + ${arrayW}xW)\t-- ${item} >> B[${pos}] : ${DTHelper.asPrettyString(B)}`
            );
        }

        console.log(`B=${DTHelper.asPrettyString(B)}`);
        console.log(
            `Done sorting. n=${B.length - 1}, k=${k}. ArrayOperations: ${arrayR + arrayW} (${arrayR}xR + ${arrayW}xW)`
        );
    }
}

Tests von oben: 
function testCountingSort() {
    let values = [2, 5, 3, 0, 2, 3, 0, 3];
    let sortedValues = Array.from(values);
    CountingSort.sortIntuitiveVerbose(sortedValues, 5);

    console.log();

    let bookValues = [null, 2, 5, 3, 0, 2, 3, 0, 3];
    let sortedBookValues = new Array(bookValues.length).fill(null);
    CountingSort.sortVerbose(bookValues, sortedBookValues, 5);
}
testCountingSort();
 
Zuletzt bearbeitet:
Deine Version hat einen entscheidenden "Fehler" (nicht wirklich Fehler ab "flaw")

for (let i = 0; i < C.length; i++) { und while (C[i] > 0) {

Du durchläufst damit einen Array mit der Länge des höchsten Wertes im Eingabe-Array.
Bei sehr großen Zahlen hast du eine viel längere Laufzeit. Dazu noch verschachtelt :)

Ich habe dein Script mal von allen console.log() usw bereinigt und mit folgendem Array die Zeit gemessen:
[99999999, 99999998, 99999997, 99999996, 99999995, 99999994, 99999993, 99999992]

Script: https://gist.github.com/asccc/7193912a174c403d8693240f4b56713a
Ergebnis:
Code: 
$ node cs-test.js
27645 // Deine Version
5764 // Buch Version
 
Die innere Schleife ist klein, solange es nicht viele Duplikate gibt.. aber jo, die äußere kann ein bisschen groß werden :eek: Ich hatte aus Faulheit einfach Max genommen (und war überrascht, dass die das im Buch auch so gemacht haben.. aber war wohl nur für das kleine Beispiel). Die Buch-Funktion kommt aber offensichtlich besser klar mit großen Max-Werten.

OK, also das heißt bei meiner Variante müsste man die Werte vorher am besten auf eine fortlaufende und lückenlose Integerrepräsentation mappen und könnte sie nicht unverändert 1:1 zählen. Und beim Mappen allein wäre schon jeglicher Vorteil gegenüber der anderen Version futsch, zumal man die Werte vorher als Set speichern müsste (oder vorab sortieren müsste, nur um sie dann sortieren zu können :poop: ).

Ich hab sogar noch eine andere Hilfsfunktion, die ich dafür hätte einsetzen könnte.. aber wenn man so oft über den Array iteriert, kann man auch gleich ein anderes Sortierverfahren nehmen:
Javascript: 
function getNumberOfDistinctElements(input) {
    let result = new Set();
    for (const item of input) {
        result.add(item);
    }
    return result.size;
}

Beide Verfahren scheinen sehr stark von der Eingabe abzuhängen. Da muss man wohl schon gezielt optimieren.
 
Zurück
Oben Unten