优化具有许多元素和不同标准的数组
Optimizing array that has many elements and different standards
我有一个将 X 作为参数并从二维数组中随机选取一个元素的函数。
二维数组有上千个元素，每个元素对X都有不同的要求，存储在arr[Y][1].
例如，
arr[0] 只应在 X 大于 4 时选择。(arr[0][1] = 4+)
那么arr[33]只有当X在37到59之间才应该选择。(arr[33][1] = 37!59)
和arr[490]只有当X小于79时才应该选择。(arr[490][1] = 79-)
还有更多，大多数具有不同的 X 要求。
解决这个问题的最佳方法是什么 space，元素重复最少？
最糟糕的方法是将每个 X 的可能选择存储在二维数组中。但是这样会造成很多重复，占用太多内存。
然后，我想过用三个数组，把X+要求，X-和X范围分开。但这对我来说还是太基础了，有没有更好的方法？
这里的一个选项是所谓的 "accept/reject sampling"：您选择一个随机索引 i 并检查该索引是否满足 X 上的条件。如果是这样，你 return arr[i]。如果没有，你随机选择另一个索引并重复直到找到一些东西。
只要满足大多数i值的大多数条件，性能就会很好。如果不是这种情况——如果有很多 X 的值只满足很少的条件——那么尝试预先计算一些东西可能是有意义的这可以让你找到（或缩小）给定 X.
允许的索引
如何做到这一点取决于您允许什么作为每个索引的条件。例如，如果每个条件都由您给出的示例中的间隔给出，您可以对列表进行两次排序，首先按左端点，然后按右端点。然后确定特定 X 值的有效索引归结为将左端点小于或等于 X 的区间与右端点大于或等于 X 的区间相交。
当然，如果您允许 "X is in this interval" 以外的条件，那么您需要不同的算法。
虽然我相信重新采样将是您的最佳解决方案（数十次重新采样的代价非常低），但这是我在实践中永远不会实现的算法（因为它使用非常复杂的数据结构和效率低于重采样），但具有可证明的界限。每个查询需要 O(n log n) 预处理时间、O(n log n) 内存和 O(log n) 时间，其中 n 是您可能采样的元素数。
您将所有范围的所有端点存储在一个数组中（称之为 ends）。例如。在你的情况下你有一个数组 [-infty, 4, 37, 59, 79, +infty] （它可能需要一些调整，比如在范围的右端添加 +1 ；现在不重要）。这个想法是，对于任何 X 我们只需要确定它位于哪一端之间。例如。如果 X=62 在 [59; 79] 范围内（我将这样的对称为 interval）。然后对于每个间隔，您存储一组所有可能的范围。对于您的输入 X 您只需找到区间（使用二进制搜索），然后输出一个随机范围，对应于该区间。
如何计算每个间隔的相应范围集？我们在 ends 数组中从左到右。假设我们计算当前间隔的集合，然后转到下一个。这些间隔之间有一些结束。如果它是某个区间的左端，我们将相应的范围添加到新集合中（因为我们输入了这个范围）。如果它是右端，我们删除范围。我们如何在 O(log n) 时间内而不是 O(n) 内做到这一点？不可变平衡树集可以做到这一点（本质上，它们创建新树而不是修改旧树）。
如何 return 从集合中获得均匀随机的范围？您应该扩充树集：每个节点都应该知道其子树包含多少个节点。首先，您对 [0; size(tree)) 范围内的整数进行采样。然后查看根节点及其子节点。例如，假设您采样了整数 15，并且您的左子树的子树大小为 10，而右子树的大小为 20。然后您转到右子树（因为 15 >= 10）并用整数 5 处理它（因为 15 - 10 = 5).您最终将访问对应于单个范围的叶子。 Return这个范围。
抱歉，如果难以理解。就像我说的，在最坏的情况下，这不是你需要上限的简单方法（之前讨论的其他方法在最坏的情况下需要线性时间；如果没有元素满足限制，重新采样可能 运行 无限期） .它还需要一些小心处理（例如，当某些范围具有重合的端点时）。
我有一个将 X 作为参数并从二维数组中随机选取一个元素的函数。
二维数组有上千个元素，每个元素对X都有不同的要求，存储在arr[Y][1].
例如，
arr[0]只应在 X 大于 4 时选择。(arr[0][1] = 4+)那么
arr[33]只有当X在37到59之间才应该选择。(arr[33][1] = 37!59)和
arr[490]只有当X小于79时才应该选择。(arr[490][1] = 79-)还有更多，大多数具有不同的 X 要求。
解决这个问题的最佳方法是什么 space，元素重复最少？
最糟糕的方法是将每个 X 的可能选择存储在二维数组中。但是这样会造成很多重复，占用太多内存。
然后，我想过用三个数组，把X+要求，X-和X范围分开。但这对我来说还是太基础了，有没有更好的方法？
这里的一个选项是所谓的 "accept/reject sampling"：您选择一个随机索引 i 并检查该索引是否满足 X 上的条件。如果是这样，你 return arr[i]。如果没有，你随机选择另一个索引并重复直到找到一些东西。
只要满足大多数i值的大多数条件，性能就会很好。如果不是这种情况——如果有很多 X 的值只满足很少的条件——那么尝试预先计算一些东西可能是有意义的这可以让你找到（或缩小）给定 X.
允许的索引如何做到这一点取决于您允许什么作为每个索引的条件。例如，如果每个条件都由您给出的示例中的间隔给出，您可以对列表进行两次排序，首先按左端点，然后按右端点。然后确定特定 X 值的有效索引归结为将左端点小于或等于 X 的区间与右端点大于或等于 X 的区间相交。
当然，如果您允许 "X is in this interval" 以外的条件，那么您需要不同的算法。
虽然我相信重新采样将是您的最佳解决方案（数十次重新采样的代价非常低），但这是我在实践中永远不会实现的算法（因为它使用非常复杂的数据结构和效率低于重采样），但具有可证明的界限。每个查询需要 O(n log n) 预处理时间、O(n log n) 内存和 O(log n) 时间，其中 n 是您可能采样的元素数。
您将所有范围的所有端点存储在一个数组中（称之为 ends）。例如。在你的情况下你有一个数组 [-infty, 4, 37, 59, 79, +infty] （它可能需要一些调整，比如在范围的右端添加 +1 ；现在不重要）。这个想法是，对于任何 X 我们只需要确定它位于哪一端之间。例如。如果 X=62 在 [59; 79] 范围内（我将这样的对称为 interval）。然后对于每个间隔，您存储一组所有可能的范围。对于您的输入 X 您只需找到区间（使用二进制搜索），然后输出一个随机范围，对应于该区间。
如何计算每个间隔的相应范围集？我们在 ends 数组中从左到右。假设我们计算当前间隔的集合，然后转到下一个。这些间隔之间有一些结束。如果它是某个区间的左端，我们将相应的范围添加到新集合中（因为我们输入了这个范围）。如果它是右端，我们删除范围。我们如何在 O(log n) 时间内而不是 O(n) 内做到这一点？不可变平衡树集可以做到这一点（本质上，它们创建新树而不是修改旧树）。
如何 return 从集合中获得均匀随机的范围？您应该扩充树集：每个节点都应该知道其子树包含多少个节点。首先，您对 [0; size(tree)) 范围内的整数进行采样。然后查看根节点及其子节点。例如，假设您采样了整数 15，并且您的左子树的子树大小为 10，而右子树的大小为 20。然后您转到右子树（因为 15 >= 10）并用整数 5 处理它（因为 15 - 10 = 5).您最终将访问对应于单个范围的叶子。 Return这个范围。
抱歉，如果难以理解。就像我说的，在最坏的情况下，这不是你需要上限的简单方法（之前讨论的其他方法在最坏的情况下需要线性时间；如果没有元素满足限制，重新采样可能 运行 无限期） .它还需要一些小心处理（例如，当某些范围具有重合的端点时）。