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

问题描述

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

的字符串属性

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

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

我的目标是对 [Player] 进行排序，首先拥有所有QB"，然后是WR"、RB"，最后是TE".

我目前的做法是循环遍历 positionOrders 中的每个元素，然后在其中循环遍历所有玩家以附加到一个新数组.但是，我想不出一个更简单(更有效)的方法来做到这一点.非常感谢任何提示或指示.谢谢.

解决方案

我最初的方法很糟糕.这篇文章受到了很大的关注，所以是时候给它更多的关注并改进它了.

<小时>

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

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

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

HardCodedOrdering

public struct HardCodedOrdering其中元素:Hashable {公共枚举 UnspecifiedItemSortingPolicy {案例优先最后一个案例case assertAllItemsHaveDefinedSorting}私人出租订购:[元素:Int]私人让sortingPolicy:UnspecifiedItemSortingPolicy公共初始化(排序:元素...，sortUnspecifiedItems sortingPolicy: UnspecifiedItemSortingPolicy = .assertAllItemsHaveDefinedSorting){self.init(排序:排序，sortUnspecifiedItems:sortingPolicy)}公共初始化(订购:S，sortUnspecifiedItems sortingPolicy: UnspecifiedItemSortingPolicy = .assertAllItemsHaveDefinedSorting) 其中 S.Element == Element {self.ordering = Dictionary(uniqueKeysWithValues: zip(ordering, 1 ...))self.sortingPolicy = 排序策略}private func sortKey(for element: Element) ->整数{if let definedSortKey = self.ordering[element] { return definedSortKey }切换排序策略{case .first: 返回 Int.mincase .last: 返回 Int.max案例.assertAllItemsHaveDefinedSorting:FatalError("找到一个没有定义顺序的元素:\(element)")}}public func contains(_ element: Element) ->布尔{返回 self.ordering.keys.contains(element)}//用于根据`keyDeriver`产生的值对`T`的集合进行排序.//如有必要，可以引入一个抛出变量.public func areInIncreasingOrder(by keyDeriver: @escaping (T) -> Element) ->(T, T) ->布尔{返回 { lhs, rhs inself.sortKey(for: keyDeriver(lhs)) 布尔{返回 sortKey(for: lhs) <sortKey(用于:rhs)}}

示例用法:

<代码>let rankOrdering = HardCodedOrdering(ordering: "Private", "Lieutenant", "Captain", "Admiral")//理想情况下，构建一次，缓存并共享让 someRanks = ["Admiral",//应该是最后的(最伟大的)银河霸王"，//假的，应该删除"Private",//应该是第一个(最少)]让 realRanks = someRanks.lazy.filter(rankOrdering.contains)let sortedRealRanks = realRanks.sorted(by: rankOrdering.areInIncreasingOrder)//也适用于变异变量 `sort(by:)`.打印(sortedRealRanks)//=>[私人"，海军上将"]

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

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

let positionOrders = ["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.

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.

解决方案

Edit: 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.

---

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".

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.

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).

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)
    }
}

Example usage:

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屋！