algorithm - 将对象插入到已排序集合中的其他对象之间

Question

我有一个已排序(Mongodb)的对象集合:

{"_id": ObjectId(...), "person": "Homer", "order": 1},
{"_id": ObjectId(...), "person": "Marge", "order": 2}

我想在两个对象之间添加、追加或插入另一个对象。我已经尝试过使用这样的 float :

{"_id": ObjectId(...), "person": "Homer", "order": 1},
{"_id": ObjectId(...), "person": "Bart", "order": 1.5},
{"_id": ObjectId(...), "person": "Marge", "order": 2}

Order 值是前一个和下一个对象中的字段 order 的算术平均值。只要数字看起来不像 1.9999999，它就可以工作。然后它会四舍五入到 2 并且集合不会排序。 我可以这样使用整数:

{"_id": ObjectId(...), "person": "Homer", "order": 1},
{"_id": ObjectId(...), "person": "Bart", "order": 2},
{"_id": ObjectId(...), "person": "Marge", "order": 3}

但这意味着需要修改其他对象，我宁愿避免这种情况。

我考虑过使用字符串和词法排序来防止顺序:

{"_id": ObjectId(...), "person": "Homer", "order": aa},
{"_id": ObjectId(...), "person": "Bart", "order": ab},
{"_id": ObjectId(...), "person": "Marge", "order": bb}

但实现起来似乎很难。有没有更简单的方法？

Answer 1

我认为 float 方法最有意义。 假设您一开始将所有位置都设为整数，则需要进行大量交换，直到遇到精度问题。

我建议每当你改变一个项目的“顺序”时，看看它是否离它的邻居之一太近。如果是，请重新分配所有对象的值(因此它们再次都是整数)。

如果您设置 |x-y| 的限制>= 2**(-50)，这很好，因为 python 为浮点保留 53 个精度位，在需要重新分配订单之前，至少需要 50 次不幸的交换。

编辑:我刚刚看到你没有具体询问Python。将精度替换为对您的系统有意义的值。