按多个键对 Racket 中的结构列表进行排序

Question

我有 list-of-cars，一个类型为 car 的结构列表，其中包含字段 "maker"、"model" 和 "year"。使用常规 Racket sort 函数，我可以按一个键进行排序（例如 "maker"）。但是我怎样才能同时按制造商和型号进行排序，并得出一个等于示例中 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 连接两个字段的过程：

(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

Racket 的 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

按多个键对 Racket 中的结构列表进行排序

Sort a list of structures in Racket by more than one key

sorting

scheme

struct

racket