☰

在 Asymptote 中搜索数组中的元素

tag-icon • tag-icon asymptote
在 Asymptote 中搜索数组中的元素

在渐近线中，我有两个数组

int[ ] a = {1, 2, 3, 4 };
int[] b = {2, 3 };

我想获取这两个数组的交集，即1, 4。我可以编写一个函数来执行此操作，但是有没有内置的替代方案。此外，search和find函数似乎具有非标准类型签名/行为。

int find(bool[], int n=1)

返回第 n 个真值的索引，如果未找到则返回 -1。如果 n 为负数，则从数组末尾向后搜索第 -n 个

我不知道如何使用它。理想情况下，我希望将键传递给 find，如果在数组中找到它，则返回 true，否则返回 false。

value; int search(T[] a, T key)

对于内置有序类型 T，在 n 个元素的排序数组 a 中搜索 k，如果 a[i] <= key < a[i+1]，则返回索引 i；如果 key 小于 a 的所有元素，则返回 -1；如果 key 大于或等于 a 的最后一个元素，则返回 n-1。

对于“大于或等于”真正奇数的键，这将返回 n-1。

答案1

总结当且仅当数组包含，则表达式find(a == 3) >= 0为。truea3

如果a已排序，则可以使用该search函数在两行中执行相同的操作；理论上这更快（O(log n)与相比O(n)，其中n的长度为a）：

int ii = search(a, 3);
bool a_contains_3 = (ii >= 0 && a[ii] == 3);

您可以在此处使用该find函数以及文档中的一条附加信息：

Asymptote 包含一整套用于算术（包括自身）和逻辑运算的矢量化数组指令。这些逐元素指令以 C++ 代码实现，以提高速度。鉴于

real[] a={1,2};
real[] b={3,2};

然后a == b和a >= 2都计算向量。要测试和{false, true}的所有分量是否 一致，请使用布尔函数。也可以使用条件语句，例如，返回数组，或 ，返回数组 {2}。aball(a == b)(a >= 2) ? a : b{3,2}(a >= 2) ? a : null

具体来说，a == 3将被广播，返回一个布尔数组，其索引i条目告诉您是否a[i] == 3。然后，按照问题中引用的行为，将返回等于 的find(a==3)第一个条目的索引，或者如果没有这样的条目。因此当且仅当数组包含元素时才返回。a3-1find(a == 3) >= 0truea2

使用此功能，您可以创建以下可能有效的相交函数（尽管我还没有实际测试以确保它能够正确编译或运行）：

int[] intersect(int[] a, int[] b) {
  int[] intersection;
  for (var w : a)
    if (find(b == w) >= 0) intersection.push(w);
  return intersection;
}

这是另一种方法，从大 O 符号的角度来看，它更快，但对于许多实际示例来说，它可能会更慢。（再次说明，我还没有测试以确保它能够编译，更不用说正常工作了。）

int[] intersect(int[] a, int[] b) {
  int sorted[], unsorted[], intersection[];
  // Sort the shorter array:
  if (a.length < b.length) {
    sorted = sort(a);  // Does not alter the original array.
    unsorted = b;
  } else {
    sorted = sort(b);  // Does not alter the original array.
    unsorted = a;
  }
  // Iterate through the longer array and save the elements that are also
  // in the shorter array.
  for (var w : unsorted) {
    int ii = search(sorted, w);
    if (ii >= 0 && sorted[ii] == w) intersection.push(w);
  }
  return intersection;
}

相关内容