Algoritme apa yang digunakan pengurutan?

24

Saya perlu menambahkan satu bilangan bulat ke daftar yang sudah diurutkan, sehingga masuk di tempat yang tepat. Orang pertama saya kira-kira seperti itu

(sort (cons newelt list) #'<)

Namun, mengingat yang listsudah diurutkan, hanya satu penyisipan benar-benar diperlukan, yang berarti solusi ini bisa sangat tidak cocok tergantung pada algoritma yang digunakan oleh sort.

Jadi, algoritma apa yang sortdigunakan?

Akankah saya lebih baik melakukan sesuatu seperti yang berikut ini?

(let ((tail list))
  ;; The first element is never less-than
  (while (and tail (< newelt (cadr tail)))
    (setq tail (cdr tail)))
  (setcdr tail (cons newelt (cdr tail)))
  list)
elisp performance emacs-internals Malabarba
sumber
1
Saya akan menggunakan tumpukan biner (misalnya heap.el ), jika itu operasi yang sering dalam kode saya.
lunaryorn
Membiarkan Bmenjadi awal sudah diurutkan listdan Adan Cawalnya kosong daftar. Dibagi Bdua bagian B1, B2panjang mdan matau m+1dan m, bandingkan neweltdengan elemen pertama B2. Jika neweltyaitu ≥memperluas Ake kanan dengan B1dan mengganti Bdengan B2, lain memperluas Cke kiri dengan B2dan mengganti Bdengan B1. Setelah O(log n)langkah-langkah tersebut tidak ada yang tersisa B. Kemudian Aberisi hal-hal ≤ newelt, dan Citu > newelt, dan rangkaian menghasilkan daftar diurutkan diperpanjang. Permintaan maaf untuk bahasa yang tidak terlalu e-lispsuka.
jfbu

Jawaban:

26

Jika Anda memasang kode sumber Emacs, Anda dapat menemukan kode sumbernya sortdengan M-x find-function.

Di sana Anda dapat melihat bahwa sortmelakukan semacam penggabungan. Ia memeriksa panjang daftar, memecah daftar menjadi setengah, mengurutkan bagian "depan" dan "belakang" secara terpisah melalui rekursi, dan kemudian menggabungkan keduanya.

Adapun apakah implementasi Anda akan lebih cepat - ukurlah! Ini lebih efisien dalam teori (O (n) vs O (n log n)), tetapi sortmemiliki keuntungan karena ditulis dalam C, sehingga hasilnya mungkin berjalan baik. (Tentu saja, jangan lupa byte-compile fungsi Anda.)

legoscia
sumber
@Malabarba Sebagai catatan, pada skala berapa Anda mengujinya?
T. Verron
8
Diuji 1000 kali memasukkan angka acak ke daftar 1000 angka acak (semua pregenerated). Metode manual 6 kali lebih cepat.
Malabarba