Efficient update of sorted JavaFX ObservableList

Question

I have a Java ObservableList with thousands of entries that receives hundreds of updates a second backing a JavaFX TableView.

The ObservableList is backed by an ArrayList. Arbitrary sort orders can be applied to the list. The updates may change the sort order of a single entity in the list. I have performance issues if I try to preform a sort after each update, so currently I have a background task that performs a sort every second. However, I'd like to try to sort in real time if possible.

Assuming that the list is already sorted and I know the index of the element to change, is there a more efficient way to update the index of the element than calling sort on the list again?

I've already determined I can use Collections.binarySearch() to efficiently find the index of the element to update. Is there also a way I can efficiently find the index the updated element needs to move to and shift the ArrayList so it remains in order?

I also need to handle add and remove operations, but those are far less common.

Answer 1

I would use a TreeSet. It can update the order with O(log N) time complexity whereas ArrayList will do an insertion sort with O(n) per entry.

Answer 2

A few suggestions when dealing with sorting on a JavaFX ObservableList/TableView combo:

1. Ensure your model class includes Property accessors.

   Due to a weird quirk in the JavaFX 2.2 implementation that is not present in JavaFX 8+, TableView is far less efficient when dealing with large data models that do not have property accessors than it is when dealing with those that do include property accessor functions. See JavaFx tableview sort is really slow how to improve sort speed as in java swing for more details.

2. Perform bulk changes on the ObservableList.

   Each time you modify an ObservableList that is being observed, the list change listeners on the list are fired to communicate the permutations of the change to the observers. By reducing the number of modifications you make on the list, you can cut down on the number of change events which occur and hence on the overhead of observer notification and processing.

   An example technique for this might be to keep a mirror copy of the list data in a standard non-observable list, sort that data, then set that sorted data into the observable list in a single operation.

   To avoid premature optimization issues, only do this sort of optimization if the operation is initially slow and the optimization itself provides a significant measurable improvement.

3. Don't update the ObservableList more often than necessary.

   JavaFX display framerate is capped, by default, at 60fps. Updating visible components more often than once a pulse (a frame render trigger) is unnecessary, so batch up all of your changes for each pulse.

   For example, if you have a new record coming in every millisecond, collate all records that come in every 20 milliseconds and apply those changes all at once.

   To avoid premature optimization issues, only do this sort of optimization if the operation is initially slow and the optimization itself provides a significant measurable improvement.

4. Java 8 contains some new classes to assist in using sorted content in tables.

   I don't really know how the TableView sorting function and SortList work in Java 8. You can request that Oracle write a tutorial with samples and best practices for the Java 8 TableView sort feature by emailing jfx-docs-feedback_ww@oracle.com

   For further reference, see the javadoc:

   • the sorting section of the JavaFX 8 TableView javadoc.
   • new SortEvent class.
   • SortedList class.

Answer 3

Regarding your answer, FXCollections.sort() should be even faster because it handles the FX-Properties better and is specifically written for ObservableLists.

Answer 4

What is not quite clear is if you need the list to be sorted the whole time? If you sort it just in order to retrieve and update your entries quicker, you can do that faster using a HashMap. You can create a HashMap<YourClass, YourClass> if you implement a proper hashCode() and equals() method on the key fields in the class. If you only need to output a sorted list occasionally, also implement the Comparable<YourClass> interface and just create a TreeSet<YourClass>( map.keySet() ), that will create a sorted representation while the data in your HashMap stays in place. If you need it sorted always, you can consider to use TreeMap<YourClass,YourClass> instead of a HashMap. Maps are easier than Sets because they provide a way to retrieve the objects.

Answer 5

After some research, I concluded that Collections.sort() is pretty fast, even for 1 item. I haven't found a more efficient way than to update the item in the list and just call sort. I can't use a TreeSet since the the TableView relies on the List interface and I'd have to rebuild the TreeSet every time the sort order is changed.

I found that I could update at 60 FPS by using a Timer or KeyFrame and still have reasonable performance. I haven't found a better solution without upgrading to JavaFX 8.

Answer 6

You could pull the element out of the array list and insert (in sorted order) the updated element.