Page 1 of 1
Finding out complexity of a list
Posted: Wed Mar 31, 2010 4:49 pm
by cormullion
Here's a quickie for you. Given a list of stupendous and garguantuan proportions*, how would you measure or describe its complexity?
flat is useful, I suppose, but I want to know how deep the levels go and that doesn't help. I don't really want to convert it to a string, unless that's the only way...
* - eg some S-XML I found recently... :)
Re: Finding out complexity of a list
Posted: Wed Mar 31, 2010 5:29 pm
by Sammo
Maybe ref-all to find reference vectors for all elements, then take the longest vector as the complexity metric? Something like this:
Code: Select all
(apply max (map length (ref-all nil aList (fn (x) true))))
Edit: Clarified list parameter in ref-all.
Re: Finding out complexity of a list
Posted: Wed Mar 31, 2010 5:35 pm
by cormullion
That's cool! Hadn't thought of looking for nil!
Re: Finding out complexity of a list
Posted: Wed Mar 31, 2010 8:40 pm
by Kazimir Majorinc
I have these three functions in my library:
(Lists are understood as trees, and complexity is measured in terms of nodes, branches and leafs. The branch is path from root to leaf.)
Code: Select all
;
; Syntax: (depth <L>) - length of the longest branch
; (size <L>) - number of nodes
; (width <L>) - number of leafs
;
; Examples:
(set 'depth (lambda(x)
;(println x)
(cond ((quote? x)(+ 1 (depth (eval x))))
((and (list? x) (empty? x)) 1)
((list? x)(+ 1 (apply max (map depth x))))
(true 1))))
(set 'size (lambda(x)
(+ 1 (cond ((quote? x)(size (eval x)))
((list? x)(apply + (map size x)))
(true 0)))))
(set 'width (lambda(x)
(cond ((quote? x)(width (eval x)))
((list? x)(apply + (map width x)))
(true 1))))
For example, when my library is loaded, I get messages like this one:
Code: Select all
Defined random-sublist with size=70, depth=8 and width=43.
That gives few measures of the complexity of the definition of the
random-sublist:
Code: Select all
(lambda(L pick-from-list)
(let ((result '())
(left-in-list (length L)))
(when (> pick-from-list left-in-list)
(throw-error (append "There is no n="
(string pick-from-list)
" elements in L.")))
(dolist (element L (= pick-from-list 0))
(let ((probability (div pick-from-list
left-in-list)))
(when (<= (random 0 1) probability)
(push element result -1)
(dec pick-from-list))
(dec left-in-list)))
result))
Re: Finding out complexity of a list
Posted: Fri Apr 02, 2010 6:08 pm
by cormullion
Thanks, Kazimir. I've just spotted your reply! These work well.
Code: Select all
(map (fn (f) (println f { } (apply f sxml))) '(depth size width))
depth 10
size 77477
width 51393
where sxml is the newLISP user manual in SXML... :)