VEX Array Functions

[robmoggach]

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 January 22, 2021 by robmoggach
fixed clobber bug

[snoot]

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 January 22, 2021 by snoot

[robmoggach]

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 January 22, 2021 by robmoggach

[robmoggach]

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

[kiryha]

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 January 23, 2021 by kiryha