Question about sorting an arrayList of arrayLists

Eluxiver

I have a large arrayList with small arrayList as objects like this:

ArrayList<ArrayList<Float>> bigList = new ArrayList<ArrayList<Float>>();

the smaller arrayList has three values and I want to sort the big arraylist (bigList) according to the second value of the smaller arrayList. I thought I found a good solution with overriding the sort function (from Collections) like this:

Collections.sort(bigList, new Comparator<ArrayList<Float>>() {
            Override 
            public int compare(ArrayList<Float> first, ArrayList<Float> second) {
              return first.get(1).compareTo(second.get(1));
            }
          });

This sorts them correctly but there is a bias towards the later added elements in the big arrayList, if the values are the same (that is, the second values of the small arrayList), then it sorts them according to their original location (in the big arraylist).

I changed it to this:

Collections.sort(gridIndivInfo, new Comparator<ArrayList<Float>>() {
            Override 
            public int compare(ArrayList<Float> first, ArrayList<Float> second) {
              if (first.get(1).compareTo(second.get(1)) == 0){
                if (random(1) >= 0.5) return 1;
                else return -1;
              }
              else return first.get(1).compareTo(second.get(1));
            }
          });

Is this the correct way (or the most efficient way?)

Thanks

koogs

my first thought is to just change the compare() to compare two random numbers if the initial compareTo returns 0 (ie they are equal). but i don't think that's legal as the compareTo() has to return a consistent result for the same inputs (because the sort call might call it more than once with same inputs and returning a different result might cause errors?)

(the bias you talk about towards the later values isn't really bias but the sort's stability - you don't (usually) want it to rearrange equal entries because that would be chaos. your random presort would fix this. Collections has a shuffle() method...)

koogs

(shuffle is 0(n) so not that expensive)

Eluxiver

Ok thanks for the explanation,

I don't think that I my case I would get in trouble if I use the random solution, in this case it doesn't matter if the outcome of checking the same values twice gives another output.

If the shuffle is 0(n) I can do this too, but I think I'll use the random solution for now

koogs

you can assign that compare() to a local variable btw, save calculating it twice...

int result = first.get(1).compareTo(second.get(1));
if (result == 0) {
  result = -1 + 2 * (int)(random(2)); // -1 or +1
}
return result;

(untested)

GoToLoop

Don't forget Processing comes w/ its own FloatList: (*)
http://processing.org/reference/FloatList.html

quark

If you shuffle the collection to mix them all up then use your original sort method, then the order of 'equal' value lists is unpredictable.

koogs

my understanding is that's what he wants 8) - a random element from the set of things with the lowest middle number. he's currently getting the earliest element from the set of things with the lowest middle number and that's not random enough.

quark

@koogs I have read this topic several times now and I can't find any reference to selecting a random element from the small list :-?

Have I missed something?

The crux of the problem appears to be

I want to sort the big arraylist (bigList) according to the second value of the smaller arrayList.

and (@Eluxiver) would prefer 'equal' small-lists to be in a random sequence within the ordered lists.

By shuffling the large-list then sorting it would do to same as the "comparitor + random" code in the first post.

GoToLoop

Here's my attempt solution: ;;)

// forum.processing.org/two/discussion/1389/
// question-about-sorting-an-arraylist-of-arraylists

import java.util.Collections;
import java.util.Comparator;

final ArrayList<float[]> bigList = new ArrayList();

final Comparator<float[]> compBy2nd = new Comparator<float[]>() {
  int compare(float[] f1, float[] f2) {
    return (int) Math.signum(f2[1] - f1[1]);
  }
};

void setup() {
  initBigList(10, 3, 100);
  shuffleAndSortBy2nd();

  for (float[] bl: bigList) {
    println(bl);
    println();
  }

  exit();
}

void initBigList(int num, int elem, int rnd) {
  int i = 0;

  while (i != num) {
    bigList.add(new float[elem]);
    final float[] bl = bigList.get(i);

    for (int j = 0; j != elem; bl[j++] = random(rnd));

    println("\n#" + i++);
    println(bl);
  }

  println();
}

void shuffleAndSortBy2nd() {
  Collections.shuffle(bigList);
  Collections.sort(bigList, compBy2nd);
}

koogs

quarks, you might be right re the description. reading it back it doesn't say what i thought it did (and there's no edit in the edit log for it). but the random call is there in the code, and that makes it clear (to me) (actually, i could swear that wasn't there when i wrote my answer, it means mine's too much of a repeat of the original post)

BUT what i said about the comparator having to return a consistent value when comparing the same two objects is true (plus other rules)* and that effectively forbids using random() in the compare. the pre-randomisation means you don't need to.

• Method Detail for compare() here http://docs.oracle.com/javase/7/docs/api/java/util/Comparator.html

GoToLoop

and that effectively forbids using random() in the compare.

My rationale is that we can do anything inside compare(), as long as it returns consistently either of these -1, 0, 1. :-B

koogs

I still think that's wrong based on what the spec says. you can't say a<b one second and a>b the next. the world would end.

GoToLoop

Seems you may be right... But anyways, I can do some other unrelated craziness there and return the right values! :@)

Eluxiver

I see there was some discussion about my question overnight (Europe here ) :)>-

@ Koog, I did change my original question like a minute after I posted it because, while formulating the question, I found a solution that could work (something that happens often)

When you proposed to do exactly the same I was quite happy to find that my solution was not too far fetched. #:-S

You are also right about my question:

my understanding is that's what he wants 8) - a random element from the set of things with the lowest middle number. he's currently getting the earliest element from the set of things with the lowest middle number and that's not random enough.

It solved the problem only partially: First it never worked (always a bias) but now in some situation it works fine and in some I still get the bias (I wont go into the details but it has to do with the amount of variation I get in the list I want to sort -> no variation: it doesn't work, some variation: it doesn't work, a lot of variation: it works ??)

I think it has to do with the fact that when there is no variation in the value (I want the list sorted by), I get a bias because all the values are the same. But I want to avoid a bias (It must be a random selection of the lowest values! (if these lowest values are the same)).

I thought that this would be solved by using random() in the sort function. (even if it is against the programming laws >:) ) but the bias is still there, the only difference is that there is now a bias towards the first elements in the list (where there was before a bias towards the last elements in the list???

In the original situation (without a random() in the sort), the later added elements (with a higher index number) were never selected (in the situation where almost all the values are the same). Now with the random() in the sort. The first values are never selected (when the values are the same).

Is there an explanation for this? I think it must be something with the random() function then??

The good thing is that with the shuffle before the sort, the problem is solved as mentioned by Koog and in the example of GoToLoop (even if I use both together: the random in the sort and the shuffle, it works) So I should obey the Programming Laws :\">

Still I don't know why it didn't work correctly with the random() in all situations??