searching for partial pattern in a list in an efficient way in TCL

user_18994986 0
Viewed 73

Introduction: (not necessarily required in order to answer my question but might help)

I have a block with multiple blocks inside it (sons). For each such block (or sub-block), I am reading its DEF (design exchange format) file and assigning all its instances names to a list. So I have created a list of all instances names from all the DEF files I have read. In addition, I have a primeTime session containing all instances in the block (including the 'son' blocks).

My question:

How to efficiently search for a partial instance name inside my list?

Elaboration:

Let's say I have a list called DefInstsLst which contains thousands of instance names (read from the DEF files as described in the introduction). For example, this list contains the following instance name:

DRO_TAP_31__ap_dro_tap/keep_dro_nr

Now, the full instance name from the top block read from primeTime is the following:

ld_top_dft_top/dro_cluster/genblk1_DRO_PACK_0__ap_dro_pack/genblk1_5__DRO_TEL_ap_dro_cell_5nm_7t_TEL/ap_dro_v2_cell/DRO_CELL_DRO_TEL_ap_dro_delay_5nm_7t_TEL/DRO_TAP_31__ap_dro_tap/keep_dro_nd

Now I want to find this instance in my list DefInstsLst according to its suffix DRO_TAP_31__ap_dro_tap/keep_dro_nd, but since it is a huge list then I have to search it efficiently (I am doing this kind of search for every instance in primeTime session). I have tried using lsort command to sort the list and then lsearch -sorted to search efficiently but when using the flag -sorted I can't search for partial patterns but only an exact match. When searching for instances that match exactly in their names the way I described with lsearch works perfectly in terms of run time.

tcl
2 Answers

Since you are looking for suffixes, you don't have any options much more efficient than lsearch -glob *$pattern that don't involve a lot of preparation work. Sorting doesn't help because that proceeds from the start of the string. That glob (with a * at the front) is about as efficient as you get for a single string check; it is one of the optimised cases in the glob matching machinery.

The preparation work you might do? Preparing another list with those values all reversed and sorting that. Then you can look for the reversed pattern at the start of those, which is something that can be done efficiently with a binary search (which is exactly what lsearch -sorted does). It is potentially a lot of overhead! Or you can split the strings to extract some sort of collation key; the suitability of that depends on exactly what you are looking for. These both have a lot of overhead; you get extra data per list entry, potentially as large as the list entry itself. (Consider using a database if there is a lot; SQLite is excellent and integrates well with Tcl.)

user_3018320

I agree with Donal that some prep work is probably your best option. Re-arrange all the data in a different way that makes it more efficient for this type of searching.

For example, you could iterate through all the instance names and arrange them by suffix into a dictionary:

set suffix_dict [dict create]
foreach instance_name $instance_names {
     # Assume the suffix are the last two parts full hierarchical instance name
     set suffix [join [lrange [split $instance_name "/"] end-1 end] "/"]
     dict lappend suffix_dict $suffix $instance_name
}

set suffix_lookup "DRO_TAP_31__ap_dro_tap/keep_dro_nr"
set matching_instances [dict get $suffix_dict $suffix_lookup]

There's the one time cost of preparing the dictionary, but then fast dictionary lookup afterwards.

Another idea is to put your lsearch command into a proc. Everytime the proc is called, then cache the results for args.

set cache [dict create]
proc lookup_instance {pattern} {
    # Check cache first
    if {[dict exists $::cache $pattern]} {
        return [dict get $::cache $pattern]
    }

    set matches [lsearch -sorted -all -inline $::instance_names]

    # Save to cache
    dict set ::cache $pattern $matches

    return $matches
}

This will save time if you're frequently looking up the same pattern.

user_163508820
Related