Mike Simmons

Ranch Foreman
+ Follow
since Mar 05, 2008
Cows and Likes
Cows
Total received
19
In last 30 days
0
Total given
0
Likes
Total received
438
Received in last 30 days
8
Total given
24
Given in last 30 days
0
Forums and Threads
Scavenger Hunt
expand Ranch Hand Scavenger Hunt
expand Greenhorn Scavenger Hunt

Recent posts by Mike Simmons

As Stephan asked: what is the return value of x++?

To put it another way, consider this program:


What does it print?  Why?
Well, we hit a little snag when the universe sort of collapsed on itself. But dad seemed cautiously optimistic.
5 days ago

Stephan van Hulst wrote:

D.J. Quavern wrote:Uh, NP-hard? Wiki has a funny definition : "the defining property of a class of problems that are, informally, "at least as hard as the hardest problems in NP"


Let's explain this in another funny way: If aliens come down to earth and hand us a small machine that does nothing else but provide answers to the traveling salesman problem instantaneously, we can build it into our computer processors to make them able to quickly provide an answer to EVERY OTHER NP-problem, even if they seem completely unrelated to the traveling salesman problem. For instance, if you want to decrypt a secret message without knowing the key, you can write a program that states the decryption operation in terms of the traveling salesman problem, and the computer will be able to provide you the decrypted message very fast.



And I, for one, welcome our new alien overlords.
5 days ago

D.J. Quavern wrote:I had a look at the minimal spanning tree: so this is the one we have, but how do you deal with them when there are no weights on the branches?



"No weights" often is really "equal weights".  The thing we are asked to minimize here is the number of pilots, which is also the number of routes, or number of selected edges in the graph  We know that ever time we select a pilot/edge, the cost of our solution is 1 pilot more than another solution without that pilot.  But all pilots have equal cost.  So we can just say that all pilots have equal weight, and for simplicity, we let that weight be 1.  So, the cost of each edge in the graph is 1.  If we were given a table that included different salaries for different pilots, then those might be our different weights - but for the given problem, all pilots are equal.

D.J. Quavern wrote: I also looked at Dijkstra algorithm: how can it find the most optimal route when it can't see the path n+2? I mean what if it choses the cheapest weight (2), but the next-one is extra salty (45)? Maybe it's not the point and it's a very stupid question though.


Not stupid, no, it's a good question.  A key point is that with Dijkstra, at step n you aren't committing to any one solution yet - you are handling *all* possible solutions, of length n.  Or of a particular maximum cost.  Well, not really *all* of the solutions, because you are weeding out the ones that waste time getting to the edge of your graph.  But you are keeping a set of all the best solutions that would reach the current edge of the search area.  Without committing to any one point on the edge, yet.

I don't think Dijkstra really applies to your original problem, though it's similar in some ways.  Dijkstra finds the best way to connect *two* particular nodes.  And one of those nodes is always in the center of your search.  (Or, you have two expanding search regions, and each node is in the center of one of them.)  SST finds the best way to make sure *all* nodes are connected.  Traveling salesman is much more similar, as the salesman needs to travel through all the cities/nodes.


6 days ago
Very true.  Also a lot of cryptography uses such integer arithmetic.  We absolutely need to be able to access this sometimes.  I just don't like it as the default.
1 week ago
Yes, I had seen your previous post re: IEEE 754, and that why I had said yes, I'm aware of the history of IEEE 754.  Yes, we know Java is following IEEE 754.  I would say I'm not disagreeing with the rationale that IEE 754 had back in 1985, nor with the reasons Sun had for using it for Java in the early nineties.  But I find it annoying to be stuck with it as a default in 2019.  (Pretty sure I felt this way in 1998 or so as well.) Java is in general pretty good about throwing a stack trace when something bad and unexpected happens, e.g. a null.  But with primitive operations, not so much - errors can get ignored or hidden by default.  This applies to integer overflow most of all, but also to the other issues discussed.
1 week ago
Personally, it's always annoyed me that Java doesn't have safer math operations by default.  Yes, I'm aware of the history of IEEE 754, and we're not going to change Java too fundamentally now.  But I would much prefer that by default, math operations should throw errors for overflow and underflow... and then there could be a way to enable a fast-but-less-safe mode for those who need it.  But frankly, most people don't need it, and I would prefer to make math errors easier to find by default.

But, given Java as it has been developed... note that since Java 1.8, java.util.Math has methods to handle exact operations for ints and longs, very similar to what Carey suggested, e.g.:

There's no divideExact() currently, mostly because the currect addExact(), subtractExact() and multiplyExact() methods only support integers, and thus only need to check for overflow, never underflow, and with integers you can never overflow from division.  I think it would be nice to have floating point equivalents for all these - though "exact" seems a poor term to use in any method name for floating point operations.  Perhaps something like "safe" instead?


An additional complication is that it's not clear whether other conditions like dividing by 0  or other overflow should be converted to an exception, or whether we can just continue to use values like POSITIVE_INFINITY and NAN, as per usual IEEE 754 rules.  Quite possibly that's why they haven't already added such methods.  I would also think it's much rarer to find situations where floating-point underflow occurs, compared to integer overflow.  Ah, well.
1 week ago
[Responding to the OP before I saw Carey's reply]

First a minor note, you don't need to write Math.pow(A,2) - you can just write A*A.  This is both faster and more readable for everyone.  Win-win.

Second, the plus-or-inus part of the equation appears to be in the wrong place.  You should be changing the sign in front of the square root.

Third, when you write something like B*B / 4 * A * A, you need to be careful to put in parentheses correctly.  What you've written is equivalent to (B*B*A*A)/4.  What you wanted was (B*B)/(4*A*A).
1 week ago

Paul Clapham wrote:Buckets don't have anything to do with the algorithm. If the Map you're asking about happens to use them, then it will have software to deal with them appropriately. You do not need to know the details of how it works.


Um, the question did specifically say HashMap, and yes the algorithm does use buckets.  I agree that we don't need to know the details in order to use any Map.  But it is still possible to learn about those details...
2 weeks ago

Arun Singh Raaj wrote:
If the key is a String instance = "hello". If hash of "hello" is 99162322 so initially when bucket size is 16, Java calculates the index:
(99162322 & 15) = 2     and the entryset gets stored into index 2.

But how does it get the same index for another "hello" when bucket size is 32 or more?
Or my understanding is wrong, it's not mandatory to have the same index for two same instances?


If you're talking about having the same index when the bucket size is 16 as when the bucket size is 32... your understanding is wrong; it's not mandatory to have the same index for the two situations.  You should always get the same hashcode, but not necessarily the same index.  

As long as the bucket size is 16, then when you get a "hello" and find its hashcode is 99162322, you calculate 99162322 & 15 = 2 and the index is 2.  That will be true every time you encounter a "hello", it will have the same index of 2.

Until, if the hash table grows and you later have a bucket size of 32, then things change.  First, when the code determines it's time to grow the hash table to a new bucket size, at that point all elements that are already in the hash table need to have their indexes recalculated, and moved to new buckets.  Before you add any new elements using the new bucket size.  So at that point, the original "hello", which still has hash code 99162322, has its index recalculated: 99162322 & 31 = 18.  Great, now the original "hello" is moved to bucket 18.  And any new "hello" found afterwards will have its index calculated the same way, 99162322 & 31 = 18, so the hash table will find there's already a "hello" there, the original "hello" which is now living in bucket 18.

Later on, the hash table may grow to bucket size 64, and then the original "hello" will be moved to 99162322 & 63 = 18.  Oh, well in that case it's got the same index it had for bucket size 32... though even then it's probably being moved to a whole new array, size 64, since the previous array with size 32 can't magically grow.

Later, at bucket size 128, the index of "hello" becomes 99162322 & 127 = 82, great, now we move to bucket 82.

And so on, if we keep growing...

Arun Singh Raaj wrote:So in case I try to store duplicate key, does it firstly calculate the index then check the particular index of bucket or
it firstly compares all the keys of all the buckets with the one you are going to store?


It calculates the index, and then looks in that bucket, and only that bucket, to see if the given string value is already there or not.  That's the key point that makes the hash table so fast at looking things up (assuming not too many collisions landing in the same bucket) - you only have to check one bucket.
2 weeks ago

Bart Ret wrote:BTW. Like you said , it doesn't work properly. Still are repeated items.


OK, you've got a LinkedList as I suggested - but it's only held in a local variable, quotesList.  Each time you reach the end of this method, that variable goes out of scope, and that particular LinkedList will never be accessed by another method call in the future, because no one has a reference to it.  The only reference ended when the method ended.  Instead, the next time the method is called, it makes a new LinkedList whose alues are populated from quotesArrays, the original array which has never changed.  Try making quotesList a field of your class, not a local variable.  Then the next call to ShowRandomQuote() will have a way to get a reference to the same list that you previously removed one or more elements from.
2 weeks ago
Arrays.asList(array) returns a List that does not support removal.  If you want to do it this way, I'd replace the array with a LinkedList that's initially populated from the array - e.g. new LinkedList<>(Arrays.asList(quotesArray)).  The new LinkedList starts as a copy of the one from Arrays.asList(), but as you remove elements from the LinkedList, they are still in the array and in the list from Arrays.asList().

By the way, do you know what you want to do when the list is eventually empty?  Will you start over with a new list copied from the original array?
2 weeks ago

Lb Ward wrote:Correction: If line 7 read "check(p1, p1->p1.age<5);", then line 7 doesn't compile.  I get an error: 'Variable 'p1' is already defined in this scope.'  So... I'm still trying to figure out what the parameter on each side of the "->" comes from.  I believe it is the object upon which the testing is done, but what determines it's value?

I'm beginning to believe that in the form "check(p1, p->p.age <5);", that p is the parameter passed to the interface containing the test method.  But I still can't see how java knows what to pass in as parameter p.  


Yes, p is the parameter of the interface.  In this case the interface is Predicate<Panda>, which has exactly one parameter, a Panda.  You could give that parameter any name you want, as long as it doesn't clash with another existing name.  The name you use won't matter outside the declaration of the lambda.  So you could write

or

or

and these would all work exactly the same.  The compiler will know that check() expects a Predicate<Panda> as its second parameter, so whatever lambda you write will be interpreted as a Predicate<Panda>, which means that there should be exactly one parameter, which has type Panda, and the lamda must either return a boolean or evaluate to a boolean (which is then treated as a return value).

What determines what is passed the expression as p?  Well, that's entirely dependent on the method that uses the lambda.  In your code, it's being passed to the check() method, so when you call check(), check() will determine what to do with the lambda.


So here, the predicate is called pred, that's the thing represented by the lambda elsewhere.  What is done with pred?  It's called exactly once: pred.test(panda).  So in this case, when it's called, it's passed the value of panda, which is the same as what was called p1 in the other method.  It could have been called with some other value.  But in this case, it's been written to call using the value of panda which is p1 elsewhere.

Some methods will call a lambda many times with different values. Some will call it once.  Some will not call it at all (or only if certain conditions are met).  The possibilities are as varied or as complicated as you want, depending on what the programmer writes.
2 weeks ago
Agreed.  That's why my next() just returns an int.
3 weeks ago
@salvin, I would recommend against using randomList.remove(0) on an ArrayList.  That's an O(N) operation each time you call it.  I would either remove from the end, or use a LinkedList.  Either would be O(1).
3 weeks ago