A good Sorted List for Java

Question

I m looking for a good sorted list for java  Googling around give me some hints about using TreeSet TreeMap  But these components is lack of one thing  random access to an element in the set  For example  I want to access nth element in the sorted set  but with TreeSet  I must iterate over other n-1 elements before I can get there  It would be a waste since I would have upto several thousands elements in my Set   Basically  I m looking for some thing similar to a sorted list in  NET  with ability to add element fast  remove element fast  and have random access to any element in the list   Has this kind of sorted list implemented somewhere  Thanks   Edited  My interest in SortedList grows out of this problems  I need to maintains a list of many thousands object  and can grow up to many hundred of thousands   These objects will be persisted to database  I want to randomly select few dozens of element from the whole list  So  I tried to maintain a separated on-memory list that contains the primary keys  Long numbers  of all objects  I need to add remove keys from the list when object is added   removed from database  I m using an ArrayList right now but I m afraid ArrayList would not suit it when the number of records grows   Imagine you have to iterate over several hundred thousands of elements every time an object is removed from database   Back to the time when I did  NET programming  then I would use a sorted List  List is a  NET class that once Sorted property set to true  will maintain order of its element  and provide binary search that help remove insert element very quick   I m hoping that I can find some thing similar from java BCL but unluckily  I didn t find a good match

User · Answer

Depending on how you re using the list  it may be worth it to use a TreeSet and then use the toArray   method at the end  I had a case where I needed a sorted list  and I found that the TreeSet   toArray   was much faster than adding to an array and merge sorting at the end

User · Answer

You need no sorted list  You need no sorting at all      I need to add remove keys from the list when object is added   removed from database    But not immediately  the removal can wait  Use an ArrayList containing the ID s all alive objects plus at most some bounded percentage of deleted objects  Use a separate HashSet to keep track of deleted objects   private List lt ID gt  mostlyAliveIds   new ArrayList lt  gt     private Set lt ID gt  deletedIds   new HashSet lt  gt          I want to randomly select few dozens of element from the whole list    ID selectOne Random random        checkState deletedIds size    lt  mostlyAliveIds size         while  true            int index   random nextInt mostlyAliveIds size             ID id   mostlyAliveIds get index           if   deletedIds contains ID   return ID           Set lt ID gt  selectSome Random random  int count        checkArgument deletedIds size    lt   mostlyAliveIds size   - count       Set lt ID gt  result   new HashSet lt  gt         while  result size    lt  count  result add selectOne random        For maintaining the data  do something like  void insert ID id        if   deletedIds remove id   mostlyAliveIds add ID       void delete ID id        if   deletedIds add id              throw new ImpossibleException  Deleting a deleted element             if  deletedIds size    gt  0 1   mostlyAliveIds size              mostlyAliveIds removeAll deletedIds           deletedIds clear              The only tricky part is the insert which has to check if an already deleted ID was resurrected   The delete ensures that no more than 10  of elements in mostlyAliveIds are deleted IDs  When this happens  they get all removed in one sweep  I didn t check the JDK sources  but I hope  they do it right  and the show goes on   With no more than 10  of dead IDs  the overhead of selectOne is no more than 10  on the average   I m pretty sure that it s faster than any sorting as the amortized complexity is O n

User · Answer

Phuong   Sorting 40 000 random numbers   0 022 seconds  import java util ArrayList  import java util Collections  import java util List  import java util Random    public class test       public static void main String   args                List lt Integer gt  nums   new ArrayList lt Integer gt             Random rand   new Random            for  int i   0  i  lt  40000  i                           nums add  rand nextInt Integer MAX VALUE                        long start   System nanoTime            Collections sort nums           long end   System nanoTime             System out println  end-start  1e9                Since you rarely need sorting  as per your problem statement  this is probably more efficient than it needs to be

User · Answer

SortedList decorator from Java Happy Libraries can be used to decorate TreeList from Apache Collections  That would produce a new list which performance is compareable to TreeSet  https   sourceforge net p happy-guys wiki Sorted 20List

User · Answer

What about using a HashMap   Insertion  deletion  and retrieval are all O 1  operations   If you wanted to sort everything  you could grab a List of the values in the Map and run them through an O n log n  sorting algorithm   edit  A quick search has found LinkedHashMap  which maintains insertion order of your keys   It s not an exact solution  but it s pretty close

User · Answer

To test the efficiancy of earlier awnser by Konrad Holl  I did a quick comparison with what I thought would be the slow way of doing it   package util collections   import java util ArrayList  import java util Collection  import java util Collections  import java util Iterator  import java util List  import java util ListIterator              author Earl Bosch     param  lt E gt  Comparable Element        public class SortedList lt E extends Comparable gt  implements List lt E gt                    The list of elements             private final List lt E gt  list   new ArrayList         public E first             return list get 0              public E last             return list get list size   - 1              public E mid             return list get list size    gt  gt  gt  1               Override     public void clear             list clear                Override     public boolean add E e            list add e           Collections sort list           return true              Override     public int size             return list size                Override     public boolean isEmpty             return list isEmpty                Override     public boolean contains Object obj            return list contains  E  obj               Override     public Iterator lt E gt  iterator             return list iterator                Override     public Object   toArray             return list toArray                Override     public  lt T gt  T   toArray T   arg0            return list toArray arg0               Override     public boolean remove Object obj            return list remove  E  obj               Override     public boolean containsAll Collection lt   gt  c            return list containsAll c               Override     public boolean addAll Collection lt   extends E gt  c             list addAll c           Collections sort list           return true              Override     public boolean addAll int index  Collection lt   extends E gt  c            throw new UnsupportedOperationException  Not supported                 Override     public boolean removeAll Collection lt   gt  c            return list removeAll c               Override     public boolean retainAll Collection lt   gt  c            return list retainAll c               Override     public E get int index            return list get index               Override     public E set int index  E element            throw new UnsupportedOperationException  Not supported                 Override     public void add int index  E element            throw new UnsupportedOperationException  Not supported                 Override     public E remove int index            return list remove index               Override     public int indexOf Object obj            return list indexOf  E  obj               Override     public int lastIndexOf Object obj            return list lastIndexOf  E  obj               Override     public ListIterator lt E gt  listIterator             return list listIterator                Override     public ListIterator lt E gt  listIterator int index            return list listIterator index               Override     public List lt E gt  subList int fromIndex  int toIndex            throw new UnsupportedOperationException  Not supported                Turns out its about twice as fast  I think its because of SortedLinkList slow get - which make s it not a good choice for a list   Compared times for same random list    SortedLinkList   15731 460  SortedList   6895 494 ca odell glazedlists SortedList   712 460 org apache commons collections4 TreeList   3226 546   Seems glazedlists SortedList is really fast

User · Answer

GlazedLists has a very  very good sorted list implementation

User · Answer

Generally you can t have constant time look up and log time deletions insertions  but if you re happy with log time look ups then you can use a SortedList   Not sure if you ll trust my coding but I recently wrote a SortedList implementation in Java  which you can download from http   www scottlogic co uk 2010 12 sorted lists in java    This implementation allows you to look up the i-th element of the list in log time

User · Answer

It seems that you want a list structure with very fast removal and random access by index  not by key  times  An ArrayList gives you the latter and a HashMap or TreeMap give you the former   There is one structure in Apache Commons Collections that may be what you are looking for  the TreeList  The JavaDoc specifies that it is optimized for quick insertion and removal at any index in the list  If you also need generics though  this will not help you

User · Answer

This is the SortedList implementation I am using  Maybe this helps with your problem   import java util Collection  import java util Collections  import java util Comparator  import java util LinkedList         This class is a List implementation which sorts the elements using the    comparator specified when constructing a new instance          param  lt T gt      public class SortedList lt T gt  extends ArrayList lt T gt                   Needed for serialization              private static final long serialVersionUID   1L                 Comparator used to sort the list              private Comparator lt   super T gt  comparator   null                 Construct a new instance with the list elements sorted in their          link java lang Comparable  natural ordering              public SortedList                          Construct a new instance using the given comparator                  param comparator             public SortedList Comparator lt   super T gt  comparator            this comparator   comparator                       Construct a new instance containing the elements of the specified        collection with the list elements sorted in their          link java lang Comparable  natural ordering                  param collection             public SortedList Collection lt   extends T gt  collection            addAll collection                        Construct a new instance containing the elements of the specified        collection with the list elements sorted using the given comparator                  param collection         param comparator             public SortedList Collection lt   extends T gt  collection  Comparator lt   super T gt  comparator            this comparator           addAll collection                        Add a new entry to the list  The insertion point is calculated using the        comparator                  param paramT         return  lt code gt true lt  code gt  if this collection changed as a result of the call               Override     public boolean add T paramT            int initialSize   this size               Retrieves the position of an existing  equal element or the             insertion position for new elements  negative           int insertionPoint   Collections binarySearch this  paramT  comparator           super add  insertionPoint  gt  -1    insertionPoint    -insertionPoint  - 1  paramT           return  this size      initialSize                        Adds all elements in the specified collection to the list  Each element        will be inserted at the correct position to keep the list sorted                  param paramCollection         return  lt code gt true lt  code gt  if this collection changed as a result of the call               Override     public boolean addAll Collection lt   extends T gt  paramCollection            boolean result   false          if  paramCollection size    gt  4                result   super addAll paramCollection               Collections sort this  comparator                     else               for  T paramT paramCollection                    result    add paramT                                   return result                       Check  if this list contains the given Element  This is faster than the          link  contains Object   method  since it is based on binary search                  param paramT         return  lt code gt true lt  code gt   if the element is contained in this list          lt code gt false lt  code gt   otherwise              public boolean containsElement T paramT            return  Collections binarySearch this  paramT  comparator   gt  -1                         return The comparator used for sorting this list              public Comparator lt   super T gt  getComparator             return comparator                       Assign a new comparator and sort the list using this new comparator                  param comparator             public void setComparator Comparator lt   super T gt  comparator            this comparator   comparator          Collections sort this  comparator             This solution is very flexible and uses existing Java functions    Completely based on generics Uses java util Collections for finding and inserting list elements Option to use a custom Comparator for list sorting   Some notes    This sorted list is not synchronized since it inherits from java util ArrayList  Use Collections synchronizedList if you need this  refer to the Java documentation for java util ArrayList for details   The initial solution was based on java util LinkedList  For better performance  specifically for finding the insertion point  Logan s comment  and quicker get operations  https   dzone com articles arraylist-vs-linkedlist-vs   this has been changed to java util ArrayList

[java] A good Sorted List for Java

Examples related to java

Examples related to sorting