what is the time complexity of list operations?
what is the big O of $lf, $lg, $li, $lts and list concatenation by "_"
Comments
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.
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.",!
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.AbstractExceptiontry {
settStart=$ZHforx=1:1:1000000 {
Set a=$LB("sdfdkjfdjklfdjklfdjklfds","dlkfdjklfgjklfgjklfgjklfgjkl","fdklfdsjkljklfgjkfgjkfg") Set b=$LG(a,2)
}
Write !,"List Duration: ",$zh-tStartsettStart=$ZHforx=1:1:1000000 {
Set a="sdfdkjfdjklfdjklfdjklfds_dlkfdjklfgjklfgjklfgjklfgjkl_fdklfdsjkljklfgjkfgjkfg"Set b=$P(a,"_",2)
}
Write !,"Piece Duration: ",$zh-tStartsettStart=$ZHforx=1:1:1000000 {
Set a=$LB("sdfdkjfdjklfdjklfdjklfds","dlkfdjklfgjklfgjklfgjklfgjkl","fdklfdsjkljklfgjkfgjkfg") Set b=$LG(a,3)
}
Write !,"List Duration Getting last element: ",$zh-tStartsettStart=$ZHforx=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 stringset$list(var,1) = value // listitem 1 is either a number or a stringkillxset$piece(x,",",1) = 100+1write$zhex($p(x,",")) --> 257killxset$list(x,1) = 100+1write$zhex($li(x,1)) --> 65killxset$piece(x,",",1) = 100write$zhex($p(x,",")) --> 256killxset$list(x,1) = 100write$zhex($li(x,1)) --> 64killxset$piece(x,",",1) = "100"write$zhex($p(x,",")) --> 256killxset$list(x,1) = "100"write$zhex($li(x,1)) --> 256In 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...