find something in a arrayList

Programming Questions

clankill3r

find something in a arrayList

in Programming Questions • 2 years ago

edit: see post 2!

i got a big list like this:

1.68187, 0.69608
2.39545, 0.71358
3.13236, 0.73691
3.86344, 0.73108
4.57216, 0.70872
5.29449, 0.72233
6.03335, 0.73886
6.78193, 0.74858
7.53829, 0.75636
8.24214, 0.70386
8.95864, 0.71650
9.66250, 0.70386
10.36539, 0.70289
11.07994, 0.71455
11.80616, 0.72622
12.48474, 0.67858
13.16915, 0.68441
13.87398, 0.70483
14.60798, 0.73400
15.35656, 0.74858
16.10708, 0.75052
16.89260, 0.78552
17.66063, 0.76802
18.42670, 0.76608
19.21028, 0.78358
19.96955, 0.75927
20.70063, 0.73108
21.42102, 0.72039
22.13654, 0.71552
22.84429, 0.70775
23.51996, 0.67567
24.13049, 0.61053
24.75171, 0.62122
25.37877, 0.62706
26.07290, 0.69414
26.81565, 0.74275
27.58075, 0.76511

Only then a few thousand more.

The first column contains time in seconds and the second interval value (of heartBeats).

To store everything i have a class named Sample which stores the time and interval.

All of those Sample objects are stored in a arraylist.

What i want to make now is a function like:

float time = 22;

float interval = getIntervalOfTime(float time)

Which should give the interval value of the closest time it could find.

I could loop over to find the closest value but this will be really slow.

Now i got something this:

float getIntervalOfTime(float timeToGet){
int minIndex = 0;
int maxIndex = samples.size();
int checkIndex = maxIndex/2;
while(minIndex != maxIndex){
println("minIndex "+minIndex +" maxIndex " + maxIndex + " checkIndex " + checkIndex);
delay(100);
if(timeToGet > samples.get(checkIndex).time){
minIndex = checkIndex;
} else if(timeToGet < samples.get(checkIndex).time){
maxIndex = checkIndex;
}
checkIndex = (maxIndex - minIndex)/2;
// to avoid endless repeating
// it doesnt return the correct one..
if(checkIndex < minIndex){
return samples.get(minIndex).getInterval();
} else if(checkIndex > maxIndex){
return samples.get(maxIndex).getInterval();
}
}
return samples.get(checkIndex).getInterval();
};

The println goes like this atm:

minIndex 0 maxIndex 3016 checkIndex 1508

minIndex 0 maxIndex 1508 checkIndex 754

minIndex 0 maxIndex 754 checkIndex 377

minIndex 0 maxIndex 377 checkIndex 188

minIndex 0 maxIndex 188 checkIndex 94

minIndex 0 maxIndex 94 checkIndex 47

minIndex 0 maxIndex 47 checkIndex 23

minIndex 0 maxIndex 23 checkIndex 11

Althought it is close, it returns the wrong one.

What goes wrong?

(also it makes my while check uselless, i also could do while(true == true) for example...

Replies(7)

clankill3r

Re: find something in a arrayList

2 years ago

struggled some more,

is this code good? (it does work atleast).

float getIntervalOfTime(float timeToGet){
int minIndex = 0;
int maxIndex = samples.size();
int checkIndex = maxIndex/2;
while(minIndex != maxIndex){
if(timeToGet > samples.get(checkIndex).time){
minIndex = checkIndex;
} else if(timeToGet < samples.get(checkIndex).time){
maxIndex = checkIndex;
}
checkIndex = minIndex + (maxIndex - minIndex)/2;
if(checkIndex == minIndex){
println("return by min");
// for some reason the maxIndex must be returned
return samples.get(maxIndex).getInterval();
}
}
// this will never happen i suppose
return -1;
};

PhiLho

Re: find something in a arrayList

2 years ago

This code uses the dichotomy algorithm, which is a good one when the data is sorted, like it looks to be here.

clankill3r

Re: find something in a arrayList

2 years ago

snap,

my data is not always sorted.

What is another method (i don't want to sort my arraylist everytime i call this function).

edit:

also it's bugged and i can't find it, it finds a lot correct (858 lines) and then it keeps hanging in a while lus.

Sample getSampleOfTime(float timeToGet){
int minIndex = 0;
int maxIndex = samples.size();
int checkIndex = maxIndex/2;
while(minIndex != maxIndex){
println("1 timeToGet " + timeToGet + " minIndex " + minIndex + " maxIndex " + maxIndex + " checkIndex " + checkIndex);
if(timeToGet > samples.get(checkIndex).time){
minIndex = checkIndex;
} else if(timeToGet < samples.get(checkIndex).time){
maxIndex = checkIndex;
}
checkIndex = minIndex + (maxIndex - minIndex)/2;
println("2 timeToGet " + timeToGet + " minIndex " + minIndex + " maxIndex " + maxIndex + " checkIndex " + checkIndex);
if(checkIndex == minIndex){
// for some reason the maxIndex must be returned
return samples.get(maxIndex);
}
}
// this will never happen i suppose
println("return null");
return null;
};

This is a part of the output.