Shuffle struct by Int

Question

Как я могу перемешать мою структуру variable priority и отобразить в TableView?

Так что теперь у меня есть 20 документы в моей структуре, но позже я будуВ моей структуре есть 100 + документов.

5 или 7 или 10 документов будут иметь priority от 10 до 1, другие документы имеют priority 0. Мне нужно отобразить 5 или 7 или 10 документов на верхней позиции в tableView.Другие документы, которые имеют priority 0, должны располагаться после первых 5, 7 или 10 документов в случайном порядке.

I.е.Первые 5 или 7 или 10 документов должны быть размещены в зависимости от приоритета, если документ имеет priority 10, он должен быть первым, следующий, который имеет priority 9, должен быть позади документа с priority10 и т. Д. К документу с приоритетом 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: { $0.priority > $1.priority } )
if let idx = sorted.firstIndex(where: { $0.priority == 0 }) {
    sorted[idx...].shuffle()
}

Альтернативой является перетасовка всего массива и затем «стабильная сортировка» путем уменьшения приоритета с использованием идей из Как сделать стабильную сортировку массива в swift?:

let sorted = documents.shuffled().enumerated()
    .sorted(by: { ($0.element.priority, $0.offset) > ($1.element.priority, $1.offset) })
    .map { $0.element }

Это позволит отсортировать записи по убыванию и случайным образом перемешать все записи с одинаковым приоритетом, а не только записи с нулевым приоритетом.

Примечание: Методы сортировки из стандартной библиотеки Swift в Swift 5 оказываются стабильными, поэтому последний подход можно упростить до

let sorted = documents.shuffled()
    .sorted(by: { $0.priority > $1.priority } )

Однако это не гарантируется,сравнить Является ли sort () стабильным в Swift 5? на форуме Swift.

Answer 2

Вот решение, в котором все элементы в массиве сортируются одновременно

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

Если вы хотите избежать приведения к Double, вы можете определить отрицательный диапазон для случайных чисел, я просто жестко закодировал значение здесь, но одним из вариантов может быть основание минимального значения (-1000) на размере array

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

Answer 3

Вы можете поместить документы в сегменты:

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

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

Это наихудший случай алгоритма O ( n ) в отличие от O TimSort ( n log (*)1008 * n )).

, а затем перетасовать последний сегмент:

buckets[10].shuffle()

последний, но не менее важный, flatMap массив buckets:

let sorted = buckets.flatMap { $0 }

---

Speed ​​Shuffle

Если вы хотите еще более быстрый перемешать, вы можете использовать этот updated Алгоритм Фишера-Йейтса (Быстрее, чем 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 (Быстрее, чем Int.random(in:), но менее случайный / равномерный):

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

---

Разделение, сортировка, перемешивание

Согласно Джош ХоманнСовет , вы также можете разбить массив documents, поместив документы с нулевым значением prирити после сводного индекса.Затем отсортируйте первый раздел и перетасуйте второй:

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

---

Тесты

Здесь - некоторые тесты:

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, запущенного в терминале с оптимизацией)