假设我有一个自定义类的数组[Player],每个类都包含一个名为player.position
[Player]
player.position
我还有一个任意值数组,称为positionOrders,如下所示:
positionOrders
let positionOrders = ["QB", "WR", "RB", "TE"]
我的目标是对[Player]所有QB 进行排序,然后再对所有WR,RB和TE 进行排序。
我当前的操作方式是遍历中的每个元素positionOrders,然后遍历所有播放器以附加到新数组。但是,我想不出一种更简单(更有效)的方法来做到这一点。非常感谢任何提示或指示。谢谢。
编辑: 我原来的方法是狗屎。这篇文章吸引了很多人的注意力,所以现在是应该给予更多关注和改进的时候了。
从根本上讲,问题很容易。我们有两个元素,还有一个数组(或任何ordered Collection),它们的相对顺序决定了它们的排序顺序。对于每个元素,我们在有序集合中找到其位置,然后比较两个索引以确定哪个“更大”。
Collection
但是,如果我们天真地进行线性搜索(例如Array.firstIndex(of:)),我们将获得非常糟糕的性能(O(array.count)),尤其是在固定排序非常大的情况下。为了解决这个问题,我们可以构造一个Dictionary,将元素映射到它们的索引。该词典提供快速O(1)查找,非常适合这项工作。
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"]