通过从另一个数组排序对Swift数组进行排序 [英] Sorting a Swift array by ordering from another array

问题描述

说我有一个自定义类[Player]的数组，每个类都包含一个名为player.position

Say I have an array of the custom class [Player], each of which contains a string property called player.position

我还有一个名为positionOrders的任意值数组，如下所示:

I also have an arbitrary array of values, called positionOrders, like so:

let positionOrders = ["QB", "WR", "RB", "TE"]

我的目标是对[Player]进行排序，以使其具有所有"QB"，然后是"WR"，"RB"，最后是"TE".

Where my goal is to sort the [Player] to have all the "QB"s first, then "WR"s, "RB"s, and finally "TE"s.

我目前的工作方式是循环遍历positionOrders中的每个元素，然后在内部遍历所有播放器以追加到新数组.但是，我想不出一种更简单(更有效)的方法来做到这一点.任何提示或指针将不胜感激.谢谢.

The current way I am doing loops through each element in positionOrders, then inside that loops through all the players to append to a new array. However, I could not figure a simpler (and more efficient) way to do this. Any tips or pointers are much appreciated. Thanks.

推荐答案

编辑:我最初的方法是狗屎.这篇文章吸引了很多人的注意力，因此该是应该多加注意和改进它的时候了.

My original approach was shit. This post got a lot of traction, so it's time to give it some more attention and improve it.

从根本上讲，问题很容易.我们有两个元素，还有一个数组(或任何有序的Collection)，其相对顺序决定了它们的排序顺序.对于每个元素，我们在有序集合中找到它的位置，并比较两个索引以确定哪个是更大"的.

Fundamentally, the problem is easy. We have two elements, and we have an array (or any ordered Collection) whose relative ordering determines their sort order. For every element, we find its position in the ordered collection, and compare the two indices to determine which is "greater".

但是，如果我们天真地进行线性搜索(例如Array.firstIndex(of:))，则会获得非常差的性能(O(array.count))，尤其是在固定排序非常大的情况下.为了解决这个问题，我们可以构造一个Dictionary，将元素映射到它们的索引.该词典提供快速的O(1)查找，非常适合这项工作.

However, if we naively do linear searches (e.g. Array.firstIndex(of:)), we'll get really bad performance (O(array.count)), particularly if the fixed ordering is very large. To remedy this, we can construct a Dictionary, that maps elements to their indices. The dictionary provides fast O(1) look-ups, which is perfect for the job.

这正是HardCodedOrdering所做的.它根据元素的顺序预先计算了一个字典，并提供了一个比较2个元素的接口.更好的是，它可以配置为以未知顺序对遇到的元素做出不同的响应.可以将它们放在其他所有事物之前，之后，或者完全崩溃(默认行为)之前.

This is exactly what HardCodedOrdering does. It pre-computes a dictionary of elements to their orderings, and provides an interface to compare 2 elements. Even better, it can be configured to respond differently to encountering elements with an unknown ordering. It could put them first before everything else, last after everything else, or crash entirely (the default behaviour).

public struct HardCodedOrdering<Element> where Element: Hashable {
    public enum UnspecifiedItemSortingPolicy {
        case first
        case last
        case assertAllItemsHaveDefinedSorting
    }

    private let ordering: [Element: Int]
    private let sortingPolicy: UnspecifiedItemSortingPolicy

    public init(
        ordering: Element...,
        sortUnspecifiedItems sortingPolicy: UnspecifiedItemSortingPolicy = .assertAllItemsHaveDefinedSorting
    ) {
        self.init(ordering: ordering, sortUnspecifiedItems: sortingPolicy)
    }

    public init<S: Sequence>(
        ordering: S,
        sortUnspecifiedItems sortingPolicy: UnspecifiedItemSortingPolicy = .assertAllItemsHaveDefinedSorting
    ) where S.Element == Element {

        self.ordering = Dictionary(uniqueKeysWithValues: zip(ordering, 1...))
        self.sortingPolicy = sortingPolicy
    }

    private func sortKey(for element: Element) -> Int {
        if let definedSortKey = self.ordering[element] { return definedSortKey }

        switch sortingPolicy {
            case .first:    return Int.min
            case .last:     return Int.max

            case .assertAllItemsHaveDefinedSorting:
                fatalError("Found an element that does not have a defined ordering: \(element)")
        }
    }

    public func contains(_ element: Element) -> Bool {
        return self.ordering.keys.contains(element)
    }

    // For use in sorting a collection of `T`s by the value's yielded by `keyDeriver`.
    // A throwing varient could be introduced, if necessary.
    public func areInIncreasingOrder<T>(by keyDeriver: @escaping (T) -> Element) -> (T, T) -> Bool {
        return { lhs, rhs in
            self.sortKey(for: keyDeriver(lhs)) < self.sortKey(for: keyDeriver(rhs))
        }   
    }

    // For use in sorting a collection of `Element`s
    public func areInIncreasingOrder(_ lhs: Element, rhs: Element) -> Bool {        
        return sortKey(for: lhs) < sortKey(for: rhs)
    }
}

用法示例:

let rankOrdering = HardCodedOrdering(ordering: "Private", "Lieutenant", "Captain", "Admiral") // ideally, construct this once, cache it and share it

let someRanks = [
    "Admiral", // Should be last (greatest)
    "Gallactic Overlord", // fake, should be removed
    "Private", // Should be first (least)
]
let realRanks = someRanks.lazy.filter(rankOrdering.contains)
let sortedRealRanks = realRanks.sorted(by: rankOrdering.areInIncreasingOrder) // works with mutating varient, `sort(by:)`, too.

print(sortedRealRanks) // => ["Private", "Admiral"]

这篇关于通过从另一个数组排序对Swift数组进行排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！