How to Speed Up This Code?

[rkriesel]

The curious thing about creating an array with split using a single char is that apparently you can use "repeat for each element" and reliably work on elements in ascending sort order of the key. This would not have occurred to me, since I'm accustomed to the keys being hashed in such a way that accessing them isn't sequential; the array normally has no sense of order at all.

The dictionary suggests this behavior in the entry for "split:"

If you don't specify a secondaryDelimiter, then a simple numeric array is created, with each key being a number, starting with 1.

Here's an example that shows it's not just a feature of split. When a hole in a broken sequence gets filled in, the element list gets sorted (and the key list doesn't).

Code: Select all

on foo
    local a, b, e1, e2, k1, k2
    put "c" into a[3]
    put "a" into a[1] -- now there's only a broken sequence
    put keyList(a) into k1 -- hash sequence
    put elementList(a) into e1 -- hash sequence
    put a into b
    put "b" into b[2] -- now there's an unbroken sequence
    put keyList(b) into k2 -- hash sequence
    put elementList(b) into e2 -- sorted by key numeric ascending
    breakpoint -- see the results in the variable watcher
end foo

function elementList p
    local t
    repeat for each element e in p
        put e & comma after t
    end repeat
    return t
end elementList

function keyList p
    local t
    repeat for each key k in p
        put k & comma after t
    end repeat
    return t
end keyList

I'm guessing that the engine has a special case for arrays in which keys are not only integers but also in unbroken sequence, and in those cases either implements them differently, perhaps as some sort of linked list, or does an internal sort.

bumping the question, hoping for the answer

[FourthWorld]

Dick, you're a better C programmer than me - dive in and let us know what you find

https://github.com/runrev/livecode

And when are you coming to SoCal? I'd love to have you give an informal talk on algorithms at our LiveCode meeting if I could talk you into it.

[rkriesel]

Dick, you're a better C programmer than me - dive in and let us know what you find

Chortle. I am not nor have I ever been one. You and I need outside help.

And when are you coming to SoCal? I'd love to have you give an informal talk on algorithms at our LiveCode meeting if I could talk you into it.

You're very convincing, but probably not that convincing. I've never, as Andre said, knelt at the alter of Knuth.

Coming to the meetings will be quite appealing when the audio-video goes live on the web.

But I was trying to stay on topic. Perhaps a Mark or a Monte or an LC engineer could enlighten us. The simple numeric array could even be an indication of native (non-delimited) lists to come. Oh, the places we'll go, and the speeds we'll reach.

[bn]

Dick,

thanks for putting this together and for appreciating the "delimiter technique" in 7.x

One thing I am wondering about is why encapsulating searchStrign with cr. This way it will not find searchString if searchString is in the first line of a text.

a little tidbit:
When doing the original delimiter thing I first I copied line 2 to - 1 of sData to tData. It messed up speed so I tried "delete line 1 of tData and speed was back again.

Try this on the original data

Code: Select all

on mouseUp
   put field "rawData" into tData
   put the milliseconds into t
   repeat 20
      put tData into tData2
      delete line 1 of tData2
   end repeat
   put the milliseconds - t into t1
   put the milliseconds into t
   repeat 20
      put line 2 to - 1 of tData into tData2
   end repeat
   put the milliseconds - t into t2
   put "delete line 1 for 20 times: " & t1 & cr & "put line 2 to - 1 for 20 times: " & t2
end mouseUp

I was surprised to see the speed difference between the functionally equivalent solutions. I alway thought that deleting in front would have more overhead than "just" copying from offset to end of data.

this snipped of code works also for delimiter redux

Code: Select all

function test7Solution searchFor
   set the lineDelimiter to searchFor & cr -- note requires at least LC v7
   set the itemDelimiter to cr
   repeat for each line aLine in sData
      put item 3 of aLine & cr after tFound
   end repeat
   delete item 1 of tFound
   return cleanResult (tFound)
end test7Solution

Kind regards

Bernd

[rkriesel]

One thing I am wondering about is why encapsulating searchStrign with cr. This way it will not find searchString if searchString is in the first line of a text.

I also get identical results when searching for the title "Special Education Director", but different results when searching for "Superintendent".

Yes. That's because
a) There is also an Assistant Superintendent listed in the data
b) which are caught by the code construction of the first two methods:
if "Superintendent" is in tLine ... ("repeat for each ...." -- list version), and
lineOffset( searchFor, tData, L2skip) .... (lineOffset version)
c) but not in my "repeat for each ....." -- array version, which requires an exact match as in
if tElement is "Superintendent" .......

I was surprised to see the speed difference between the functionally equivalent solutions. I alway thought that deleting in front would have more overhead than "just" copying from offset to end of data.

Another pleasant surprise. "Test 7" now appears to win every time, sometimes even by more than a millisecond. That's still insignificant of course, except for trying to write exemplary code. So thanks again, Bernd.

-- Dick

[bbalmerTotalFluency]

I see that I am more than a decade late and perhaps both livecode and my computer are much faster but my solution takes < 1 second and I haven't optimised it.

Solution:
Build the data with the format
title (key is the word "education" or not in that title
name
phone num
fax num

Then I loop through the data.
If line 1 does not include the word education, delete lines 1 to 4 of the data
if line 1 DOES contain the word education then store line 2 (name) & line 4 (giving name and fax number)
delete line 1 to 4 of the data -- get next set
and repeat

I was going to try to do something clever but this suffices I think. 1 second is surely not too slow for this sort of problem.

So, am I brilliant (possible but less probable explanation) or has LC and our computers made a combined 900x or 300x or 100x increase in performance since this problem was submitted? I work on an m1 mini with LC 10.something.

I know people sometimes say LC is slow and maybe it is compared to some other languages but I generally find that it is almost insanely fast. I have a lot of functions in an app I am writing where time is not critical but speed is always nice. A little clever rewriting brought them down typically from 125 milliseconds per function to 1 or less than 1 millisecond. No code utility was lost and actually my code is simpler and clearer than the more complex stuff before.