Kate Libby wrote:He's also unlikey to be spoon fed here :)
Hi there,
Might I suggest that you are unlikely to learn anything by just copy-pasting code.
Thanks for ur quick response.Cud u plz give ur codeI've named the class and I've also named one of the methods you have to call. That plus the Javadoc should be quite sufficient. Could you please make the effort to write in standard English without the ambiguous abbreviations. Your employers and customers won't put up with that and neither will I.
millionsIf you really have millions of data items, all bets are off: I would certainly use a database rather than trying to do it all in memory with any data structure.
as for me its very difficult to understand the vocabulary.So learn it. If you can't understand the standard techical vocabulary yet, you need to make more of an effort. This is what it will be like for the rest of your career. And specifically I suggest you get used to the idea that nobody will do your work for you, at least not unless you pay them the money you're being paid to do it. And if this is a course assignment, the idea is that you learn something amd exhibit that understanding in your assignmments. You wouldn't want to hand in someone else's work as your own, would you?
EJP wrote:How do you figure? We have to process every element to know its rank before we can find out which ones are in the first two ranks. Our last two elements in the original unsorted list could be the two with the second highest score, and we can't know that until we've added them all to the PQ, which means we've done N number of insertions at a cost of log(N) each--i.e. O(N log(N)).
But we're not processing N elements.
EJP wrote:And of course, OPs always ask the right question. ;-)In any case we are talking about small amounts of data.and in any case the OP asked for the optimal solution. Personally I would probably just use Collections.sort() as jverd suggested, as I personally wouldn't care about the optimal solution over a small dataset. But that doesn't answer the OP's question.
821046 wrote:Speaking of hard to understand, when you write using non-words like "plz" and "ur" and "cud", it makes you look like an idiot and makes it very annoying to read your posts.
Hi,
Thanks for ur immediate reply. Cud u plz give ur code as for me its very difficult to understand the vocabulary.
jverd wrote:So I wrote a little test. I don't want to post it here yet because I don't want to spoonfeed the OP. Here are the results though.EJP wrote:How do you figure? We have to process every element to know its rank before we can find out which ones are in the first two ranks. Our last two elements in the original unsorted list could be the two with the second highest score, and we can't know that until we've added them all to the PQ, which means we've done N number of insertions at a cost of log(N) each--i.e. O(N log(N)).
But we're not processing N elements.
Unless the PQ doesn't determine the ordering until we extract an item from it? But that would mean we'd have to look at each element every time we extract one, to determine which one is next, so the overall operation becomes O(N * M).
heap[i] <= heap[i*2] <= heap[i*2+1]
for every i. This process takes O(log N) time per insertion, i.e. O(N log N) over the entire dataset, but because it's only doing a partial ordering it is much faster than a full O(N log N) sort (lower constant factor).EJP wrote:I'm with you so far. That's what I stated initially, except you added some detail.
It doesn't sound like you guys know how a PriorityQueue works. Stop me if you've heard this before, but a PriorityQueue is a 'priority heap', which is not a memory-management-type heap but a binary-tree structure:
1. A heap does a partial ordering when you insert, such thatfor every i. This process takes O(log N) time per insertion, i.e. O(N log N) over the entire dataset,heap[i] <= heap[i*2] <= heap[i*2+1]
but because it's only doing a partial ordering it is much faster than a full O(N log N) sort (lower constant factor).Here's where you lose me. How is this any faster? We have to insert the entire data set, so it's the O(N log N) I stated previously and you confirmed just above.
2. When you remove that element, it then does another process to ensure that the constraint above holds again. This is also O(log N) per removal, with a low constant factor, and again it is much faster than a full O(N log N) sort.This part I was not aware of. Or forgot. I thought all ordering came at insertion time.
In the OP's situation, he has to do the partial ordering part over all N elements, but he only has to do the removal/re-partial ordering part over the first M elements that satisfy his constraint, plus 1, where M <= N.Okay, I'll buy that, and it's consistent with what little experimental data I have.
So the algorithmic complexity is O(N log N) with a low constant factor plus O(M log N), where M <= N, again with a low constant factor.
Or are you saying that it is still O(N log N), but just with a lower constant?That's exactly what I did say. 'Lower constant factor'.
EJP wrote:Yes, you did say "lower constant factor." However, you did not say (until later in the post) that it is still O(N log N). This phrase tripped me up:Or are you saying that it is still O(N log N), but just with a lower constant?That's exactly what I did say. 'Lower constant factor'.
because it's only doing a partial ordering it is much faster than a full O(N log N) sort (lower constant factor).The "faster than a full O(N log N)" at first sounded to me like you were saying that it's not a "full" O(N log N). I don't know what a "full" O(N log N) is vs. any other kind, but you seemed to be contrasting this approach with O(N log N), which in turn implies that this approach is not in fact O(N log N), but some O(something less). Possibly in addition to having a smaller constant? I don't know. It wasn't clear to me. That's why I asked.
Yes, you did say "lower constant factor." However, you did not say (until later in the post) that it is still O(N log N).Bzzt. I quote: 'This process takes O(log N) time per insertion, i.e. O(N log N) over the entire dataset, but because it's only doing a partial ordering it is much faster than a full O(N log N) sort (lower constant factor).'.
I don't know what a "full" O(N log N) isNor do I. I was talking about a full sort.
EJP wrote:Yes, I am perfectly aware of what you said. I noticed and understood "O(N log N) over the entire dataset," but I also noticed that it was immediately followed by "but because it's only doing a partial ordering it is much faster than a full O(N log N)".Yes, you did say "lower constant factor." However, you did not say (until later in the post) that it is still O(N log N).Bzzt. I quote: 'This process takes O(log N) time per insertion, i.e. O(N log N) over the entire dataset, but because it's only doing a partial ordering it is much faster than a full O(N log N) sort (lower constant factor).'.
Note also that I said 'full O(N log N) sort'.
EJP wrote:Ah. "full" modifies "sort," not "O(N log N)." That makes much more sense.I don't know what a "full" O(N log N) isNor do I. I was talking about a full sort.