İki listeye katılmalı, bunları sıralamalı ve çoğaltmaları kaldırmalıyım. Bunu yapmanın daha iyi bir yolu var mı?

Question

İki tane ayrılmamış listelerim var ve sıralanan ve tüm öğelerin benzersiz olduğu başka bir liste üretmem gerekiyor.

Öğeler her iki listede de birden çok kez oluşabilir ve bunlar orijinal olarak sıralanmamıştır.

Benim işlevi şöyle görünür:

(defun merge-lists (list-a list-b sort-fn) 
    "Merges two lists of (x, y) coordinates sorting them and removing dupes" 
    (let ((prev nil)) 
     (remove-if 
      (lambda (point) 
       (let ((ret-val (equal point prev))) 
        (setf prev point) 
        ret-val)) 
      (sort 
       (merge 'list list-a list-b sort-fn) ;' 
       sort-fn)))) 

aynı başarmak için daha iyi bir yolu var mı?

Numune çağrı:

[CL]> (merge-lists '(9 8 4 8 9 7 2) '(1 7 3 9 2 6) #'>) 
    ==> (9 8 7 6 4 3 2 1) 

Answer 1

Mahallemiz dostu Lisp guru, remove-duplicates function işaret etti. Onlar, yinelenen-kaldırılmış birleştirilmiş ve aynı zamanda sıralanabilir, bunları birleştirme önce listeleri sıralanır ise

(defun merge-lists (list-a list-b sort-fn test-fn) 
    (sort (remove-duplicates (append list-a list-b) :test test-fn) sort-fn)) 

Answer 2

Ben ilk ayrı iki listeyi sıralamak ve sonra da yinelenenler üzerinde atlar bir fonksiyonu birleştirebilirsiniz düşünüyorum. Bu, her iki listeden bir daha az çapraz geçiş gerektirdiğinden biraz daha hızlı olmalıdır.

P.S .: Temel olarak her zaman en az bir sıralama ve birleştirme gereksinimi duyduğunuzdan çok daha hızlı yapılabilir. Belki her ikisini de tek bir fonksiyonda birleştirebilirsiniz, ama eğer (büyük) bir fark yaratmazsa şaşırmam.

Answer 3

Küme kullanmanız gerektiği gibi görünüyor.

Answer 4

:

O da şu pasajı sağladı. Sıralı VE çoğaltılmasızlarsa, birleştirme/sıralama/çoğalt-kaldır işlevi gerçekten önemsiz olur. Aslında, ekleme işlevinizi değiştirmek için çoğaltmaları denetleyen sıralı bir ekleme gerçekleştirmesi daha iyi olabilir. Sonra her zaman çiftleri içermeyen sıralanmış listeler var ve bunları birleştirmek önemsiz bir konudur.

Ardından, daha sonra yinelenen kopyaları ayırma/çıkarma pahasına hızlı bir ekleme işlevine sahip olmayı tercih edebilirsiniz.

Answer 5

Kaldırma-çoğaltmaları, sıralama çoğaltmaları öncesinde sıralama uygulanmışsa, çoğaltma işlevi daha iyi çalışmayabilir miydi?

Answer 6

Antti'nin belirttiği gibi, muhtemelen REMOVE-DUPLICATES ve SORT'tan yararlanmak isteyebilirsiniz, muhtemelen test işlevi için bir anahtar kelime (veya isteğe bağlı argüman) kullanmam gerekir: (birleştirme listeleri (liste-1 listesi) 2 çeşit-fn & anahtar (test # 'EQL)) ...) veya (defun birleştirme listeleri (liste-1 listesi-2 sort-fn & opsiyonel (test #' EQL) ...)

EQL yeterince iyi değil sürece

Bu şekilde, test fonksiyonunu belirtmek zorunda kalmazsınız, (test etmek için KALDIR-dUPLICATES kullandığı "bu kabul çiftleri ise").