what is the time complexity of list operations?

Question

Question

Adel Elsayed · Dec 21, 2022

#InterSystems IRIS

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

Product version: IRIS 2022.1

Discussion (7)3

Log in or sign up to continue

Eduard Lebedyuk · Dec 21, 2022

$lf, $lg, $li, $lts

O(n)

list concatenation by "_", $listnext

O(1)

0 0

score 0 · Answer 1 · 2022-12-21T04:44:36-05:00

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.

score 0 · Answer 2 · 2022-12-21T09:51:36-05:00

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.

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

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

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

score 2 · Answer 3 · 2022-12-21T12:00:10-05:00

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.

score 6 · Answer 4 · 2022-12-21T11:55:16-05:00

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."

score 0 · Answer 5 · 2023-01-10T13:26:11-05:00

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.

score 0 · Answer 6 · 2023-01-10T16:54:38-05:00

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...