c - 用于同步多个项目集合的高效数据结构和策略

Question

我想要一个单一类型项目的主要集合，随着时间的推移对其进行修改。周期性地，几个从属集合将与主集契约(Contract)步。主集合应向从属集合发送一个项目增量。

Primary Collection: A, C, D
Slave Collection 1: A, C    (add D)
Slave Collection 2: A, B    (add C, D; remove B)

slave 集合不能自己添加或删除项目，它们可能存在于不同的进程中，所以我可能会使用管道来推送数据。

我不想推送不必要的数据，因为集合可能会变得非常大。

哪种数据结构和策略最适合这种情况？

Answer 1

为此我使用 differential execution 。

(顺便说一句，“奴隶”这个词让某些人感到不舒服，这是有原因的。)

对于每个远程站点，主站点上都有一个顺序文件，代表远程站点上存在的内容。

在主站点有一个遍历主集合的过程，当它遍历时，它会读取相应的文件，检测远程站点上当前存在的内容与应该存在的内容之间的差异。这些差异会产生增量，这些增量会传输到远程站点。同时，该过程写入一个新文件，表示在处理增量后远程站点将存在的内容。

这样做的好处是它不依赖于检测主要集合中的更改事件，因为这些更改事件通常是不可靠的，或者可以 self 取消或与其他更改无关，因此您可以减少不必要的传输到远程站点。

如果集合是简单的事物列表，这归结为拥有远程集合的本地副本并运行 diff 算法来获取增量。这里有几个这样的算法:

如果可以对集合进行排序(如您的 A、B、C 示例)，只需运行合并循环:

while(ix<nx && iy<ny){
  if (X[ix] < Y[iy]){
    // X[ix] was inserted in X
    ix++;
  } else if (Y[iy] < X[ix]){
    // Y[iy] was deleted from X
    iy++;
  } else {
    // the two elements are equal. skip them both;
    ix++; iy++;
  }
}
while(ix<nx){
  // X[ix] was inserted in X
  ix++;
}
while(iy<ny>){
  // Y[iy] was deleted from X
  iy++;
}

如果集合无法排序(注意与 Levenshtein distance 的关系)，

Until we have read through both collections X and Y,
  See if the current items are equal

  else see if a single item was inserted in X
  else see if a single item was deleted from X

  else see if 2 items were inserted in X
  else see if a single item was replaced in X
  else see if 2 items were deleted from X

  else see if 3 items were inserted in X
  else see if 2 items in X replaced 1 items in Y
  else see if 1 items in X replaced 2 items in Y
  else see if 3 items were deleted from X

  etc. etc. up to some limit

性能通常不是问题，因为程序不必高频运行。

有一个 crude video demonstrating this concept 和 source code where it is used for dynamically changing user interfaces 。