Quote:
Originally Posted by kamocat
I have two small arrays of integers. (I don't expect more than 16 elements in each array) No integer occurs more than once in an array. Integers are sorted from least to greatest, though they are not necessarily consecutive.
|
With only 16 elements, the major factor in performance is going to be the implementation details rather than the actual algorithm so the following is more of an academic exercise. You probably won't notice any kind of difference in run time.
Leveraging the facts that a) the arrays are already sorted and b) there are no repetitions in the individual arrays, you can use a stack-matching algorithm. This will run in O(max(n,m)) time instead of the naive methods which will run O(n*m) for arrays sizes n and m. Here's implementations in C and Java.
Code:
#include <stdlib.h>
#include <stdio.h>
/* Selects the unique elements between two arrays
*
* in1 is the first array
* in1end is the pointer to past the end of the first array
* in2 is the second array
* in2end is the pointer to past the end of the second array
* out1 is the first output array
* out2 is the second output array
*
* returns the number of common elements, so
* length(out1) = length(in1) - result;
* length(out2) = length(in2) - result;
*/
int unique(register int *in1, int *in1end, int *in2, int *in2end, int *out1, int *out2)
{
register int common = 0;
register int val1 = *in1, val2 = *in2;
for(;;)
{
if (val1 < val2)
{
*(out1++) = val1;
if (++in1 > in1end)
break;
val1 = *in1;
}
else if (val1 > val2)
{
*(out2++) = val2;
if (++in2 > in2end)
break;
val2 = *in2;
}
else
{
common++;
if ((++in1 > in1end) || (++in2 > in2end))
break;
val1 = *in1;
val2 = *in2;
}
}
while(in1 < in1end)
*(out1++)=*(in1++);
while(in2 < in2end)
*(out2++)=*(in2++);
return common;
}
int main(int argc, char *argv[])
{
int *arr1, *arr2, *out1, *out2;
int i, common, len1, len2;
if (argc!=3)
{
printf("Usage: %s <first length> <second length>\n", argv[0]);
return 1;
}
/* read lengths */
len1 = atoi(argv[1]);
len2 = atoi(argv[2]);
/* allocate array space */
arr1 = malloc(len1*sizeof(int));
out1 = malloc(len1*sizeof(int));
arr2 = malloc(len2*sizeof(int));
out2 = malloc(len2*sizeof(int));
/* create two arrays of strictly increasing elements */
srand ( time(NULL) );
arr1[0] = rand() % 3;
for(i=1; i < len1; i++)
arr1[i] = arr1[i-1] + (rand()%3)+1;
arr2[0] = rand() % 3;
for(i=1; i < len2; i++)
arr2[i] = arr2[i-1] + (rand()%3)+1;
/* print initial contents of the arrays */
printf("\nArray 1\n");
for(i=0; i < len1; i++)
printf("%d\n", arr1[i]);
printf("\nArray 2\n");
for(i=0; i < len2; i++)
printf("%d\n", arr2[i]);
/* run algorithm */
common = unique(arr1, arr1+len1, arr2, arr2+len2, out1, out2);
/* print results */
printf("\n%d common elements\n", common);
printf("\nArray 1\n");
for(i=0; i < len1-common; i++)
printf("%d\n", out1[i]);
printf("\nArray 2\n");
for(i=0; i < len2-common; i++)
printf("%d\n", out2[i]);
/* free memory */
free(arr1);
free(arr2);
free(out1);
free(out2);
}
Code:
import java.util.Arrays;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.Random;
public class Unique<E extends Comparable<E>>
{
private ArrayList<E> out1, out2;
public Unique(E[] in1, E[] in2)
{
int len1 = in1.length;
int len2 = in2.length;
out1 = new ArrayList<E>(len1);
out2 = new ArrayList<E>(len2);
Iterator<E> it1 = Arrays.asList(in1).iterator();
Iterator<E> it2 = Arrays.asList(in2).iterator();
E cur1 = it1.next();
E cur2 = it2.next();
for(;;)
{
int comp = cur1.compareTo(cur2);
if (comp < 0)
{
out1.add(cur1);
if (!it1.hasNext())
{
out2.add(cur2);
break;
}
cur1 = it1.next();
}
else if (comp > 0)
{
out2.add(cur2);
if (!it2.hasNext())
{
out1.add(cur1);
break;
}
cur2 = it2.next();
}
else
{
if (!it1.hasNext() || !it2.hasNext())
break;
cur1 = it1.next();
cur2 = it2.next();
}
}
while(it1.hasNext())
{
out1.add(it1.next());
}
while(it2.hasNext())
{
out2.add(it2.next());
}
}
public ArrayList<E> getOut1()
{
return out1;
}
public ArrayList<E> getOut2()
{
return out2;
}
public static void main(String[] args)
{
if (args.length!=2)
{
System.err.println("Usage: java Unique <first length> <second length>");
return;
}
/* read lengths */
int len1 = Integer.parseInt(args[0]);
int len2 = Integer.parseInt(args[1]);
/* allocate array space */
Integer[] arr1 = new Integer[len1];
Integer[] arr2 = new Integer[len2];
/* create two arrays of strictly increasing elements */
Random rand = new Random();
arr1[0] = rand.nextInt(3);
for(int i=1; i < len1; i++)
arr1[i] = arr1[i-1] + rand.nextInt(3)+1;
arr2[0] = rand.nextInt(3);
for(int i=1; i < len2; i++)
arr2[i] = arr2[i-1] + rand.nextInt(3)+1;
/* print initial contents of the arrays */
System.out.print("Array 1: ");
System.out.println(Arrays.toString(arr1));
System.out.print("Array 2: ");
System.out.println(Arrays.toString(arr2));
System.out.println();
/* run algorithm */
Unique<Integer> u = new Unique<Integer>(arr1, arr2);
/* print results */
System.out.print("Array 1: ");
System.out.println(u.getOut1());
System.out.print("Array 2: ");
System.out.println(u.getOut2());
}
}
Theoretically might run faster with a big array, but leads to a little messier code than, say, [buildmaster5000]'s
EDIT: Just read [Chris27]'s post again. I think I'm doing the same thing he is, just entirely iteratively instead of the combination iterative/recursive approach he took.
--Ryan