How Can I Optimize Recursive List Search?


(Jim Underwood) #1

How Can I Optimize Recursive List Search?

Any ideas on how I might further optimize this recursive script?
TIA.

This is a test script that is the same as my production script I’m writing for Evernote Mac, except for the acquisition of the source list data.
The purpose is to build a list of Evernote Tags, starting with the top-level parent tag, and then drill down into each child tag, then using it as the Parent Tag, get all of its children.


EDIT: 2018-07-12 14:41 GMT-5

Please see my Revised Script below for a simpler, more clear example.

Each EN Tag has this structure:

  • name
  • parent
    • name

So, I’m looking at a hierarchical tag list like this:
(with some tags cut out for brevity)

image

In the below script, I have hard-coded the source lists to search to make it easy for you guys to test. You don’t need Evernote.

Recursive Script to Build Child Tag List

property ptyScriptName : "Get List of Child Tags for a Parent Tag"
property ptyScriptVer : "2.0"
property ptyScriptDate : "2018-07-11"
property ptyScriptAuthor : "JMichaelTX"

property tagNameList : {}
property parNameList : {}


set parTagName to "HOME"

### Normally Get Lists from Evernote Mac ###
-- runs very fast, only 0.24 sec for 1500 tags
(*
    set tagNameList to name of every tag
    set parNameList to name of parent of every tag
  *)

### FOR TESTING ###
set {tagNameList, parNameList} to {{"Home.Kitchen", "Home.Refrigerator", "Home.Crystal", "Home.Cooking", "Home.Tool", "TOOLS", "Tool.Craftsman", "Tool.PowerTool", "Tool.Router", "Tool.Vacuum", "Tool.HandTool", "Tool.Saw", "Tool.TableSaw", "Home.Cleaning", "HomeDepot", "Home.Electrical", "Home.Landscaping", "Home.Improvement", "Home Note", "Home.Knives", "Home.Maint", "Home.DisasterPlan", "Home.Furniture", "Home.Outdoor", "Home.Repair", "Home.Dining", "UTILITIES", "UTIL.Mobile_Phone", "UTIL.NatGas", "UTIL.Phone", "UTIL.Sat_TV", "UTIL.Electric", "UTIL.Water", "UTIL.Internet_Service", "Home.Appliance"}, {"HOME", "HOME", "HOME", "HOME", "HOME", "HOME", "TOOLS", "TOOLS", "TOOLS", "TOOLS", "TOOLS", "TOOLS", "TOOLS", "HOME", "HOME", "HOME", "HOME", "HOME", "HOME", "HOME", "HOME", "HOME", "HOME", "HOME", "HOME", "HOME", "HOME", "UTILITIES", "UTILITIES", "UTILITIES", "UTILITIES", "UTILITIES", "UTILITIES", "UTILITIES", "HOME"}}

set childTagList to {}


my getChildTags(parTagName, childTagList)

return childTagList

### Can This be Optimized?  Takes ~7 sec in Real World ###

on getChildTags(pParTagName, pChildTagList)
  repeat with iTag from 1 to (count of tagNameList)
    set tagName to item iTag of tagNameList
    set parName to item iTag of parNameList
    
    if (parName = pParTagName) then
      set end of pChildTagList to tagName
      my getChildTags(tagName, pChildTagList)
    end if
  end repeat
end getChildTags

Results

{"Home.Kitchen", "Home.Refrigerator", "Home.Crystal", "Home.Cooking", "Home.Tool",
"TOOLS", "Tool.Craftsman", "Tool.PowerTool", "Tool.Router", "Tool.Vacuum",
"Tool.HandTool", "Tool.Saw", "Tool.TableSaw", "Home.Cleaning", "HomeDepot",
"Home.Electrical", "Home.Landscaping", "Home.Improvement", "Home Note",
"Home.Knives", "Home.Maint", "Home.DisasterPlan", "Home.Furniture", "Home.Outdoor",
"Home.Repair", "Home.Dining", "UTILITIES", "UTIL.Mobile_Phone", "UTIL.NatGas",
"UTIL.Phone", "UTIL.Sat_TV", "UTIL.Electric", "UTIL.Water", "UTIL.Internet_Service",
"Home.Appliance"}

#2

Not sure that I’ve quite understood your inputs and outputs, or the context into which you need to fit them.

When you say “I’m looking at a hierarchical tag list like this”, are you telling us that that is the output you are after ?

The flat list generated by your code seems a little hard to interpret – the special TOOLS and UTILITIES tokens are followed by parent.child tokens with a visible relationship to them, but the picture is less clear with the various (and variously distributed) strings which begin with home – all lower case, some with a dot infix, some without.


#3

but broadly, If the goal is a nested listing, I might try folding your tag list down into a nested record of tags, so that Parent -> Children searches are lookups in a dictionary.

(i.e., I would experiment with using recursive data structures, as an alternative to applying recursive algorithms to flat lists).

Some sketches of that kind of thing here:

use AppleScript version "2.4"
use framework "Foundation"
use scripting additions

on run
    
    set tags to {"Home.Kitchen", "Home.Refrigerator", "Home.Crystal", "Home.Cooking", "Home.Tool", "Tool.Craftsman", "Tool.PowerTool", "Tool.Router", "Tool.Vacuum", "Tool.HandTool", "Tool.Saw", "Tool.TableSaw", "Home.Cleaning", "Home.Depot", "Home.Electrical", "Home.Landscaping", "Home.Improvement", "Home Note", "Home.Knives", "Home.Maint", "Home.DisasterPlan", "Home.Furniture", "Home.Outdoor", "Home.Repair", "Home.Dining", "UTILITIES", "UTIL.Mobile_Phone", "UTIL.NatGas", "UTIL.Phone", "UTIL.Sat_TV", "UTIL.Electric", "UTIL.Water", "UTIL.Internet_Service", "Home.Appliance"}
    
    -- THE LIST OF TAGS FOLDED INTO A NESTED RECORD,
    set tagDict to foldl(tagAdded, {name:""}, tags)
    
    -- PERHAPS REWRITTEN  AS AS GENERIC NODE+NEST TREE,
    set tagTree to treeFromDict(tagDict)
    
    -- AND SERIALIZED AS A TAB-INDENTED OUTLINE.
    set strOutline to tabIndentFromTrees({tagTree})
    
end run

-- NESTED TAG DICTIONARIES AND TREES

-- tagAdded :: Dict -> String -> Dict
on tagAdded(dict, dotTag)
    set parts to splitOn(".", dotTag)
    if 2 > length of parts then
        dict
    else
        set {k, v} to items 1 thru 2 of parts
        set mb to lookupDict(k, dict)
        
        if Nothing of mb then
            set rec to {name:""}
        else
            set rec to Just of mb
        end if
        insertMap(dict, k, insertMap(rec, v, ""))
    end if
end tagAdded

-- tabIndentFromTrees :: [Tree String] -> String
on tabIndentFromTrees(trees)
    script go
        on |λ|(tabs)
            script
                on |λ|(tree)
                    tabs & root of tree
                    if 0 < length of nest of tree then
                        tabs & root of tree & linefeed & ¬
                            unlines(map(go's |λ|(tab & tabs), nest of tree))
                    else
                        tabs & root of tree
                    end if
                end |λ|
            end script
        end |λ|
    end script
    
    unlines(map(go's |λ|(""), trees))
end tabIndentFromTrees


-- treeFromDict :: Dict -> Tree String
on treeFromDict(dict)
    script go
        on |λ|(rootLabel, rec)
            script subTree
                on |λ|(k)
                    set mb to lookupDict(k, rec)
                    if Nothing of mb then
                        {}
                    else
                        set v to Just of mb
                        if record is (class of v) then
                            {go's |λ|(k, v)}
                        else
                            {Node(k, {})}
                        end if
                    end if
                end |λ|
            end script
            
            Node(rootLabel, concatMap(subTree, sort(keys(rec))))
        end |λ|
    end script
    
    go's |λ|("Tags", dict)
end treeFromDict


-- GENERIC FUNCTIONS -------------------------------------------------------

-- https://github.com/RobTrew/prelude-applescript

-- Just :: a -> Just a
on Just(x)
    {type:"Maybe", Nothing:false, Just:x}
end Just

-- Nothing :: () -> Nothing
on Nothing()
    {type:"Maybe", Nothing:true}
end Nothing

-- Node :: a -> [Tree a] -> Tree a
on Node(v, xs)
    {type:"Node", root:v, nest:xs}
end Node

-- concatMap :: (a -> [b]) -> [a] -> [b]
on concatMap(f, xs)
    if class of xs is text then
        set ys to characters of xs
    else
        set ys to xs
    end if
    tell mReturn(f)
        set lng to length of ys
        set acc to {}
        repeat with i from 1 to lng
            set acc to acc & |λ|(item i of ys, i, ys)
        end repeat
    end tell
    return acc
end concatMap

-- foldl :: (a -> b -> a) -> a -> [b] -> a
on foldl(f, startValue, xs)
    tell mReturn(f)
        set v to startValue
        set lng to length of xs
        repeat with i from 1 to lng
            set v to |λ|(v, item i of xs, i, xs)
        end repeat
        return v
    end tell
end foldl

-- insertMap :: Dict -> String -> a -> Dict
on insertMap(rec, k, v)
    tell (current application's NSMutableDictionary's ¬
        dictionaryWithDictionary:rec)
        its setValue:v forKey:(k as string)
        return it as record
    end tell
end insertMap

-- keys :: Dict -> [String]
on keys(rec)
    (current application's NSDictionary's dictionaryWithDictionary:rec)'s allKeys() as list
end keys

-- lookupDict :: a -> Dict -> Maybe b
on lookupDict(k, dct)
    set ca to current application
    set v to (ca's NSDictionary's dictionaryWithDictionary:(dct))'s objectForKey:k
    if v ≠ missing value then
        Just(item 1 of ((ca's NSArray's arrayWithObject:v) as list))
    else
        Nothing()
    end if
end lookupDict

-- map :: (a -> b) -> [a] -> [b]
on map(f, xs)
    tell mReturn(f)
        set lng to length of xs
        set lst to {}
        repeat with i from 1 to lng
            set end of lst to |λ|(item i of xs, i, xs)
        end repeat
        return lst
    end tell
end map

-- Lift 2nd class handler function into 1st class script wrapper 
-- mReturn :: First-class m => (a -> b) -> m (a -> b)
on mReturn(f)
    if class of f is script then
        f
    else
        script
            property |λ| : f
        end script
    end if
end mReturn

-- sort :: Ord a => [a] -> [a]
on sort(xs)
    ((current application's NSArray's arrayWithArray:xs)'s ¬
        sortedArrayUsingSelector:"compare:") as list
end sort

-- splitOn :: String -> String -> [String]
on splitOn(needle, haystack)
    set {dlm, my text item delimiters} to ¬
        {my text item delimiters, needle}
    set xs to text items of haystack
    set my text item delimiters to dlm
    return xs
end splitOn

-- unlines :: [String] -> String
on unlines(xs)
    set {dlm, my text item delimiters} to ¬
        {my text item delimiters, linefeed}
    set str to xs as text
    set my text item delimiters to dlm
    str
end unlines

Output

Tags
    Home
        Appliance
        Cleaning
        Cooking
        Crystal
        Depot
        Dining
        DisasterPlan
        Electrical
        Furniture
        Improvement
        Kitchen
        Knives
        Landscaping
        Maint
        Outdoor
        Refrigerator
        Repair
        Tool
    Tool
        Craftsman
        HandTool
        PowerTool
        Router
        Saw
        TableSaw
        Vacuum
    UTIL
        Electric
        Internet_Service
        Mobile_Phone
        NatGas
        Phone
        Sat_TV
        Water

(Jim Underwood) #4

Thanks for taking a look at my script.
Sorry for the confusion. In my attempt to provide real-world data, I made it too complex.

Here’s a revised script with new sample data that will hopefully make it clearer:

  • The tag list is shown as a hierarchical list in the EN UI
  • But when tags are retrieved from EN, it is just a flat list
  • I have ~1500 tags
  • Of the 1500, I want to get a flat list of all tags in the tag hierarchy starting with a given Parent tag, down through all descendent tags

Revised Script

(*
~~~ Evernote Tags ~~~~
  • Each tag object has a name and a parent tag (which has a name)
  * The tag list is shown as a hierarchical list in the EN UI
  * But when tags are retrieved from EN, it is just a flat list
  * I have ~1500 tags
  * Of the 1500, I want to get a flat list of all tags in the tag hierarchy starting with a given Parent tag, down through all descendent tags
  
  ### Problem:  It takes too long, about 7 sec ###
*)
property tagNameList : {}
property parNameList : {}
property tagNameCount : missing value

--- This Represents the Tags stored in Evernote ---
# TagName, ParentTagName (top-level tags do NOT have a Parent)
set enTags to "tag1,
tag2,tag1
tag3,tag1
tag4,tag1
tag5,
tag6,tag5
tag7,tag5
tag8,tag5
tag9,tag5
tag10,tag6
tag11,tag6
tag12,tag6
tag13,tag7
tag14,tag7"

--- Get Tags from Evernote ---
(*
tell application "Evernote"
  set tagNameList to name of every tag
  set parNameList to name of parent of every tag
end tell
*)

### FOR TESTING, Build Equivalent Lists as if they came from Evernote ##

set enTagList to paragraphs of enTags
set tagNameList to {}
set parNameList to {}
set AppleScript's text item delimiters to ","
repeat with oTag in enTagList
  set oTag to text items of oTag
  set end of tagNameList to item 1 of oTag
  set end of parNameList to item 2 of oTag
end repeat

### OK, Now I have the same lists like form Evernote ###
#  tagNameList
#  parNameList

### Now, Get Flat Tag List of All Tags Starting with this Parent Tag:
set parTagName to "tag5"
set tagNameCount to count of tagNameList

set childTagList to {}
my getChildTags(parTagName, childTagList)

### The Results are Corrent -- Exactly what I want ###
# The problem is in the real world, with 1500 source tags, this takes ~7 sec
# Can this time be reduced?

return childTagList
-->{"tag6", "tag10", "tag11", "tag12", "tag7", "tag13", "tag14", "tag8", "tag9"}

--~~~~~~~~~~~~ END OF MAIN SCRIPT ~~~~~~~~~~~~~~~

on getChildTags(pParTagName, pChildTagList)
  repeat with iTag from 1 to tagNameCount
    set tagName to item iTag of tagNameList
    set parName to item iTag of parNameList
    
    if (parName = pParTagName) then
      set end of pChildTagList to tagName
      my getChildTags(tagName, pChildTagList)
    end if
  end repeat
end getChildTags


Questions?


#5

I think folding the list down to a record, and then retrieving from the record is likely to be a bit quicker.

How deep is the hierarchy ? and if more than two levels deep, what does a third level look like in terms of the tags and their relationships ?

Might you be able to give a Dropbox link to a list of the full 1500, as you get it from Evernote ?

If its just a two level structure, then perhaps something like this:

use AppleScript version "2.4"
use framework "Foundation"
use scripting additions

on run
    
    set tags to {"Home.Kitchen", "Home.Refrigerator", "Home.Crystal", "Home.Cooking", "Home.Tool", "Tool.Craftsman", "Tool.PowerTool", "Tool.Router", "Tool.Vacuum", "Tool.HandTool", "Tool.Saw", "Tool.TableSaw", "Home.Cleaning", "Home.Depot", "Home.Electrical", "Home.Landscaping", "Home.Improvement", "Home Note", "Home.Knives", "Home.Maint", "Home.DisasterPlan", "Home.Furniture", "Home.Outdoor", "Home.Repair", "Home.Dining", "UTILITIES", "UTIL.Mobile_Phone", "UTIL.NatGas", "UTIL.Phone", "UTIL.Sat_TV", "UTIL.Electric", "UTIL.Water", "UTIL.Internet_Service", "Home.Appliance"}
    
    -- THE LIST OF TAGS FOLDED INTO A NESTED RECORD,
    set dctTags to foldl(tagAdded, {name:""}, tags)
    
    
    -- Tags with a UTIL prefix before the dot
    tagsForPrefix(dctTags, "UTIL")
end run

-- tagsForPrefix :: Dict -> String -> [String]
on tagsForPrefix(dctTags, strPrefix)
    set mb to lookupDict(strPrefix, dctTags)
    if Nothing of mb then
        {}
    else
        sort(keys(Just of mb))
    end if
end tagsForPrefix


-- NESTED TAG DICTIONARIES AND TREES

-- tagAdded :: Dict -> String -> Dict
on tagAdded(dict, dotTag)
    set parts to splitOn(".", dotTag)
    if 2 > length of parts then
        dict
    else
        set {k, v} to items 1 thru 2 of parts
        set mb to lookupDict(k, dict)
        
        if Nothing of mb then
            set rec to {name:""}
        else
            set rec to Just of mb
        end if
        insertMap(dict, k, insertMap(rec, v, ""))
    end if
end tagAdded

-- tabIndentFromTrees :: [Tree String] -> String



-- GENERIC FUNCTIONS -------------------------------------------------------

-- https://github.com/RobTrew/prelude-applescript

-- Just :: a -> Just a
on Just(x)
    {type:"Maybe", Nothing:false, Just:x}
end Just

-- Nothing :: () -> Nothing
on Nothing()
    {type:"Maybe", Nothing:true}
end Nothing

-- foldl :: (a -> b -> a) -> a -> [b] -> a
on foldl(f, startValue, xs)
    tell mReturn(f)
        set v to startValue
        set lng to length of xs
        repeat with i from 1 to lng
            set v to |λ|(v, item i of xs, i, xs)
        end repeat
        return v
    end tell
end foldl

-- insertMap :: Dict -> String -> a -> Dict
on insertMap(rec, k, v)
    tell (current application's NSMutableDictionary's ¬
        dictionaryWithDictionary:rec)
        its setValue:v forKey:(k as string)
        return it as record
    end tell
end insertMap

-- keys :: Dict -> [String]
on keys(rec)
    (current application's NSDictionary's dictionaryWithDictionary:rec)'s allKeys() as list
end keys

-- lookupDict :: a -> Dict -> Maybe b
on lookupDict(k, dct)
    set ca to current application
    set v to (ca's NSDictionary's dictionaryWithDictionary:(dct))'s objectForKey:k
    if v ≠ missing value then
        Just(item 1 of ((ca's NSArray's arrayWithObject:v) as list))
    else
        Nothing()
    end if
end lookupDict

-- map :: (a -> b) -> [a] -> [b]
on map(f, xs)
    tell mReturn(f)
        set lng to length of xs
        set lst to {}
        repeat with i from 1 to lng
            set end of lst to |λ|(item i of xs, i, xs)
        end repeat
        return lst
    end tell
end map

-- Lift 2nd class handler function into 1st class script wrapper 
-- mReturn :: First-class m => (a -> b) -> m (a -> b)
on mReturn(f)
    if class of f is script then
        f
    else
        script
            property |λ| : f
        end script
    end if
end mReturn

-- sort :: Ord a => [a] -> [a]
on sort(xs)
    ((current application's NSArray's arrayWithArray:xs)'s ¬
        sortedArrayUsingSelector:"compare:") as list
end sort

-- splitOn :: String -> String -> [String]
on splitOn(needle, haystack)
    set {dlm, my text item delimiters} to ¬
        {my text item delimiters, needle}
    set xs to text items of haystack
    set my text item delimiters to dlm
    return xs
end splitOn

-- unlines :: [String] -> String
on unlines(xs)
    set {dlm, my text item delimiters} to ¬
        {my text item delimiters, linefeed}
    set str to xs as text
    set my text item delimiters to dlm
    str
end unlines

(Jim Underwood) #6

Thanks again for your review.

In general, it can be n levels deep – there is no limit. In practice, most are ≤ 4 levels.
All levels (tags) look the same.

From the SDEF – tag

image

The “parent” is just another tag.

Sure, be glad to.

This is how it looks in SD:

image

How do you want it exported to text?
tagName,ParentName ?

BTW, the tags in Evernote are stored in random order. When you retrieve them, there is no specific order you can count on.

Thanks.


(Jim Underwood) #7

That’s a good idea. Unfortunately, you can’t count on all child tags having a parent prefix. That’s why I have two lists:

tell application "Evernote"
  set tagNameList to name of every tag
  set parNameList to name of parent of every tag
end tell


#8

Got it – thanks.

Could you generate a full JSON file with code something like that below, and give a Dropbox link to it ?

use AppleScript version "2.4"
use framework "Foundation"
use scripting additions

on run
    set strJSON to showJSON(everNoteTagPairs())
    
    writeFile("~/Desktop/EnTags.json", strJSON)
    
    strJSON
end run

-- everNoteTagPairs :: Evernote () -> [(String, String)]
on everNoteTagPairs()
    tell application "Evernote"
        set {ps, names} to {parent, name} of tags
        script
            on |λ|(x)
                using terms from application "Evernote"
                    if missing value is x then
                        ""
                    else
                        name of x
                    end if
                end using terms from
            end |λ|
        end script
        set parentNames to my map(result, ps)
    end tell
    zip(parentNames, names)
end everNoteTagPairs


-- Tuple (,) :: a -> b -> (a, b)
on Tuple(a, b)
    {type:"Tuple", |1|:a, |2|:b, length:2}
end Tuple

-- map :: (a -> b) -> [a] -> [b]
on map(f, xs)
    tell mReturn(f)
        set lng to length of xs
        set lst to {}
        repeat with i from 1 to lng
            set end of lst to |λ|(item i of xs, i, xs)
        end repeat
        return lst
    end tell
end map

-- min :: Ord a => a -> a -> a
on min(x, y)
    if y < x then
        y
    else
        x
    end if
end min

-- Lift 2nd class handler function into 1st class script wrapper 
-- mReturn :: First-class m => (a -> b) -> m (a -> b)
on mReturn(f)
    if class of f is script then
        f
    else
        script
            property |λ| : f
        end script
    end if
end mReturn

-- showJSON :: a -> String
on showJSON(x)
    set c to class of x
    if (c is list) or (c is record) then
        set ca to current application
        set {json, e} to ca's NSJSONSerialization's dataWithJSONObject:x options:1 |error|:(reference)
        if json is missing value then
            e's localizedDescription() as text
        else
            (ca's NSString's alloc()'s initWithData:json encoding:(ca's NSUTF8StringEncoding)) as text
        end if
    else if c is date then
        "\"" & ((x - (time to GMT)) as «class isot» as string) & ".000Z" & "\""
    else if c is text then
        "\"" & x & "\""
    else if (c is integer or c is real) then
        x as text
    else if c is class then
        "null"
    else
        try
            x as text
        on error
            ("«" & c as text) & "»"
        end try
    end if
end showJSON

-- use framework "Foundation"
-- writeFile :: FilePath -> String -> IO ()
on writeFile(strPath, strText)
    set ca to current application
    (ca's NSString's stringWithString:strText)'s ¬
        writeToFile:(stringByStandardizingPath of ¬
            (ca's NSString's stringWithString:strPath)) atomically:true ¬
            encoding:(ca's NSUTF8StringEncoding) |error|:(missing value)
end writeFile

-- zip :: [a] -> [b] -> [(a, b)]
on zip(xs, ys)
    set lng to min(length of xs, length of ys)
    set lst to {}
    repeat with i from 1 to lng
        set end of lst to {item i of xs, item i of ys}
    end repeat
    return lst
end zip

(Jim Underwood) #9

I’ll work on that. BTW, if you would prefer to use JavaScript/JXA, I’m good with that.


#10

Both fine, but this is a forum for an AppleScript tool, so let’s stick with AS.


(Jim Underwood) #11

I think I have a solution. There may be better solutions, but this reduces the time from 7 sec to 0.66 sec.

I want to thank @ComplexPoint for his time and effort to solve this issue. He may yet come up with a better solution…

The key is to limit the getChildTags to only those tags that are a parent tag.
if (parSortedList contains tagName) then my getChildTags(tagName, pChildTagList) ## 0.66 sec

Interestly enough, I tested another method where I had changed the name of the parent tags to have a suffix of “:exclamation:”. Then test for this in the getChildTags handler:
if (tagName ends with "❗️") then my getChildTags(tagName, pChildTagList) ## 0.64 sec

To my great surprise, it was only 0.02 sec faster!!!

So, using the first method is the best overall method as it is almost a fast, and does not require changing any tag names.

I also created the parSortedList from the master parNameList, removing missing value and dups, and then sorting. This reduces the list from 1500 to ~300. I was expecting this to have a greater impact than it did (only ~0.02 sec). I guess that’s a testimony to efficiency of the native AppleScript (list contains <value>) command. But I decided to leave the parSortedList in the handler.

As always, I welcome all feedback.


Here’s my revised handler:

on getChildTags(pParTagName, pChildTagList)
  repeat with iTag from 1 to tagNameCount
    set tagName to item iTag of tagNameList
    set parName to item iTag of parNameList
    
    if (parName = pParTagName) then
      set end of pChildTagList to tagName
      
      --- Get Child Tags of This Tag, IF it is a Parent Tag ---
      
      ## my getChildTags(tagName, pChildTagList)    ## ~7 sec
      ## if (tagName ends with "❗️") then my getChildTags(tagName, pChildTagList)  ## 0.64 sec
      if (parSortedList contains tagName) then my getChildTags(tagName, pChildTagList) ## 0.66 sec
      
    end if
  end repeat
end getChildTags

Revised Test Script

use AppleScript version "2.5" -- El Capitan (10.11) or later
use framework "Foundation"
use scripting additions

(*
TEST Script to Get All Child Tags in hierarchy
VER:  2      2018-07-12

~~~ Evernote Tags ~~~~
  • Each tag object has a name and a parent tag (which has a name)
  * The tag list is shown as a hierarchical list in the EN UI
  * But when tags are retrieved from EN, it is just a flat list
  * I have ~1500 tags
  * Of the 1500, I want to get a flat list of all tags in the tag hierarchy starting with a given Parent tag, down through all descendent tags
  
  ### Problem:  It takes too long, about 7 sec ###
  ### This Revision SOLVES the Problem:  0.66 sec ###
*)
property tagNameList : {}
property parNameList : {}
property parSortedList : {}
property tagNameCount : missing value

--- This Represents the Tags stored in Evernote ---
# TagName, ParentTagName (top-level tags do NOT have a Parent)
set enTags to "tag1,
tag2,tag1
tag3,tag1
tag4,tag1
tag5,
tag6,tag5
tag7,tag5
tag8,tag5
tag9,tag5
tag10,tag6
tag11,tag6
tag12,tag6
tag13,tag7
tag14,tag7"

--- Get Tags from Evernote ---
(*
tell application "Evernote"
  set tagNameList to name of every tag
  set parNameList to name of parent of every tag
end tell
*)

### FOR TESTING, Build Equivalent Lists as if they came from Evernote ##

set enTagList to paragraphs of enTags
set tagNameList to {}
set parNameList to {}
set AppleScript's text item delimiters to ","
repeat with oTag in enTagList
  set oTag to text items of oTag
  set end of tagNameList to item 1 of oTag
  set end of parNameList to item 2 of oTag
end repeat

## to simulate data from Evernote use missing value for empty strings ##
set {item 1 of parNameList, item 5 of parNameList} to {missing value, missing value}

### OK, Now I have the same lists like from Evernote ###
#  tagNameList
#  parNameList

--- Make Clean, Sorted List of Parent Tags to use in Handler ---
set parSortedList to my sortListMakeUnique(parNameList)


### Now, Get Flat Tag List of All Tags Starting with this Parent Tag:
set parTagName to "tag5"
set tagNameCount to count of tagNameList

set childTagList to {}
my getChildTags(parTagName, childTagList)

### The Results are Corrent -- Exactly what I want ###
# Real-world use with 1500 source tags takes ~7 sec using original script.
# This solution takes 0.66 sec.

return childTagList
-->{"tag6", "tag10", "tag11", "tag12", "tag7", "tag13", "tag14", "tag8", "tag9"}

--~~~~~~~~~~~~ END OF MAIN SCRIPT ~~~~~~~~~~~~~~~

on getChildTags(pParTagName, pChildTagList)
  repeat with iTag from 1 to tagNameCount
    set tagName to item iTag of tagNameList
    set parName to item iTag of parNameList
    
    if (parName = pParTagName) then
      set end of pChildTagList to tagName
      
      --- Get Child Tags of This Tag, IF it is a Parent Tag ---
      
      ## my getChildTags(tagName, pChildTagList)    ## ~7 sec
      ## if (tagName ends with "❗️") then my getChildTags(tagName, pChildTagList)  ## 0.64 sec
      if (parSortedList contains tagName) then my getChildTags(tagName, pChildTagList) ## 0.66 sec
      
    end if
  end repeat
end getChildTags


--~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
on sortListMakeUnique(pList) -- @List @Sort @Unique @Dups @ASObjC @Shane
  (*  VER: 1.2    2018-07-12
  ---------------------------------------------------------------------------------
  PURPOSE:  Remove Duplicate Items, and Sort List
  PARAMETERS:
    • pList    ┃ list  ┃ List of items
  RETURNS:  list  ┃ 
  AUTHOR:  JMichaelTX, refactored script by ShaneStanley & Chris Stone
  REF:  
    1. 2015-11-01, @ShaneStanley, Everyday ASObjC 3rd ed, p77
        See p55 for more complex sorts
    2.  2018-07-12, ShaneStanley, Late Night Software Ltd.
        How to Make ASObjC Sort Handle missing value?
        http://forum.latenightsw.com/t/how-to-make-asobjc-sort-handle-missing-value/1412/2
—————————————————————————————————————————————————————————————————————————————————
*)
  set theSet to current application's NSSet's setWithArray:pList
  set anArray to theSet's allObjects()
  
  --- Remove Array Elements with missing value ---
  set thePred to current application's NSPredicate's predicateWithFormat:"SELF != nil"
  set anArray to anArray's filteredArrayUsingPredicate:thePred
  
  return (anArray's sortedArrayUsingSelector:"compare:") as list
end sortListMakeUnique
--~~~~~~~~~~~~~~~ END OF handler sortListMakeUnique ~~~~~~~~~~~~~~~~~~~~~~~~~


#12

‘Good enough’ is exactly what we need.

(Beyond that things get expensive and uncertain : -)


(Nigel Garvey) #13

Hi.

The tagNameList item only needs to be fetched when parName matches pParTagName:

on getChildTags(pParTagName, pChildTagList)
	repeat with iTag from 1 to tagNameCount
		set parName to item iTag of parNameList
		
		if (parName = pParTagName) then
			set tagName to item iTag of tagNameList
			set end of pChildTagList to tagName
			
			--- Get Child Tags of This Tag, IF it is a Parent Tag ---
			
			## my getChildTags(tagName, pChildTagList)    ## ~7 sec
			## if (tagName ends with "❗️") then my getChildTags(tagName, pChildTagList)  ## 0.64 sec
			if (parSortedList contains tagName) then my getChildTags(tagName, pChildTagList) ## 0.66 sec
			
		end if
	end repeat
end getChildTags

(Jim Underwood) #14

Thanks Nigel! You’re the king of recursive scripting, and I was hoping you’d take a look at this. :smile:

Running a real-world test using Evernote, with 1500+ tags:
my ver: 0.66 sec.
Your ver: 0.36 sec

46% time savings. :+1:

That’s running from Script Debugger 7.0.3 (7A55) on macOS 10.12.6.