集合调和算法的实现

Question

我在寻找集合协调算法的实现。问题是这样的：有两个集合，它们的元素通过一些相对紧凑的值来标识（比如 UUID 或 MD5/SHA1 等哈希值），这些集合分别在不同的机器上。这两个集合之间的差异相对较小，我想在传输最少数据的情况下同步这两个集合。大部分的搜索结果都指向这里。这是一个 GPL 许可的实现，看起来是这个任务的最先进的方法。问题是我不能在我的应用中使用 GPL 许可的代码。很可能我得自己重新实现一个，可能会用到 nzmath，但也许还有其他的实现（最好是 Python 或 C/C++），或者也许还有其他更好的算法？

Answer 1

这个同步密钥服务器项目是用OCaml语言实现的，目的是让不同的密钥集合之间能够高效地进行对比和协调。

Answer 2

这段代码是我自己想出来的，所以它遵循这个网站上代码示例的相关许可协议。

# given two finite sequences of unique and hashable data,
# return needed opcodes and data needed for reconciliation

def set_reconcile(src_seq, dst_seq):
    "Return required operations to mutate src_seq into dst_seq"
    src_set= set(src_seq) # no-op if already of type set
    dst_set= set(dst_seq) # ditto

    for item in src_set - dst_set:
        yield 'delete', item

    for item in dst_set - src_set:
        yield 'create', item

使用方法如下：

for opcode, datum in set_reconcile(machine1_stuff, machine2_stuff):
    if opcode == 'create':
        # act accordingly
    elif opcode == 'delete':
        # likewise
    else:
        raise RuntimeError, 'unexpected opcode'

Answer 3

不能使用GPL许可证通常是因为一些抽象的概念，也就是说，如果你对这个许可证有问题的话。如果你创建了一个小的GPL应用程序（按照GPL发布），你可以在你的非GPL应用程序中调用它。何必重新发明轮子呢？

特别是如果你可以使用已经存在的Python脚本，那为什么不利用它呢？当然，如果你不能公开元素重新整合的算法，那事情就不一样了。