2

场景：

  • 照片清单
  • 每张照片都有以下属性
    • id
    • sequence_number
    • main_photo_bit
  • 第一张照片main_photo_bit设置为1（所有其他照片都是0）
  • 照片按sequence_number（任意）排序
  • 主图不一定最低sequence_number（排序前）

见下表：

id, sequence_number, main_photo_bit
1   10               1             
2    5               0             
3   20               0

现在您想通过更改序列号和主照片位来更改顺序。

排序后的要求：

  • 第一sequence_number张照片的没有改变
  • 第一sequence_number张照片的最低
  • 尽可能少的变化

例子：

示例 #1（第二张照片放在第一个位置）：

id, sequence_number, main_photo_bit
2   10               1             
1   15               0             
3   20               0

这就是发生的事情：

  • id 1：新建sequence_number并main_photo_bit设置为0
  • id 2：旧的第一张照片（id 2）sequence_number并main_photo_bit设置为1
  • id 3：什么都没发生

示例#2（第三张照片到第一位置）：

id, sequence_number, main_photo_bit
3   10               1             
1   20               0             
2   30               0

这就是发生的事情：

  • id 1：新sequence_number的比第一张照片大并且main_photo_bit到0
  • id 2：新sequence_number的大于新生成的第二个sequence_number
  • id 3：旧的第一张照片sequence_number并main_photo_bit设置为1

计算保存新订单所需步骤的最佳方法是什么？

编辑：
我想要尽可能少的更新的原因是因为我想将它同步到外部服务，这是一个非常昂贵的操作。
我已经得到了该算法的工作原型，但在某些极端情况下它会失败。因此，与其修补它（这可能有效——但它会变得比现在更复杂），我想知道是否有其他（更好的）方法可以做到这一点。
在我的版本中（简而言之），它对照片进行排序（更改sequence_number's），并交换 's main_photo_bit，但这不足以解决所有场景。

4

2 回答 2

3

据我了解，一个好的解决方案不仅会尽量减少更改（因为更新 是一项昂贵的操作），而且还会尽量减少未来的更改，因为越来越多的照片被重新排序。我首先添加一个临时字段dirty，以指示该行是否必须更改：

id, sequence_number, main_photo_bit, dirty
 1         10               1        false
 2          5               0        false
 3         20               0        false
 4         30               0        false
 5         31               0        false
 6         33               0        false

如果有sequence_number比第一个小的行，它们肯定会改变（要么获得更大的数字，要么成为第一个）。让我们将它们标记为dirty：

id, sequence_number, main_photo_bit, dirty
 2          5               0        true

（如果第一个有最低的不是很重要，请跳过这一步sequence_number）

现在让我们看看照片列表，因为它们应该在结果中（根据问题，只有一张照片改变了位置，从任何地方到任何地方）。粗体字：

[1, 2 , 3, 4, 5, 6] # 原始排序

[ 2 , 1 , 3, 4, 5, 6] # 示例 1：第 2 到第 1 名

[ 3 , 1 , 2 , 4, 5, 6] # 示例 2：第 3 到第 1 名

[1, 2 , 4, 3 , 5, 6] # 例子3：第3到第4名

[1, 3 , 2 , 4, 5, 6] # 示例 4：第 3 到第 2 名

首先要做的是确保第一个元素具有最低的sequence_number. 如果它没有改变位置，那么根据定义它已经改变了，否则旧的第一个应该被标记为脏，main_photo_bit清除它，新的应该接收这些值给它自己。

此时，第一个元素应该有一个固定的sequence_number，并且每个脏元素都可以随意更改其值（因为无论如何它都必须更改，因此最好更改为有用的值）。在继续之前，我们必须确保可以通过仅更改脏行来解决它，或者如果更多的行也必须被弄脏。这只是确定每对干净行之间的间隔是否足够大以适应它们之间的脏行数：

[10, D, 20, 30, 31, 33]   # Original ordering (the first is dirty, but fixed)

[10, D, 20, 30, 31, 33]   # Example 1: 2nd to 1st place (ok: 10 < ? < 20)
[10, D, D, 30, 31, 33]    # Example 2: 3rd to 1st place (ok: 10 < ? < ? < 30)
[10, D, 30, D, 31, 33]    # Example 3: 3rd to 4th place (NOT OK: 30 < ? < 31)
  [10, D, 30, D, D, 33]   #   must mark 5th as dirty too (ok: 30 < ? < ? < 33)
[10, D, D, 30, 31, 33]    # Example 4: 3rd to 2nd place (ok)

现在只需将 new 分配给sequence_number脏行即可。一个简单的解决方案是只增加前一个，但更好的方法是将它们设置为尽可能等距。这样，未来的重新排序需要更少更改的可能性更大（换句话说，为了避免像示例 3 这样的问题，其中由于某些sequence_numbers 彼此太接近而必须更新比必要更多的行）：

[ 10 , 15 , 20, 30, 31, 33] # 示例 1：第 2 名到第 1 名

[ 10 , 16 , 23 , 30, 31, 33] # 示例 2：第 3 到第 1 名

[10, 20 , 30, 31 , 32 , 33] # 示例 3：第 3 到第 4 名

[10, 16 , 23 , 30, 31, 33] # 示例 4：第 3 到第 2 名

奖励：如果您真的想将解决方案推向极限，请进行两次计算 - 一次移动照片，另一次固定并移动周围的照片 - 看看哪一次导致较少的变化。以示例 3A 为例，我们将其视为“第 4 到第 3 位”而不是“第 3 到第 4 位”（排序结果相同，但变化不同）：

[1, 2 , 4 , 3, 5, 6] # 示例 3A：第 4 到第 3 名

[10, D, D, 20, 31, 33] # (ok: 10 < ? < ? < 20)

[10, 13 , 16 , 20, 31, 33] # 少变化

在大多数情况下，它可以做到（例如：第 2 到第 4 位置 == 第 3/4 到第 2/第 3 位置），增加的复杂性是否值得小小的收益，由您决定。

于 2012-10-26T08:09:33.160 回答
1

使用链表而不是序列号。然后您可以从列表中的任何位置删除图片并重新插入列表中的任何位置，您只需要更改数据库文件中的 3 行。主照片位应该是不必要的，第一张照片是通过没有任何指向它的指针来隐式定义的。

id      next
1       3
2       1
3

顺序是：2、1、3

用户将图片 3 移动到位置 1：

id      next
1       
2       1
3       2

新顺序是：3、2、1

于 2012-11-01T10:13:44.757 回答