通過多個鍵對球拍中的結構列表進行排序

Question

我有list-of-cars，這是car類型的結構列表，其中包含字段「maker」，「model」和「year」。使用常規球拍sort功能，我可以通過一個鍵（例如「製造商」）進行排序。但是，我怎麼能通過製造商和型號進行排序，並在例子中列出一個等於輸出sort-by-maker-and-model的列表？

這不是一個學校的任務，我試圖做一個清晰的例子，比我需要處理的實際數據更枯燥。昂貴的汽車對我來說似乎不算太無聊。

享受我狡猾的例子！祝你今天愉快！

#lang racket/base 

(define-struct car (maker model year) #:transparent) 

(define list-of-cars (list (car "Ferrari" "250 Europa GT" "1954") 
          (car "Bugatti" "Type 2" "1900") 
          (car "Lamborghini" "Flying Star II" "1966") 
          (car "Bugatti" "Type 10" "1908") 
          (car "Ferrari" "166 Inter" "1949") 
          (car "Bugatti" "Type 5" "1903") 
          (car "Maserati" "A6 1500" "1946") 
          (car "Ferrari" "340 America" "1951") 
          (car "Maserati" "5000 GT" "1959") 
          (car "Maserati" "Quattroporte" "1963") 
          (car "Lamborghini" "Egoista" "2013"))) 

(define (sort-by-maker lst) 
    (sort lst 
     string<? 
     #:key car-maker)) 

(sort-by-maker list-of-cars) 
; => 
(list 
(car "Bugatti" "Type 2" "1900") 
(car "Bugatti" "Type 10" "1908") 
(car "Bugatti" "Type 5" "1903") 
(car "Ferrari" "250 Europa GT" "1954") 
(car "Ferrari" "166 Inter" "1949") 
(car "Ferrari" "340 America" "1951") 
(car "Lamborghini" "Flying Star II" "1966") 
(car "Lamborghini" "Egoista" "2013") 
(car "Maserati" "A6 1500" "1946") 
(car "Maserati" "5000 GT" "1959") 
(car "Maserati" "Quattroporte" "1963")) 

(define (sort-by-maker-and-model lst) 
    ; ??? 
    #f) 

(sort-by-maker-and-model list-of-cars) 
; => 
(list 
(car "Bugatti" "Type 2" "1900") 
(car "Bugatti" "Type 5" "1903") 
(car "Bugatti" "Type 10" "1908") 
(car "Ferrari" "166 Inter" "1949") 
(car "Ferrari" "250 Europa GT" "1954") 
(car "Ferrari" "340 America" "1951") 
(car "Lamborghini" "Egoista" "2013") 
(car "Lamborghini" "Flying Star II" "1966") 
(car "Maserati" "5000 GT" "1959") 
(car "Maserati" "A6 1500" "1946") 
(car "Maserati" "Quattroporte" "1963")) 

Answer 1

您需要創建自己的less-than?對比功能：

(define (sort-by-maker-and-model lst) 
    (sort lst 
     (lambda (e1 e2) 
      (or (string<? (car-maker e1) (car-maker e2)) 
       (and (string=? (car-maker e1) (car-maker e2)) 
        (string<? (car-model e1) (car-model e2))))))) 

或者，你可以只創建一個key過程，地連接了2場：

(define (sort-by-maker-and-model lst) 
    (sort lst 
     string<? 
     #:key (lambda (e) (string-append (car-maker e) " " (car-model e))))) 

這應該在這裏工作，但前者是更普遍的方法。任何方式：

> (sort-by-maker-and-model list-of-cars) 
(list 
(car "Bugatti" "Type 10" "1908") 
(car "Bugatti" "Type 2" "1900") 
(car "Bugatti" "Type 5" "1903") 
(car "Ferrari" "166 Inter" "1949") 
(car "Ferrari" "250 Europa GT" "1954") 
(car "Ferrari" "340 America" "1951") 
(car "Lamborghini" "Egoista" "2013") 
(car "Lamborghini" "Flying Star II" "1966") 
(car "Maserati" "5000 GT" "1959") 
(car "Maserati" "A6 1500" "1946") 
(car "Maserati" "Quattroporte" "1963")) 

Answer 2

球拍的sort是穩定，所以另一種替代方法是調用sort兩次。當然，這需要兩次通過，但根據您的目的，這可能沒有問題。 （請注意，string<?不會產生你在model列想要的結果，因爲"Type 10"排在最後第一個。）

(define (sort-by-maker-and-model lst) 
    (sort 
    (sort lst string<? #:key car-model) 
    string<? #:key car-maker)) 

(require rackunit) 
(check-equal? 
(sort-by-maker-and-model list-of-cars) 
(list 
    (car "Bugatti" "Type 10" "1908") 
    (car "Bugatti" "Type 2" "1900") 
    (car "Bugatti" "Type 5" "1903") 
    (car "Ferrari" "166 Inter" "1949") 
    (car "Ferrari" "250 Europa GT" "1954") 
    (car "Ferrari" "340 America" "1951") 
    (car "Lamborghini" "Egoista" "2013") 
    (car "Lamborghini" "Flying Star II" "1966") 
    (car "Maserati" "5000 GT" "1959") 
    (car "Maserati" "A6 1500" "1946") 
    (car "Maserati" "Quattroporte" "1963"))) 

更新：增加一些時序數據

(define (sort-by-maker-and-model lst) 
    (sort 
    (sort lst string<? #:key car-model) 
    string<? #:key car-maker)) 
(define (sort-by-maker-and-model2 lst) 
    (sort lst 
     (lambda (e1 e2) 
      (or (string<? (car-maker e1) (car-maker e2)) 
       (and (string=? (car-maker e1) (car-maker e2)) 
        (string<? (car-model e1) (car-model e2))))))) 
(define (sort-by-maker-and-model3 lst) 
    (sort lst 
     string<? 
     #:key (lambda (e) (string-append (car-maker e) " " (car-model e))))) 

(define (random-string) 
    (define len (+ 4 (random 6))) 
    (apply string (map integer->char (build-list len (λ _ (+ (random 26) 65)))))) 
(define (random-car . xs) 
    (car (random-string) (random-string) (number->string (+ (random 9000) 1000)))) 
(let ([cars (build-list 1000000 random-car)]) 
    (collect-garbage) 
    (collect-garbage) 
    (collect-garbage) 
    (void (time (sort-by-maker-and-model cars))) 
    (collect-garbage) 
    (collect-garbage) 
    (collect-garbage) 
    (void (time (sort-by-maker-and-model2 cars))) 
    (collect-garbage) 
    (collect-garbage) 
    (collect-garbage) 
    (void (time (sort-by-maker-and-model3 cars)))) 

定製低於爲最快，然後雙排序，然後字符串追加鍵，這是我會猜到的：

$ racket sort-cars.rkt 
cpu time: 5008 real time: 5015 gc time: 76 
cpu time: 1960 real time: 1967 gc time: 0 
cpu time: 6633 real time: 6643 gc time: 1588