Question
Adel Elsayed · Dec 21, 2022

what is the time complexity of list operations?

what is the big O of $lf, $lg, $li, $lts and list concatenation by "_"

Product version: IRIS 2022.1
0
1 292
Discussion (7)3
Log in or sign up to continue

Hello,

I have done a CSP page that allows to measure timings. This shows that using a delimited string, is somehow "a slight" faster than using a list.

Running 10,000,000 iterations on the following code gives:
 

Set a=$LB(1,2,3) Set b=$LG(a,2) 1.214642 sec.
Set a="1_2_3" Set b=$P(a,"_",2) 1.1711362 sec.

$lf, $lg, $li, $lts

O(n)

 list concatenation by "_", $listnext

O(1)

Your example does not take into account which element is selected.

For example, if you select the last element, then the list wins instead of the delimited string.

L=1e4,N=1e5,a="1",b=$lb(1)
i=2:1:a=a_"_"_i,b=b_$lb(i)

t=$zh
f i=1:1:c=$p(a,"_",L)
w $zh-t," s.",!  

t=$zh
f i=1:1:c=$li(b,L)
w $zh-t," s.",!

the original example(first) likely isn't the best test as all of the elements are 1 character long.  My understanding is $LB data is an encoded string with the first part of the encoding containing the length of the data for an individual element.  Getting the length means you can jump a number of characters to the next element.  On the other hand $Piece does a character-by-character scan.  

ClassMethod Test() As %Status
{
	#dim tSC 			As %Status=$$$OK
	#dim eException  	As %Exception.AbstractException
	try {
		set tStart=$ZH
		for x=1:1:1000000 {
			Set a=$LB("sdfdkjfdjklfdjklfdjklfds","dlkfdjklfgjklfgjklfgjklfgjkl","fdklfdsjkljklfgjkfgjkfg") Set b=$LG(a,2)
		}
		Write !,"List Duration: ",$zh-tStart
		set tStart=$ZH
		for x=1:1:1000000 {
			Set a="sdfdkjfdjklfdjklfdjklfds_dlkfdjklfgjklfgjklfgjklfgjkl_fdklfdsjkljklfgjkfgjkfg" Set b=$P(a,"_",2)
		}
		Write !,"Piece Duration: ",$zh-tStart
		set tStart=$ZH
		for x=1:1:1000000 {
			Set a=$LB("sdfdkjfdjklfdjklfdjklfds","dlkfdjklfgjklfgjklfgjklfgjkl","fdklfdsjkljklfgjkfgjkfg") Set b=$LG(a,3)
		}
		Write !,"List Duration Getting last element: ",$zh-tStart
		set tStart=$ZH
		for x=1:1:1000000 {
			Set a="sdfdkjfdjklfdjklfdjklfds_dlkfdjklfgjklfgjklfgjklfgjkl_fdklfdsjkljklfgjkfgjkfg" Set b=$P(a,"_",3)
		}
		Write !,"Piece Duration Geting last element: ",$zh-tStart
	}
	catch eException {
		Set tSC=eException.AsStatus()
	}
	Quit tSC
}

at the same time I'd much rather deal with $List and not have to worry about escaping delimeters.

If you make a loooonnnnng $piece-delimited string, and a lonnnnnnnnng $list, and you loop 1000000 times, accessing random pieces and random $list items, and sum up the time, and divide by 1000000, you'll find that for access, $lists are faster than delimited strings. At least that's what I saw when $list first appeared. But my mentor from that time said "Yes Joel, they are faster, but $list was added to ObjectScript so that we wouldn't have to worry anymore about delimiters, and sub-delimiters, and sub-sub-delimiters, etc."

One issue is that so much code out there is full of delimited lists, it gets to be a challenge to integrate the $LIST utilities into the existing code. It's easy for new code, but existing code still remains an issue.  Of course.

The bad news is,
you have to be careful when you adapt delimited list to $list(). A stubborn change from a delimited list to $list() can become dangerous. The reason:

set $piece(var,del,1) = value // piece 1 of var is ALWAYS a string
set $list(var,1)      = value // listitem 1 is either a number or a string

kill x set $piece(x,",",1) = 100+1 write $zhex($p(x,",")) --> 257
kill x set $list(x,1)      = 100+1 write $zhex($li(x,1))  --> 65

kill x set $piece(x,",",1) = 100 write $zhex($p(x,",")) --> 256
kill x set $list(x,1)      = 100 write $zhex($li(x,1))  --> 64

kill x set $piece(x,",",1) = "100" write $zhex($p(x,",")) --> 256
kill x set $list(x,1)      = "100" write $zhex($li(x,1))  --> 256

In other words, $list() retains the type of the expression whereas $piece() always converts it to a string.

The good news is,
there are just a few situations, where this could cause a problem, to tell the truth, in a nutshell, I can only think of two possibilities: $zhex() and $zboolean(). But who knows, what a mad programmer accomplish...