efficient sorting of an array based on another arr

问题:

Suppose I have this:

struct Pet {
    let name: String
}

let pets = [Pet(name: "Z"), Pet(name: "F"), Pet(name: "A"), Pet(name: "E")]
let petNames = ["E", "F", "Z", "A"]

and my intended output is:

[Pet(name: "E"), Pet(name: "F"), Pet(name: "Z"), Pet(name: "A")]

How do I sort pets efficiently by following petNames' order?

My current method appears to be horribly inefficient:

var sortedPets = [Pet]()
for n in petNames {
    sortedPets.append(pets.first(where: { return $0.name == n })!)
}

Any functional approach that I could use?

回答1:

Not efficient, but it solves the problem functionally:

let pets2 = pets.sorted{petNames.index(of:$0.name)! < petNames.index(of:$1.name)!}

Now that we know what we're after, this is more elaborate but much more efficient, because dictionary lookup is fast:

var d = [String:Int]()
zip(petNames, 0..<petNames.count).forEach { d[$0.0] = $0.1 }
let pets2 = pets.sorted{d[$0.name]! < d[$1.name]!}

回答2:

I have written an extension just for this. It's pretty flexible, in that it lets you define by what field the input is sorted, and how to handle elements whose sort ordering isn't defined according to the sortingOrder list.

It's pretty long, so I suggest you tuck it away in its own file:

enum UnspecifiedItemSortingPolicy {
    case first
    case last
    case omitEntirely
    case assertAllItemsHaveDefinedSorting
}

extension MutableCollection {
    typealias Element = Iterator.Element

    func sorted<T: Equatable>(
            byOrderOf sortingMemberDeriver: @escaping (Element) -> T,
            in sortingOrder: [T],
            sortUnspecifiedItems unspecifiedItemSortingPolicy: UnspecifiedItemSortingPolicy = .assertAllItemsHaveDefinedSorting
        ) -> [Element] {

        switch unspecifiedItemSortingPolicy {
            case .omitEntirely: return self
                    .lazy
                    .map { (element: Element) -> (element: Element, position: Int) in
                        let sortingMember = sortingMemberDeriver(element)
                        guard let position = sortingOrder.index(of: sortingMember) else {
                            fatalError("Attempted to sort a collection (\(self)) containing an item (\(element)) whose ordering was not defined in the sorting order: \(sortingOrder).")
                        }
                        return (element: element, position: position)
                    }
                    .sorted{ $0.position < $1.position }
                    .map{ $0.element }
            case .assertAllItemsHaveDefinedSorting: return self
                    .lazy
                    .flatMap { (element: Element) -> (element: Element, position: Int)? in
                        let sortingMember = sortingMemberDeriver(element)
                        return sortingOrder.index(of: sortingMember).map{ (element: element, position: $0) }
                    }
                    .sorted{ $0.position < $1.position }
                    .map{ $0.element }

            case .first, .last:
                var unspecifiedItems = Array<Element>() //items whose ordering isn't in the sortingOrder

                let sortedPortion = self.flatMap { (element: Element) -> (element: Element, position: Int)? in
                        let sortingMember = sortingMemberDeriver(element)
                        guard let position = sortingOrder.index(of: sortingMember) else {
                            unspecifiedItems.append(element)
                            return nil
                        }
                        return (element: element, position: position)
                    }
                    .sorted{ $0.position < $1.position }
                    .map{ $0.element }

                switch unspecifiedItemSortingPolicy {
                    case .first: return unspecifiedItems + sortedPortion
                    case .last: return sortedPortion + unspecifiedItems
                    default: fatalError("This should never happen.")
                }
        }
    }
}

extension MutableCollection where Iterator.Element: Equatable {
    func sorted(
            byOrderIn sortingOrder: [Element],
            sortUnspecifiedItems unspecifiedItemSortingPolicy: UnspecifiedItemSortingPolicy = .assertAllItemsHaveDefinedSorting
        ) -> [Element] {
        return self.sorted(byOrderOf: {$0}, in: sortingOrder, sortUnspecifiedItems: unspecifiedItemSortingPolicy)
    }
}

From there, the usage is really easy and elegant:

struct Pet {
    let name: String
}

let pets = [Pet(name: "Z"), Pet(name: "F"), Pet(name: "A"), Pet(name: "E")]
let petNames = ["E", "F", "Z", "A"]

let sorted = pets.sorted(byOrderOf: { $0.name }, in: petNames, sortUnspecifiedItems: .last)
sorted.forEach{ print($0) }