Pure Tcl implementation of "lsearch -stride"

[Alexandru]

Hi,

I would like to share my implementation of "lsearch -stride". It's pure Tcl. I don't know if it's already available or not in the core. I have Tcl 8.6 and it's missing there.

You can call the function like this:
Lsearch -stride 2 -index 0 {10 a 20 b 30 c} 20


## Pure TCL implementation of the -stride option for lsearch command.
# \param args arguments as for Tcl command lsearch
# \return result as lsearch command
proc Lsearch {args} {
# Get the position of the -stride option
set idx [lsearch $args -stride]
# If stride option is not available
if {$idx<0} {
# Execute standard lsearch command
return [lsearch {*}$args]
# If stride option is available
} else {
# Extract last two list arguments, which are the list and the searched string
lassign [lrange $args end-1 end] l searchstring
# Get the preceding options
set opts [lrange $args 0 end-2]
# Get the stride length, which is the value following the -stride option
set stridelen [lindex $opts [expr {$idx+1}]]
# Compose a nested list with the length of the sublists equal to the stride length
set searchlist [ListGroups $l [expr {[llength $l]/$stridelen}]]
# Remove -stride option
set idx [lsearch $opts -stride]
set opts [lreplace $opts $idx [expr {$idx+1}]]
# Execute the standard Tcl command with remaining options
return [lsearch {*}$opts $searchlist $searchstring]
}
}
## Group elements of list l into n groups
proc ListGroups {l n} {
# If list has less or equal elements than groups
if {[llength $l]<=$n} {
return $l
# If list has more elements than groups
} else {
# Compute the rounded number of elements in each group
set nelem [expr {[llength $l]/$n}]
# Create a list of groups
set groups {}
for {set i 1} {$i <= $n} {incr i} {
if {$i<$n} {
lappend groups [lrange $l [expr {($i-1)*$nelem}] [expr {$i*$nelem-1}]]
} else {
lappend groups [lrange $l [expr {($i-1)*$nelem}] end]
}
}
return $groups
}
}

[Alexandru]

I would also like to know your opinion on this. Is this a good implementation. Any improvements?

Regards
Alexandru

[heinrichmartin]

On Monday, August 13, 2018 at 6:57:12 PM UTC+2, Alexandru wrote:
> set idx [lsearch $args -stride]

This creates a string representation for all elements of the searched list, if no -stride is found. You could (at least) make a shortcut to legacy lsearch, if {2 >= [llength $args]}. It might even be worth to extract [lrange $args 0 end-2] and only process these as switches ...

Use cases of lsearch will unlikely make this micro-optimization worth, but learning insights of Tcl does ;-)

#!/usr/bin/env tclsh

set longlist [lmap void [lrepeat 100000 0] {::tcl::mathfunc::rand}]
set longargs [list -index 0 -stride 2 $longlist]
set shortargs [list $longlist]

puts stderr [::tcl::unsupported::representation $longargs]
puts stderr "Early find: [time {lsearch $longargs -stride}]"

puts stderr [::tcl::unsupported::representation $shortargs]
puts stderr [::tcl::unsupported::representation [lindex $shortargs end]] ;# no string rep
puts stderr [::tcl::unsupported::representation $longlist] ;# $longlist wasn't string compared yet
puts stderr "Create string rep: [time {lsearch $shortargs -stride}]"
puts stderr [::tcl::unsupported::representation $shortargs] ;# no string rep; just for all items
puts stderr [::tcl::unsupported::representation [lindex $shortargs end]] ;# string rep created
puts stderr [::tcl::unsupported::representation $longlist] ;# note the side-effect on $longlist
puts stderr "String rep available: [time {lsearch $shortargs -stride}]"

[heinrichmartin]

On Monday, August 13, 2018 at 6:57:12 PM UTC+2, Alexandru wrote:

> set opts [lrange $args 0 end-2]

> ...

> set opts [lreplace $opts $idx [expr {$idx+1}]]

set opts [lreplace $opts $idx $idx+1] ;# incr is another option

On Monday, August 13, 2018 at 6:57:12 PM UTC+2, Alexandru wrote:

> set searchlist [ListGroups $l [expr {[llength $l]/$stridelen}]]

> ...
> proc ListGroups {l n} {

Why not use make $n mimic stride?

You can look at http://wiki.tcl.tk/440#pagetoc47290fd7 for an implementation.

[Alexandru]

It's very interssting to see another implementation of this list grouping task. I was about to replace my "ListGroups" by "partitionlist" but then I noticed that "partitionlist" takes 50% longer to process than "ListGroups". I have no idea why...

[Alexandru]

Am Dienstag, 14. August 2018 09:30:08 UTC+2 schrieb heinrichmartin:
> On Monday, August 13, 2018 at 6:57:12 PM UTC+2, Alexandru wrote:
> > set idx [lsearch $args -stride]
>
> This creates a string representation for all elements of the searched list, if no -stride is found. You could (at least) make a shortcut to legacy lsearch, if {2 >= [llength $args]}. It might even be worth to extract [lrange $args 0 end-2] and only process these as switches ...
>

Thanks for the tip. I changed the procedure accordingly:

proc ::meshparts::Lsearch {args} {
# If there are no options
if {[llength $args]<=2} {
return [lsearch {*}$args]
}

# Get the preceding options
set opts [lrange $args 0 end-2]

# Get the position of the -stride option

set idx [lsearch $opts -stride]

# If stride option is not available
if {$idx<0} {
# Execute standard lsearch command
return [lsearch {*}$args]
# If stride option is available
} else {
# Extract last two list arguments, which are the list and the searched string
lassign [lrange $args end-1 end] l searchstring

# Get the stride length, which is the value following the -stride option
set stridelen [lindex $opts [expr {$idx+1}]]
# Compose a nested list with the length of the sublists equal to the stride length

set searchlist [::meshparts::ListGroups $l [expr {[llength $l]/$stridelen}]]

[heinrichmartin]

On Tuesday, August 14, 2018 at 12:01:01 PM UTC+2, Alexandru wrote:
> > You can look at http://wiki.tcl.tk/440#pagetoc47290fd7 for an implementation.
>
> It's very interssting to see another implementation of this list grouping task. I was about to replace my "ListGroups" by "partitionlist" but then I noticed that "partitionlist" takes 50% longer to process than "ListGroups". I have no idea why...

You are not using the braintwister version, are you?
And you are comparing with matching parameters (translation between n for ListGroups and partitionlist is required), aren't you? Runtime varies depending on n!

On Monday, August 13, 2018 at 6:57:12 PM UTC+2, Alexandru wrote:

> if {$i<$n} {
> lappend groups [lrange $l [expr {($i-1)*$nelem}] [expr {$i*$nelem-1}]]
> } else {
> lappend groups [lrange $l [expr {($i-1)*$nelem}] end]
> }

Not required: lrange is robust enough to handle this!

[Alexandru]

Now I know, why my procedure was faster. The second argument has a diffrent meaning in my case. This is why the procedure is more complex. Second argument is not the length of the sublists. It's the number of sublists. But this is not a good idea. So I'll change the meaning and use the procedure from the Wiki.

Thanks again.

[Alexandru]

This is the final version:

## Pure TCL implementation of the -stride option for lsearch command.
# \param args arguments as for Tcl command lsearch
# \return result as lsearch command
proc Lsearch {args} {

# If there are no options
if {[llength $args]<=2} {

return [lsearch {*}$args]
}
# Get the preceding options

set opts [lrange $args 0 end-2]

# Get the position of the -stride option

set idx [lsearch $opts -stride]

# If stride option is not available
if {$idx<0} {
# Execute standard lsearch command
return [lsearch {*}$args]
# If stride option is available
} else {
# Extract last two list arguments, which are the list and the searched string
lassign [lrange $args end-1 end] l searchstring

# Get the stride length, which is the value following the -stride option
set stridelen [lindex $opts [expr {$idx+1}]]
# Compose a nested list with the length of the sublists equal to the stride length

set searchlist [ListGroups $l $stridelen]

# Remove -stride option
set idx [lsearch $opts -stride]

set opts [lreplace $opts $idx [expr {$idx+1}]]

# Execute the standard Tcl command with remaining options
return [lsearch {*}$opts $searchlist $searchstring]
}
}

## Group elements of list l into groups of n elements.
# see http://wiki.tcl.tk/440#pagetoc47290fd7
proc ListGroups {l n} {
set result [list]
for {set p 0} {$p < [llength $l]} {incr p $n} {
lappend result [lrange $l $p [expr {$p+$n-1}]]
}
return $result
}

[Ralf Fassel]

* Alexandru <alexandr...@meshparts.de>

| for {set p 0} {$p < [llength $l]} {incr p $n} {

Nitpick: if the list gets large and does not change in the loop, it might be better
to precompute the end condition instead of calling [llength] on each iteration:

proc l1 {l} { for {set i 0} {$i < [llength $l]} {incr i} {}}
proc l2 {l} { set max [llength $l] ; for {set i 0} {$i < $max} {incr i} {}}

# force byte-compile
l1 foo
l2 foo

# run test
set l [lrepeat 100000000 x]
% time {l1 $l} 10
4320497.7 microseconds per iteration

% time {l2 $l} 10
3268068.4 microseconds per iteration

3268068.4/4320497.7 ~ 76%

HTH
R'

[Alexandru]

Thanks Ralf, you're absolutely right.
Here is the updated procedure:

proc ListGroups {l n} {
set result [list]

set len [llength $l]
for {set p 0} {$p < $len} {incr p $n} {

[Alexandru]

Question: What is better to return when using stride, the index of the "virtual" sublist, in which the element was found, or the true element index in the flat list?

[jda...@gmail.com]

what happens if the -inline option is given to Lsearch?

I suspect the -index, -inline and -all options will need more processing before and after the call to lsearch in Lsearch.

Dave B

[Alexandru]

I don't know how this helps to my question but this is an example:
::meshparts::Lsearch -stride 2 -index 1 -inline {1 a 2 b 3 c} b
>>2 b

Seems fine to me.

[Donald Arseneau]

Alexandru <alexandr...@meshparts.de> writes:

> Am Dienstag, 14. August 2018 14:53:14 UTC+2 schrieb Ralf Fassel:
>> * Alexandru <alexandr...@meshparts.de>
>> | for {set p 0} {$p < [llength $l]} {incr p $n} {
>>
>> Nitpick: if the list gets large and does not change in the loop, it might be better
>> to precompute the end condition instead of calling [llength] on each iteration:

On the other hand, looking up a list length is not much overhead
compared to looking up just the variable value.



--
Donald Arseneau as...@triumf.ca