28 Replies
⌛ This post has been reserved for your question.
Hey @gkn1! Please useTIP: Narrow down your issue to simple and precise questions to maximize the chance that others will reply in here./closeor theClose Postbutton above when your problem is solved. Please remember to follow the help guidelines. This post will be automatically closed after 300 minutes of inactivity.
💤 Post marked as dormant
This post has been inactive for over 300 minutes, thus, it has been archived.
If your question was not answered yet, feel free to re-open this post or create a new one.
In case your post is not getting any attention, you can try to use /help ping.
Warning: abusing this will result in moderative actions taken against you.you could try using
TreeMap which is a sorted Map
or you could insert each entry in both the HashMap and a PriorityQueue
but it depends what exactly you needHow would that make sense? Those are two different equivalence relationships. I'm trying to wrap my head around how a "PriorityHashMap" would even work?
I think they want a
LinkedHashMap-like thing where they can remove elements with lowest priority
but idkstrange 🙂
idk whether that's what they want
but I don't have a better guess
HashMap already has O(1) removal based on a specific key
What do you need from a PriorityQueue?.
so essentially you just want a
PriorityQueue that allows you to remove arbitrary elements in logarithmic time?
yeah the key from the priority queue, right?
essentially build your own min heap and add a HashMap storing a reference to your nodes in order to remove arbitrary elements
or you do a bit of trickery and don't actually remove elements but instead mark them as removed and just skip them when you get themIf you are finished with your post, please close it.
If you are not, please ignore this message.
Note that you will not be able to send further messages here after this post have been closed but you will be able to create new posts.
I mean, you could still use the marking approach
with a
HashSet and a PriorityQueue
everything is a trade-off
Why do you even need the combination of priority-queue and map?
Are you sure you need O(1) retrieval of the min element?
Why?
well that's your issue lol
There's rarely the case where you actually need the above requirements in practice
and tbh idk in which interview it would help to have an implementation of what you described
You need to store multiple data structures
it requires more memory and makes it slower in most cases
slower than using a single data structure that actually fits the application
Depends
probably TreeMap, a normal PriorityQueue or HashMap
actually let me check something
because a BST can have O(1) retrieval of the first element
TreeSet doesn't but it's possible
depends
you said you just need https://discord.com/channels/648956210850299986/1219090714231705711/1219226884701687859O(1) get min, O(logn) remove min and remove arbitrary
These requirements can be achieved with a BST that has a reference to its min entry
Don't do that unless you have benchmarks first
Code simplicity should be preferred over performance unless you have benchmarks measuring a significant performance improvement
you first need benchmarks for that
I claim that in most practical cases, the overhead of having to maintain two data structures as you mentioned results in worse performance
you have additional memory requirements
you have locality issues resulting in cache misses
and cache misses can result in a 100x or even higher performance decrease
if you manage to have the BST in its own cache line
HashMaps typically work well regarding cache hits
but is it the case in every scenario? YOu'd need benchmarks for that
depending on how stuff is inserted
like if you insert all nodes together
or manage to pre-reserve a chunk of memory for the nodes and put them there
then it's possible
but is it worth it? Probably not
and definitely not if you don't have benchmarks
and again, don't optimize anything before you have benchmarks
and then check the benchmarks before and after the optimization
often it's the case that "optimizations" actually make performance worse
and only optimize stuff that's actually a performance bottleneck, don't waste your time on code that isn't relevant for performance
there are APIs like the foreign function and memory API but it's complicatedI had a feeling about this question
If the reason is "for an interview", is it considered an XY problem? lmao
Yeah, I've done a lot of coding now, and I've never ever needed to use a structure like that, that's when I get sus 😄
esp when trying to combine equivalence relations, you either hash, or order, not both
so?
Hashmap no
Treemap yes
But a treemap is halfway a priority queue already
a treemap is also a map
so same rules apply
except that the equivalence relation is ordering
for a hashmap it's equals and hashcode based
this means treemaps have different characteristics as well
yeah, so does a priority queue
They're not that much different
that does not matter
it's what the collection uses
yes it does
again, that does not matter
if they compare to 0, a treemap considers them the same
so does a priority queue
not equal
compareTo
you kept hammering on about equals, just wanted to make it absolutely clear
i want priorityqueue behaviour specifically (constant get-min, nicely handled remove-min, insert, and remove-arbitrary)A treemap can do this pretty well actually all of it but a priority queue does the same! I'm opening intellij now You have to sift as well in a priorityqueue, it's pretty much rebalancing a node based heap is way slower than an array based heap fyi so pq's impl is pretty good Also java's treemap is a red-black tree not a plain binary heap
oh also
PriorityQueue#remove is O(log n) and not O(1) according to the JavadocThis implementation provides guaranteed log(n) time cost for the containsKey, get, put and remove operations.
Implementation note: this implementation provides O(log(n)) time for the enqueuing and dequeuing methods (offer, poll, remove() and add); linear time for the remove(Object) and contains(Object) methods; and constant time for the retrieval methods (peek, element, and size).
so a Treemap is actually "faster" in all cases?
It just does more work if you need JUST a PriorityQueue
if faster means "at least as fast in all operations when only considering asymptotic complexity and ignoring constant factors", probably
yeah
hence the quotes
not a bst, a red black tree
well, it ticks all your boxes for complexity
and requirements
So...
yeah, but you need fast removal
well it's easy, write a benchmark
Use JMH
Make a mix of the operations you will need and test it
Can't just fantasize performance based on a feeling
Or a hypothesis
You made a hypothesis
Experiment is your next step
Otherwise this entire conversation is meaningless, and you should just look at the big o complexity of treemap and priorityqueue and pick the one you want
Because those have actually been tested and verified
Yea you can
You sample problem sizes, do measurements and fit a curve
It's actually really simple
OK, you apparently have access to some programming and mathemathics wisdom that I haven't
data structures don't even have computational complexities
there are algorithms that aren't that easy to analyze
idk GP-eval maybe
The remove in Java's PQ is O(n), does a linear scan over the contents
Well, the regular remove is, removeAt is not
hashmap is O(1)
ah
yeah, so does remove from a treemap
also o(logn)
a heap has to sift
explained in the docs
ye
again, not a BST
In computer science, a red–black tree is a specialised binary search tree data structure noted for fast storage and retrieval of ordered information, and a guarantee that operations will complete within a known time. Compared to other self-balancing binary search trees, the nodes in a red-black tree hold an extra bit called "color" representing "red" and "black" which is used when re-organising the tree to ensure that it is always approximately balanced.ah If you invent your own data structure that has all of these properties and is faster than what out of the box java has, let me know what are the requirements again? they have to be compared unique. they don't have to be equals If you make a collection of something, you have to say that they're equivalent for one reason and one reason only. If you mix those up a lot of contract break equals can be false and compareTo can return 0 no that's a hashmap treemap is Comparable Otherwise smaller than or bigger than don't work Taht's not always the case though That's fine, just state that as a limitation Technically if you use a map that has this compareTo = 0 but not equals, you're technically violating the map contract anyway or set no I've used it a couple times for a case insensitive unique index give the treemap a case insensitive comparator well, 'twas a set but that's the same anyway, just no values
💤 Post marked as dormant
This post has been inactive for over 300 minutes, thus, it has been archived.
If your question was not answered yet, feel free to re-open this post or create a new one.
In case your post is not getting any attention, you can try to use /help ping.
Warning: abusing this will result in moderative actions taken against you.