小编典典

通过从另一个数组排序对Swift数组进行排序

swift

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

我还有一个任意值数组,称为positionOrders,如下所示:

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

我的目标是对[Player]所有QB 进行排序,然后再对所有WR,RB和TE 进行排序。

我当前的操作方式是遍历中的每个元素positionOrders,然后遍历所有播放器以附加到新数组。但是,我想不出一种更简单(更有效)的方法来做到这一点。非常感谢任何提示或指示。谢谢。


阅读 545

收藏
2020-07-07

共1个答案

小编典典

编辑: 我原来的方法是狗屎。这篇文章吸引了很多人的注意力,所以现在是应该给予更多关注和改进的时候了。


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

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

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

HardCodedOrdering

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"]
2020-07-07