Tentu saja, perbandingannya harus membandingkan performa dua fungsi quickSort() dan quickSortInPlace()........

Ah.. sekarang saya paham maksud Anda. Rupanya Anda tidak memahami apa yang harus dibandingkan dengan apa.... algoritma quick sort itu bukan berarti ada dua cara implementasi, yaitu quicksort dan in-place......

Sejak awal, yang saya persoalkan adalah bagian ketika quickSortGPT() dan quickSort() pada kode di atas (keduanya adalah kode yang dihasilkan GPT), yang sudah menyertakan penggabungan Array bawaan, ditulis lalu disediakan kepada pengguna AI.

Lalu, membagikan hasil yang menunjukkan perbedaan output lebih dari 2 kali sampai 3–4 kali, tetapi kemudian mengatakan rasanya tidak sampai 2 kali itu maksudnya apa?

Bahkan sekarang pun, kalau harus bekerja bersama developer usia 40–50-an, kadang bikin frustrasi karena ada yang ingin mengembangkan dengan cara-cara yang dipakai puluhan tahun lalu, duh. Secara pribadi, menurut saya masyarakat akan lebih sehat kalau, seperti di Jepang, anak muda bisa masuk ke pekerjaan tetap alih-alih kerja paruh waktu atau kontrak, sementara lansia lebih banyak masuk ke kerja harian atau kerja paruh waktu. Korea membagi pendapatan kerja dengan struktur piramida terbalik, jadi makin lama yang terjadi hanya semakin parahnya praktik menarik tangga agar orang lain tak bisa naik.

> Platform perawat memeriksa status kredit perawat melalui broker data, dan semakin banyak utangnya, semakin rendah upah yang ditawarkan.

Bagaimana data ini bisa disediakan?

Saya sudah menjalankannya langsung, dan memang cenderung sedikit lebih lambat, tetapi sepertinya tidak sampai 2 kali lipat.

function quickSortInPlace(arr, left = 0, right = arr.length - 1) {  
    if (left >= right) return;  
  
    const pivotIndex = partition(arr, left, right);  
    quickSortInPlace(arr, left, pivotIndex - 1);  
    quickSortInPlace(arr, pivotIndex + 1, right);  
}  
  
function partition(arr, left, right) {  
    const pivot = arr[right];  
    let i = left;  
  
    for (let j = left; j < right; j++) {  
        if (arr[j] < pivot) {  
            [arr[i], arr[j]] = [arr[j], arr[i]];  
            i++;  
        }  
    }  
  
    [arr[i], arr[right]] = [arr[right], arr[i]];  
    return i;  
}  
  
function quickSort(arr) {  
    if (arr.length <= 1) return arr;  
  
    const pivot = arr[arr.length - 1];  
    const left = [];  
    const right = [];  
  
    for (let i = 0; i < arr.length - 1; i++) {  
        if (arr[i] < pivot) {  
            left.push(arr[i]);  
        } else {  
            right.push(arr[i]);  
        }  
    }  
  
    return [...quickSort(left), pivot, ...quickSort(right)];  
}  
  
// =============  
  
function quickSortGPT(arr) {  
    if (!Array.isArray(arr)) {  
        throw new TypeError('quickSort expects an array');  
    }  
    if (arr.length <= 1) return [...arr];  
  
    const pivot = arr[Math.floor(arr.length / 2)];  
    const left = [];  
    const equal = [];  
    const right = [];  
  
    for (const el of arr) {  
        if (el < pivot) left.push(el);  
        else if (el > pivot) right.push(el);  
        else equal.push(el);  
    }  
  
    return [...quickSortGPT(left), ...equal, ...quickSortGPT(right)];  
}  
  
function quickSortInPlaceGPT(arr) {  
    if (!Array.isArray(arr)) {  
        throw new TypeError('quickSortInPlace expects an array');  
    }  
  
    const stack = [[0, arr.length - 1]];  
  
    while (stack.length) {  
        const [lo, hi] = stack.pop();  
        if (lo >= hi) continue;  
  
        const pivotIndex = partitionGPT(arr, lo, hi);  
  
        // Eliminasi tail-recursion: dorong partisi yang lebih besar lebih dulu  
        if (pivotIndex - 1 - lo > hi - (pivotIndex + 1)) {  
            stack.push([lo, pivotIndex - 1]);  
            stack.push([pivotIndex + 1, hi]);  
        } else {  
            stack.push([pivotIndex + 1, hi]);  
            stack.push([lo, pivotIndex - 1]);  
        }  
    }  
    return arr;  
}  
  
function medianOfThreeGPT(a, b, c) {  
    return (a - b) * (c - a) >= 0 ? a  
        : (b - a) * (c - b) >= 0 ? b  
            : c;  
}  
  
function partitionGPT(arr, lo, hi) {  
    const mid = lo + ((hi - lo) >> 1);  
    const pivotValue = medianOfThreeGPT(arr[lo], arr[mid], arr[hi]);  
  
    while (true) {  
        while (arr[lo] < pivotValue) lo++;  
        while (arr[hi] > pivotValue) hi--;  
  
        if (lo >= hi) return hi;  
  
        [arr[lo], arr[hi]] = [arr[hi], arr[lo]];  
        lo++;  
        hi--;  
    }  
}  
  
function testQuicksort(qs, qsp) {  
    const repeat = 100;  
    const arrLength = 100000;  
    const unsortedArray = new Array();  
    for (let i = 0; i < arrLength; i++)  
        unsortedArray.push(Math.round(Math.random() * arrLength));  
  
    let sorted = [];  
  
    const qb = performance.now();  
    for (let i = 0; i < repeat; i++)  
        sorted = qs(unsortedArray);  
    const qe = performance.now();  
  
    const rqb = performance.now();  
    for (let i = 0; i < repeat; i++) {  
        let copied = [...unsortedArray];  
        qsp(copied);  
    }  
    const rqe = performance.now();  
  
    // hingga 2 angka di belakang koma  
    const p1 = ((qe - qb) / repeat).toFixed(2);  
    const p2 = ((rqe - rqb) / repeat).toFixed(2);  
    
    console.log(`Quicksort: ${p1} ms, In-place: ${p2} ms`);  
}  
  
function main() {  
    const useGPT = process.argv.includes('--gpt');  
    console.log(`Using ${useGPT ? 'GPT' : 'geekNews'} quicksort implementation.`);  
    if (useGPT) {  
        testQuicksort(quickSortGPT, quickSortInPlaceGPT);  
    } else {  
        testQuicksort(quickSort, quickSortInPlace);  
    }  
}  
  
main();  

===
node q.js
Using geekNews quicksort implementation.
Quicksort: 29.55 ms, In-place: 9.94 ms
node q.js
Using geekNews quicksort implementation.
Quicksort: 28.42 ms, In-place: 9.07 ms
node q.js
Using geekNews quicksort implementation.
Quicksort: 26.91 ms, In-place: 9.15 ms
node q.js --gpt
Using GPT quicksort implementation.
Quicksort: 28.73 ms, In-place: 9.22 ms
node q.js --gpt
Using GPT quicksort implementation.
Quicksort: 26.87 ms, In-place: 9.22 ms
node q.js --gpt
Using GPT quicksort implementation.
Quicksort: 27.97 ms, In-place: 9.30 ms
node --version
v22.14.0

bun q.js
Using geekNews quicksort implementation.
Quicksort: 32.05 ms, In-place: 17.39 ms
bun q.js
Using geekNews quicksort implementation.
Quicksort: 30.97 ms, In-place: 17.82 ms
bun q.js
Using geekNews quicksort implementation.
Quicksort: 29.73 ms, In-place: 16.14 ms
bun q.js --gpt
Using GPT quicksort implementation.
Quicksort: 30.61 ms, In-place: 12.63 ms
bun q.js --gpt
Using GPT quicksort implementation.
Quicksort: 31.09 ms, In-place: 12.76 ms
bun q.js --gpt
Using GPT quicksort implementation.
Quicksort: 33.24 ms, In-place: 12.75 ms
bun --version
1.2.14

deno q.js
Using geekNews quicksort implementation.
Quicksort: 32.30 ms, In-place: 6.79 ms
deno q.js
Using geekNews quicksort implementation.
Quicksort: 26.79 ms, In-place: 6.86 ms
deno q.js
Using geekNews quicksort implementation.
Quicksort: 26.09 ms, In-place: 6.85 ms
deno q.js --gpt
Using GPT quicksort implementation.
Quicksort: 27.18 ms, In-place: 7.92 ms
deno q.js --gpt
Using GPT quicksort implementation.
Quicksort: 25.34 ms, In-place: 8.12 ms
deno q.js --gpt
Using GPT quicksort implementation.
Quicksort: 25.39 ms, In-place: 8.09 ms
deno --version
deno 2.3.3 (stable, release, x86_64-pc-windows-msvc)
v8 13.7.152.6-rusty
typescript 5.8.3

....Eh?

Sebelum presentasi, ada pengenalan sponsor dari Google dan Facebook.

Sama seperti ungkapan "menutup kandang setelah sapi hilang" bukan berarti kita tidak perlu bersiap untuk masa depan,
menurut saya, "jangan menciptakan ulang roda" juga bukan berarti kita tidak perlu meluangkan waktu untuk memperoleh wawasan.
Jika bagian sebelum dan sesudahnya dipotong dari konteks situasi saat ungkapan seperti itu muncul, makna aslinya akan terdistorsi.

Saya rasa komoditas khas terbesar Amerika Serikat adalah dolar

Kalau harus mengulang berkali-kali untuk menyelesaikan masalah yang sama, akhirnya jadi melewati ukuran context window, dan saya sudah beberapa kali mengalami AI seperti jadi rusak saat itu. Jadi saya penasaran, dalam kasus seperti ini biasanya orang lain menanganinya bagaimana.

Kalau saya, kalau setelah dicoba berkali-kali masih bertingkah bodoh, saya ganti model lalu buka jendela prompt yang baru.

Ini pengalaman yang belum lama terjadi, tetapi baru-baru ini saya membuat roda saya sendiri yang sangat istimewa.
Membangun aplikasi 1000 halaman di Nuxt memakan waktu 7 menit,
tetapi setelah mengorbankan beberapa otomatisasi dan menulis ulang, saya berhasil memangkas waktu build menjadi 20 detik.

OSSU Open Source Society University - Belajar Computer Science secara otodidak

Sepertinya ini pernah diperkenalkan pada masa awal GeekNews. Selama itu, sudah cukup banyak hal yang ditambahkan.

Terima kasih atas jawabannya!

quickSortInPlace() kedua yang Anda lampirkan ini juga merupakan implementasi yang lambat.

Coba jalankan kode di bawah ini.

function quickSortInPlace(arr, left = 0, right = arr.length - 1) {
if (left >= right) return;

const pivotIndex = partition(arr, left, right);
quickSortInPlace(arr, left, pivotIndex - 1);
quickSortInPlace(arr, pivotIndex + 1, right);
}

function partition(arr, left, right) {
const pivot = arr[right];
let i = left;

for (let j = left; j < right; j++) {
if (arr[j] < pivot) {
[arr[i], arr[j]] = [arr[j], arr[i]];
i++;
}
}

[arr[i], arr[right]] = [arr[right], arr[i]];
return i;
}

function quickSort(arr) {
if (arr.length <= 1) return arr;

const pivot = arr[arr.length - 1];
const left = [];
const right = [];

for (let i = 0; i < arr.length - 1; i++) {
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}

return [...quickSort(left), pivot, ...quickSort(right)];
}

const repeat = 100;
const arrLength = 10000;
const unsortedArray = new Array<number>();
for(let i = 0; i < arrLength; i++)
unsortedArray.push(Math.round(Math.random() * arrLength));

let sorted: Array<number>;

const qb = performance.now();
for(let i = 0; i < repeat; i++)
sorted = quickSort(unsortedArray);
const qe = performance.now();

const rqb = performance.now();
for(let i = 0; i < repeat; i++) {
let copied = [...unsortedArray];
quickSortInPlace(copied);
}
const rqe = performance.now();

console.log(q: ${qe - qb} ::: rq: ${rqe - rqb});

Tulisan yang memberi kesan wawasan mendalam. Memang khas a16z.

Saya biasanya tidak terlalu sering menulis komentar, tetapi alasan saya meninggalkan komentar pada tulisan ini adalah karena saya sangat sependapat dengan pemikiran penulis. Yang penting bukanlah AI atau LLM, melainkan saya harus siap sebagai seorang developer dalam lingkungan apa pun yang datang.

Karena karakteristik sumber yang dipelajari LLM, ia terutama memberikan data yang berada di sekitar nilai rata-rata dari data online yang tersebar di seluruh dunia. (Sebelumnya, quicksort di js membuktikan hal ini.) Karena itu, biasanya saya banyak menggunakannya untuk menanyakan apakah dari sisi gagasan/desain ada penyimpangan dari sudut pandang yang umum dan sampai sejauh mana hal itu bisa dipahami, atau untuk hal-hal yang selama ini agak sulit ditentukan harus ditanyakan ke mana.

Saya kurang paham apa makna dari melanjutkan percakapan ini lebih jauh.

Kalau sejak awal maksudnya adalah bahwa kode yang dihasilkan AI bisa saja memiliki sejumlah risiko, jadi sebaiknya disaring dengan baik lalu dimanfaatkan secara tepat, rasanya Anda cukup menjelaskan bagian mana dari tulisan penulis yang menurut Anda menunjukkan pemikiran penulis yang bias. Bahkan di ringkasannya juga ada isi dengan makna serupa, yaitu bahwa AI dapat dengan cepat menyediakan kode scaffold/draf tanpa konteks, tetapi desain dan tuning yang utuh tetap menjadi tanggung jawab pengembang manusia.

Pada dasarnya, ini bisa dianggap sebagai kode yang sama sekali tidak memahami beban dalam pembuatan, pengelolaan, dan penggabungan collection. Dalam kasus C++, sekitar 10 tahun lalu saja sudah ada usulan/implementasi untuk Move Constructor, dan bersikap sangat sensitif terhadap beban yang terkait dengan penyalinan memori adalah hal yang paling mendasar. Quick sort, secara mekanisme, adalah algoritme yang dapat menetapkan index semua nilai, dan sebaiknya setiap field mendukung random access.

Bahkan tanpa optimasi yang terlalu maniak, hanya dengan menerapkan hal-hal di atas saja sudah menghasilkan perbedaan performa lebih dari 2x dibanding cara pada tautan yang Anda berikan.

return [...quickSort(left), ...equal, ...quickSort(right)];

Coba pikirkan baik-baik bagian kode ini.