> 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 > | > 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 [ https://leetcode.com/submissions/detail/418028305/ | Balanced BST > ] > (AVL tree) and it executed in ~180ms and when I tried using [ > https://leetcode.com/submissions/detail/418070375/ | TreeSet headSet().size() > ] > , 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 < [ mailto:fo...@univ-mlv.fr | > 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#headMap(K,boolean) >> ] >> [ >> https://docs.oracle.com/en/java/javase/15/docs/api/java.base/java/util/NavigableMap.html#tailMap(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" < [ mailto:mayankbansal...@gmail.com | >> > mayankbansal...@gmail.com ] > >>> À: "core-libs-dev" < [ mailto:core-libs-dev@openjdk.java.net | >> > 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
