Jump to content
Sign in to follow this  
Quantumkiwi

Can I optimize this?

Recommended Posts

All you great Java gods of Wotlabs,

Is there any way I can optimize this code? I am using recursion to find Fibonacci numbers (just a little yolo thing) and it was orders of magnitude slower than using non-recursive methods.

 

Here is a screenshot of a test, finding the 55th Fibonacci number. The times are in nanoseconds and are really stupid for the recursion side.

 

Y6XmnXU.pngglaj571.png

 

 

Here is a screenshot of my code, just excuse my messy, haven't been learning java that long.

42UBlFM.png

Fibonacci.txt

Share this post


Link to post
Share on other sites

Unfortunately that's just the way recursive methods work on OOP languages... Typically slower than iterative due to the required overhead for recursive methods (unless in C, there's a way to make it faster... Forgot how :/)

Why recursive? Unless there's no algorithm for the iterative code on-hand and/or you have space constraints (file sizes yo), I don't see that much purpose in recursive methods.

...

EDIT: shit I just realized... Fibonacci numbers. Welp, using fib(x-2)+fib(x-1) means the program is doing extra work as its rescanning over the same values. Unless you implement memorization to store the values (to skip over/ quickly refer back to), there isn't anything else you can do.

...

Either way, I've personally tried to avoid recursive methods ( unless it proves to have a significant edge, whether it be easier debugging or it being more efficient) because brute-forcing iterative is best (lolno, but easier algorithms) and that I'm generally shit at writing them (I can't wrap my mind around its application beyond simple programs).

Share this post


Link to post
Share on other sites

 

 

Also, the amount of cringe worthy things in the OP is kinda funny.

Please tell. I have a java exam in 4 days. Engage cramming mode.

Share this post


Link to post
Share on other sites

Please tell. I have a java exam in 4 days. Engage cramming mode.

Com sci student here (lel), but I don't really find any horribad mistakes. It's either variable type use (I personally prefer sticking to 3 types: int, float and double) or deviance from "proper" formatting (lol who gives a shit as long as its commented, so later programmers know what the hell you were doing, and readable (anyone that tries to one- line an entire method in an attempt to minimize whitespace, please go jump off a cliff kthxbye))

I'm still considered a potato compared to anyone working in a tech company ATM, so take this with a handful of salt.

Share this post


Link to post
Share on other sites

(anyone that tries to one- line an entire method in an attempt to minimize whitespace, please go jump off a cliff kthxbye))

 

I do this to prevent myself from running out of paper.

 

Please tell. I have a java exam in 4 days. Engage cramming mode.

 

You are fine. Unless your exam require you to do something stupid like compare the performances of recursive and iterative loops on paper, just use whichever is easier for you. If your code works, it works.

Share this post


Link to post
Share on other sites

Extreme nitpicking:

https://google-styleguide.googlecode.com/svn/trunk/javaguide.html

 

Skim in your free time. There's a lot of places in your code where you don't even follow your own convention. It's nitpicky, but it makes it more readable. Also, if this was Python or something, then you'd be fucked. (And for the love of god indent those comments.) Your names are pretty terrible, too. Having function names "Fibo" and "Fibb" is really not helpful (you can go ham and be like "fibUsingRecurrance" and "fibUsingLooping" since you're probably going to shoot yourself in the foot if you're trying to remember those function names in another file without using an IDE). Also, Fib1,2,3 aren't descriptive as well.

 

As for coding things, both of your while loops should be for loops. Also, IIRC, printing in any language causes some variable lag (don't quote me on that, though), so you should just run the function and not print it.

 

And I really did lol when I saw that you attached the source as a .txt file.

 

Also: http://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_expression

 

on paper

 

There are only a few things worse than CS exams on paper: timed math tests in class and being shot in the balls.

 

deviance from "proper" formatting (lol who gives a shit as long as its commented, so later programmers know what the hell you were doing, and readable (anyone that tries to one- line an entire method in an attempt to minimize whitespace, please go jump off a cliff kthxbye))

 

https://xkcd.com/378/

Share this post


Link to post
Share on other sites

I do this to prevent myself from running out of paper.

You are fine. Unless your exam require you to do something stupid like compare the performances of recursive and iterative loops on paper, just use whichever is easier for you. If your code works, it works.

Oh shit you just brought back bad memories from CS AP exams years ago... (I hear they still do this, RiP). Whoever came up with that idea deserves to read horribly written (but correct in syntax, kek) code.

Writing code on paper is about as productive as making windows with a hammar and an open flame.

...

Mmm for loops, overlooked that one. I wouldn't recommend it for general purpose (e.x. Needing to access the variable outside the loop) but it definitely simplifies/cleans the code a bit here.

Share this post


Link to post
Share on other sites

Oh shit you just brought back bad memories from CS AP exams years ago... (I hear they still do this, RiP). Whoever came up with that idea deserves to read horribly written (but correct in syntax, kek) code.

Writing code on paper is about as productive as making windows with a hammar and an open flame.

...

Mmm for loops, overlooked that one. I wouldn't recommend it for general purpose (e.x. Needing to access the variable outside the loop) but it definitely simplifies/cleans the code a bit here.

Yeah. AP CS happens to be the exam I am taking. RIP.

 

Also, the reason I attached the code as .txt is because wotlabs whined at me about .java file attachments

Share this post


Link to post
Share on other sites

Yeah. AP CS happens to be the exam I am taking. RIP.

 

Also, the reason I attached the code as .txt is because wotlabs whined at me about .java file attachments

Aye, good luck on the exam ;)

Don't sweat over the open ended too much, seeing the 2015 questions released on CB and they're more-or-less as easy as those back in 2012.

Multiple choice... I hope you're good at tracing code, and know the algorithms to basic sorting. Those 2 were a PITA because I slacked off on them :P

Share this post


Link to post
Share on other sites

Yeah. AP CS happens to be the exam I am taking. RIP.

 

Wasn't that last week or something? Did they change the AP test times?

Share this post


Link to post
Share on other sites

Aye, good luck on the exam ;)

Don't sweat over the open ended too much, seeing the 2015 questions released on CB and they're more-or-less as easy as those back in 2012.

Multiple choice... I hope you're good at tracing code, and know the algorithms to basic sorting. Those 2 were a PITA because I slacked off on them :P

Yeah. I've been coding in Python for 8 years, but I have been slaking a lot off this year. The logic is fine to me, but I'm gonna suck some big cock when it come to syntax.

 

 

Wasn't that last week or something? Did they change the AP test times?

 

Yeah. I'm taking the late exam.

Share this post


Link to post
Share on other sites

Yeah. I've been coding in Python for 8 years, but I have been slaking a lot off this year. The logic is fine to me, but I'm gonna suck some big cock when it come to syntax.

 

I, for one, would never want to have to read any of your old Python code. (And you wouldn't want to read mine, either.) And Google exists for a reason.

 

(And fuck Python.)

Share this post


Link to post
Share on other sites

Python is a good language to start with, just not an ideal one for development.

 

Idk, I can appreciate Python for what it is, but there's just so many quirks of it that I can't stand.

 

But C master race even if I don't know it well.

Share this post


Link to post
Share on other sites

It's unfortunate that Fibonacci numbers are the typical introduction to recursion because doing that calculation recursively is almost always the wrong way to go. Tree traversals would be a better case study.

Python is a good language to start with, just not an ideal one for development.

WoTScout.com is 100% Python on the server. What makes you say that it isn't good for development?

I do most of my professional work in C, but that's mostly because I work with embedded systems. A Python interpreter doesn't fit in less than 1kB of RAM, and garbage collection is a deal breaker. For web apps, Python lets me get so much more done in the little time that I can devote to it.

Share this post


Link to post
Share on other sites

42UBlFM.png

 

As the others have said:

 

Class/type names = UpperCamelCase

Identifiers/methods = lowerCamelCase. (can't start these with a number but I'm sure you know that anyway :D)

Constants = CAPS_LOCK_IS_CRUISE_CONTROL_FOR_COOL.

 

Paraphrasing this from a book I have called "clean code" by Robert C. Martin. Just for the purpose of ever improving. ^^ (though note that this is some craftsmanship shit).

 

Making meaningful distinctions (comments/var names etc):

 

Intentional naming:

It is not sufficient to add number series or noise words, even though the compiler is satisfied. If names must be different, then they should also mean something different. Number-series naming (like Fib1 etc...) is the opposite of intentional naming. Such names are not disinformative - they are likely noninformative; they provide no clue to the author's intention.

 

Noise words:

Imagine you have a Product class. if you have another called ProductInfo or ProductData, you have made the names different without making them mean anything different. Info and data are indistinct noise words like a, an and the. Note: no problem using prefix conventions like these so long as they make meaningful distinctions. Ex: a for all local variable and the for all function arguments. The problem comes when you decide to call a variable theZork because you already have another variable named zork.

 

Noise words are redundant, the word variable should never appear in a variable name. Would name ever be a floating point number? if it is, then it breaks the earlier rule about disinformation. Imagine finding a class called Customer and another named CustomerObject. What should you understand as the distinction? There is a legit application with this error:

 

getActiveAccount();

getActiveAccounts();

getActiveAccountInfo(); 

 

How's anyone meant to know what one to call? 

 

TL;DR - Distinguish names in such a way that the reader knows what the differences offer.

 

Use pronounceable names:

If you can't pronounce it, you can't discuss it without sounding like an idiot. Compare:

 

class DtaRcrd102{

private Date genymdhms;

private Date modymdhms;

private final String pszqint = "102";

...

}

with

 

class Customer{

private Date generationTimestamp;

private Date modificationTimestamp;

private final String recordId = "102";

...

}

 

Use searchable names:

Single letter names and numeric constants have a particular problem in that they are not easy to locate across a body of text. One might easily grip for MAX_CLASSES_PER_STUDENT, but the number 7 could be more troublesome. Searches may turn up the digit as part of file names, other constant definitions, and in various expression where the value is used with different intent. It is even worse when a constant is a long number and someone might have transposed digits, thereby creating a bug while simultaneously evading the programmer's search.

 

Likewise the name e is a poor choice for any variable for which a programmer might need to search. It is the most common letter in the English language and likely to show up in every passage of text in every programme. In this regard, longer names trump shorter names, and any searchable name trumps a constant in code.

 

His personal preference is that single-letter names can ONLY be used as local variables inside short methods.

 

TL;DR - The length of a name should correspond to the size of its scope.

Share this post


Link to post
Share on other sites

Here's an optimization (I added an alternate recursive Fibonacci function):


public class Practice {
	//Finds the xth Fibonacci number using recursion
	public static int Fibb(int x){
		if (x==1 || x==2){
			return 1;
		} else {
			return Fibb(x-1)+Fibb(x-2);
		}
	}
	//Finds the yth Fibonacci number using non-recursive methods	
	public static int Fibo(int y){
		int i = 1;
		int Fib1 = 1;
		int Fib2 = 1;
		int Fib3 = 1;

		while (i<y) {
			Fib1 = Fib2;
			Fib2 = Fib3;
			Fib3 = Fib1 + Fib2;
			i++;
		}
		return Fib2;

	}

	/**
	 * Finds the zth Fibonacci number recursively
	 * @param z the rank of the Fibonacci number desired
	 * @return An array of integers of size 2.
	 * The idea here is to store the relevant sequence of previous 
	 * Fibonacci numbers in order to cut down on recursive calls by half.
	 */
	private static int[] alternateRecursiveFibo(int z){

		if (z == 1){
			return new int[] {0, 1};
		} else {

			/* the previous 2 Fibonacci numbers where
			 * sequence[0] = Fibonacci(z-2)
			 * sequence[1] = Fibonacci(z-1)
			 * */
			int[] sequence = alternateRecursiveFibo(z-1); //the recursive call

			//return the sequence for the next function call
			return new int[] {sequence[1], sequence[0] + sequence[1]};
		}
	}

	/**
	 * A simple wrapper function to use the alternate recursive Fibonnaci
	 * like the other functions.
	 * @param z the rank of the Fibonacci number desired
	 * @return the Fibonacci number itself
	 */
	public static int alternateFiboWrapper(int z){
		return alternateRecursiveFibo(z)[1];
	}

	public static void main (String[] args){
		int k = 0;
		final int FIBO_NUMBER = 45;
		int fiboOutput;
		//Just get 10 samples of times
		while (k<10) {
			//Time using Fibonacci recursive
			long start1 = System.nanoTime();	
			fiboOutput = Fibb(FIBO_NUMBER);
			long est1 = System.nanoTime() - start1;
			System.out.println("Recursive Fibonacci of " + FIBO_NUMBER + ": " + fiboOutput);

			//Time using Fibonacci non-recursive
			long start2 = System.nanoTime();
			fiboOutput = Fibo(FIBO_NUMBER);
			long est2 = System.nanoTime() - start2;
			System.out.println("Non recursive Fibonacci of " + FIBO_NUMBER + ": " + fiboOutput);

			//Time using Fibonacci non-recursive
			long start3 = System.nanoTime();
			fiboOutput = alternateFiboWrapper(FIBO_NUMBER);
			long est3 = System.nanoTime() - start3;
			System.out.println("Alternate recursive Fibonacci of " + FIBO_NUMBER + ": " + fiboOutput);

			//Print the times
			System.out.println("Recursion:" + est1);
			System.out.println("Normal:" + est2);
			System.out.println("Alternate:" + est3);
			k++;
		}
	}
}

Here's the output calculating the 45th Fibonacci number:

Recursive Fibonacci of 45: 1134903170
Non recursive Fibonacci of 45: 1134903170
Alternate recursive Fibonacci of 45: 1134903170
Recursion:5188456487
Normal:5133
Alternate:11549
Recursive Fibonacci of 45: 1134903170
Non recursive Fibonacci of 45: 1134903170
Alternate recursive Fibonacci of 45: 1134903170
Recursion:5244994801
Normal:1711
Alternate:9411
Recursive Fibonacci of 45: 1134903170
Non recursive Fibonacci of 45: 1134903170
Alternate recursive Fibonacci of 45: 1134903170
Recursion:5259395642
Normal:1711
Alternate:18392
Recursive Fibonacci of 45: 1134903170
Non recursive Fibonacci of 45: 1134903170
Alternate recursive Fibonacci of 45: 1134903170
Recursion:5143529780
Normal:1711
Alternate:9410
Recursive Fibonacci of 45: 1134903170
Non recursive Fibonacci of 45: 1134903170
Alternate recursive Fibonacci of 45: 1134903170
Recursion:5185913627
Normal:1710
Alternate:8983
Recursive Fibonacci of 45: 1134903170
Non recursive Fibonacci of 45: 1134903170
Alternate recursive Fibonacci of 45: 1134903170
Recursion:5320559010
Normal:18820
Alternate:215576
Recursive Fibonacci of 45: 1134903170
Non recursive Fibonacci of 45: 1134903170
Alternate recursive Fibonacci of 45: 1134903170
Recursion:6881610954
Normal:1711
Alternate:29085
Recursive Fibonacci of 45: 1134903170
Non recursive Fibonacci of 45: 1134903170
Alternate recursive Fibonacci of 45: 1134903170
Recursion:5807730293
Normal:1711
Alternate:2994
Recursive Fibonacci of 45: 1134903170
Non recursive Fibonacci of 45: 1134903170
Alternate recursive Fibonacci of 45: 1134903170
Recursion:5465185492
Normal:1283
Alternate:2994
Recursive Fibonacci of 45: 1134903170
Non recursive Fibonacci of 45: 1134903170
Alternate recursive Fibonacci of 45: 1134903170
Recursion:5214146855
Normal:1711
Alternate:5561

My laptop is too much of a potato to calculate the 55th number in a reasonable time frame. 

Change the constant "FIBO_NUMBER" in the main function to 55 if you wish to try it out.

From these results, the alternate fibo function is several orders of magnitude faster than the regular recursive call. Although the iterative is faster, it's not ridiculously faster.

The alternate recursive function stores the last two Fibonacci numbers in the sequence, hence cutting the recursive calls in half from the regular recursive function.

Share this post


Link to post
Share on other sites

It's unfortunate that Fibonacci numbers are the typical introduction to recursion because doing that calculation recursively is almost always the wrong way to go. Tree traversals would be a better case study.

 

They should do Ramsey numbers.

Share this post


Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Sign in to follow this  

  • Recently Browsing   0 members

    No registered users viewing this page.

×
×
  • Create New...