按 Int 打乱结构

Question

我怎样才能打乱我的结构 variable priority 并显示在 TableView 中？

所以现在我的结构中有 20 个文档，但稍后我的结构中会有 100+ 个文档。

5 or 7 or 10 documents will have priority from 10 to 1, other documents have priority 0. 我需要在 tableView 的顶部显示 5 or 7 or 10 documents。 priority 0 的其他文档必须位于随机顺序的前 5、7 或 10 个文档之后。

我。 e.前5或7或10个文件应根据优先级放置，如果一个文件有priority 10，它应该是第一个，下一个有priority 9的应该在文件后面priority 10 依此类推优先级为 1 的文档。其他到期文档随机排列。

此代码可帮助我从 firestore:

获取文档

fileprivate func observeQuery() {
    MBProgressHUD.showAdded(to: self.view, animated: true)
    guard let query = query else { return }
    let time = DispatchTime.now() + 0.5
    listener = query.addSnapshotListener { [unowned self] (snapshot, error) in
        if let snapshot = snapshot {
            DispatchQueue.main.asyncAfter(deadline: time) {
                var photoModels = snapshot.documents.map { (document) -> Photographer in
                    if let photoModel = Photographer(dictionary: document.data(), id: document.documentID) {
                        return photoModel
                    } else {
                        fatalError("Fatal error")
                    }
                }
                self.photographers = photoModels
                // this need use shuffle
                self.document = snapshot.documents
                self.tableView.reloadData()
                MBProgressHUD.hide(for: self.view, animated: true)
            }
        }
    }
}

Answer 1

你能做的是

按优先级从高到低的顺序对文档进行排序。
然后将数组中优先级为零的文档打乱。

示例：

var sorted = documents.sorted(by: { [=10=].priority > .priority } )
if let idx = sorted.firstIndex(where: { [=10=].priority == 0 }) {
    sorted[idx...].shuffle()
}

另一种方法是打乱整个数组，然后通过降低优先级进行“稳定排序”，使用来自的想法：

let sorted = documents.shuffled().enumerated()
    .sorted(by: { ([=11=].element.priority, [=11=].offset) > (.element.priority, .offset) })
    .map { [=11=].element }

这将按降序对条目进行排序，并随机混洗所有个具有相同优先级的条目，而不仅仅是具有零优先级的条目。

备注： Swift 标准库中的排序方法恰好在 Swift 5 中是稳定的，因此最后一种方法可以简化为

let sorted = documents.shuffled()
    .sorted(by: { [=12=].priority > .priority } )

但是，这并不能保证，请比较 Swift 论坛中的 Is sort() stable in Swift 5?。

Answer 2

您可以将文件放入桶中：

var buckets = Array(repeating: [Document](), count: 11)

for i in documents.indices {
    buckets[10 - documents[i].priority].append(documents[i])
}

这是一个 O(n) 算法的最坏情况，不像 TimSort 的 O(nlog(n)).

然后洗牌最后一个桶：

buckets[10].shuffle()

最后但同样重要的是，flatMap buckets 数组：

let sorted = buckets.flatMap { [=12=] }

快速随机播放

如果您想进行更快的随机播放，可以使用此 modified Fisher-Yates 算法（比 Array.shuffled() 更快）：

extension Array where Element: Comparable {
    mutating func fisherYatesShuffle()  {
        if count < 2 {
            return
        }
        for i in 1..<count {
            let ix = abs(x.next()) % (i+1)
            swapAt(i,ix)
        }
    }
}

或更一般地 MutableCollection（包括 ArraySlice）：

extension MutableCollection where Index == Int, Element: Comparable {
    mutating func fisherYatesShuffle()  {
        if count < 2 {
            return
        }

        let start = self.index(after: startIndex)

        for i in start..<endIndex {
            let ix = abs(x.next()) % (i + 1 - startIndex) + startIndex
            swapAt(i, ix)
        }
    }
}

此扩展程序使用 Xoshiro random number generator（比 Int.random(in:) 快，但低于 random/uniform）：

struct Xoshiro: RandomNumberGenerator {
    public typealias StateType = (UInt32, UInt32, UInt32, UInt32)

    private var state: StateType

    public init(seed: StateType) {
        self.state = seed
    }

    public mutating func next() -> Int {
        let x = state.1 &* 5
        let result = ((x &<< 7) | (x &>> 25)) &* 9
        let t = state.1 &<< 9
        state.2 ^= state.0
        state.3 ^= state.1
        state.1 ^= state.2
        state.0 ^= state.3
        state.2 ^= t
        state.3 = (state.3 &<< 21) | (state.3 &>> 11)
        return Int(result)
    }
}

var x = Xoshiro(seed: (UInt32.random(in: 0..<10),  //Other upper limits could be used to increase randomness
                       UInt32.random(in: 0..<10),
                       UInt32.random(in: 0..<10),
                       UInt32.random(in: 0..<10)))

要使用它，Document 应该是 Comparable :

struct Document: Comparable {
    let priority: Int
    static func < (lhs: Document, rhs: Document) -> Bool {
        return lhs.priority < rhs.priority
    }
}

然后像这样调用我们的洗牌：

buckets[10].fisherYatesShuffle()

分区、排序、随机播放

根据 Josh Homann 的建议，您还可以对 documents 数组进行分区，将优先级为零的文档放在主索引之后。然后对第一个分区进行排序，并对第二个分区进行打乱：

var result = documents
let pivot = result.partition { [=18=].priority == 0 }
result[..<pivot].sort(by: > )
result[pivot...].shuffle()

基准

Here 是一些基准：

Joakim Danielson's : 1643µs
MartinR's          :  169µs 
Josh Homann's      :  152µs
Orig. Fisher-Yates :   38µs
This               :   15µs

（尽管 TIO 使用 Swift 4，但在我的本地机器上使用相同的代码得到了相对可比的结果 Swift 5，终端中的运行进行了优化）

Answer 3

这是一个解决方案，其中数组中的所有元素一次排序

array.sort(by: {
    let first = [=10=].priority == 0 ? Double.random(in: 0..<1) : Double([=10=].priority)
    let second = .priority == 0 ? Double.random(in: 0..<1) : Double(.priority)
    return first > second
})

如果你想避免强制转换为 Double，你可以为随机数定义一个负数范围，我只是在这里硬编码了一个值，但一个选项可能是将最小值 (-1000) 基于 array

array.sort(by: {
    let first = [=11=].priority == 0 ? Int.random(in: -1000..<1) : [=11=].priority
    let second = .priority == 0 ? Int.random(in: -1000..<1) : .priority
    return first > second
})

按 Int 打乱结构

Shuffle struct by Int

arrays

shuffle

swift

快速随机播放

分区、排序、随机播放

基准