• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Devaka Cooray
  • Liutauras Vilda
  • Jeanne Boyarsky
  • Bear Bibeault
Sheriffs:
  • Paul Clapham
  • Knute Snortum
  • Rob Spoor
Saloon Keepers:
  • Tim Moores
  • Ron McLeod
  • Piet Souris
  • Stephan van Hulst
  • Carey Brown
Bartenders:
  • Tim Holloway
  • Frits Walraven
  • Ganesh Patekar

Calculating Fibonacci numbers with Map#computeIfAbsent

 
Marshal
Posts: 65113
247
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
So we look in Ken Kousen's book (page 123) and it tells you about the Map#computeIfAbsent(), and there is an example for calculating Fibonacci numbers. So I tried it on the train yesterday, where I didn't have any internet connection and I thought I couldn't check the documentation:-So let's try a nice big number and see if we can't calculate Fibonacci numbers up to it:-

java AbsentFibonacciDemo
1000000
Exception in thread "main" java.lang.StackOverflowError
at java.base/java.lang.Long.hashCode(Long.java:1404)

Surprise, surprise. At least the stack trace wasn't 1,000,000 lines long So let's try a smaller number:-

java AbsentFibonacciDemo
2000

Exception in thread "main" java.util.ConcurrentModificationException
at java.base/java.util.HashMap.computeIfAbsent(HashMap.java:1138)
at AbsentFibonacciDemo.fib(AbsentFibonacciDemo.java:25)
at AbsentFibonacciDemo.lambda$fib$0(AbsentFibonacciDemo.java:25)
at java.base/java.util.HashMap.computeIfAbsent(HashMap.java:1137)
at AbsentFibonacciDemo.fib(AbsentFibonacciDemo.java:25)
at AbsentFibonacciDemo.lambda$fib$0(AbsentFibonacciDemo.java:25)
at java.base/java.util.HashMap.computeIfAbsent(HashMap.java:1137)
at AbsentFibonacciDemo.fib(AbsentFibonacciDemo.java:25)

java AbsentFibonacciDemo
0
fib(0) = 0
1
fib(1) = 1
2
fib(2) = 1
3
fib(3) = 2
4
fib(4) = 3
5
fib(5) = 5
6
fib(6) = 8
7
fib(7) = 13
8
fib(8) = 21
9
fib(9) = 34
10
fib(10) = 55
11
fib(11) = 89
-1

Which appears to mean you can't calculate big Fibonacci numbers like that. Only a key one larger than the preceding keys in the Map. So today I went to look in the documentation (link above) and it seems the computeIfAbsent method is intended for computing a single value to be put into the Map; since the method I was using would appear to be attempting to put multiple values into the Map, that isn't allowed and any attempt would appear to require a concurrent modification exception be thrown.
I haven't checked whether computeIfPresent also only calculates a single value: Let's look. Yes, it does:

That API link (computeIfPresent) wrote:The remapping function should not modify this map during computation. . . . Non-concurrent implementations should override this method and, on a best-effort basis, throw a ConcurrentModificationException if it is detected

Isn't that in line with the conventions of functional programming? Altering the Map anywhere else would constitute a side effect and side effects are to be avoided.
 
Rancher
Posts: 352
21
Mac OS X Monad Clojure Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
In Functional Programming, you wouldn’t be updating in place — your hash map would be immutable — so there wouldn’t be any concurrency issues to avoid.
 
Author
Posts: 160
31
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Not sure what the question is (I can't reproduce the ConcurrentModificationException), but it will not work anyway since Java recursion is extremely limited. Using corecursion through TCE is not possible neither, but it is possible with Stream (and of course with a simple loop!). Here is a quick and dirty working corecursive version using Stream:

 
Campbell Ritchie
Marshal
Posts: 65113
247
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
SC: Yes, isn't that why you would only compute one value at a time. I am not sure a Java® Map would be immutable because the computeIfAbset methpd puts a new Entry into the Map.
P-YS: I was wondering about whether it was possible to calculate lots of Fibonacci numbers like that; if I start with 2 and go up one at a time, I get Fibonacci numbers printed. If I leave a gap inthe sequence however (e.g. 5→7 without using 6 first), I got that exception.
I am going to have to take some time to study your code. Thank you. I think however, you are iterating from the pairs already in the Map, in which case you would be avoiding any gaps. You get the exception if you have any gaps between the current size of the Map and the new value of input.
 
Pierre-Yves Saumont
Author
Posts: 160
31
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Yes, I think I understand that, but I can't reproduce it. Whatever value I use for input, it works except for the StackOverflow problem.
 
Pierre-Yves Saumont
Author
Posts: 160
31
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
By the way, I fixed a bug in my code. (I was not using the map!)
 
Saloon Keeper
Posts: 3416
149
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
With Campbells code, you can get the fib for much larger values if you build up the cache slowly.
For instance:
 
Campbell Ritchie
Marshal
Posts: 65113
247
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Yes, that's what I said; if you go up one at a time you don't suffer any exceptions.

By the way: that code is copied with very few changes from Ken Kousen's book; I'm not clever enough to work it out for myself.
 
Pierre-Yves Saumont
Author
Posts: 160
31
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
@Piet Yes, this effect may be observed with some recursive calls. But it will not work for really high values.


 
Pierre-Yves Saumont
Author
Posts: 160
31
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
@Piet Sorry, I did not read the code fully. You example is no longer recursive. Using forEach is like using a loop. I was thinking of the recursive example, if you ask for values incremented by one, the StackOverflowException may occur much later.
 
Pierre-Yves Saumont
Author
Posts: 160
31
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
@Sean Using an immutable map, you would have to store it somewhere, which means a mutable reference to a map. Or you can pass the map along with the number, and get back a map. Then you can extract the value from the map and ask for a new value passing the map along.

This would either mean that your successive calls are chained, or that they are made from a non functional program. Here his an example where the program is functional (although it is a simulation with a mutable map, but it would work just the same with an immutable one). Only the user (here the main method) is not functional:

 
Piet Souris
Saloon Keeper
Posts: 3416
149
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
My example was only meant to show that building up the cache slowly would allow for much larger values. I got to fib(164.000) before I got an OOM error.
 
Piet Souris
Saloon Keeper
Posts: 3416
149
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
@Pierre-Yves
Thanks for this code, it looks pretty impressive at first sight.

But if you compare this code with Campbells code, isn't the price for working with an immutable map not pretty high (in terms of complexity of the code)? (I wanted to ask a similar question like this on the forum about your book, but did not get to that unfortunately).
 
Sean Corfield
Rancher
Posts: 352
21
Mac OS X Monad Clojure Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
It’s instructive to compare those Java versions with three (very short, simple) Clojure versions in this article: http://blog.klipse.tech/clojurescript/2016/04/20/fibonacci.html
 
Pierre-Yves Saumont
Author
Posts: 160
31
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
@Piet  The cost is not very high but the benefit is null.  Of course, here you have to populate the map with three values. But this could be encapsulated in a FibCache class. So the only cost would be to get the initial FibCache and store it between successive calls. What are the benefits? In fact, there are none because either you share the cache, allowing other threads to benefit from the already computed values, but requiring synchronization of the cache, or you don't share the cache and you get the same result as when using a mutable map and not sharing the AbsentFibonacciDemo instance.

It is a common mistake to think that using immutable data structures makes sharing mutable state safer or easier. Immutable data structures prevent unintentional sharing of mutable state. This is fine when you don't need to share state. It makes sure you don't accidentally share mutable state. But it make sharing mutable state much more difficult. One solution, although not a functional one, is to use an actor framework which encapsulates access serialization and safe state mutation. It is not functional, but it fits nicely with functional programming. (This is chapter 14 of my book.)
 
Pierre-Yves Saumont
Author
Posts: 160
31
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
@Sean Fibonacci in Kotlin:

 
Pierre-Yves Saumont
Author
Posts: 160
31
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
@Piet: Your solution does not really consist in building up the cache slowly, but in precomputing the cache in increments of 1000 elements, which allows using recursion inside each increment. As Java is able to handle a few thousand recursion steps with the default stack size, you could use a value higher than 1000.

Stream.foEach is actually a loop. You don't need to display the precomputed values, so you could simply write:



These parameters allow for relatively fast precomputation and a function working up to n = 34 * 3000, so you can, for example, compute fib(100_000).

However, it is still limited. You can't go any further because you will be out of memory. Memoized functions should generally use some way of invalidating cache entries in order to recover memory space when necessary.


 
Pierre-Yves Saumont
Author
Posts: 160
31
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Here is an example of a very simple memoized recursive Fibonacci function. It works without any loop (not counting the loop in the main method, of course) for input values up to 100_000_000, without causing stack overflow nor heap overflow. It is very easy to alter to make it work for any long value (since this will, in any case, be limited to the maximum long value in Java).

It is not the fastest way to compute Fibonacci numbers (corecursion is not fast!). Only an example of handling recursion in a stack safe manner. Note that a maximum depth of 10_000 might not work for you. In such case, just use a lower value. Using 3_000 should work in all cases and allow calling the function with values up to 9_000_000. Also note that the fib(0 ) = 1. This is consistent with the definition, as the first Fibonacci number is 1.

 
Piet Souris
Saloon Keeper
Posts: 3416
149
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
hi Pierre-Yves,

thanks for this demo. It does work as you say, 5.000.000 is no problem, and you showed us (well, me at least) some totally new things. I just ordered your book, since I think there are quite some interesting new things to learn.

To get some practice, I took the liberty of adjusting your code slightly, even though it is just a demo. The fact that a Fib is recalculated from the ground up when it is not present in the cache is a pity. I changed the HashMap to a TreeMap, and only stored a Fib if its index is a multiple of 1000. If an index is absent, then I start from the closest available index in the cache, and calculating from there, either going forward of going backward. I added for this reason also a 'predecessor' to the Pair class.
Well, it was just to keep me busy for a while.

Thanks Campbell, for starting this interesting topic.
 
Pierre-Yves Saumont
Author
Posts: 160
31
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Very good idea. In a previous example, I had implemented a system consisting of starting from the highest value present in the cache in case the needed value was not found, but it  would not work with a WeakHashMap. (Or should we implement a WeakTreeMap?   )
 
Campbell Ritchie
Marshal
Posts: 65113
247
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thank you for the cow whoever it was.
 
Don't get me started about those stupid light bulbs.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!