使用 Firebase/Firestore 具有重新排序功能的任务列表
Muh*_*ori 12 database-design firebase swift firebase-realtime-database google-cloud-firestore
我想列出可以更改顺序的任务列表，但我不确定如何将其存储在数据库中。
我不想使用数组，因为我将来必须做一些进一步的查询。
这是我的数据库的屏幕截图：
我正在尝试制作类似 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)
}
}
}
}
CTS*_*_AE 12
我认为您要问的问题更多是关于数据库设计。
当您希望能够保持一组项目的订单同时能够重新排序它们时，您将需要一列来保持订单。
如果它们按顺序排列，当您尝试订购它们时会遇到问题。
例子
例如，如果您想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”我在下面添加了一个相关问题，该问题涉及该想法以及为什么您应该避免它。
您或许可以验证订单客户端的安全性，并避免访问数据库来确定移动的新订单 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（更好）——链表
正如下面的相关链接中提到的，您可以使用像链表这样的数据结构。这保留了要更新的恒定数量的更改，因此它是大 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]
相关问题
Big O 上的资源
其他注意事项
您的数据库设计将取决于您要完成的任务。项目可以属于多个板或用户吗？
您能否将一些订单卸载到客户端并允许它告诉服务器新订单是什么？您仍然应该避免在客户端使用低效的排序算法，但是如果您信任它们，并且如果多个人同时处理相同的项目，那么您可以让它们做一些肮脏的工作，并且在数据完整性方面没有任何问题时间（这些是其他设计问题，可能与数据库有关，也可能无关，具体取决于您处理它们的方式。）
我很长一段时间都被同一个问题困扰。我发现的最好的解决方案是按字典顺序对它们进行排序。
尝试管理小数排名（1、2、3、4...）会遇到很多问题，这些问题在这个问题的其他答案中都提到过。相反，我将排名存储为字符串（“aaa”、“bbb”、“ccc”...），并使用字符串中字符的字符代码在进行调整时找到排名之间的位置。
例如，我有：
{
item: "Star Wars",
rank: "bbb"
},
{
item: "Lord of the Rings",
rank: "ccc"
},
{
item: "Harry Potter",
rank: "ddd"
},
{
item: "Star Trek",
rank: "eee"
},
{
item: "Game of Thrones",
rank: "fff"
}
现在我想移动"Game of Thrones"到第三个位置，位于"Lord of the Rings"( 'ccc') 下方和"Harry Potter"( 'ddd') 上方。
'ccc'所以我使用和的字符代码'ddd'从数学上求出两个字符串之间的平均值；在这种情况下，最终结果是'cpp'，我将把文档更新为：
{
item: "Game of Thrones",
rank: "cpp"
}
我现在有：
{
item: "Star Wars",
rank: "bbb"
},
{
item: "Lord of the Rings",
rank: "ccc"
},
{
item: "Game of Thrones",
rank: "cpp"
},
{
item: "Harry Potter",
rank: "ddd"
},
{
item: "Star Trek",
rank: "eee"
}
如果两个行之间的空间不足，我可以简单地在字符串末尾添加一个字母；所以，在'bbb'和之间'bbc'，我可以插入'bbbn'。
这是相对于十进制排名的一个好处。
需要注意的事项
不要将'aaa'或分配'zzz'给任何项目。需要保留这些，以便轻松地将项目移动到列表的顶部或底部。如果"Star Wars"有等级'aaa'并且我想将某些东西移到它之上，就会出现问题。可以解决的问题，但如果你从 等级 开始，这很容易避免'bbb'。'bbb'然后，如果您想将某些内容移动到最高排名之上，您只需找到和之间的平均值即可'aaa'。
如果您的列表经常重新洗牌，那么定期刷新排名将是一个很好的做法。如果事物被移动到列表中的同一位置数千次，您可能会得到一个长字符串，例如'bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbn'. 当字符串达到一定长度时，您可能需要刷新列表。
执行
可以在此处找到用于实现此效果的算法和函数说明。这个想法要归功于该文章的作者。
我在项目中使用的代码
同样，这段代码的功劳归于我上面链接的文章的作者，但这是我在项目中运行的代码，用于查找两个字符串之间的平均值。这是用 Dart 为 Flutter 应用程序编写的
import 'dart:math';
const ALPHABET_SIZE = 26;
String getRankBetween({String firstRank, String secondRank}) {
assert(firstRank.compareTo(secondRank) < 0,
"First position must be lower than second. Got firstRank $firstRank and second rank $secondRank");
/// Make positions equal
while (firstRank.length != secondRank.length) {
if (firstRank.length > secondRank.length)
secondRank += "a";
else
firstRank += "a";
}
var firstPositionCodes = [];
firstPositionCodes.addAll(firstRank.codeUnits);
var secondPositionCodes = [];
secondPositionCodes.addAll(secondRank.codeUnits);
var difference = 0;
for (int index = firstPositionCodes.length - 1; index >= 0; index--) {
/// Codes of the elements of positions
var firstCode = firstPositionCodes[index];
var secondCode = secondPositionCodes[index];
/// i.e. ' a < b '
if (secondCode < firstCode) {
/// ALPHABET_SIZE = 26 for now
secondCode += ALPHABET_SIZE;
secondPositionCodes[index - 1] -= 1;
}
/// formula: x = a * size^0 + b * size^1 + c * size^2
final powRes = pow(ALPHABET_SIZE, firstRank.length - index - 1);
difference += (secondCode - firstCode) * powRes;
}
var newElement = "";
if (difference <= 1) {
/// add middle char from alphabet
newElement = firstRank +
String.fromCharCode('a'.codeUnits.first + ALPHABET_SIZE ~/ 2);
} else {
difference ~/= 2;
var offset = 0;
for (int index = 0; index < firstRank.length; index++) {
/// formula: x = difference / (size^place - 1) % size;
/// i.e. difference = 110, size = 10, we want place 2 (middle),
/// then x = 100 / 10^(2 - 1) % 10 = 100 / 10 % 10 = 11 % 10 = 1
final diffInSymbols =
difference ~/ pow(ALPHABET_SIZE, index) % (ALPHABET_SIZE);
var newElementCode = firstRank.codeUnitAt(secondRank.length - index - 1) +
diffInSymbols +
offset;
offset = 0;
/// if newElement is greater then 'z'
if (newElementCode > 'z'.codeUnits.first) {
offset++;
newElementCode -= ALPHABET_SIZE;
}
newElement += String.fromCharCode(newElementCode);
}
newElement = newElement.split('').reversed.join();
}
return newElement;
}
您可以采用多种方法来实现此类功能。
方法#1：
您可以为您的任务提供远程位置而不是连续位置，如下所示：
Date: 10 April 2019
Name: "some task name"
Index: 10
...
Index: 20
...
Index: 30
这里总共有 3 个任务，位置为 10、20、30。现在假设您想将第三个任务移到中间，只需将位置更改为 15，现在您有三个任务，位置为 10、15、20，我相信您从数据库中获取所有任务时可以根据位置进行排序，并且我还假设您可以获取任务的位置，因为用户将在移动应用程序或网络应用程序上重新排列任务，以便您可以轻松获取周围任务的位置并计算周围任务的中间位置，现在假设您想将第一个任务（现在位置索引为 10）移动到中间，只需获取周围任务的位置（15 和 20）并计算中间位置（即 17.5） ( (20-15)/2=17.5 ) 现在你的位置是 15, 17.5, 20
有人说 1 和 2 之间有无穷大，所以我认为你不会运行我们的数字，但你仍然认为你很快就会用完除法，你可以增加差值，你可以使它成为 100000...00而不是 10
方法#2：
您可以将所有任务保存在同一个文档中，而不是采用分层 json 形式的单独文档，如下所示：
任务：[ {name:"some name",date: "some date" },{name:"some name",date: "some date"},{name:"some name",date: "some date" } ]
通过这样做，您将立即在屏幕上获取所有任务，并将 json 解析为本地数组，当用户重新排列任务时，您只需在本地更改该数组元素的位置并将任务的分层版本保存在数据库中：好吧，这种方法有一些缺点，如果您使用分页，可能会很难做到这一点，但希望您不会在任务管理应用程序中使用分页，并且您可能想同时在屏幕上显示所有任务就像 Trello 一样。
| 归档时间： |
|
| 查看次数： |
1605 次 |
| 最近记录： |