Hi Remi, I raised a PR for improving the complexity of size() method of HeadMap/ TailMap https://github.com/openjdk/jdk/pull/1255 . I am getting jcheck failed exception because of wrong commit message as it is not yet assigned to any issue id. Could you please help here ? Thanks.
On Sun, Nov 8, 2020 at 5:38 PM <fo...@univ-mlv.fr> wrote: > > > ------------------------------ > > *De: *"mayank bansal" <mayankbansal...@gmail.com> > *À: *"Remi Forax" <fo...@univ-mlv.fr> > *Cc: *"core-libs-dev" <core-libs-dev@openjdk.java.net> > *Envoyé: *Dimanche 8 Novembre 2020 12:55:09 > *Objet: *Re: Class TreeMap<K,V> | Lower and Upper Count Support > > Hi Remi, > Thank you for pointing that out. This is providing the same feature but it > is not the optimal approach for calculating the size. > > AscendingSubMap().size() is actually iterating each and every element > using Iterator to calculate the size resulting in the O(N) time complexity > which can be reduced to O(logN) and this will be a huge improvement. Code > snippet for the reference - > https://github.com/openjdk/jdk/blob/master/src/java.base/share/classes/java/util/TreeMap.java#L1937-L1950 > > I am coming from the fact that I was trying to solve one coding problem, I > tried using own Balanced BST > <https://leetcode.com/submissions/detail/418028305/> (AVL tree) and it > executed in ~180ms and when I tried using TreeSet headSet().size() > <https://leetcode.com/submissions/detail/418070375/>, it resulted in a > TLE - Time Limit Exceeded. > > > Interesting, I've always though that all collections of java.util had a > size() implementation in O(1). > It may be worth fixing this if there is a simple fix. > > One issue with TreeMap is that unlike most of the other implementations, > TreeMap is not used a lot so we are still discovering issues. > > Rémi > > > > > On Sun, Nov 8, 2020 at 4:09 PM Remi Forax <fo...@univ-mlv.fr> wrote: > >> Is it different from >> headMap(key, true).size() / tailMap(key, true).size() ? >> >> >> https://docs.oracle.com/en/java/javase/15/docs/api/java.base/java/util/NavigableMap.html#headMap(K,boolean) >> >> https://docs.oracle.com/en/java/javase/15/docs/api/java.base/java/util/NavigableMap.html#tailMap(K,boolean) >> >> cheers, >> Rémi >> >> ----- Mail original ----- >> > De: "mayank bansal" <mayankbansal...@gmail.com> >> > À: "core-libs-dev" <core-libs-dev@openjdk.java.net> >> > Envoyé: Dimanche 8 Novembre 2020 11:22:01 >> > Objet: Class TreeMap<K,V> | Lower and Upper Count Support >> >> > Hi Everyone, >> > >> > I would like to propose and work on a feature request of supporting the >> > lower and higher count in java class TreeMap. >> > "lower count" is the number of elements that are strictly less than the >> > given value. >> > "upper count" is the number of elements that are strictly greater than >> the >> > given value. >> > >> > *Method definitions-* >> > int getLowerCount(K key); >> > int getHigherCount(K key); >> > >> > *Follow-up feature -* >> > Class TreeSet<E> constructor initializes the TreeMap<K,V> in the TreeSet >> > constructor. >> > It puts the dummy value as *new Object()* whenever we add the entry in >> > TreeSet. >> > I would like to work on the feature to provide the *Duplicate count* in >> > case of the same Key and the same Value. >> > >> > I will be happy to work on both and raise a PR. I need some guidance if >> the >> > proposed feature looks good and I can start working on it and also would >> > like to know about the process whether I can directly raise the PR. >> > >> > Thanks >> > -- >> > Regards, >> > Mayank Bansal >> > > > -- > Regards, > Mayank Bansal > > -- Regards, Mayank Bansal
