algorithm - 从多组任意项目中挑选项目时最大限度地减少重复项

Question

由于我不确定如何表达这个问题，我将用一个与我想要实现的非常相似的例子来说明它。

我正在寻找一种方法来优化执行以下任务所需的时间。

假设我有三组标记为“A”、“B”和“C”的数字，每组包含任意数量的整数。

我收到一堆要求“包”数字的订单，每个订单都要求特定的整数组合，每组一个。因此，订单可能看起来像“A3、B8、C1”，这意味着我需要从 A 组中取出 3，从 B 组中取出 8，从 C 组中取出 1。

任务很简单:拿一个订单，查看数字，然后去收集它们并将它们放在一个“包裹”中。

我需要一些时间来收集号码，而且经常有一个订单要求提供与之前订单相同的号码，所以我决定存储所有包裹以备日后检索；这样一来，我处理重复订单所需的时间就会大大减少，而不必再去收集相同的号码。

取号的时间比较长，但如果我当天订单很多的话，还不如一个一个检查一个包裹那么长。

例如，如果我有以下几组数字和订单

set A: [1, 2, 3]set B: [4, 5, 6, 12, 18]set C: [7, 8]Order 1: A1, B6, C7Order 2: A3, B5, C8Order 3: A1, B6, C7

我会为订单 1 和 2 打包，但后来我注意到订单 3 是重复订单，所以我可以选择只拿我为第一个订单打包的包裹并快速完成最后一个订单。

目标是优化处理一堆订单所花费的时间。目前我想到了两种方法，但也许还有更多的方法可以做事

1. 收集每个订单的编号，无论它是否重复。最后我得到了很多包裹，在极端情况下，有人批量订购 50 个相同的包裹，这显然是浪费时间

2. 检查包是否已存在于缓存中，也许对订单使用某种哈希方法。

有什么想法吗？

Answer 1

没有详细说明如何获取数据以组成包等。这使得很难针对您的问题提出不同的解决方案。例如，现有的包可能会引导您找到组成新包所需的数据，尽管它们在某种程度上有所不同。为此，实际上有可用的专用哈希方法，如局部敏感哈希。

考虑到您提出的两种方法，选择路线 2 听起来很自然。索引中的散列听起来微不足道(一阶很容易通过数字 167 或字符串“167”识别，对吗？)因此使用散列不会有任何真正的缺点。也许是内存限制，因为您需要保留旧包。还有一些常用方法可以定义哪些包要保留在(散列)缓存中，哪些要丢弃。