algorithm - 如何巧妙地将任意元数据编码为 UUID？

Question

(此算法适用于我正在开发的 iPhone 应用程序，如果它对上下文有帮助的话。)

我们需要制作UUID来唯一标识一些产品。通常这就像分配唯一编号一样简单，但我们还想将元数据编码到我们的 UUID 中。我们的 API 只允许我们使用一个字段，因此我们希望将 UUID 字段用作唯一标识符和元数据载体。

通常，您可以将数据与下划线混合在一起，但我们有一个要求使这变得困难:其中一个元数据项可以是 n 项的列表。

这是元数据:

• 设备类型(~最多 16 种离散类型)
• 支持的最低操作系统版本(x.x.x 格式，其中 x 是 0-99 之间的数字)
• 支持的最小二进制(应用程序)版本(x.x.x 格式，其中 x 是 0-99 之间的数字)
• 此产品取代的任何产品(n 个 ID 的列表，其格式是此设计问题的一部分)

限制

我们唯一的技术限制是我们最多只能使用 128 个字母数字字符 (a-zA-Z0-9)，包括下划线、句点和连字符，来表示 UUID(它是一个 API)。

用例

这里有一些用例来解释这个算法将帮助解决什么问题:

1. 一位用户购买了产品 A 和产品 B。我们随后发布了产品 C，它是产品 A+B 的组合。通过 C 的 UUID，我们希望我们的应用程序代码能够确定 C 确实是 A+B，并且由于用户已经拥有 A+B，因此 C 不会出现在可用产品列表中。

2. 用户有 2 台设备，A 和 B。设备 B 不支持产品 C，因此当用户在设备 B 上查看产品时，他们不应可以使用 C，但设备 A 上应该可以使用.

到目前为止我做了什么

设备类型应该很简单 - 有 16 种离散类型，我可以对其进行位掩码 - 16 位 = 4 个十六进制字符。很简单。

版本控制是相同的 - 我可以将每个版本段 (x.y.z) 填充为 2 位数字，然后只使用 2 次 6 位数字作为版本信息。

重要的是如何引用以前的产品 ID。显然，我的内存空间有限——我只有 128 个字符(使用上述方法，我只剩下 112 个字符)。如果我需要一个包含 n 个项目的列表，我将用完空间。

实际上 n<=5 是合理的。任何给定的产品最多只能取代 5 种其他产品。

固定长度的 UUID 不是必需的。是的，一个“便宜”的解决方案是将 ID 列表与下划线菊花链连接在一起，但是由于许多 ID 必须首先手动输入，所以我们希望尽可能避免使用 128 字节躲开它。最小化 UUID 长度应该是算法正确性之后的优先事项。

另一个可能使这变得困难的部分——尽管它的实现不是在 UUID 本身而是在代码中——是如果一个被取代的产品正在取代其他东西，那需要向下级联。

关于我可以从哪里开始的任何指示？

Answer 1

用十进制或十六进制数字来思考是个坏主意，它只会浪费太多空间。

您的 UUID 字母表有 65 (2*26+10+3) 个字符。因此，对于 n 个字符，您可以编码 65^n 个不同的值。例如 x.x.x 格式(其中 x 是 0-99 之间的数字)实际上只有 100^3 个不同的值，因此它可以用 log65(100^3) ~ 3.31 = 4 个字符进行编码。因此，对于前三个元数据，您需要 1+4+1=9 个字符，或者如果您将三个字段组合在一起，则为 log65(100^3*100^3*16) ~ 7.28 = 8 个字符。

对于产品取代级联问题，我建议将 UUID 分成两部分，第一部分包含一个短 UUID，第二部分包含元数据。当您引用被取代的产品时，请使用短 UUID。