4

In asymptote, I have two arrays

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

I would like to get the intersection of these two arrays i.e 1, 4. I can write a function to do this, but is there a builtin alternative. Also search and find function seem to have non-standard type signature/behavior.

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

returns the index of the nth true value or -1 if not found. If n is negative, search backwards from the end of the array for the -nth

I don't know how to use it. Ideally i would like to pass the key to find and return true if it is found in array, else false.

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

For built-in ordered types T, searches a sorted array a of n elements for k, returning the index i if a[i] <= key < a[i+1], -1 if key is less than all elements of a, or n-1 if key is greater than or equal to the last element of a.

This return n-1 for a key "which is greater than or equal to" the key which is really odd.

4
  • 2
    find(a == 3) returns 2, the index of the first occurrence of 3 in a. find(a == 3) > 0 returns true iff a contains 3. Mar 18, 2016 at 17:24
  • I didn't know that one can use numpy like a == 3 . I'll try and let you know.
    – Dilawar
    Mar 19, 2016 at 6:22
  • @Charles: I just found your comment while trying to figure out how to find if an integer existed in an array of integers. Your code is very simple and useful and, as far as I can tell, not in the documentation. One correction though, is that one should use find(a == 3) > -1, because 0 is a valid index of the array.
    – James
    Jul 1, 2016 at 16:02
  • @James: You're correct -- I probably meant find(a == 3) >= 0. Technically the functionality is documented, but not in a particularly user-friendly way. (Search that page for the word 'vectorized'.) Jul 1, 2016 at 16:31

1 Answer 1

2

TL;DR The expression find(a == 3) >= 0 will be true iff the array a contains 3.

If a is sorted, you can do the same thing in two lines using the search function; theoretically this is faster (O(log n) versus O(n), where n is the length of a):

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

You can use the find function here with one additional piece of information from the documentation:

Asymptote includes a full set of vectorized array instructions for arithmetic (including self) and logical operations. These element-by-element instructions are implemented in C++ code for speed. Given

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

then a == b and a >= 2 both evaluate to the vector {false, true}. To test whether all components of a and b agree, use the boolean function all(a == b). One can also use conditionals like (a >= 2) ? a : b, which returns the array {3,2}, or (a >= 2) ? a : null, which returns the array {2}.

In particular, a == 3 will be broadcast, returning an array of booleans whose index i entry tells you whether a[i] == 3. Then, following the behavior quoted in the question, find(a==3) will return the index of the first entry of a equal to 3, or -1 if there is no such entry. So find(a == 3) >= 0 returns true iff the array a contains the element 2.

Using this, you can create the following intersect function that probably works (although I haven't actually tested to make sure it compiles or runs correctly):

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

Here's an alternate approach that is faster in terms of big-O notation, but probably slower for many practical examples. (Again, I haven't tested to make sure it compiles, much less works correctly.)

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;
}

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .