Java Project Trouble: Searching one ArrayList with another ArrayList

[BC2210]

Hey,

To start out, basically, our program is supposed to fill up two ArrayLists with integers using 4 bytes from a binary file, then sort one list ascendingly, then search for the numbers contained in the second list in the first list, and ultimately display how many were found. I think there is something wrong with my searchList method.

Basically, the first arraylist is filled with {11, 2, 5, 1, 12, 3, 12, 7} and once I sort it, it becomes {1, 2, 3, 5, 7, 11, 12, 12}. The second arraylist (which doesnt have to be sorted) contains {2, 5, 12, 4}. Using my searchList method (which takes in the two arraylists as parameters) I am getting the wrong answer. It is saying that 4 of the 4 in arraylist2 are contained in arraylist1; when actually, only 3 of the 4 is in the first list.

My searchList method looks like this:

-------------------------------------------------------------------------------------------------------------------------------------------------

public String searchList(ArrayList first, ArrayList second)
{
long timeAtBeg = System.nanoTime();
int firstSize = first.size();
int secondSize = second.size();

while(current2 < secondSize)
{ 
Integer secondTemp = (Integer) second.get(current2);
int numberInSecondList = secondTemp.intValue();

for(int i=0; i<firstSize; i++)
{
Integer firstTemp = (Integer) first.get(i);
int numberInFirstList = firstTemp.intValue();

if(numberInFirstList == numberInSecondList)
{
numberContained++; 
current2++;
searchList(first, second);
}
}

current2++;
searchList(first, second);
}
long timeAtEnd = System.nanoTime();
long timeTaken = timeAtEnd - timeAtBeg;

return ("The second list contained " + numberContained + " of the same 
integers as the first list." + "\n" + "It took " + timeTaken + " nanoseconds to
find those " + numberContained + " ints.");
}

-------------------------------------------------------------------------------------------------------------------------------------------------

I couldnt figure out what it was doing, cause basically, its picking up the first number in the second list, searching the entire first list till it finds a match, and then moving on through till the end of the second list.

I did some trial and error by sticking in some print statements in the loops to see exactly what integers its comparing. I put a * next to the numbers in the second list, and a -- next to the integers from the first list...I came up with this...

The first list contains 8 integers.
The second list contains 4 integers.
The sort of the first list took 44977 nanoseconds.
2* <----first number of the second list
1-
2-
5* <-----second
1-
2-
3-
5-
12* <-----third
1-
2-
3-
5-
7-
11-
12-
4* <----last
1-
2-
3-
5-
7-
11-
12-
12-
12-
7-
11-
12-
12-
3-
5-
7-
11-
12-
12-
The second list contained 4 of the same integers as the first list.
It took 3044521 nanoseconds to find those 4 ints.

For some reason, it goes through on the first 3 till it finds the number, then moves on, but when it doesnt find the 4, it does something crazy and goes through the list over and under and backwards!!

Anybody know whats happening??

Thanks alot!

[sukatoa]

Debugging time!!!!

(just for me)
For some situations like this, i will do it step by step safely, not to code it all and test @ once....

Start on a small ArrayList.... if test is done and you're satisfied on the result, make it bigger and bigger, as you test it every changes made...

Just like logic circuits, when you just wire them all and not tracing each specific output, you might get stuck on its strange outputs.
unless you have an experience on it.
Instead, by moduling is safe and recommended by experts.

kind regards,
sukatoa

[Phoxtrot]

To use recursion with a mix of global variables and parameters is a call to disasters... To mix recursion and iteration is a call to disasters. To make different recursion calls at different syntaxic levels (once in an outer loop and once in an inner loop) is a call to disasters...

Not exiting a loop once a match has been found is generaly a bug (here your '12' is matched twice because it is present twice in the first list. Apparently this is not what you wanted, but anyone else reading your code would be hard pressed to know whether it is intended or not since you didn't comment your method with what it is supposed to do).

Since I Don't see current2 defined in your method, I gather it is a global variable (bad practice in general).

Your method starts a while loop to match each of the remaining object in the second list but it also makes a recursive call to also match the remaining objects in the second list minus the one just matched. This is incorrect, you iterate through a while loop (or similar) OR you make recursive calls. In your case, a second problem is the fact that your index current2 will be modified within the recursive call. When the deepest recursive calls returns, the code will resume to where the previous recursive call was made. When the previous recursive call was made at the end of the wile loop (no match found), the while loop will exit and you'll go back to the next previous place were a recursive call was made but when the previous recursive call was made within the inner loop, that loop will continue before the while loop is exited and this is where you see your strange results.

Bad coding conventions leads to code that is hard to understand and debug.

As a general practice, you should avoid using global variable when possible, definetly avoid mixing iteration and recursion, avoid recursion when possible.

if you replace

if(numberInFirstList == numberInSecondList)
{
numberContained++; 
current2++;
searchList(first, second);
}

by

if(numberInFirstList == numberInSecondList)
{
numberContained++; 
break;
}

It will work a lot better but it will still be poor programming:

-Code hard to understand
-Unnecessary recursion (leading to unnecessary complexity, unnecessary memory use as well as time lost in the useless calls)
-No javacode comments

Remove the other recursive call below as well and it will work even better though it will still be rather poor programming ( use of a global variable, no comments).

A proper name for the thread would be problem with mixing recursion and iteration :D