Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

I have written the following code using a dynamic programming technique. Can I use ArrayList here? Please let me know if I can improve this code.

package com.java.fib;

import java.math.BigInteger;
import java.util.HashMap;

public class Fibonaci {

    public static void main(String[] args) {
        System.out.println(" number ");
        long startTime = System.currentTimeMillis();
        HashMap<Integer, BigInteger> memoized = new HashMap<Integer, BigInteger>();
         fibonanci(220, memoized);
        System.out.println(" Total Time "
                + (System.currentTimeMillis() - startTime));
    }

    private static BigInteger fibonanci(int n, HashMap<Integer, BigInteger> memoized) {
        if (memoized.containsKey(n)) {
            return memoized.get(n);
        }
        if (n <= 0) {
             return BigInteger.ZERO;
        }
        if (n <= 2) {
            return BigInteger.ONE;
        } else {
            BigInteger  febonani = fibonanci(n - 1, memoized).add (fibonanci(n - 2, memoized));
            System.out.println(" febonani " + febonani);
                memoized.put(n, febonani);
            return febonani;
        }
    }
}
share|improve this question
add comment

6 Answers 6

A few things:

Naming:

It's neither Fibonaci, nor febonani, nor fibonanci it's fibonacci. Please get your names to reflect what you're actually talking about and not some disfigured mutation of it :(

memoized OTOH is a relatively nice name, I'd probably prefer memoizedFibonacciNumbers, but that's a thing of preference

Calculating:

quoting wikipedia:

By definition, the first two numbers in the Fibonacci sequence are \$1\$ and \$1\$, or \$0\$ and \$1\$, depending on the chosen starting point of the sequence, and each subsequent number is the sum of the previous two.

You on the other hand say:

The value of Fibonacci for \$n <= 0\$ is \$0\$, and for \$n <= 2\$ is \$1\$, and each subsequent number is the sum of the previous two.

Wikipedia also mentions "negative Fibonacci numbers". Your definition does not match the actual Fibonacci sequence definition :(

instead your fibonacci method should look like this, if you exactly follow the rules for only positive fibonacci numbers:

private static BigInteger fibonacci(Integer n, HashMap<Integer, BigInteger> memoized) {
    if (n < 0) {
       throw new IllegalArgumentException("We assume the positive Fibonacci sequence only");
    }
    if (memoized.containsKey(n)) {
        return memoized.get(n);
    }
    if (n == 0) {
        memoized.put(n, BigInteger.ZERO);
        return memoized.get(n);
    }
    if (n == 1) {
        memoized.put(n, BigInteger.ONE);
        return memoized.get(n);
    }
    BigInteger fibonacci = fibonacci(n-1, memoized).add(fibonacci(n-2, memoized));
    memoized.put(n, finbonacci);
    return fibonacci;
}

Printing is slow:

I see you benchmarking your code. Please keep in mind, that writing something to the Console is quite slow. Your measured execution time is not matching the calculation time.

You should remove the System.out.println() in your fibonacci method.

Conditionals

Also you maybe have already realized, I removed the else in the fibonacci method.

This is because if your code reaches that area, all other branches have returned early, and the else is quite useless.

share|improve this answer
    
Maybe "memorized" instead of "memoized"? –  Dmitry Ginzburg 2 days ago
    
Let my native Russian fix your native German :) –  Dmitry Ginzburg 2 days ago
6  
No, he means memoized, without the r. Memoization is a technique where you cache results of computations that are likely to be repeated. In particular, it's used often in recursive functions. –  Schism 2 days ago
2  
    
@Schism caught between two worlds... ahem. After seing the wikipedia article I think I will just roll back my own edits... –  Vogel612 2 days ago
show 1 more comment

@Vogel612 has already mentioned all major defects and areas of improvement in your code. I want to talk about one more thing:

Your package naming is horrible. You are using com.java.fib, please do not ever do that again, because:

  1. Although Java classes are prefixed with java.*, it still creates confusion as people might think this is a library class. In extreme cases when you use professional names, it might even lead to a name clash.
  2. You are pretending to be or have anything to do with java.com, which you really aren't and haven't.
  3. Change it to something imaginary or existing. Use your own name, or your own website, I usually use com.skiwi.*.
  4. Even com.skiwi.fib would be horrible because it offers barely any extra information, com.java.fib.Fibonacci is not helpful, consider something along the lines of com.skiwi.algorithms, in which the class Fibonacci can be found.
share|improve this answer
add comment

Don't use ArrayList. A lookup in the list with get(220) will throw an IndexOutOfBoundsException. Your list is not initialized by default. What you can do is to use an array for your values. It allows you to check, if an index is already filled (via != null). On the other hand, you'll have to predefine the size of your array. Also you'll have to check for indexbounds as well.

public static void main(String[] args) {
    final BigInteger[] fibonacciCache = new BigInteger[221];
    fibonacciCache[0] = BigInteger.ZERO;
    fibonacciCache[1] = BigInteger.ONE;
    fibonacci(220, fibonacciCache);
}

private static BigInteger fibonacci(int n, final BigInteger[] fibonacciCache) {
    if (n<0) n=0;
    if (fibonacciCache[n]!=null) {
      return fibonacciCache[n];
    }
    fibonacciCache[n] = fibonacci(n - 1, fibonacciCache).add(fibonacci(n - 2, fibonacciCache));
    return fibonacciCache[n];
}
share|improve this answer
add comment

Aside from the things other people have mentioned (notably throwing an error on negative numbers and correcting the spelling), I would reorder some of the functionality and add more elses like so:

    private static BigInteger fibonacci(int n, HashMap<Integer, BigInteger> memoized)
    {
            if (n <= 0) {
                 return BigInteger.ZERO;
            } else if (n <= 2) {
                return BigInteger.ONE;
            } else if (memoized.containsKey(n)) {
                return memoized.get(n);
            } else {
                BigInteger  result = fibonacci(n - 1, memoized).add (fibonacci(n - 2, memoized));
                memoized.put(n, result);
                return result;
            }
    }

I'd also suggest that instead of making the user provide the memoized hash, you instead make a private static hash. Aside from making less work for the user, this would also allow you to preload the hash with the values of 0, 1 and 2, meaning you could strim out some of the function's logic and make it simpler.

    private static HashMap<Integer, BigInteger> memoizedHash;
    static
    {
        memoizedHash = new HashMap<Integer, BigInteger>();
        memoizedHash.put(0, BigInteger.ZERO);
        memoizedHash.put(1, BigInteger.ONE);
        memoizedHash.put(2, BigInteger.ONE);
    }
    private static BigInteger fibonacci(int n)
    {
        if (memoizedHash.containsKey(n)) {
            return memoizedHash.get(n);
        } else {
            BigInteger  result = fibonacci(n - 1).add (fibonacci(n - 2));
            memoizedHash.put(n, result);
            return result;
        }
    }
share|improve this answer
add comment

You can use ArrayList instead of HashMap here.

Update:

After some comments, I reimplement using non-recursive way, it took a bit longer than your source code (15 ms in comparison with 11 ms running on my computer), but most of time is spent to print output by System.out.println function. There is a small difference, I added 3 first numbers of Fibonaci sequence (0, 1, 1) to the result array.

public class Fibonaci {

    public static int count = 0;

    public static void main(String[] args) {
        ArrayList<BigInteger> memoized = new ArrayList<BigInteger>();

        long startTime = System.currentTimeMillis();
        fibonanci(220, memoized);

        for(int i = 0; i < memoized.size(); i++) {
            System.out.println(" febonani " + memoized.get(i));
        }

        System.out.println(" Total Time " + (System.currentTimeMillis() - startTime));
    }

    private static BigInteger fibonanci(int n, ArrayList<BigInteger> memoized) {
        BigInteger febonani = BigInteger.ZERO;
        int size = memoized.size();
        if (n < 0) {
            return BigInteger.ZERO;
        }
        if (size > n) {
                febonani = memoized.get(n);
        } else {
            for(int i = size; i <= n; i++) {
                if(i == 0) {
                    febonani = BigInteger.ZERO;
                } else if(i == 1 || i == 2) {
                    febonani = BigInteger.ONE;
                } else {
                    febonani = memoized.get(i - 1).add(memoized.get(i - 2));
                }
                memoized.add(febonani);
            }
        }
        return febonani;
    }
}
share|improve this answer
2  
You might want to elaborate a bit on why ArrayList is better than HashMap. Additionally you should declare memoized as a List<BigInteger>. That makes swapping ArrayList for e.g. LinkedList much easier –  Vogel612 Jul 22 at 7:49
    
I tried to replace but encountered this error: The type List is not generic; it cannot be parameterized with arguments –  Dai Nguyen-Van Jul 22 at 8:04
1  
You use the wrong import. Don't use java.awt.List, but java.util.List –  Vogel612 Jul 22 at 8:29
    
IS the logic of using ArrayList is correct for 2 the fibonacci value is 1 does your logic handle this –  VIckyb Jul 22 at 8:47
1  
@Dai : i mean to say n can be 100 but your adding to arraylist the value of 100 at may 40 place suppose in that this may fail –  VIckyb 2 days ago
show 10 more comments

You can avoid using the HashMap:

public class Fibonacci {

    public static void main(String[] args) {
        System.out.println(" number ");
        long startTime = System.currentTimeMillis();
        fibonancci(220, BigInteger.ONE, BigInteger.ZERO);
        System.out.println(" Total Time "
                + (System.currentTimeMillis() - startTime));
    }

    private static BigInteger fibonancci(int n, BigInteger last, BigInteger prev_last) {
        if (n==1) return last;
        if (n<=0) return prev_last;
        return fibonancci(n-1, last.add(prev_last), last);
    }
}

it may be faster without recursion:

private static BigInteger fibonancci(int n) {
    BigInteger last =  BigInteger.ONE;
    BigInteger prev_last = BigInteger.ZERO;
    for (int i = 1; i<n; i++) {
        BigInteger sum = last.add(prev_last);
        prev_last = last;
        last = sum;
    }
    return last;
}
share|improve this answer
2  
Hello there and welcome to Code Review! I have a big problem with your answer. You don't explain why the changes you suggest should be performed. Also you should never make guesses on performance. Most guesses, even by extremely experienced people are far off... You have provided a possible different attempt, but I can tell you (because I ran some tests) that using the hash map is faster by orders of magnitude. I'd personally remove the first half of your answer and explain the second one. If you edit, I may / will revoke my downvote or even upvote –  Vogel612 15 hours ago
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.