How to fill an array asynchronously in a sorted way in Java?

Question

I'm developing an app where I need to get a list of files, read some data from it, and display all of these files, sorted based on that data, in a ListView.

The problem is that there might be plenty of them, so it takes time to load them all. I had a choice to either load them asynchronously (in a thread), or display a loading box. I am having a problem with the first one: the ArrayAdapter is being filled, then sorted in the end, so by the time all the items are there, the list is not sorted. The solutions I thought of are:

I thought of sorting the list every time I insert an item, but that would make the process even slower... But again, there's this, but I'm not sure I understand how to use such a sorting algorithm.
Use some kind of a sorted array, as mentioned here. I'm not sure how/if I can implement it with an ArrayAdapter.
Forget about using a thread to fill the ListView. Just add a "Loading" message or nothing at all.
Store the data in the files in a database, with the path of the file stored, and read all the entries from the database. But I'm not sure this will make the process faster...

la = new ArrayAdapter(this, R.layout.list_item);
setListAdapter(la);

Handler handler = new Handler() {
    public void handleMessage(Message message) {
        switch (message.what) {
        case TrackBrowser.DID_SUCCEED: {
            // This is called when the thread is done finding the list of items
            // mComparator is my own Comparator
            la.sort(mComparator);
            break;
        }
        case TrackBrowser.ADD: {
            // This is called everytime an item is parsed
            TrackBrowser.TrackView tv = (TrackBrowser.TrackView) message.obj;
            la.add(tv);
            // Should I sort here everytime?
            //la.sort(mComparator);
            break;
        }
        }
    }
};

// This class just loops through the files returned by listFiles and sends messages.
TrackBrowser tb = new TrackBrowser(handler); 
Thread thread = new Thread(tb);
thread.start();

I need your feedback on which solution I should use, and how to use the first two (if I should use them)?

Thanks a lot.

Zheka · Accepted Answer · 2012-05-14T16:59:21.590

1

You can use a binary search to find an appropriate position for inserting new element. As a result, the list is always sorted.

For example:

public static void add(List<Integer> list, Integer value) {
    int index = Collections.binarySearch(list, value);
    list.add((index < 0) ? (-index - 1) : index, value);
}

public static void main(String[] args) {
    List<Integer> list = new ArrayList<Integer>();

    add(list, 1);
    add(list, -5);
    add(list, -7);
    add(list, 100);
    add(list, 0);
    add(list, 90);
    add(list, -10);
    add(list, 0);
    add(list, 1);

    System.out.print(list);
}

Then you will get an output like this:

[-10, -7, -5, 0, 0, 1, 1, 90, 100]

It works fine. The binary search takes O(log(N)) and the inserting takes O(N) in the worst case (because when you is inserting a new element, can occur the relocating elements in the list). As a result, it takes O(N + log(N)) time. It better than O(N*log(N)) when you sort the list everytime.

edited May 14 '12 at 16:59

answered May 14 '12 at 16:07

Zheka

287
5
11

How good is it performance wise? And can you please just give a small example? Something like `i = Collections.binarySearch(myList, newItem, myCustomComparator); myList.add(i, newItem);` ? – jadkik94 May 14 '12 at 16:17
Okay. Thanks. I suppose it should work with other that integers. But how does this work? I thought binarySearch returns the index of `value` if it's present and `-1` if it is not... If so, then why did 100 in your example end up in the end? – jadkik94 May 14 '12 at 17:06
Nevermind, I had read the article in Wikipedia about Binary Search, now I read its implementation in Java. I understand, thanks a lot!! – jadkik94 May 14 '12 at 17:09
http://docs.oracle.com/javase/6/docs/api/java/util/Collections.html#binarySearch%28java.util.List,%20T%29 – Zheka May 14 '12 at 17:10
I just tested this, and it doesn't work, because I pass the ArrayAdapter constructor a list, then add to that list, but the items I add to that list do not show... So, I think I should either re-implement a binary search for the ArrayAdapter, or make my own Adapter which uses a List and binarySearch internally. I think that's the way to go, but still waiting to see if there's a better option. – jadkik94 May 14 '12 at 17:23
http://grepcode.com/file/repository.grepcode.com/java/ext/com.google.android/android/1.5_r4/android/widget/ArrayAdapter.java#ArrayAdapter.add%28java.lang.Object%29 You can see implementation of ArrayAdapter.add(...) and you can try after adding an item to the List invoke ArrayAdapter.notifyDataSetChanged() – Zheka May 14 '12 at 17:36

score 0 · Answer 2 · answered May 14 '12 at 14:37

0

Maybe you can use a TreeMap or TreeSet. When an item is added to the tree it is added to the correct position, so that the list stays sorted.

answered May 14 '12 at 14:37

Sjoerd

74,049
16
131
175

I need something similar to a list, so it's not the TreeMap. But how can I use a TreeSet with an adapter (ListAdapter or ArrayAdapter)? – jadkik94 May 14 '12 at 14:44
I looked it up, I might need to subclass from BaseAdapter, because ArrayAdapter expects either nothing or a List to be passed... If you know of another way... – jadkik94 May 14 '12 at 15:12

How to fill an array asynchronously in a sorted way in Java?

2 Answers2