passing a custom function for lsearch
Balachandra Krishnamurthy
I would like to know how easy or difficult it is to get lsearch modified
so that it becomes a little easier to use. lsearch searches for items in
a list and it works for simple lists. But for lists with complex data
types, I would like to pass a function that will extract something out
of the complex data type which lsearch can use to do the searching. Let
me explain what I mean by using the example of lsort.
lsort takes a comparison function which it uses to compare two elements
while sorting. e.g., if a list contains first_name last_name as
elements, then I can use a NameCompare function that will return the
last name, so that the list is sorted on last name.
i.e., [set list {{Brent Welch} {John Ousterhout}}]
To sort the above list by last name, I can do
[lsort -command NameCompare $list]
where NameCompare (proc NameCompare {a b} {...}) will compare the last
names (example 5-8 in the book Practical Programming in Tcl and Tk by
Brent Welch et. al.).
Similarly, why can't we have an option for lsearch? (My search on
wiki.tcl.tk and the book mentioned above didn't reveal a way).
In the above example, if I want to find the index of Brent Welch, I have
to do a foreach and then compare the last names. Instead it would be a
lot easier to do *[lsearch -command GetLastName $list Welch]* and I will
get the index of Brent Welch. I think this is particularly useful if I
have a list of objects and I want to retrieve the objects based on a
particular field in that object. E.g., say the above list is made of
name objects. Then the GetLastName can be
proc GetLastName {name_object} {
return [$name_object getLastName]
}
TIP 127 has a solution using -index option for the above example where
names are lists themselves, but if they are objects, then the -index
option wouldn't work (link: http://www.tcl.tk/cgi-bin/tct/tip/127.html).
Thanks.
--
Balachandra B. Krishnamurthy
Michael Schlenker
functions in the struct::list module in tcllib to do it.
The -command option to lsort is very slow, and a command option to
lsearch would not be much faster than a proc that does the same thing,
as it could not really use the small optimizations in place.
Michael
Gerald W. Lester
> Balachandra Krishnamurthy schrieb:
>> ...
>> Similarly, why can't we have an option for lsearch? (My search on
>> wiki.tcl.tk and the book mentioned above didn't reveal a way).
>>
Because no one has implemented it. You can TIP it, if you do it would be
best to provide a sample implementation/patch.
> You could easily write something like that yourself, or use some of the
> functions in the struct::list module in tcllib to do it.
>
> The -command option to lsort is very slow, and a command option to
> lsearch would not be much faster than a proc that does the same thing,
> as it could not really use the small optimizations in place.
I assume the reason he wants it is not execution speed, but rather easy of
readability of the code.
If he was really concerned about speed, the way to do it is use an array as
an "index table". E.g.
set bookList {
{{Title {A hole in time} {ISBN 1234} {Author {John Smith}}
{{Title {A hole in space} {ISBN 1234} {Author {Jane Doe}}
}
array set bookIndex {}
set listLen [llenght $bookList]
for {set i 0} {$i < $listLen} {incr i} {
foreach item [lindex $bookList $i] {
lappend bookIndex($item) $i
}
}
##
## Look up all books whose authors have the last name Doe
##
set doeList {}
foreach key [array names bookIndex [list Author [list * Doe]] {
set doeList [concat $doeList $bookIndex($key)
}
--
+--------------------------------+---------------------------------------+
| Gerald W. Lester |
|"The man who fights for his ideals is the man who is alive." - Cervantes|
+------------------------------------------------------------------------+
Alexandre Ferrieux
> Michael Schlenker wrote:
>
> >> Similarly, why can't we have an option for lsearch?
>
> best to provide a sample implementation/patch.
I'd advise against TIPping it: calling a Tcl callback from the C-
optimized list iterator [lsearch] completely loses the gain of the
optimizations; the result would only be marginally faster than
proc lsearch_predicate {l p} {
set pos -1
foreach x $l {
incr pos
if {[uplevel 1 $p [list $x]]} {return $pos}
}
return -1
}
> I assume the reason he wants it is not execution speed, but rather easy of
> readability of the code.
You don't TIP when you're after readability regardless of speed. Tcl
is so good at introspection that it is a pleasure to write new control
structures or higher order functions like the obvious one above. TIPs
are for things that cannot be done in Tcl currently.
-Alex
MartinLemburg@UGS
the path of the development of "lsearch" from tcl 8.3 to 8.5 is
support the way "lsort" works, to support its options.
To support the "-command" option in "lsearch" too, would be a good
thing, looking at the development of "lsearch" in the last sub
versions.
But ... I never had the need for such a "-command" using "lsearch", so
I don't know if is really usefull to TIP such an option.
Especially if finding "special" elements (structured data or objects)
in a list using foreach is not that slow and could be packed into a
"specialLSearch" procedure.
About the slowliness of "lsort"'s "-command" option ... I know that it
is slow to providing a tcl procedure for a C sorting algorithm for
comparison. So I wouldn't expect a "-command" option of "lsearch" to
be very quick.
It's the choice of the developer of the runtime drawback is acceptable
or not.
Ok - my 2 cent about this.
Best regards and a nice weekend!
Martin Lemburg
UGS - a Siemens Company - Transforming the Process of Innovation
On Mar 10, 5:50 pm, Michael Schlenker <schl...@uni-oldenburg.de>
wrote:
Michael Schlenker
> On Mar 10, 7:38 pm, "Gerald W. Lester" <Gerald.Les...@cox.net> wrote:
>> Michael Schlenker wrote:
>>
>>>> Similarly, why can't we have an option for lsearch?
>> Because no one has implemented it. You can TIP it, if you do it would be
>> best to provide a sample implementation/patch.
>
> I'd advise against TIPping it: calling a Tcl callback from the C-
> optimized list iterator [lsearch] completely loses the gain of the
> optimizations; the result would only be marginally faster than
If i would TIP something like this, especially for Tcl 8.5+, where we
have apply for lambda functions, would be something similar to pythons
map()/reduce()/filter() functions. lsearch is currently very similar to
filter() for specific cases (if you use the -all -inline switches).
If you know you have a sorted list you gain some optimized behaviour,
but otherwise lsearch is not much better than foreach as an iterator, in
that case you can also simply do an:
package require struct::list
and use:
struct::list filterfor
http://tcllib.sourceforge.net/doc/struct_list.html
(which has the wrong argument order for playing nice with apply, as some
people already mentioned on various occasions).
Michael
Gerald W. Lester
> ... TIPs are for things that cannot be done in Tcl currently.
Alex,
Sorry but you are wrong on that one.
It is entirely appropriate to make a TIP for the sake of lsearch having
options similar to lsort -- if it passes or not will depend on many factors
but including a proposed implementation that matches the Tcl C coding
standards will greatly increase its chances.
Balachandra Krishnamurthy
>> Alexandre Ferrieux schrieb:
>> I'd advise against TIPping it: calling a Tcl callback from the C-
>> optimized list iterator [lsearch] completely loses the gain of the
>> optimizations; the result would only be marginally faster than
Not implementing a -command option because it reduces the speed of
lsearch doesn't solve anything because I will then have to use foreach
(or other substitutes) on the list of objects, which is not fast anyway.
Given that I can't do any better than an O(n) search of the list, it is
much preferable to have lsearch do it rather than a new proc.
> If i would TIP something like this, especially for Tcl 8.5+, where we
> have apply for lambda functions, would be something similar to pythons
> map()/reduce()/filter() functions. lsearch is currently very similar to
> filter() for specific cases (if you use the -all -inline switches).
> package require struct::list
> and use:
> struct::list filterfor
Thanks. I think I will stick to doing a foreach for now, but I will work
on using something like lsearch as I could then pass a lambda function
(which is now supported in 8.5). That would be much cleaner than the
struct::list filterfor workaround.
--
Balachandra B. Krishnamurthy
Donal K. Fellows
> It is entirely appropriate to make a TIP for the sake of lsearch having
> options similar to lsort -- if it passes or not will depend on many
> factors but including a proposed implementation that matches the Tcl C
> coding standards will greatly increase its chances.
Having an implementation makes it possible to expedite voting. We don't
like voting on things without an implementation, as then there's a risk
that TIPs will hang around in the Accepted state instead of going Final.
Donal.
Donal K. Fellows
> If he was really concerned about speed, the way to do it is use an array
> as an "index table".
Either that or have it all in a database, such as SQLite.
Donal.
Michael Schlenker
> Michael Schlenker wrote:
>
>
>> If i would TIP something like this, especially for Tcl 8.5+, where we
>> have apply for lambda functions, would be something similar to pythons
>> map()/reduce()/filter() functions. lsearch is currently very similar to
>> filter() for specific cases (if you use the -all -inline switches).
>
>> package require struct::list
>> and use:
>> struct::list filterfor
>
> Thanks. I think I will stick to doing a foreach for now, but I will work
> on using something like lsearch as I could then pass a lambda function
> (which is now supported in 8.5). That would be much cleaner than the
> struct::list filterfor workaround.
Just for a simple comparision:
package require struct::list
proc plsearch {l p} {
set result [list]
foreach i $l {
if {[regexp $p $i]} {lappend result $i}
}
return $result
}
proc slsearch {l p} {
struct::list filterfor i $l [format {[regexp {%s} $i]} $p]
}
proc main {} {
# test with the snitfaq docs from tcllib
set fd [open "snitfaq.html"]
set l [split [read $fd] \n]
close $fd
puts "Lsearch time:"
puts [time {lsearch -all -inline -regexp $l {.*SNIT.*}} 1000]
puts "proc time:"
puts [time {plsearch $l {.*SNIT.*}} 1000]
puts "struct::list filterfor time:"
puts [time {slsearch $l {.*SNIT.*}} 1000]
}
main
I ran this on my local machine with the snitfaq from ActiveTcl 8.4.13
(where SNIT occurs 3 times in the text).
Here are the timings:
% source speed.tcl
Lsearch time:
7738.964 microseconds per iteration
proc time:
10270.794 microseconds per iteration
struct::list filterfor time:
8243.896 microseconds per iteration
So list filterfor is quite close to a filtering lsearch, while the naive
foreach approach is a bit slower...
Michael
Alexandre Ferrieux
wrote:
> Michael Schlenker wrote:
> >> Alexandre Ferrieux schrieb:
> >> I'd advise against TIPping it: calling a Tcl callback from the C-
> >> optimized list iterator [lsearch] completely loses the gain of the
> >> optimizations; the result would only be marginally faster than
>
> Not implementing a -command option because it reduces the speed of
> lsearch
You misunderstood. It won't slow down vanilla lsearches; it will only
be (disappointingly) not much fatster than foreach in your case.
> doesn't solve anything
No but it prevents unneeded bloat. Code size. Redundancy. Lack of
orthogonality.
> because I will then have to use foreach
> (or other substitutes) on the list of objects, which is not fast anyway.
None of the alternatives is fast.
> Given that I can't do any better than an O(n) search of the list, it is
> much preferable to have lsearch do it rather than a new proc.
Are you advocating to add bloat to the core just for a (say) 15%
improvement on the constant linear factor ? Just for your special
case ? The dream of a Lean and Mean Tcl is getting more and more
unreachable with every such proposal...
-Alex
Don Porter
> Having an implementation makes it possible to expedite voting. We don't
> like voting on things without an implementation, as then there's a risk
> that TIPs will hang around in the Accepted state instead of going Final.
The other big benefit is that even the most carefully drafted proposal
tends to have some details not spelled out. If there's a draft
implementation, then the de facto answers to any questions can be
determined (and possibly objected to/ revised/ improved ) by reviewers.
--
| Don Porter Mathematical and Computational Sciences Division |
| donald...@nist.gov Information Technology Laboratory |
| http://math.nist.gov/~DPorter/ NIST |
|______________________________________________________________________|
Balachandra Krishnamurthy
> case ? The dream of a Lean and Mean Tcl is getting more and more
> unreachable with every such proposal...
Is there a study that compares how Tcl performs in memory usage as
compared to other languages like Python and/or Lisp? I found many pages
on wiki.tcl.tk that talk about how to measure memory usage in Tcl and so
on but no comparisons as such. Even a comparison of memory usage in Tcl
from version to version will be useful (just for the core shell, not
with extensions).
Thanks for the input folks. It has been very helpful.
--
Balachandra B. Krishnamurthy
Michael Schlenker
> Alexandre Ferrieux wrote:
>> case ? The dream of a Lean and Mean Tcl is getting more and more
>> unreachable with every such proposal...
>
> Is there a study that compares how Tcl performs in memory usage as
> compared to other languages like Python and/or Lisp? I found many pages
> on wiki.tcl.tk that talk about how to measure memory usage in Tcl and so
> on but no comparisons as such. Even a comparison of memory usage in Tcl
> from version to version will be useful (just for the core shell, not
> with extensions).
Take a look at the memory usage in the benchmarks at:
http://shootout.alioth.debian.org
Michael
Fredderic
Balachandra Krishnamurthy <bkri...@purdue.edu> wrote:
> Thanks. I think I will stick to doing a foreach for now, but I will
> work on using something like lsearch as I could then pass a lambda
> function (which is now supported in 8.5). That would be much cleaner
> than the struct::list filterfor workaround.
I'm not sure why you consider [struct::list filterfor] to be a
workaround at all. struct::list contains functions for a variety of
rather useful but possibly uncommon tasks, or simply tasks that can't
be done a whole lot better by core. It might be interesting if EVERY
command was extensible, so [struct::list filterfor] could be mapped
somehow onto [lsearch -filterfor], but you've got a command that does
what you want it to do, and it's within the standard TCL support
library. How is that a workaround?
Fredderic