You are viewing [info]dennisgorelik's journal

Dennis Gorelik [entries|archive|friends|userinfo]
Dennis Gorelik

[ website | My Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Comparing complexity of imperative code versus functional programming code [May. 29th, 2012|04:07 am]
Here are two programs that are functionally equivalent - generate list of prime numbers.

C# version (imperative programming):
=============
int[] Primes;
private void FindPrimes(int numberOfPrimeToFind)
{
	Primes = new int[numberOfPrimeToFind];
	Primes[0] = 2;
	int primeCount = 1;
	for (int primeCandidate = 3; primeCount < numberOfPrimeToFind; primeCandidate++)
	{
		if (IsPrime(primeCandidate))
		{
			Primes[primeCount] = primeCandidate;
			primeCount++;
		}
	}
}

private bool IsPrime(int primeCandidate)
{
	int maxDivisor = (int)Math.Sqrt(primeCandidate);
	int i = 0;
	while (Primes[i] <= maxDivisor)
	{
		if (primeCandidate % Primes[i] == 0)
		{
			return false;
		}
		i++;
	}
	return true;
}
=============

Here's Version 2 in Functional Programming:
-----
val primes: Stream[Int] = 2 #:: Stream.from(3,2).filter( x=> !primes.takeWhile( _ <= sqrt(x) ).exists( x % _ == ) ) )
-----
That's right, just one line.
That's a huge gain in simplicity, right?

Actually - no. Second version is more complex even though it's a one-liner.
Let's count to be sure.

I evaluate complexity of the code by number of potential connections that programmer may guess during very brief look at the code.
Here's the algorithm:
To calculate class complexity - let's count number of methods in that class.
Then assume, that every method may relate to any other method in that class. Bi-directionally.
That means number of connections (complexity) would be:
NumberOfMethods * (NumberOfMethods - 1).

For two methods the complexity would be 2 * 1 = 2

In a similar way we can count complexity of every method - by number of lines in these methods.
For example, FindPrimes() has 14 lines.
So FindPrimes()'s complexity is: 14*13 = 182.

Again, in a similar way count complexity of every individual line -- by number of tokens that line contains.
Every word - one token. Every operator - one token. Every parenthesis, bracket, comma, point, or semicolon - one token.
For example, the most complex line
for (int primeCandidate = 3; primeCount < numberOfPrimeToFind; primeCandidate++)
contains 14tokens.
So that line complexity is: 182.

End result:
Total complexity of first (C#) version of program is - 1232 connections.

The second (one line Functional Programming) example contains 44 tokens in single line.
That implies 1892 potential connections. 1892 points of complexity.
That means 54% more complex than much longer C# example.

Appendix:
Detailed complexity calculations:
https://docs.google.com/spreadsheet/ccc?key=0AlMRv1CN7-PXdElaemcwSE1Eb0NCS2xhUS16Rm1DalE

Note, that if original task would be more complex, then one-line approach for solving it would give truly terrible results (due to number of potential relations between tokens in that super-line - the relations that programmer must evaluate in his head while trying to understand that one-line solution).

See original discussion (Russian)
Link34 comments|Leave a comment

Zuck married [May. 21st, 2012|12:21 am]
http://news.ycombinator.com/item?id=3997999
The last week for Zuckerberg:
Monday: Girlfriend got M.D.
Tuesday: 28th birthday.
Friday: IPO.
Saturday: Married.
LinkLeave a comment

One day on Earth from 35000 km above [May. 14th, 2012|02:07 pm]


You can see how Sun reflects from Earth.

Source
LinkLeave a comment

The joy of tech: Christmas past and Christmas present [Dec. 31st, 2011|10:58 pm]


Thanks to MySpace First Friend
Link15 comments|Leave a comment

DBMS vs BDSM [Dec. 29th, 2011|02:16 pm]
Developers' joke in Wikipedia:
====
http://en.wikipedia.org/wiki/BDSM
Not to be confused with DBMS.
====

I guess there are enough similarities between BDSM and DMBS that people confuse these things:
1) Both are complex systems.
2) Dominant (DBA) and submissive (DBMS) participants are present at both.
3) Mutual dependence.
4) Occasional misbehavior.
Link6 comments|Leave a comment

North Korea [Dec. 22nd, 2011|01:40 am]
North Korea constantly reminds us what's still possible in the 21st century.



LinkLeave a comment

Learning WordPress [Dec. 6th, 2011|03:36 pm]
It took a few years to get around it, but I'm finally switching to WordPress.
Blogger.com looks pathetic in comparison.
Even Google+ is not as good.
Besides there is a risk that Google Plus team would go on killing spree like Blogger did.

Anyway, here's my new poll:
http://dennisgorelik.wordpress.com/2011/12/06/poll-what-to-write-about/

Please leave your suggestions about what you'd like me to write about.

Does anyone know if I can autopost my WordPress postings into LiveJournal?
Link11 comments|Leave a comment

Google Blogger deleted my blog [Nov. 30th, 2011|11:29 pm]
That's not the first Blogger deleted one of my blogs by mistake, but this time it looks like I'm not getting my blog back.

Here's the discussion with "helping Samaritan":
============
http://www.google.com/support/forum/p/blogger/thread?hl=en&tid=71ad4b179828d855

Dennis Gorelik: I personally wrote every one of these articles.
There is (and never was) scrapped content there.

.....

nitecruzr: OK, back to the "scraping" operations.
1. From where do you scrape?
2. To where do you scrape?
3. How often do you scrape?
4. Do you scrape whole pages, whole posts, or excerpts?
5. Is it possible that someone else scrapes a second time - regardless of whether you "control" such process or not?

============

No surprise that Blogger is on the decline:
http://www.quantcast.com/blogger.com
Link13 comments|Leave a comment

Demi and Ashton Are Divorcing [Nov. 17th, 2011|11:08 pm]
Demi Moore divorces Ashton (Ashton confirms it).

That made me learn what cougar means.
Link1 comment|Leave a comment

Cocos (Keeling) Islands [Nov. 15th, 2011|10:36 pm]
http://en.wikipedia.org/wiki/Cocos_(Keeling)_Islands
Population - 596
The islands have a five-person police force...

History
In 1814 ... a wealthy Englishman named Alexander Hare ... hired a captain ... to bring him and a harem of forty Malay women to the islands.

When Clunies-Ross returned two years later with his wife, children and mother-in-law, and found Hare already established on the island and living with a private harem, a feud grew instantly between the two men. Clunies-Ross' eight sailors, "began at once the invasion of the new kingdom to take possession of it, women and all".

After some time, Hare's women began deserting him, and instead finding themselves mates amongst Clunies-Ross' sailors. Disheartened, Hare left the island.


Map of Cocos (Keeling) Islands

Cocos (Keeling) Islands own .cc Internet domain zone.
LinkLeave a comment

navigation
[ viewing | most recent entries ]
[ go | earlier ]