| 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) |
|
|
| 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. |
|
|
| North Korea |
[Dec. 22nd, 2011|01:40 am] |
North Korea constantly reminds us what's still possible in the 21st century.
|
|
|
| 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 |
|
|
| 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. |
|
|
| navigation |
| [ |
viewing |
| |
most recent entries |
] |
| [ |
go |
| |
earlier |
] |
| |
|
|