Jump to content
robmoggach

VEX Array Functions

Recommended Posts

Harder, Better, Faster, Stronger please!

Looking for some voodoo to optimize these snippets...

Find Unique Elements in One Array

function int[] unique_elements (int arr[]) {
    int _arr[] = sort(arr);
    for (int i=0; i<len(_arr); i++) {
        while(_arr[i] == _arr[i+1]) pop(_arr,i);
    }
    return _arr;
}

Get Duped Elements in One Array

function int[] duped_elements (int arr[]) {
    int _arr[] = sort(arr);
    int result[] = {};
    int dupe;
    for (int i=0; i<len(_arr); i++) {
        while(_arr[i] == _arr[i+1]) {
            dupe = pop(_arr,i);
        }
        append(result, dupe);
    }
    return result;
}

Find Common Elements in Two Arrays

function int[] common_elements (int arr1[]; int arr2[]) {
    int result[];
    foreach (int i; unique_elements(arr1)) {
        foreach (int j; unique_elements(arr2)) {
            if (i==j) push(result,j);
        }
    }
    return result;
}

Find Different Elements in Two Arrays

function int[] different_elements (int arr1[]; int arr2[]) {
    int result[];
    int _arr1[] = unique_elements(arr1);
    int _arr2[] = unique_elements(arr2);
    foreach(int i; _arr1) {
        if(find(_arr2,i)<0) append(result,i);
    }
    foreach(int j; _arr2) {
        if(find(_arr1,j)<0) append(result,j);
    }
    return result;
}

Swap Arrays

function int[] swap (int arr1[]; int arr2[]) {
    int temp[] = arr1;
    arr1 = arr2;
    arr2 = temp;
    return {1};
}

Here's some of what I was using to test it... these are all based on arrays of integers but could be tweaked obviously for other types.

i[]@arr1 = {3, 2, 15, 27, 1, 3}; 
i[]@arr2 = {3, 2, 3, 15, 41, 41, 1, 2, 2}; 
i[]@arr_comm = common_elements (@arr1, @arr2); 
i[]@arr_diff = different_elements (@arr1, @arr2); 
i[]@arr_uniq = unique_elements (@arr1); 
i[]@arr_dupe = duped_elements (@arr2); 

 

Edited by robmoggach
fixed clobber bug

Share this post


Link to post
Share on other sites

Regarding "unique elements".

I would:

1.Sort the input array. 2. Loop over it checking if the previous iteration's element matches the current iteration's element.  3. If it didn't append.

Essentially all identical elements will always be neighbours by sorting. I forget, but there are functions that will help you restore the original order if that is important.

In my experience avoid using vex's find function.  I found it quite slow in the situations I used it. 

Hope this helps.

Edited by snoot
  • Thanks 1

Share this post


Link to post
Share on other sites
3 hours ago, snoot said:

Regarding "unique elements".

I would:

1.Sort the input array. 2. Loop over it checking if the previous iteration's element matches the current iteration's element.  3. If it didn't append.

Essentially all identical elements will always be neighbours by sorting. I forget, but there are functions that will help you restore the original order if that is important.

In my experience avoid using vex's find function.  I found it quite slow in the situations I used it. 

Hope this helps.

 

Updated the first and second functions to use the sort method. Thanks for the tip.

Edited by robmoggach

Share this post


Link to post
Share on other sites

maybe these should likely follow vex/houdini nomenclature and change "element" to "comp" for "component"...???

Share this post


Link to post
Share on other sites

Interesting... I don't have a particular solution, but in general, if you will be able to avoid nested loops (which complexity is O(n^2)) it will increase the algorithm speed.
E.g. "Find Different Elements in Two Arrays" twice faster than "Find Common Elements in Two Arrays". And keep in mind that sorting also takes time.

Higher speed can be reached by the cost of higher memory usage (you can store results in a variable/hash table and check them before the next calculation).

You may find some ideas here: https://leetcode.com/problems/intersection-of-two-arrays/solution/

Though on arrays of such length you would not notice any difference.

Edited by kiryha

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

×