swift - 使用 Firebase/Firestore 具有重新排序功能的任务列表

Question

我想列出可以更改顺序的任务列表，但我不确定如何将其存储在数据库中。

我不想使用数组，因为我将来必须做一些进一步的查询。

这是我的数据库的屏幕截图:



我正在尝试制作类似 Trello 的东西，用户可以在其中添加任务，并且可以根据任务的优先级上下移动任务。我还需要更改数据库中任务的位置以维护记录。我无法理解如何在任何数据库中执行此操作。我是一名经验丰富的开发人员，我曾与 mongodb 和 firebase 合作过，但这对我来说是独一无二的。

这是创建和获取所有任务的代码。当我尝试在集合中移动一些任务时。我在每个任务中维护了一个索引。
假设当我将任务从索引 5 的位置移动到索引 2 时，我必须通过 +1 编辑所有即将出现的索引有没有更好的方法？

代码示例

class taskManager {
    static let shared = taskManager()
    typealias TasksCompletion = (_ tasks:[Task],_ error:String?)->Void
    typealias SucessCompletion = (_ error:String?)->Void

    func addTask(task:Task,completion:@escaping SucessCompletion){
        Firestore.firestore().collection("tasks").addDocument(data: task.toDic) { (err) in
            if err != nil {
                print(err?.localizedDescription as Any)
            }
            completion(nil)
        }
    }

    func getAllTask(completion:@escaping TasksCompletion){
        Firestore.firestore().collection("tasks")
            .addSnapshotListener { taskSnap, error in
                taskSnap?.documentChanges.forEach({ (task) in
                    let object = task.document.data()
                    let json = try! JSONSerialization.data(withJSONObject: object, options: .prettyPrinted)
                    var taskData = try! JSONDecoder().decode(Task.self, from: json)
                    taskData.id = task.document.documentID

                    if (task.type == .added) {
                        Task.shared.append(taskData)
                    }
                    if (task.type == .modified) {
                        let index = Task.shared.firstIndex(where: { $0.id ==  taskData.id})!
                        Task.shared[index] = taskData
                    }
                })
                if error == nil{
                    completion(Task.shared,nil)
                }else{
                    completion([],error?.localizedDescription)
                }
            }
    }
}

Answer 1

我认为您要问的问题更多是关于 数据库设计 .

当您希望能够保持一组项目的订单同时能够重新排序它们时，您将需要一列来保持订单。

如果它们按顺序排列，当您尝试订购它们时会遇到问题。

示例

例如，如果您想移动 Item1后面 Item4 :

之前

具有排序索引的项目。

 1. Item1, order: 1
 2. Item2, order: 2
 3. Item3, order: 3
 4. Item4, order: 4
 5. Item5, order: 5
 6. Item6, order: 6

之后

问题 :我们必须更新正在移动的项目和放置它的位置之间的每条记录。

为什么这是一个问题 :这是一个大 O(n) - 对于我们移动的每个空间，我们必须更新那么多记录。随着您获得更多任务，这将成为一个更大的问题，因为它需要更长的时间并且无法很好地扩展。有一个大 O(1) 会很好，我们有恒定数量的变化或尽可能少的变化。

 1. Item2, order: 1 - Updated
 2. Item3, order: 2 - Updated
 3. Item4, order: 3 - Updated
 4. Item1, order: 4 - Updated
 5. Item5, order: 5
 6. Item6, order: 6

可能的解决方案 #1(也许可以？) - 间距

您可以尝试想出一种巧妙的方法，尝试将订单号隔开，以便在不更新多个记录的情况下填补空缺。

但这可能会变得棘手，您可能会想，“为什么不按顺序存储 Item1:4.5”我添加了 related question下面进入这个想法以及为什么你应该避免它。

您或许可以验证订单客户端的安全性，并避免访问数据库来确定移动的新订单 ID。

这也有局限性，因为您可能需要重新平衡间距，或者您的项目数量不足。您可能需要检查是否存在冲突，当发生冲突时，您对所有内容执行重新平衡或递归处理冲突周围的项目，以确保其他平衡更新不会导致更多冲突并解决其他冲突。

 1. Item2, order: 200
 2. Item3, order: 300
 3. Item4, order: 400
 4. Item1, order: 450 - Updated
 5. Item5, order: 500
 6. Item6, order: 600

可能的解决方案#2(更好)——链表

如 related link below 中所述你可以使用像链表这样的数据结构。这保留了要更新的恒定数量的更改，因此它是大 O(1)。如果您还没有使用过数据结构，我将稍微介绍一下链表。

正如您在下面看到的，此更改只需要 3 次更新，我相信最大值将为 5，如 Expected Updates 所示。 .您可能会想，“嗯，第一个原始问题/示例花了那么多时间!”问题是，与使用原始方法 [Big O(n)] 的数千或数百万的可能性相比，这将始终是最多 5 次更新。

 1. Item2, previous: null, next: Item3 - Updated // previous is now null
 2. Item3, previous: Item2, next: Item4
 3. Item4, previous: Item3, next: Item1 - Updated // next is now Item1
 4. Item1, previous: Item4, next: Item5 - Updated // previous & next updated
 5. Item5, previous: Item1, next: Item4 - Updated // previous is now Item1
 6. Item6, previous: Item6, next: null

预期更新

正在移动的项目(上一个，下一个)

旧的上一个项目的下一个

旧的下一个项目的上一个

新上一项的下一项

新的下一个项目的上一个

链表

我想我用了 double linked list .您可能只使用一个没有 previous 的链表就可以逃脱。属性，只有一个 next相反。

链表背后的想法是将其视为一个链式链接，当您想要移动一个项目时，您可以将它与其前后的链接分离，然后将这些链接链接在一起。接下来，您将打开您想要放置它的位置，现在它的每一侧都有新链接，对于这些新链接，它们现在将链接到新链接而不是彼此链接。

可能的解决方案 #3 - 文档/Json/阵列存储

你说你想远离阵列，但你可以利用文档存储。您仍然可以拥有一个可搜索的项目表，然后每个项目集合将只有一个项目 ID/引用数组。

项目表

 - Item1, id: 1
 - Item2, id: 2
 - Item3, id: 3
 - Item4, id: 4
 - Item5, id: 5
 - Item6, id: 6

物品收藏

 [2, 3, 4, 1, 5, 6]

相关问题

Storing a reorderable list in a database

Big O 上的资源

A guide on Big O

More on Big O

Wiki Big O

其他注意事项

您的数据库设计将取决于您要完成的任务。项目可以属于多个板或用户吗？

您能否将一些订单卸载到客户端并允许它告诉服务器新订单是什么？您仍然应该避免在客户端使用低效的排序算法，但是如果您信任它们，并且如果多个人同时处理相同的项目，那么您可以让它们做一些肮脏的工作，并且在数据完整性方面没有任何问题时间(这些是其他设计问题，可能与数据库有关，也可能无关，具体取决于您处理它们的方式。)