Re: Class TreeMap | Lower and Upper Count Support
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 wrote: > > > -- > > *De: *"mayank bansal" > *À: *"Remi Forax" > *Cc: *"core-libs-dev" > *Envoyé: *Dimanche 8 Novembre 2020 12:55:09 > *Objet: *Re: Class TreeMap | 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 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" >> > À: "core-libs-dev" >> > Envoyé: Dimanche 8 Novembre 2020 11:22:01 >> > Objet: Class TreeMap | 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 constructor initializes the TreeMap 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
Re: Class TreeMap | Lower and Upper Count Support
> De: "mayank bansal" > À: "Remi Forax" > Cc: "core-libs-dev" > Envoyé: Dimanche 8 Novembre 2020 12:55:09 > Objet: Re: Class TreeMap | 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 | 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 constructor initializes the TreeMap 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
Re: Class TreeMap | 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. On Sun, Nov 8, 2020 at 4:09 PM Remi Forax 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" > > À: "core-libs-dev" > > Envoyé: Dimanche 8 Novembre 2020 11:22:01 > > Objet: Class TreeMap | 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 constructor initializes the TreeMap 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
Re: Class TreeMap | Lower and Upper Count Support
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" > À: "core-libs-dev" > Envoyé: Dimanche 8 Novembre 2020 11:22:01 > Objet: Class TreeMap | 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 constructor initializes the TreeMap 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
Class TreeMap | 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 constructor initializes the TreeMap 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
