?

Log in

No account? Create an account
 
 
29 May 2012 @ 04:07 am
Comparing complexity of imperative code versus functional programming code  
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)


Update:
And the winner is ... drumroll ... combination of imperative and functional code in Python by justy_tylor:
def is_prime(candidate):
    limit = int(sqrt(candidate)+0.1)
    for prime in primes:
        if prime>limit: return True
        if candidate%prime==0: return False
primes = lazy_seq([2], ifilter(is_prime, xrange(3, 10000000, 2)))

866 units of complexity -- 34% improvement over pure imperative version.
 
 
 
sassa_nf on May 29th, 2012 12:08 pm (UTC)
garbage metric for biased results.

Prove the following properties of IsPrime:

a. will ever finish
b. will always read within array bounds
c. will always read primes that were computed


You forgot to mention what I already pointed out: you completely missed the point of the "one liner". It is not the number of lines that matters. You can re-write it as multiple lines, you can separate the result of each computation into separate values, it doesn't matter. What matters is that you get the implementation that is correct by construction.
Dennis Gorelikdennisgorelik on May 29th, 2012 06:30 pm (UTC)
Look, that's prototype code, not production code.
The main purpose of this prototype code is to be close to potential production version and compare complexity of that code vs alternative implementation (Functional Programming).

Regarding your suggestions:
a. will ever finish

IsPrime() will always finish.
It may finish with an exception if you pass parameters outside of the scope, but that would be ok finish anyway.

b. will always read within array bounds

That check is done by .NET framework.
If violated - it throws an exception.
I should try to avoid exceptions for normal business use, other manual checks are optional.

c. will always read primes that were computed

Not sure what you mean here.

sassa_nf on May 29th, 2012 06:54 pm (UTC)
no, the original point I was making is the actual complexity of code verification, so no point comparing to "production code".


"IsPrime() will always finish."

where's the proof? I am asking for the proof exactly to show how complex the verification is.


"That check is done by .NET framework."

who cares? You still will bum out, if the array bounds are crossed, instead of finishing correctly.


"Not sure what you mean here."

Is Primes[i] computed, or the initial 0 written there by the array constructor?
(no subject) - sassa_nf on May 29th, 2012 07:09 pm (UTC) (Expand)
(no subject) - dennisgorelik on May 29th, 2012 08:58 pm (UTC) (Expand)
(no subject) - sassa_nf on May 29th, 2012 09:14 pm (UTC) (Expand)
(no subject) - dennisgorelik on May 29th, 2012 11:06 pm (UTC) (Expand)
(no subject) - sassa_nf on May 30th, 2012 07:19 am (UTC) (Expand)
(no subject) - dennisgorelik on May 30th, 2012 07:47 am (UTC) (Expand)
(no subject) - sassa_nf on May 30th, 2012 09:23 am (UTC) (Expand)
(no subject) - dennisgorelik on May 30th, 2012 03:01 pm (UTC) (Expand)
(no subject) - sassa_nf on May 30th, 2012 06:51 pm (UTC) (Expand)
(no subject) - dennisgorelik on May 30th, 2012 07:13 pm (UTC) (Expand)
(no subject) - sassa_nf on May 30th, 2012 08:26 pm (UTC) (Expand)
(no subject) - dennisgorelik on May 30th, 2012 08:48 pm (UTC) (Expand)
(no subject) - sassa_nf on May 30th, 2012 09:00 pm (UTC) (Expand)
(no subject) - sassa_nf on May 30th, 2012 08:38 pm (UTC) (Expand)
(no subject) - dennisgorelik on May 30th, 2012 09:09 pm (UTC) (Expand)
(Deleted comment)
(no subject) - dennisgorelik on May 31st, 2012 10:39 am (UTC) (Expand)
(no subject) - sassa_nf on May 31st, 2012 08:34 am (UTC) (Expand)
(no subject) - dennisgorelik on May 31st, 2012 10:47 am (UTC) (Expand)
(no subject) - sassa_nf on May 31st, 2012 11:54 am (UTC) (Expand)
(no subject) - dennisgorelik on May 31st, 2012 08:44 pm (UTC) (Expand)
(no subject) - sassa_nf on May 31st, 2012 09:14 pm (UTC) (Expand)
(no subject) - dennisgorelik on May 31st, 2012 09:32 pm (UTC) (Expand)
(no subject) - sassa_nf on June 1st, 2012 08:55 am (UTC) (Expand)
(no subject) - dennisgorelik on June 1st, 2012 05:56 pm (UTC) (Expand)
(no subject) - sassa_nf on June 2nd, 2012 08:47 am (UTC) (Expand)
(no subject) - dennisgorelik on June 2nd, 2012 03:12 pm (UTC) (Expand)
(no subject) - sassa_nf on June 6th, 2012 11:12 am (UTC) (Expand)
(no subject) - dennisgorelik on June 6th, 2012 09:51 pm (UTC) (Expand)
(no subject) - sassa_nf on June 8th, 2012 01:21 pm (UTC) (Expand)
(no subject) - dennisgorelik on June 8th, 2012 03:38 pm (UTC) (Expand)
(no subject) - sassa_nf on June 8th, 2012 04:53 pm (UTC) (Expand)
(no subject) - dennisgorelik on June 8th, 2012 06:06 pm (UTC) (Expand)
(no subject) - sassa_nf on June 8th, 2012 06:18 pm (UTC) (Expand)
(no subject) - dennisgorelik on June 8th, 2012 06:38 pm (UTC) (Expand)
(no subject) - sassa_nf on June 8th, 2012 06:52 pm (UTC) (Expand)
(no subject) - dennisgorelik on June 8th, 2012 07:18 pm (UTC) (Expand)
(no subject) - dennisgorelik on June 6th, 2012 09:55 pm (UTC) (Expand)
(no subject) - sassa_nf on June 8th, 2012 12:59 pm (UTC) (Expand)
(no subject) - dennisgorelik on June 8th, 2012 03:33 pm (UTC) (Expand)
(no subject) - sassa_nf on June 8th, 2012 04:32 pm (UTC) (Expand)
(no subject) - dennisgorelik on June 8th, 2012 05:19 pm (UTC) (Expand)
(no subject) - sassa_nf on May 31st, 2012 08:48 am (UTC) (Expand)
(no subject) - dennisgorelik on May 31st, 2012 10:55 am (UTC) (Expand)
(no subject) - sassa_nf on May 31st, 2012 12:04 pm (UTC) (Expand)
(no subject) - dennisgorelik on May 31st, 2012 08:34 pm (UTC) (Expand)
(no subject) - sassa_nf on May 30th, 2012 09:24 am (UTC) (Expand)
(no subject) - dennisgorelik on May 29th, 2012 10:33 pm (UTC) (Expand)
occam_agaoccam_aga on May 29th, 2012 05:00 pm (UTC)
"C#" убрать, "imperative programming" оставить. В C# есть и while и filter и exists и from и даже var.
Dennis Gorelikdennisgorelik on May 29th, 2012 06:01 pm (UTC)
Спасибо - то есть можно написать эту FP строчку и на C#?
occam_agaoccam_aga on May 29th, 2012 06:37 pm (UTC)
Ну если тупо странслировать понятое мной, один в один, то получится так:

int count = 10;
var primes = Enumerable.Range(2, int.MaxValue-1).Where(x => Enumerable.Range(2, int.MaxValue-1).TakeWhile(div => div <= Math.Sqrt(x)).All(div => x % div != 0)).Take(count);

Хотя я синтаксис скалы не знаю.

[Update]

var primes = Enumerable.Range(2, int.MaxValue-1).Where(x => Enumerable.Range(2, int.MaxValue-1).TakeWhile(div => div <= Math.Sqrt(x)).All(div => x % div != 0));

Так ближе к оригиналу, primes.Take(count) можно потом добавить

Edited at 2012-05-29 06:47 pm (UTC)
Dennis Gorelikdennisgorelik on May 29th, 2012 07:37 pm (UTC)
Спасибо - первая версия для первого ознакомления полезнее, потому что понятнее, что делать с результатом.

Но всё в целом понять - всё равно очень тяжело:

Почему "Range(2, int.MaxValue-1)"?
int.MaxValue-1 -- это просто верхняя граница, которая совсем необязательно достигается?

TakeWhile определяет когда нужно из цикла вывалиться?
(no subject) - occam_aga on May 29th, 2012 08:51 pm (UTC) (Expand)
(no subject) - dennisgorelik on May 30th, 2012 12:37 am (UTC) (Expand)
(no subject) - occam_aga on May 30th, 2012 12:53 am (UTC) (Expand)
(no subject) - dennisgorelik on May 30th, 2012 01:03 am (UTC) (Expand)
(no subject) - occam_aga on May 30th, 2012 09:44 pm (UTC) (Expand)
(no subject) - dennisgorelik on May 30th, 2012 11:36 pm (UTC) (Expand)
(no subject) - sassa_nf on May 31st, 2012 08:51 am (UTC) (Expand)
Dennis Gorelikdennisgorelik on June 2nd, 2012 04:32 pm (UTC)
Подскажите пожалуйста, можно ли написать на C# аналог вот этого Python кода?
def is_prime(candidate):
    limit = int(sqrt(candidate)+0.1)
    for prime in primes:
        if prime>limit: return True
        if candidate%prime==0: return False
primes = lazy_seq([2], ifilter(is_prime, xrange(3, 10000000, 2)))


Моя версия почему-то впадает в бесконечный цикл:
public string GetPrimes(int count)
{
	Primes = Enumerable.Range(2, int.MaxValue - 1).Where(x => IsPrime(x)).Take(count);
	return string.Join(" ", Primes);
}

IEnumerable Primes;
private bool IsPrime(int primeCandidate)
{
	int maxDivisor = (int)Math.Sqrt(primeCandidate);
	int maxPrimeDivisor = (int)Math.Sqrt(primeCandidate);
	foreach (int prime in Primes)
	{
		if (primeCandidate % prime == 0) return false;
		if (prime > maxPrimeDivisor) return true;
	}
	return true;
}
occam_agaoccam_aga on June 2nd, 2012 06:25 pm (UTC)
IEnumerable <int> Primes;

public void Run()
{
	Primes = Enumerable.Range(2, int.MaxValue - 1).Where(x => IsPrime(x));

	var xx = Primes.Take(10).ToArray();
}

bool IsPrime(int primeCandidate)
{
	if (primeCandidate == 2) return true;
	int maxDivisor = (int)Math.Sqrt(primeCandidate);
	foreach (int prime in Primes)
	{
		if (primeCandidate % prime == 0) return false;
		if (prime > maxDivisor) return true;
	}
	return true;
}

Только это как-то все запутано, если нет цели иметь рекурсию то можно попроще. Алгоритмы это не самая сильная моя сторона, вроде бы тупое Решето Эратосфена наилучший:
int maxN = 100;

Func<int, int, IEnumerable<int>> nonprimes = (multiplier, limit) => 
	Enumerable.Range(2, int.MaxValue-1)
	.Select(i => multiplier * i)
	.TakeWhile(y => y < limit);

var allNonprimes = Enumerable.Range(2, maxN - 1)
	.SelectMany(i => nonprimes(i, maxN));

var primes = Enumerable.Range(2, maxN - 2)
	.Except(allNonprimes)
	.ToArray();

BTW, если каждый метод писать на новой строчке то читать легче, новые переменные при этом вводить не обязательно.

Блин, как эти html ные значки замучали. И превью нет, приходится & lt ; методом проб и ошибок расставлять :) Вот еще в одном месте. Ща еще попробую pre добавить. Ну тогда и опечатки исправлю, сорри за "тыщу" правок :)

Edited at 2012-06-02 06:34 pm (UTC)
Dennis Gorelikdennisgorelik on June 2nd, 2012 06:52 pm (UTC)
Почему добавление
if (primeCandidate == 2) return true;
решило проблему бесконечного цикла?

Если Primes изначально пустой, то foreach loop должен был закончиться не начавшись с тем же самым результатом true.

Это какая-то хитрая специфика Enumerable.Range()?
(no subject) - occam_aga on June 2nd, 2012 07:21 pm (UTC) (Expand)
(no subject) - dennisgorelik on June 2nd, 2012 08:19 pm (UTC) (Expand)
(no subject) - occam_aga on June 2nd, 2012 08:24 pm (UTC) (Expand)
(no subject) - dennisgorelik on June 2nd, 2012 10:49 pm (UTC) (Expand)
(no subject) - occam_aga on June 2nd, 2012 11:22 pm (UTC) (Expand)
(no subject) - dennisgorelik on June 3rd, 2012 12:19 am (UTC) (Expand)
(no subject) - occam_aga on June 3rd, 2012 03:35 am (UTC) (Expand)
(no subject) - occam_aga on June 3rd, 2012 05:29 am (UTC) (Expand)
(no subject) - dennisgorelik on June 3rd, 2012 07:27 am (UTC) (Expand)
(no subject) - occam_aga on June 3rd, 2012 07:37 am (UTC) (Expand)
(no subject) - dennisgorelik on June 3rd, 2012 09:02 am (UTC) (Expand)
(no subject) - occam_aga on June 3rd, 2012 06:29 pm (UTC) (Expand)
Dennis Gorelikdennisgorelik on June 2nd, 2012 07:47 pm (UTC)
Решето Эратосфена получилось почти в тридцать раз быстрее (1.4 megaticks vs 41 megaticks для первых десяти тысяч простых чисел).
:-О

Но это бизнес-улучшение (лучший алгоритм от математиков), а не улучшение в стиле кодирования.
Поэтому из конкурса дисквалифицируется
:-)

Кстати, зачем использовать Func<...>?
Чтобы за скалой в обфункционаливании угнаться?
:-)

Может быть лучше так:
int maxN = 105000;

var allNonprimes = Enumerable.Range(2, maxN - 1)
	.SelectMany(i => NotPrimes(i, maxN));

Primes = Enumerable.Range(2, maxN - 2)
	.Except(allNonprimes)
	.ToArray();

IEnumerable<int> NotPrimes(int multiplier, int limit)
{
	return Enumerable.Range(2, int.MaxValue - 1)
		.Select(i => multiplier * i)
		.TakeWhile(y => y < limit);
}
?
(no subject) - occam_aga on June 2nd, 2012 08:12 pm (UTC) (Expand)
(no subject) - dennisgorelik on June 2nd, 2012 09:28 pm (UTC) (Expand)
(no subject) - occam_aga on June 2nd, 2012 08:35 pm (UTC) (Expand)
(no subject) - occam_aga on June 2nd, 2012 09:18 pm (UTC) (Expand)
журнал закрытjuan_gandhi on May 29th, 2012 05:48 pm (UTC)
You are mixing adhoc complexity with parameteric complexity.

The c# example - one has to read carefully every line to see wtf is going on and whether something is fucked up. Elements are variables, control statements etc.

The scala example - elements are the usual functional building blocks; the line more or less reads fast if you eye is trained, and if you look for fuckups, there's not much to look for:

(3,2) - is it the right seed?
is the condition (_<=sqrt(x)) good enough? (I don't believe it is)
is the condition x%_== the right condition (I believe it is not)
is the !... exists the right condition? seems like it is
And also check that #:: is the same as Stream.cons

That's it.

Dennis Gorelikdennisgorelik on May 29th, 2012 06:08 pm (UTC)
You are mixing adhoc complexity with parameteric complexity.

What is "adhoc complexity" and which one did I use in my complexity calculations example?


How can that one-liner scala example be split into somewhat independent parts (to reduce number of tokens in line)?
журнал закрытjuan_gandhi on May 29th, 2012 06:27 pm (UTC)
Adhoc complexity is the one where the constructs are good only in this specific case.

How to split:
def possibleDivisors(x: Int, numbers: Seq[Int]) = numbers dropWhile (_ < 2) takeWhile (i => i*i <= x)
def hasDivisors(x: Int, numbers: Seq[Int]) = numbers exists (x %_ == 0)
def isPrimeRelativeto(numbers: Seq[Int], x: int) = !hasDivisors(x, possibleDivisors(x, numbers))
val primes:Stream[Int] = 2 #:: Stream.from(3, 2) filter (isPrimeRelativeto(primes, _))


Edited at 2012-05-29 06:31 pm (UTC)
Dennis Gorelikdennisgorelik on May 30th, 2012 12:29 am (UTC)
About naming: why "isPrimeRelativeto", why not "isPrimeRelativeTo"?
(no subject) - juan_gandhi on May 30th, 2012 12:42 am (UTC) (Expand)
Dennis Gorelikdennisgorelik on May 30th, 2012 01:26 am (UTC)
About recursion:
val primes:Stream[Int] = 2 #:: Stream.from(3, 2) filter (isPrimeRelativeto(primes, _))

Is second "primes" calculated every time it's called, or it just returns whatever "val primes" accumulated at the moment of filter evaluation?
Dennis Gorelikdennisgorelik on May 30th, 2012 03:23 am (UTC)
2960 units of complexity
See "Scala 4-liner" tab.

It's even more than one-liner (1892 units of complexity).

Probably need to split further.

For example, could you split it into 8 lines?
(Declaration on the first line, assignment on the second).

If that code cannot really be refactored into smaller chunks then perhaps functional programming should be limited to smaller tasks?

That's exactly what happens with SQL: great for smaller queries, but not so great for really complex business logic.
Dennis Gorelikdennisgorelik on May 30th, 2012 03:37 am (UTC)
Adhoc complexity is the one where the constructs are good only in this specific case.

I don't understand:
What does "constructs are good only in this specific case" mean?
What is "specific case" in this context?

What complexity did I calculate here: parametric or adhoc?
(no subject) - juan_gandhi on May 30th, 2012 07:07 am (UTC) (Expand)
(no subject) - dennisgorelik on May 30th, 2012 07:30 am (UTC) (Expand)
(no subject) - sassa_nf on May 30th, 2012 09:54 am (UTC) (Expand)
(no subject) - dennisgorelik on May 30th, 2012 03:12 pm (UTC) (Expand)
(no subject) - sassa_nf on May 30th, 2012 06:43 pm (UTC) (Expand)
(no subject) - dennisgorelik on May 30th, 2012 07:17 pm (UTC) (Expand)
sassa_nf on May 29th, 2012 06:47 pm (UTC)
interesting. Why is (_<=math.sqrt(x)) not good enough? Or did you mean just the omission of math?

Also, is x%_==0 not right condition because of shift+0 accidentally translating into a ')'?

(@dennisgorelink: btw these would be picked up by parser)
журнал закрытjuan_gandhi on May 29th, 2012 06:59 pm (UTC)
How do you know it'll pass for i*i== x?
x%_==0 is a good condition; x%== is not. :)
sassa_nf on May 29th, 2012 07:08 pm (UTC)
yes, I agree with possible loss of accuracy in sqrt(x) :)
(no subject) - sassa_nf on May 29th, 2012 07:12 pm (UTC) (Expand)
(no subject) - juan_gandhi on May 29th, 2012 09:25 pm (UTC) (Expand)
(no subject) - sassa_nf on May 30th, 2012 07:41 am (UTC) (Expand)
(no subject) - juan_gandhi on May 30th, 2012 07:47 am (UTC) (Expand)
(no subject) - dennisgorelik on May 30th, 2012 08:17 am (UTC) (Expand)
(no subject) - juan_gandhi on May 30th, 2012 04:22 pm (UTC) (Expand)
(no subject) - dennisgorelik on May 30th, 2012 06:45 pm (UTC) (Expand)
(no subject) - sassa_nf on May 30th, 2012 08:24 pm (UTC) (Expand)
(no subject) - dennisgorelik on May 30th, 2012 08:44 pm (UTC) (Expand)
(no subject) - sassa_nf on May 30th, 2012 08:58 pm (UTC) (Expand)
(no subject) - dennisgorelik on May 30th, 2012 09:12 pm (UTC) (Expand)
(no subject) - sassa_nf on May 31st, 2012 07:47 am (UTC) (Expand)
(no subject) - dennisgorelik on May 31st, 2012 10:37 am (UTC) (Expand)
(no subject) - sassa_nf on May 31st, 2012 11:57 am (UTC) (Expand)
(no subject) - dennisgorelik on May 31st, 2012 08:35 pm (UTC) (Expand)
(no subject) - juan_gandhi on May 31st, 2012 03:49 am (UTC) (Expand)
(no subject) - dennisgorelik on May 31st, 2012 04:45 am (UTC) (Expand)
(no subject) - juan_gandhi on May 31st, 2012 07:09 am (UTC) (Expand)
(no subject) - dennisgorelik on May 31st, 2012 08:09 am (UTC) (Expand)
(no subject) - juan_gandhi on May 31st, 2012 08:12 am (UTC) (Expand)
(no subject) - dennisgorelik on May 31st, 2012 08:19 am (UTC) (Expand)
(no subject) - juan_gandhi on May 31st, 2012 04:26 pm (UTC) (Expand)
(no subject) - dennisgorelik on May 31st, 2012 07:30 pm (UTC) (Expand)
(no subject) - sassa_nf on May 30th, 2012 08:48 am (UTC) (Expand)
(no subject) - dennisgorelik on May 30th, 2012 07:50 am (UTC) (Expand)
(no subject) - sassa_nf on May 30th, 2012 08:46 am (UTC) (Expand)
(no subject) - sassa_nf on May 30th, 2012 08:33 am (UTC) (Expand)
(no subject) - justy_tylor on May 29th, 2012 10:07 pm (UTC) (Expand)
(no subject) - sassa_nf on May 29th, 2012 10:16 pm (UTC) (Expand)
(no subject) - sassa_nf on May 29th, 2012 10:17 pm (UTC) (Expand)
(no subject) - justy_tylor on May 29th, 2012 10:42 pm (UTC) (Expand)
(no subject) - dennisgorelik on May 29th, 2012 11:57 pm (UTC) (Expand)
(no subject) - sassa_nf on May 30th, 2012 07:48 am (UTC) (Expand)
(no subject) - dennisgorelik on May 30th, 2012 08:00 am (UTC) (Expand)
(no subject) - sassa_nf on May 30th, 2012 09:44 am (UTC) (Expand)
(no subject) - justy_tylor on May 30th, 2012 07:49 am (UTC) (Expand)
(no subject) - dennisgorelik on May 30th, 2012 08:05 am (UTC) (Expand)
(no subject) - sassa_nf on May 30th, 2012 08:53 am (UTC) (Expand)
(no subject) - sassa_nf on May 30th, 2012 07:35 am (UTC) (Expand)
(no subject) - justy_tylor on May 30th, 2012 07:58 am (UTC) (Expand)
(no subject) - dennisgorelik on May 30th, 2012 08:09 am (UTC) (Expand)
(no subject) - sassa_nf on May 30th, 2012 08:55 am (UTC) (Expand)
(no subject) - sassa_nf on May 30th, 2012 08:58 am (UTC) (Expand)
Dmitry Popovthedeemon on May 30th, 2012 05:41 am (UTC)
The metric looks fishy. Is "a + b + c" really 3 times more complicated than "a + b"? Syntax makes dependencies rather linear than quadratic.
Dennis Gorelikdennisgorelik on May 30th, 2012 06:31 am (UTC)
These are simplified complexity calculations.
Of course there are exceptions, and you found one of them.

But if you consider these two lines:
result = a + b

result = a + b * c

then you would agree that complexity of second line (7 * 6 = 42) is really about two times higher than complexity of the first ( 5 * 4 = 20 )

LiveJournal: pingback_botlivejournal on May 31st, 2012 01:22 pm (UTC)
Сложность, времена, модальности...
LiveJournal: pingback_botlivejournal on May 31st, 2012 11:05 pm (UTC)
Реальная ценность ООП.
User thesz referenced to your post from Реальная ценность ООП. saying: [...] Источник вдохнования [...]