getting the index of the closest value in an array that is sorted in reverse order

[Jon Swanson]

I am maintaining two arrays (x and y time series data) that I pass to an application to plot. I've now been asked to return the time given a specific value of the data. This works nicely with ArrayLists. I can do a binarySearch when the data increases over time and a binary search with a comparator when the data decreases with time. So far, so good- the following works:

import java.util.*;

class BSearchTest
{
   public static void main(String[] args)
   {
      ArrayList<Double> test = new ArrayList<Double>();
      test.add(1.1);
      test.add(1.4);
      test.add(1.7);
      test.add(2.1);
      test.add(2.5);
      test.add(2.9);

      System.out.println("ArrayList- forward order");
// Found at index = 3
      int index = Collections.binarySearch(test,2.1);
      System.out.println("2.1 at " + index);

// Found at index = -7
      index = Collections.binarySearch(test,4.1);
      System.out.println("4.1 at " + index);
 
// Found at index = -1
      index = Collections.binarySearch(test,0.5);
      System.out.println("0.5 at " + index);
 
// Found at index = -3
      index = Collections.binarySearch(test,1.5);
      System.out.println("1.5 at " + index);

      ArrayList<Double> tset = new ArrayList<Double>(); 
      tset.add(2.9);
      tset.add(2.5);
      tset.add(2.1);
      tset.add(1.7);
      tset.add(1.4);
      tset.add(1.1);

      Comparator<Double> comparator = Collections.reverseOrder();
      
      System.out.println("ArrayList- reverse order");
// Found at index = 2
      index = Collections.binarySearch(tset,2.1,comparator);
      System.out.println("2.1 at " + index);

// Found at index = -7
      index = Collections.binarySearch(tset,4.1,comparator);
      System.out.println("4.1 at " + index);

// Found at index -1
      index = Collections.binarySearch(tset,0.5,comparator);
      System.out.println("0.5 at " + index);
 
// Found at index = -1
      index = Collections.binarySearch(tset,1.5,comparator);
      System.out.println("1.5 at " + index);
   }
}

However, the program is time-sensitive and I have found ArrayList<Double> to be a lot slower than double[]. So I tried to create the equivalent with double[] arrays. That doesn't quite work. I know the problem, there is an Arrays.binarySearch(double[] a, double b) but not one with a comparator. For that I need to use objects.

I'm concerned if I go from double[] to Double[] I'll start taking the performance hits I saw with ArrayList<Double>. So can anyone tell me a) is there a better (fastest execution) way to find the index of the element closest to x in a double[] array and b) what sort of performance differences there might be between Double[] and double[]?

I am using the index to pull a value from another array. So I have two arrays I need to keep in synch. The plot package also requires two separate double[] to plot x,y data and I can't change that.

Doesn't compile

import java.util.*;

class BSearchTest
{
   public static void main(String[] args)
   {
      double[] atest = {1.1,1.4,1.7,2.1,2.5,2.9};
      double[] tseta = {2.9,2.5,2.1,1.7,1.4,1.1};
 
      System.out.println("Array- forward order");
// Found at index = -3
      index = Arrays.binarySearch(atest,1.5);
      System.out.println("1.5 at " + index);

      System.out.println("Array- reverse order");
      Comparator comparator = Collections.reverseOrder();
// Found at index = -1
      index = Arrays.binarySearch(tseta,1.5,comparator);
      System.out.println("1.5 at " + index);
   }
}

Best I have so far

import java.util.*;

class BSearchTest
{
   public static void main(String[] args)
   {
      Double[] atest = {1.1,1.4,1.7,2.1,2.5,2.9};
      Double[] tseta = {2.9,2.5,2.1,1.7,1.4,1.1};
 
      System.out.println("Array- forward order");
// Found at index = -3
      index = Arrays.binarySearch(atest,1.5);
      System.out.println("1.5 at " + index);

      System.out.println("Array- reverse order");
      Comparator<Double> comparator = Collections.reverseOrder();
// Found at index = -1
      index = Arrays.binarySearch(tseta,1.5,comparator);
      System.out.println("1.5 at " + index);
   }
}

[Winston Gutkowski]

Jon Swanson wrote:However, the program is time-sensitive and I have found ArrayList<Double> to be a lot slower than double[]. So I tried to create the equivalent with double[] arrays. That doesn't quite work. I know the problem, there is an Arrays.binarySearch(double[] a, double b) but not one with a comparator. For that I need to use objects.

I'm not sure you do (see below).

I'm concerned if I go from double[] to Double[] I'll start taking the performance hits I saw with ArrayList<Double>. So can anyone tell me a) is there a better (fastest execution) way to find the index of the element closest to x in a double[] array and b) what sort of performance differences there might be between Double[] and double[]?

It sounds like you have quite a few things going on here:
1. Access time per element.
2. Mutability of the array size.
3. Search time for a specific value.
(feel free to add any others that I've missed).

Dealing with them individually:
1. ArrayList should be close to an array for element retrieval. The only real overhead is the method call itself.
2. ArrayList's algorithm is about as good as it gets.
3. Double's compareTo() method is pretty quick. Again, the only real overhead is the method call itself.

The main issue with a List<Double>, as opposed to a double[] is that every element has to be converted. This adds time and space; and if you change values a lot, you have a double overhead (boxing/unboxing) every time it's done.

If searching is your only concern, you might want to check out the time difference between calling Arrays.binarySearch() on a double[] and a Double[]; but I'd be surprised if it's outlandishly different.

However, here's a possibility: create a MutableArray wrapper class that gives you access to all the internals of an array, but has an ensureSize() method that does the same thing that ArrayList does: increase the size of the array if it's too short.

You could also add a "view" class like this (filched from 'Effective Java'):

private static class DoublesAsList
	extends AbstractList<Double>
{
	private final double[] array;

	private DoublesAsList(double[] values) {
		super(values.length);
		this.array = values;
	}

	@Override public final Double get(int index) {
		return array[index];
	}

	// OPTIONAL - If you don't need it; don't include it
	@Override public final Double set(int index, Double val) {
		Double d = array[index];
		array[index] = val;
		return d;
	}

	@Override public final int size(int index) {
		return array.length;
	}
}

On its own, it doesn't help you much, but it provides you with another way of looking at (and optionally updating) the array.
Then anything that changes the array (eg, a sort), or searches it, can be done on the array itself, while anything that simply needs to view it can use the List (or its Iterators).

HIH

Winston

[Jon Swanson]

I think access time might be my biggest concern, not related to the particular look up, but for the whole package, of which doing these look ups is one piece. I started out using ArrayLists, since I will not know the eventual size of the arrays. But the main function that I wrote was taking 14/1000 of a second to run. The values are not changed often, by they are iterated over multiple times. When I changed the function to use double[] where I had used ArrayList<Double> the function ran in 4/1000 of a second. This only matters because the function is used in a Monte Carlo estimator, and is called 1K - 10K times. Which means 14 or 4 seconds and now it is a bigger deal. The client wants the 4 second run time reduced to 0.4 seconds, which at the moment does not seem realistic. But on the other hand, I don't want to increase it with these look ups more than I have to. Plus I am a little concerned if I am maintaining an ArrayList and an Array and using one or the other at different points, I'm asking for bugs or at least maintenance issues.

Here are the timing tests on the ArrayList<Double>, Double[] and double[], just doing the search. I created an array of 1000 elements with values from 0 to 999 and searched for 25.5, 500.1 and 975.9. The worst performance was for 25.5, so I will report that.

ArrayList<Double> 72 ms forward 28 ms reverse
Double[] 48 ms forward 19 ms reverse
double[] 10 ms forward reverse does not work

the average values are

ArrayList<Double> 30 ms forward 14 ms reverse
Double[] 19 ms forward 11 ms reverse
double[] 5 ms forward reverse does not work

so... double[] is faster, as I found with my other code. If I run a bunch of times, reverse is always faster, but ArrayList<Double> and Double[] average to more similar times, Double[] being a little bit faster. But double[] is consistently faster than the other two and also more consistent in the time reported. Which gets me back to the fact that binarySearch does not accept a comparator when the first argument is a double[] so I need some workaround to use double[] when sorted in descending order.

I'm tempted to just keep two more arrays- the x values in reverse order and the y values in reverse order and use those if the x values decrease with time.

[Winston Gutkowski]

Jon Swanson wrote:Here are the timing tests on the ArrayList<Double>, Double[] and double[], just doing the search. I created an array of 1000 elements with values from 0 to 999 and searched for 25.5, 500.1 and 975.9. The worst performance was for 25.5, so I will report that.

ArrayList<Double> 72 ms forward 28 ms reverse

Wow. 72 milliseconds? Are you sure you're doing a binary search? I ran a test search on 100,000 random Doubles in an ArrayList, and it came in at 450 nanoseconds (averaged over 10,000,000 searches) on my clunky old Dell.

Makes me wonder if there might be something else wrong.

Winston

[Jon Swanson]

Sorry, I have gotten in such a habit of multiplying by 1000 to estimate the MC times I did that automatically. It is taking 72 usec not msec. Still that is a lot longer than what you are seeing. This is what I did:

import java.util.*;

class BSearchTimingTest
{
   public static void main(String[] args)
   {
      ArrayList<Double> test = new ArrayList<Double>();
      ArrayList<Double> tset = new ArrayList<Double>();

      Double[] dtest = new Double[1000];
      Double[] tsetd = new Double[1000];

      double[] atest = new double[1000];
      double[] tseta = new double[1000];

      long startTime;
      long endTime;

      for (int i = 0; i < 1000; i++)
      {
         test.add((double) i );
         dtest[i] = (double) i;
         atest[i] = (double) i;
         tset.add((double)(1000-i-1) );
         tsetd[i] = (double)(1000-i-1);
         tseta[i] = (double)(1000-i-1);
      }

      System.out.println("ArrayList- forward order");

      startTime = System.nanoTime();
      int index = Collections.binarySearch(test,25.5);
      endTime   = System.nanoTime();
      System.out.println("\tTime: " + (endTime - startTime));
      System.out.println("25.5 at " + index);

      startTime = System.nanoTime();
      index = Collections.binarySearch(test,500.1);
      endTime   = System.nanoTime();
      System.out.println("\tTime: " + (endTime - startTime));
      System.out.println("500.1 at " + index);

      startTime = System.nanoTime();
      index = Collections.binarySearch(test,975.9);
      endTime   = System.nanoTime();
      System.out.println("\tTime: " + (endTime - startTime));
      System.out.println("975.9 at " + index);

      Comparator<Double> comparator = Collections.reverseOrder();
      
      System.out.println("ArrayList- reverse order");

      startTime = System.nanoTime();
      index = Collections.binarySearch(tset,25.5,comparator);
      endTime   = System.nanoTime();
      System.out.println("\tTime: " + (endTime - startTime));
      System.out.println("25.5 at " + index);

      startTime = System.nanoTime();
      index = Collections.binarySearch(tset,500.1,comparator);
      endTime   = System.nanoTime();
      System.out.println("\tTime: " + (endTime - startTime));
      System.out.println("500.1 at " + index);

      startTime = System.nanoTime();
      index = Collections.binarySearch(tset,975.9,comparator);
      endTime   = System.nanoTime();
      System.out.println("\tTime: " + (endTime - startTime));
      System.out.println("975.9 at " + index);
//
// Using arrays instead of arrayList
//
      System.out.println("Double Array- forward order");

      startTime = System.nanoTime();
      index = Arrays.binarySearch(dtest,25.5);
      endTime   = System.nanoTime();
      System.out.println("\tTime: " + (endTime - startTime));
      System.out.println("25.5 at " + index);

      startTime = System.nanoTime();
      index = Arrays.binarySearch(dtest,500.1);
      endTime   = System.nanoTime();
      System.out.println("\tTime: " + (endTime - startTime));
      System.out.println("500.1 at " + index);

      startTime = System.nanoTime();
      index = Arrays.binarySearch(dtest,975.9);
      endTime   = System.nanoTime();
      System.out.println("\tTime: " + (endTime - startTime));
      System.out.println("975.9 at " + index);

      System.out.println("Double Array- reverse order");

      Comparator<Double> comparatora = Collections.reverseOrder();

      startTime = System.nanoTime();
      index = Arrays.binarySearch(tsetd,25.5,comparatora);
      endTime   = System.nanoTime();
      System.out.println("\tTime: " + (endTime - startTime));
      System.out.println("25.5 at " + index);

      startTime = System.nanoTime();
      index = Arrays.binarySearch(tsetd,500.1,comparatora);
      endTime   = System.nanoTime();
      System.out.println("\tTime: " + (endTime - startTime));
      System.out.println("500.1 at " + index);

      startTime = System.nanoTime();
      index = Arrays.binarySearch(tsetd,975.9,comparatora);
      endTime   = System.nanoTime();
      System.out.println("\tTime: " + (endTime - startTime));
      System.out.println("975.9 at " + index);
   }
}

Nothing fancy at all. For my really long processes, i.e. seconds, it seems to be reporting timings that are consistent to what I observe in practice. Would you be willing to run it on your old Dell? Or should I add some loops around each binarySearch to get a more accurate average time?

[Winston Gutkowski]

Jon Swanson wrote:Nothing fancy at all. For my really long processes, i.e. seconds, it seems to be reporting timings that are consistent to what I observe in practice. Would you be willing to run it on your old Dell? Or should I add some loops around each binarySearch to get a more accurate average time?

I would certainly do that, because I suspect you're running into the Heisenberg principle. Simply put, measuring the time something takes takes time, and so affects the result (a call to System.nanoTime() takes 70-100ns on my machine); so the easiest way to eliminate that is to run the "thing to measure" a lot of times and take the mean of the total elapse time divided by the number of calls. I've actually written a Stopwatch class to do precisely that.

BTW, my test (other than running each search 10,000,000 times) was similar in effect to yours, except that I added 100,000 random double values and then sorted the result before searching. I also used 0.5 as my search value, which was unlikely to be found (theoretically, the worst case; although it's possible the compiler could optimize the constant).

If I see anything else, I'll get back to you, but even 72µs seems an awful lot - about 150 times slower than what I'm seeing for your worst case (ArrayList<Double>).

Winston

[Jeff Verdegan]

I second Winston's advice: Put LOTS of searches inside your timing loop. For what it's worth, here's my attempt. In a list/array of 10,000,000 elements, I did 10,000 searches for each of 2,000 random values (20,000,000 calls to binarySearch()), half of which were in the list and half of which were not, with the search values shuffled to a random order.

A single call to binarySearch() on an array took about 5ns.
A single call to binarySearch() on a List took about 19ns, whether forward or backward. So, yes, slower, but not by an order of magnitude, and not enough to cause me concern. As Winston already pointed out, it's just a little overhead for unboxing and method invocations.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Random;

public class Scratch {
    public static void main(final String[] args) throws Exception {
        int numElements =  10 * 1000 * 1000;
        int numIters = 10 * 1000;

        long start;
        long end;
        long elapsed;
        double millisPerSearch;
        double nanosPerSearch;

        List<Double> list1 = new ArrayList<Double>(numElements);
        double[] arr1 = new double[numElements];

        List<Double> list2;
        double[] arr2 = new double[numElements];

        List<Double> targetList = new ArrayList<Double>();
        double[] targetArr;
        Random rand = new Random();

        // populate and sort forward list and its equivalent array
        for (int i = 0; i < numElements; i++) {
            list1.add(rand.nextDouble());
        }
        Collections.sort(list1);
        for (int i = 0; i < arr1.length; i++) {
            arr1[i]= list1.get(i);
        }
        
        // populate the reverse list and array
        list2 = new ArrayList<Double>(list1);
        Collections.reverse(list2);
        for (int i = 0; i < arr2.length; i++) {
            arr1[2]= list2.get(i);
        }

        // populate and shuffle list of elements to search for
        for (int i = 0; i < 1000; i++) {
            targetList.add(list1.get(rand.nextInt(numElements)));
            targetList.add(rand.nextDouble());
        }
        Collections.shuffle(targetList);
        targetArr = new double[targetList.size()];
        for (int i = 0 ; i < targetArr.length; i++) {
            targetArr[i] = targetList.get(i);
        }

        // search in forward list
        start = System.currentTimeMillis();
        for (int i = 0; i < numIters; i++) {
            for (Double d : targetList) {
                Collections.binarySearch(list1, d);
            }
        }
        end = System.currentTimeMillis();
        elapsed = end - start;
        millisPerSearch = ((double)elapsed) / (numElements * numIters);
        nanosPerSearch = millisPerSearch * 1000.0 * 1000.0;
        System.out.println("FORWARD LIST");
        System.out.println("list size: " + list1.size());
        System.out.println("target size: " + targetList.size());
        System.out.println("num iters: " + numIters);
        System.out.println("elapsed millis: " + elapsed);
        System.out.println("nanosPerSearch: " + nanosPerSearch);

        System.out.println();

        // search in forward array
        start = System.currentTimeMillis();
        for (int i = 0; i < numIters; i++) {
            for (double d : targetArr) {
                Arrays.binarySearch(arr1, d);
            }
        }
        end = System.currentTimeMillis();
        elapsed = end - start;
        millisPerSearch = ((double)elapsed) / (numElements * numIters);
        nanosPerSearch = millisPerSearch * 1000.0 * 1000.0;
        System.out.println("FORWARD ARRAY");
        System.out.println("list size: " + list1.size());
        System.out.println("target size: " + targetList.size());
        System.out.println("num iters: " + numIters);
        System.out.println("elapsed millis: " + elapsed);
        System.out.println("nanosPerSearch: " + nanosPerSearch);

        System.out.println();

        // search in reverse list
        start = System.currentTimeMillis();
        for (int i = 0; i < numIters; i++) {
            for (Double d : targetList) {
                Collections.binarySearch(list2, d, Collections.reverseOrder());
            }
        }
        end = System.currentTimeMillis();
        elapsed = end - start;
        millisPerSearch = ((double)elapsed) / (numElements * numIters);
        nanosPerSearch = millisPerSearch * 1000.0 * 1000.0;
        System.out.println("REVERSE LIST");
        System.out.println("list size: " + list1.size());
        System.out.println("target size: " + targetList.size());
        System.out.println("num iters: " + numIters);
        System.out.println("elapsed millis: " + elapsed);
        System.out.println("nanosPerSearch: " + nanosPerSearch);

        System.out.println();
    }
}

FORWARD LIST
list size: 10000000
target size: 2000
num iters: 10000
elapsed millis: 22649
nanosPerSearch: 18.629618888649308

FORWARD ARRAY
list size: 10000000
target size: 2000
num iters: 10000
elapsed millis: 6500
nanosPerSearch: 5.346484294062453

REVERSE LIST
list size: 10000000
target size: 2000
num iters: 10000
elapsed millis: 24151
nanosPerSearch: 19.865068028600355

[Campbell Ritchie]

Jeff Verdegan wrote: . . .
nanosPerSearch: 5.346484294062453
. . .
nanosPerSearch: 19.865068028600355 . . .

You’re sure it wan’t 5.34649 and 18.866 ns?

I think this is now too complicated for “beginning” and shall move it.

[Jon Swanson]

Thanks for running the tests for me. I wrapped the binarySearch in a loop and then looked at the worst case times on my arrays of 1000 numbers.

   n            ArrayList<Double>   double[]

1000000             75                  44
 100000            292                 170
  10000           1256                 340
   1000           3790                 865
    100           4764                1006
     10          10898                1808
      1          67442               10263

I hadn't realized the overhead of the time call would be so high. But what seems odd is that the ratio of the time to use the ArrayList to the time to use the double array decreases with the number of iterations. It makes me think that there is some optimization going on that contaminates the benchmark. The ratio of 19/5 Jeff provided is pretty consistent with the other application I was running that used ArrayList<Double> versus double[]. Though that required a lot more calculations and the difference in run time was about 14 seconds versus 4 seconds (I really mean seconds this time). That required a lot of arrays and accessing the array elements a lot of times. So whether a difference of 19 ns versus 5 ns matters depends on how many times the calculation is run. At least the problem is not my computer. You had me worried I had a virus.

My loop includes the assignment of the return value to index. I was wondering if that mattered. If I take that out-

   n            ArrayList<Double>   double[]

1000000              66                  48
 100000             268                 146
  10000            1334                 343
   1000            4293                 852
    100            5273                1006
     10           10067                2590
      1           71352               12217

the variability from run to run seems higher than the difference between actually assigning the result to a variable or not.

[Winston Gutkowski]

Jon Swanson wrote:Thanks for running the tests for me. I wrapped the binarySearch in a loop and then looked at the worst case times on my arrays of 1000 numbers.

I hate to say, but I think you're looking at this far too simplistically. You assume that a call to x() takes half the time of two calls to x() and it simply isn't true.
The machine you're running on has LOTS of things (the vast majority of which, neither you nor I need to know about) to do other than running your test. And if it didn't, it wouldn't be a proper test would it?

I ran my 10,000,000 search tests several times before I gave you my results, and I'm sure Jeff did with his too. But at the end of the day, it's all hogwash. Our tests are based on the machine spending most of its time doing our test, which is far from likely in the real world.

My advice: Look to your code. 72 microseconds for a search? Please. Are you running this on a Sinclair?

Winston

[Jon Swanson]

The timings that Jeff provided are pretty consistent with the timing differences I see in the complete code (which runs 14 or 4 seconds depending on whether array lists or arrays are used). So I think I will stick with arrays for now. Since there does not seem to be an option to binary search an array sorted in reverse order, I think I will just use the rate constant to determine if I have data that increases or decreases with time and create new arrays that are in reverse order at the start. I can binary search those and use the other arrays for plots.