<div dir="ltr"><div dir="ltr"><div>Firstly, about queues. As far as I know, priority queue is implemented as heap, not tree, so things like subQueue doesn't make much sense in this context.</div><div><br></div>About popularity: this is indeed not very popular, might even be negligible outside of sorted multiset (lets adopt java naming conventions for those from now on). Although, I could provide at least few examples:<div><br></div><div>1. Batch tasks processing, especially in concurrent environments, when tasks could have different priorities. Sometimes tasks that are stored in a queue are processed in batches. Using today's stdlib of Java, acquiring such a batch of tasks from collection would be a O(n * log n) complexity, because each heapification is log n and called after each task is popped. Using TreeMultiset, this could be achieved in log (n). This also applies to messaging.</div><div><br></div><div>2. Implementing custom data structures. Not a task most of commercial developers encounter, although for specific types of tasks, like big data processing, custom datastructs could be a thing. Some collections, expeciall ordered, like B-tree, could require sorted multiset as part of internal implementation.</div><div><br></div><div>3. Again, for sorted multisets, counting frequency is a common task for commercial developers. Counting element frequencies using multisets is the thing that simply couldn't be achieved by set and is inefficient in list. This could have various use cases, from data displaying in histograms in generated reports to data validation is stateful systems (checking if user has not exceeded permitted amount of attempts, for example).</div><div><br></div><div>4. Storage for the result of db queries. Another common task is to fetch some ordered data from the database, and then modify it to preserve order. This category of tasks could be optimized using ordered multisets. </div><div><br></div><div>5. Concurent bag, as you just mentioned. This could be used in concurrent environment as I mentioned above, or just as less restricting concurrent collection as preserving sequence of elements could be a complex and resource consuming task in mutable concurrent collections</div><div><br></div><div>As you might see, almost all of those indeed converge to a sorted collection of duplicating elements. I am not sure If there is much more to it, but what i would like to say is that feature like this would definitely not be redundant for "enterprise" language like Java, where optimizing some operations from O(n) or even O(n * log n) to O (log n) could introduce significant performance improvement, as well as reducing amount of possible bugs by taking on some of responsibilities related to preserving order of elements sorted.</div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">вс, 21 апр. 2024 г. в 00:33, Holo The Sage Wolf <<a href="mailto:holo3146@gmail.com" target="_blank">holo3146@gmail.com</a>>:</div></div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">вс, 21 апр. 2024 г. в 01:06, ІП-24 Олександр Ротань <<a href="mailto:rotan.olexandr@gmail.com">rotan.olexandr@gmail.com</a>>:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div>Firstly, about queues. As far as I know, priority queue is implemented as heap, not tree, so things like subQueue doesn't make much sense in this context.</div><div><br></div>About popularity: this is indeed not very popular, might even be negligible outside of sorted multiset (lets adopt java naming conventions for those from now on). Although, I could provide at least few examples:<div><br></div><div>1. Batch tasks processing, especially in concurrent environments, when tasks could have different priorities. Sometimes tasks that are stored in a queue are processed in batches. Using today's stdlib of Java, acquiring such a batch of tasks from collection would be a O(n * log n) complexity, because each heapification is log n and called after each task is popped. Using TreeMultiset, this could be achieved in log (n). This also applies to messaging.</div><div><br></div><div>2. Implementing custom data structures. Not a task most of commercial developers encounter, although for specific types of tasks, like big data processing, custom datastructs could be a thing. Some collections, expeciall ordered, like B-tree, could require sorted multiset as part of internal implementation.</div><div><br></div><div>3. Again, for sorted multisets, counting frequency is a common task for commercial developers. Counting element frequencies using multisets is the thing that simply couldn't be achieved by set and is inefficient in list. This could have various use cases, from data displaying in histograms in generated reports to data validation is stateful systems (checking if user has not exceeded permitted amount of attempts, for example).</div><div><br></div><div>4. Storage for the result of db queries. Another common task is to fetch some ordered data from the database, and then modify it to preserve order. This category of tasks could be optimized using ordered multisets. </div><div><br></div><div>5. Concurent bag, as you just mentioned. This could be used in concurrent environment as I mentioned above, or just as less restricting concurrent collection as preserving sequence of elements could be a complex and resource consuming task in mutable concurrent collections</div><div><br></div><div>As you might see, almost all of those indeed converge to a sorted collection of duplicating elements. I am not sure If there is much more to it, but what i would like to say is that feature like this would definitely not be redundant for "enterprise" language like Java, where optimizing some operations from O(n) or even O(n * log n) to O (log n) could introduce significant performance improvement, as well as reducing amount of possible bugs by taking on some of responsibilities related to preserving order of elements sorted.</div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">вс, 21 апр. 2024 г. в 00:33, Holo The Sage Wolf <<a href="mailto:holo3146@gmail.com" target="_blank">holo3146@gmail.com</a>>:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="auto"><div>Let me prefix this by saying that I'm a mathematician, so maybe the lingo I use is a bit different. A multi set has no structure apart from "counting duplication", just like a set has no structure at all, ordered set **is not a set** and ordered multi set **is not a multi set**.</div><div dir="auto"><br></div><div dir="auto">With the clarification you gave I understand what you mean and retract my first question (although I believe that "sortedX" or "priorityX" are the naming Java has for what you called "orderedX").</div><div dir="auto"><br></div><div dir="auto">> THe whole point of the bag is to store duplicate elements without preserving order, which allows things like ordered collections.</div><div dir="auto"><br></div><div dir="auto">No, the whole point of the bag is to store elements. The difference between a bag and a list is that a bag has less, anything you can do with a bag you can do with a list.</div><div dir="auto"><br></div><div dir="auto">The benefit of having a bag is to have a more restrictive interface for the times you don't need the extra structure, as well as the possible performant implementation that doesn't need to respect a stricted contract.</div><div dir="auto"><br></div><div dir="auto">CopyOnWriteArratList is more than just a bag.</div><div dir="auto"><br></div><div dir="auto"><br></div><div dir="auto">> then that just adds one more use case to potential Bag interface</div><div dir="auto"><br></div><div dir="auto">Indeed, I gave concurrent bag as an example of a possible implementation of a bag interface, but you didn't answer my main question, just how common is a use if a bag to change the std for it?</div><div dir="auto"><br></div><div dir="auto">To me it sounds like you are interested only on the sorted/navigable variations, so an alternative solution will be to improve PriorityQueue to have a "subQueue" methods (and friends) as well as extending it to a Navigable variation.</div><div dir="auto"><br></div><div dir="auto"><br></div><div dir="auto"><br><br><div class="gmail_quote" dir="auto"><div dir="ltr" class="gmail_attr">On Sun, 21 Apr 2024, 00:01 ІП-24 Олександр Ротань, <<a href="mailto:rotan.olexandr@gmail.com" target="_blank">rotan.olexandr@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr">Concurrent Bag is something like CopyOnWriteArrayList or Vector, don't we have it already? (I know vectors aren't optimized). THe whole point of the bag is to store duplicate elements without preserving order, which allows things like ordered collections. There could be mutable collections for concurrency optimized with read-write locks though, if that is what you are referring to as "concurrent bag", and I am missing the point why this can't be a part of list interface, then that just adds one more use case to potential Bag interface.<div><br></div><div>PS: Ordered means it preserves order based on comparator, what you are referring to as ordered essentially means sequential, or am I missing a point?</div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">сб, 20 апр. 2024 г. в 23:52, Holo The Sage Wolf <<a href="mailto:holo3146@gmail.com" rel="noreferrer" target="_blank">holo3146@gmail.com</a>>:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="auto"><div>By "ordered collection" you mean "unordered collection"?</div><div dir="auto"><br></div><div dir="auto">How common is it to actually use a multiset in general? Of course there are use cases, and there are areas in which it is used a lot, but I don't believe it is common enough to be part of the std with the one exception of concurrent bag.</div><div dir="auto"><br><div class="gmail_quote" dir="auto"><div dir="ltr" class="gmail_attr">On Sat, 20 Apr 2024, 23:25 ІП-24 Олександр Ротань, <<a href="mailto:rotan.olexandr@gmail.com" rel="noreferrer noreferrer" target="_blank">rotan.olexandr@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr">In this letter I would like to express some of my thoughts regarding the potential Multiset interface.<div><br></div><div>I, personally, have encountered a few situations where such an interface could come in handy, mostly when I needed an ordered collection that permits duplicates. That time I used guava`s TreeMultiset, but I think Java itself should have such a collection in its std library. While it is not a very common problem, there are still a bunch of use cases where such things could come in handy.</div><div><br></div><div>I am willing to take on development of such thing, but there are a few concerns about Multiset: </div><div><br></div><div>1. Is there any other use for this besides ordered collection that permits duplicates? I can't remember anything else from the top of my head.</div><div><br></div><div>2. Guava's TreeMultiset class hierarchy pretty much imitates TreeSet class hierarchy, while not being directly connected. I think introducing any other ordered collection will require some refactoring of existing collection interfaces (for example extract SortedCollection from SortedSet, Navigable Collection from NavigableSet etc.). From the perspective of clean code, this would be the right decision, but I feel like this will be a very complex task to accomplish.</div><div><br></div><div>3. Maybe there should be few versions of Tree collection (for example, for regular tasks red-black tree and B-Tree for large amounts of data). I have some expirience implementing both, but is it really needed in standard library?</div></div>
</blockquote></div></div></div>
</blockquote></div>
</blockquote></div></div></div>
</blockquote></div>
</blockquote></div>