Hi all

mass numbers analysis , need improve speed ...

hope someone can give me some hint ,or other way search ....

code list below

set lst [lmap v [lrepeat 3125 1] {set v [expr int($v * [::tcl::mathfunc::rand]*39)]} ]

##### each number +id %39
proc adv_chg_no_range4 {id lst} {
set new_lst [lindex $lst 0]
for {set i 1} {$i < [llength $lst]} {incr i} {
set tmp_val [expr {([lindex $lst $i] + $id -1) % 39} ]
if {$tmp_val == 0} {set tmp_val 39}
lappend new_lst $tmp_val
}
return $new_lst
}

puts [time {

foreach x {1 12 18 5 6} {
lsearch -all -exact $lst $x
}

}

]

puts "###combine ##"

puts [time {

foreach x {1 12 18 5 6} {
lsearch -all [adv_chg_no_range4 1 $lst] $x
}

}

]\n

puts "#### regexp"
puts [time {lsearch -all -regexp $lst (^1$|^12$|^18$|^5$|^6$)}]
puts "###combine ##"
puts [time {lsearch -all -regexp [adv_chg_no_range4 1 $lst] (^1$|^12$|^18$|^5$|^6$)}

output:

328 microseconds per iteration
###combine ##
4928 microseconds per iteration

#### regexp
1341 microseconds per iteration
###combine ##
2525 microseconds per iteration

as the output use single proc -regexp less perfomance ....
but combine with other proc seem better .. Why....

could someone give me direction to overcome speed issue

thanks
Rolance

On Thursday, November 3, 2022 at 9:28:30 AM UTC+1, Rolance wrote:
> Hi all
>
> mass numbers analysis , need improve speed ...
>
> hope someone can give me some hint ,or other way search ....

Are you looking for the fastest code to solve a problem or for a better understanding of the observed timing.
If it is the first, then please also state the actual problem.

Anyway, here are a few comments (hopefully correct, but most likely not covering all aspects).

> set lst [lmap v [lrepeat 3125 1] {set v [expr int($v * [::tcl::mathfunc::rand]*39)]} ]

* $v is always 1 and that factor can be removed from expr.
* The argument to expr should be braced.
* "set v" is unnecessary; {expr {int([::tcl::mathfunc::rand]*39)}} will do.
* You could try whether a simple for-loop is faster than lrepeat+lmap. Tcl increases the internal list size progressively.

> ##### each number +id %39
> proc adv_chg_no_range4 {id lst} {

I guess there is a reason for a proc, i.e. why are you not creating these values straight away.

> set new_lst [lindex $lst 0]

The comment says "each number", but you are not processing the first one.

> for {set i 1} {$i < [llength $lst]} {incr i} {

You seem to know about lmap, why not here?

> set tmp_val [expr {([lindex $lst $i] + $id -1) % 39} ]

You could [incr id -1] once in advance (inside the proc before the loop).

> if {$tmp_val == 0} {set tmp_val 39}

You could time whether [expr {(($v+$id)%-39)+39}] is faster to obtain the range 1~39.

Or the other way round, perform $id%39 in advance and do a conditional range shift in the loop, i.e.
if {$tmp_val > 39} {incr tmp_val -39} {set tmp_val} ;# assuming lmap

Please cross-check correctness on your own, i.e. do not blindly trust me who does not know your actual problem statement.

> puts [time {
>
> foreach x {1 12 18 5 6} {
> lsearch -all -exact $lst $x

Should that be -integer instead of -exact?
Internally, you are creating string reps of the list items here.

> puts "###combine ##"
>
> puts [time {
>
> foreach x {1 12 18 5 6} {
> lsearch -all [adv_chg_no_range4 1 $lst] $x

Is there a reason for calling the proc in every loop?

> puts "#### regexp"
> puts [time {lsearch -all -regexp $lst (^1$|^12$|^18$|^5$|^6$)}]
> puts "###combine ##"
> puts [time {lsearch -all -regexp [adv_chg_no_range4 1 $lst] (^1$|^12$|^18$|^5$|^6$)}

Here, you definitely have a single call to the proc.

>
>
> output:
>
> 328 microseconds per iteration
> ###combine ##
> 4928 microseconds per iteration

This could include compile time of the proc. Do the timing more than once (or call the proc once in advance).

> #### regexp
> 1341 microseconds per iteration
> ###combine ##
> 2525 microseconds per iteration
>
>
> as the output use single proc -regexp less perfomance ....

Exact string comparison is way faster. Even glob-matching is faster, e.g. Expect creates glob-gatekeepers for regexp-matching.
You could try whether {^(?:x1|x2|...)$} matches faster (i.e. if the state-machine is simpler), but in the end the above statement will stand.

> but combine with other proc seem better .. Why....
> could someone give me direction to overcome speed issue

Double the time for 5 times the calls to the proc seems to proof different. You will find out in a cross-check.
In the end, most of my comments turn out to be irrelevant for that final finding ... Maybe they help anyway.

heinrichmartin 在 2022年11月3日 星期四晚上11:25:02 [UTC+13] 的信中寫道：
> On Thursday, November 3, 2022 at 9:28:30 AM UTC+1, Rolance wrote:
> > Hi all
> >
> > mass numbers analysis , need improve speed ...
> >
> > hope someone can give me some hint ,or other way search ....
> Are you looking for the fastest code to solve a problem or for a better understanding of the observed timing.
> If it is the first, then please also state the actual problem.
>
> Anyway, here are a few comments (hopefully correct, but most likely not covering all aspects).
> > set lst [lmap v [lrepeat 3125 1] {set v [expr int($v * [::tcl::mathfunc::rand]*39)]} ]
> * $v is always 1 and that factor can be removed from expr.
> * The argument to expr should be braced.
> * "set v" is unnecessary; {expr {int([::tcl::mathfunc::rand]*39)}} will do.
> * You could try whether a simple for-loop is faster than lrepeat+lmap. Tcl increases the internal list size progressively.
> > ##### each number +id %39
> > proc adv_chg_no_range4 {id lst} {
> I guess there is a reason for a proc, i.e. why are you not creating these values straight away.
> > set new_lst [lindex $lst 0]
> The comment says "each number", but you are not processing the first one.
> > for {set i 1} {$i < [llength $lst]} {incr i} {
> You seem to know about lmap, why not here?
> > set tmp_val [expr {([lindex $lst $i] + $id -1) % 39} ]
> You could [incr id -1] once in advance (inside the proc before the loop).
> > if {$tmp_val == 0} {set tmp_val 39}
> You could time whether [expr {(($v+$id)%-39)+39}] is faster to obtain the range 1~39.
>
> Or the other way round, perform $id%39 in advance and do a conditional range shift in the loop, i.e.
> if {$tmp_val > 39} {incr tmp_val -39} {set tmp_val} ;# assuming lmap
>
> Please cross-check correctness on your own, i.e. do not blindly trust me who does not know your actual problem statement.
> > puts [time {
> >
> > foreach x {1 12 18 5 6} {
> > lsearch -all -exact $lst $x
> Should that be -integer instead of -exact?
> Internally, you are creating string reps of the list items here.
> > puts "###combine ##"
> >
> > puts [time {
> >
> > foreach x {1 12 18 5 6} {
> > lsearch -all [adv_chg_no_range4 1 $lst] $x
> Is there a reason for calling the proc in every loop?
> > puts "#### regexp"
> > puts [time {lsearch -all -regexp $lst (^1$|^12$|^18$|^5$|^6$)}]
> > puts "###combine ##"
> > puts [time {lsearch -all -regexp [adv_chg_no_range4 1 $lst] (^1$|^12$|^18$|^5$|^6$)}
> Here, you definitely have a single call to the proc.
> >
> >
> > output:
> >
> > 328 microseconds per iteration
> > ###combine ##
> > 4928 microseconds per iteration
> This could include compile time of the proc. Do the timing more than once (or call the proc once in advance).
> > #### regexp
> > 1341 microseconds per iteration
> > ###combine ##
> > 2525 microseconds per iteration
> >
> >
> > as the output use single proc -regexp less perfomance ....
> Exact string comparison is way faster. Even glob-matching is faster, e.g. Expect creates glob-gatekeepers for regexp-matching.
> You could try whether {^(?:x1|x2|...)$} matches faster (i.e. if the state-machine is simpler), but in the end the above statement will stand.
> > but combine with other proc seem better .. Why....
> > could someone give me direction to overcome speed issue
> Double the time for 5 times the calls to the proc seems to proof different. You will find out in a cross-check.
> In the end, most of my comments turn out to be irrelevant for that final finding ... Maybe they help anyway.

hi heinrichmartin

thanks for your advice

1. looking for the fastest code to mass data , speed issue need cut down consume time as least half..
this code is part of project , the most affect effience part -- > lsearch command
already try serveal way to get best search time .....
or you have other best way to achieve like dict .. or array search code for reference?

2. (a).why use --> foreach x {1 12 18 5 6} {
lsearch -all -exact $lst $x
(b) not ---> Should that be -integer instead of -exact?

(a): 351 microseconds per iteration <<<<
(b): 583 microseconds per iteration

3. single proc Vs combine proc the time consume not proportional .....
still try to find out which affect momory occupy , not the simply code can get the best perforamce ...
5times faster than one line (-regexp ) code ....

thanks
Rolance

On Thursday, November 3, 2022 at 12:05:37 PM UTC+1, Rolance wrote:
> heinrichmartin 在 2022年11月3日 星期四晚上11:25:02 [UTC+13] 的信中寫道：
> > On Thursday, November 3, 2022 at 9:28:30 AM UTC+1, Rolance wrote:
> > > Hi all
> > >
> > > mass numbers analysis , need improve speed ...
> > >
> > > hope someone can give me some hint ,or other way search ....
> > Are you looking for the fastest code to solve a problem or for a better understanding of the observed timing.
> > If it is the first, then please also state the actual problem.
> >
> > Anyway, here are a few comments (hopefully correct, but most likely not covering all aspects).
> > > set lst [lmap v [lrepeat 3125 1] {set v [expr int($v * [::tcl::mathfunc::rand]*39)]} ]
> > * $v is always 1 and that factor can be removed from expr.
> > * The argument to expr should be braced.
> > * "set v" is unnecessary; {expr {int([::tcl::mathfunc::rand]*39)}} will do.
> > * You could try whether a simple for-loop is faster than lrepeat+lmap. Tcl increases the internal list size progressively.
> > > ##### each number +id %39
> > > proc adv_chg_no_range4 {id lst} {
> > I guess there is a reason for a proc, i.e. why are you not creating these values straight away.
> > > set new_lst [lindex $lst 0]
> > The comment says "each number", but you are not processing the first one.
> > > for {set i 1} {$i < [llength $lst]} {incr i} {
> > You seem to know about lmap, why not here?
> > > set tmp_val [expr {([lindex $lst $i] + $id -1) % 39} ]
> > You could [incr id -1] once in advance (inside the proc before the loop).
> > > if {$tmp_val == 0} {set tmp_val 39}
> > You could time whether [expr {(($v+$id)%-39)+39}] is faster to obtain the range 1~39.
> >
> > Or the other way round, perform $id%39 in advance and do a conditional range shift in the loop, i.e.
> > if {$tmp_val > 39} {incr tmp_val -39} {set tmp_val} ;# assuming lmap
> >
> > Please cross-check correctness on your own, i.e. do not blindly trust me who does not know your actual problem statement.
> > > puts [time {
> > >
> > > foreach x {1 12 18 5 6} {
> > > lsearch -all -exact $lst $x
> > Should that be -integer instead of -exact?
> > Internally, you are creating string reps of the list items here.
> > > puts "###combine ##"
> > >
> > > puts [time {
> > >
> > > foreach x {1 12 18 5 6} {
> > > lsearch -all [adv_chg_no_range4 1 $lst] $x
> > Is there a reason for calling the proc in every loop?
> > > puts "#### regexp"
> > > puts [time {lsearch -all -regexp $lst (^1$|^12$|^18$|^5$|^6$)}]
> > > puts "###combine ##"
> > > puts [time {lsearch -all -regexp [adv_chg_no_range4 1 $lst] (^1$|^12$|^18$|^5$|^6$)}
> > Here, you definitely have a single call to the proc.
> > >
> > >
> > > output:
> > >
> > > 328 microseconds per iteration
> > > ###combine ##
> > > 4928 microseconds per iteration
> > This could include compile time of the proc. Do the timing more than once (or call the proc once in advance).
> > > #### regexp
> > > 1341 microseconds per iteration
> > > ###combine ##
> > > 2525 microseconds per iteration
> > >
> > >
> > > as the output use single proc -regexp less perfomance ....
> > Exact string comparison is way faster. Even glob-matching is faster, e.g. Expect creates glob-gatekeepers for regexp-matching.
> > You could try whether {^(?:x1|x2|...)$} matches faster (i.e. if the state-machine is simpler), but in the end the above statement will stand.
> > > but combine with other proc seem better .. Why....
> > > could someone give me direction to overcome speed issue
> > Double the time for 5 times the calls to the proc seems to proof different. You will find out in a cross-check.
> > In the end, most of my comments turn out to be irrelevant for that final finding ... Maybe they help anyway.
> hi heinrichmartin
>
> thanks for your advice

Not replying inline makes it hard for me to set your points in context.
> 1. looking for the fastest code to mass data , speed issue need cut down consume time as least half..
> this code is part of project , the most affect effience part -- > lsearch command
> already try serveal way to get best search time .....
> or you have other best way to achieve like dict .. or array search code for reference?

lsearch requires O(N) unless you can sort the list in advance WLOG. Dict and array (when using the data as keys) make the values unique; if that was acceptable, then why are you using -all? Besides, lsearch -integer should be unbeatable.

> 2. (a).why use --> foreach x {1 12 18 5 6} {
> lsearch -all -exact $lst $x
> (b) not ---> Should that be -integer instead of -exact?
>
> (a): 351 microseconds per iteration <<<<
> (b): 583 microseconds per iteration

My bad, -integer requires -exact (or -sorted) to take effect and that is not implied. (We had that here on clt; it is counter-intuitive.)

> 3. single proc Vs combine proc the time consume not proportional ....
> still try to find out which affect momory occupy , not the simply code can get the best perforamce ...
> 5times faster than one line (-regexp ) code ....

Let me comment with a quote:

On Thursday, August 13, 2020 at 9:07:54 AM UTC+2, Arjen wrote:
> [...] I do know that such benchmarks are notoriously difficult to get right. [...]

And you seem to have missed many very basic hints about possible improvements wrt Tcl/coding/algorithms in my previous answer ...

On Thursday, November 3, 2022 at 12:41:53 PM UTC+1, heinrichmartin wrote:
> On Thursday, November 3, 2022 at 12:05:37 PM UTC+1, Rolance wrote:
> > 3. single proc Vs combine proc the time consume not proportional ....
> > still try to find out which affect momory occupy , not the simply code can get the best perforamce ...
> > 5times faster than one line (-regexp ) code ....
> Let me comment with a quote:
>
> On Thursday, August 13, 2020 at 9:07:54 AM UTC+2, Arjen wrote:
> > [...] I do know that such benchmarks are notoriously difficult to get right. [...]

Btw, here is my quick take on it (including a few cross-checks):
expect:~$ set l [lmap x [lrepeat 10000 1] {expr {int(rand()*39)}}]; puts foo
foo
expect:~$ ll $l
10000
expect:~$ lindex $l 25
22
expect:~$ ::tcl::mathfunc::max {*}$l
38
expect:~$ time {lsearch -all -integer $l [expr {int(rand()*39)}]} 1000
230.131 microseconds per iteration
expect:~$ time {lsearch -all -exact $l [expr {int(rand()*39)}]} 1000
193.889 microseconds per iteration
expect:~$ time {lsearch -all -integer $l [expr {int(rand()*39)}]} 1000
230.803 microseconds per iteration
expect:~$ time {lsearch -all -exact $l [expr {int(rand()*39)}]} 1000
193.114 microseconds per iteration
expect:~$ set s [lsort -integer $l]; puts foo
foo
expect:~$ time {lsearch -all -sorted -exact $s [expr {int(rand()*39)}]} 1000
170.89 microseconds per iteration
expect:~$ set s [lsort -integer $l]; puts foo
foo
expect:~$ time {lsearch -all -sorted -integer $s [expr {int(rand()*39)}]} 1000
103.633 microseconds per iteration
expect:~$ time {lsearch -all -integer -exact $s [expr {int(rand()*39)}]} 1000
104.209 microseconds per iteration
expect:~$ time {lsearch -all -integer -exact $l [expr {int(rand()*39)}]} 1000
106.351 microseconds per iteration
expect:~$

rola...@gmail.com <rolance1@gmail.com> wrote:
> Hi all
>
> mass numbers analysis , need improve speed ...
>
> hope someone can give me some hint ,or other way search ....

As no one here knows what you are trying to achieve, we are limited in
our ability to offer suggestions.

> code list below
>
>
> set lst [lmap v [lrepeat 3125 1] {set v [expr int($v * [::tcl::mathfunc::rand]*39)]} ]
>
> ##### each number +id %39
> proc adv_chg_no_range4 {id lst} {
> set new_lst [lindex $lst 0]
> for {set i 1} {$i < [llength $lst]} {incr i} {
> set tmp_val [expr {([lindex $lst $i] + $id -1) % 39} ]
> if {$tmp_val == 0} {set tmp_val 39}
> lappend new_lst $tmp_val
> }
> return $new_lst
> }
>
>
>
>
> puts [time {
>
> foreach x {1 12 18 5 6} {
> lsearch -all -exact $lst $x
> }
>
> }
>
> ]
>
> puts "###combine ##"
>
> puts [time {
>
> foreach x {1 12 18 5 6} {
> lsearch -all [adv_chg_no_range4 1 $lst] $x
> }
>
> }
>
> ]\n
>
> puts "#### regexp"
> puts [time {lsearch -all -regexp $lst (^1$|^12$|^18$|^5$|^6$)}]
> puts "###combine ##"
> puts [time {lsearch -all -regexp [adv_chg_no_range4 1 $lst] (^1$|^12$|^18$|^5$|^6$)}
>
>
> output:
>
> 328 microseconds per iteration
> ###combine ##
> 4928 microseconds per iteration

Unsurprising here. The first does 5 searches over a static list.

The second makes 5 calls into a proc, that iterates the entire list via
foreach, returning a new list, and that new list is then searched.

Iterating the entire list, in Tcl, to generate a new list is where most
of this time difference is being consumed.

> #### regexp
> 1341 microseconds per iteration
> ###combine ##
> 2525 microseconds per iteration

Also unsurprising, searches using the regex engine will be slower than
searches using simple comparisons, because the regex engine does far
more than simple comparisons.

The time difference between the static list and the newly generated
list via a proc comments above also apply here.

> could someone give me direction to overcome speed issue

If your issue is lsearch speed, then:

1) only search a static list (i.e., don't recreate the list first
before searching it)

2) if your desired results can also be obtained from searching a sorted
list, then first sort the list (sort only once, then search plural
times). Using the -sorted option to lsearch causes lsearch to
perform a binary search of the list, which will be faster than
without -sorted, which causes lsearch to perform a linear search
(start at first element, look at each in sequence until found).

But you've failed to describe your actual problem. You've shown a
solution that does not work for you speed wise, but not described to us
what you are trying to achieve by this solution you've given. It is
quite possible there is some alternative way, without using lsearch, to
achieve your desired result, but we can't read your mind over Usenet to
know what your actual problem is to even be able to consider some
alternate.

heinrichmartin 在 2022年11月4日 星期五凌晨12:49:33 [UTC+13] 的信中寫道：
> On Thursday, November 3, 2022 at 12:41:53 PM UTC+1, heinrichmartin wrote:
> > On Thursday, November 3, 2022 at 12:05:37 PM UTC+1, Rolance wrote:
> > > 3. single proc Vs combine proc the time consume not proportional ....
> > > still try to find out which affect momory occupy , not the simply code can get the best perforamce ...
> > > 5times faster than one line (-regexp ) code ....
> > Let me comment with a quote:
> >
> > On Thursday, August 13, 2020 at 9:07:54 AM UTC+2, Arjen wrote:
> > > [...] I do know that such benchmarks are notoriously difficult to get right. [...]
> Btw, here is my quick take on it (including a few cross-checks):
> expect:~$ set l [lmap x [lrepeat 10000 1] {expr {int(rand()*39)}}]; puts foo
> foo
> expect:~$ ll $l
> 10000
> expect:~$ lindex $l 25
> 22
> expect:~$ ::tcl::mathfunc::max {*}$l
> 38
> expect:~$ time {lsearch -all -integer $l [expr {int(rand()*39)}]} 1000
> 230.131 microseconds per iteration
> expect:~$ time {lsearch -all -exact $l [expr {int(rand()*39)}]} 1000
> 193.889 microseconds per iteration
> expect:~$ time {lsearch -all -integer $l [expr {int(rand()*39)}]} 1000
> 230.803 microseconds per iteration
> expect:~$ time {lsearch -all -exact $l [expr {int(rand()*39)}]} 1000
> 193.114 microseconds per iteration
> expect:~$ set s [lsort -integer $l]; puts foo
> foo
> expect:~$ time {lsearch -all -sorted -exact $s [expr {int(rand()*39)}]} 1000
> 170.89 microseconds per iteration
> expect:~$ set s [lsort -integer $l]; puts foo
> foo
> expect:~$ time {lsearch -all -sorted -integer $s [expr {int(rand()*39)}]} 1000
> 103.633 microseconds per iteration
> expect:~$ time {lsearch -all -integer -exact $s [expr {int(rand()*39)}]} 1000
> 104.209 microseconds per iteration
> expect:~$ time {lsearch -all -integer -exact $l [expr {int(rand()*39)}]} 1000
> 106.351 microseconds per iteration
> expect:~$

hi heinrichmartin

thank for your detail reply and try result

1. the data come from mass data file over 10G, each data line prefix with tile-id , that is why not use [lindex 0] data..
data must get form other source
2. need learch -all to get all value position , alreay try -inline and -regexp , the total running perfromnce less than simple -all

3. already view Tcl/coding/algorithms and do improve my program perviously , I think it the best solution , but customer not satisify with the speed
need get best performce for each proc code ....
lsearch can fit all request , or your have suggestion command to replace this with better perforamce.

4. will try all your suggestion later and repport the result

thanks
BR
Rolance

Rich 在 2022年11月4日 星期五凌晨3:09:19 [UTC+13] 的信中寫道：
> rola...@gmail.com <rola...@gmail.com> wrote:
> > Hi all
> >
> > mass numbers analysis , need improve speed ...
> >
> > hope someone can give me some hint ,or other way search ....
> As no one here knows what you are trying to achieve, we are limited in
> our ability to offer suggestions.
> > code list below
> >
> >
> > set lst [lmap v [lrepeat 3125 1] {set v [expr int($v * [::tcl::mathfunc::rand]*39)]} ]
> >
> > ##### each number +id %39
> > proc adv_chg_no_range4 {id lst} {
> > set new_lst [lindex $lst 0]
> > for {set i 1} {$i < [llength $lst]} {incr i} {
> > set tmp_val [expr {([lindex $lst $i] + $id -1) % 39} ]
> > if {$tmp_val == 0} {set tmp_val 39}
> > lappend new_lst $tmp_val
> > }
> > return $new_lst
> > }
> >
> >
> >
> >
> > puts [time {
> >
> > foreach x {1 12 18 5 6} {
> > lsearch -all -exact $lst $x
> > }
> >
> > }
> >
> > ]
> >
> > puts "###combine ##"
> >
> > puts [time {
> >
> > foreach x {1 12 18 5 6} {
> > lsearch -all [adv_chg_no_range4 1 $lst] $x
> > }
> >
> > }
> >
> > ]\n
> >
> > puts "#### regexp"
> > puts [time {lsearch -all -regexp $lst (^1$|^12$|^18$|^5$|^6$)}]
> > puts "###combine ##"
> > puts [time {lsearch -all -regexp [adv_chg_no_range4 1 $lst] (^1$|^12$|^18$|^5$|^6$)}
> >
> >
> > output:
> >
> > 328 microseconds per iteration
> > ###combine ##
> > 4928 microseconds per iteration
> Unsurprising here. The first does 5 searches over a static list.
>
> The second makes 5 calls into a proc, that iterates the entire list via
> foreach, returning a new list, and that new list is then searched.
>
> Iterating the entire list, in Tcl, to generate a new list is where most
> of this time difference is being consumed.
> > #### regexp
> > 1341 microseconds per iteration
> > ###combine ##
> > 2525 microseconds per iteration
> Also unsurprising, searches using the regex engine will be slower than
> searches using simple comparisons, because the regex engine does far
> more than simple comparisons.
>
> The time difference between the static list and the newly generated
> list via a proc comments above also apply here.
> > could someone give me direction to overcome speed issue
> If your issue is lsearch speed, then:
>
> 1) only search a static list (i.e., don't recreate the list first
> before searching it)
>
> 2) if your desired results can also be obtained from searching a sorted
> list, then first sort the list (sort only once, then search plural
> times). Using the -sorted option to lsearch causes lsearch to
> perform a binary search of the list, which will be faster than
> without -sorted, which causes lsearch to perform a linear search
> (start at first element, look at each in sequence until found).
>
> But you've failed to describe your actual problem. You've shown a
> solution that does not work for you speed wise, but not described to us
> what you are trying to achieve by this solution you've given. It is
> quite possible there is some alternative way, without using lsearch, to
> achieve your desired result, but we can't read your mind over Usenet to
> know what your actual problem is to even be able to consider some
> alternate.

Hi Rich

thanks for your advice
is possible relate memory occupy issue , see the running program get more an more memory after long time running...
will try all your suggestion later in real running program and give your detail reply

BR
Rolance

heinrichmartin 在 2022年11月4日 星期五凌晨12:49:33 [UTC+13] 的信中寫道：
> On Thursday, November 3, 2022 at 12:41:53 PM UTC+1, heinrichmartin wrote:
> > On Thursday, November 3, 2022 at 12:05:37 PM UTC+1, Rolance wrote:
> > > 3. single proc Vs combine proc the time consume not proportional ....
> > > still try to find out which affect momory occupy , not the simply code can get the best perforamce ...
> > > 5times faster than one line (-regexp ) code ....
> > Let me comment with a quote:
> >
> > On Thursday, August 13, 2020 at 9:07:54 AM UTC+2, Arjen wrote:
> > > [...] I do know that such benchmarks are notoriously difficult to get right. [...]
> Btw, here is my quick take on it (including a few cross-checks):
> expect:~$ set l [lmap x [lrepeat 10000 1] {expr {int(rand()*39)}}]; puts foo
> foo
> expect:~$ ll $l
> 10000
> expect:~$ lindex $l 25
> 22
> expect:~$ ::tcl::mathfunc::max {*}$l
> 38
> expect:~$ time {lsearch -all -integer $l [expr {int(rand()*39)}]} 1000
> 230.131 microseconds per iteration
> expect:~$ time {lsearch -all -exact $l [expr {int(rand()*39)}]} 1000
> 193.889 microseconds per iteration
> expect:~$ time {lsearch -all -integer $l [expr {int(rand()*39)}]} 1000
> 230.803 microseconds per iteration
> expect:~$ time {lsearch -all -exact $l [expr {int(rand()*39)}]} 1000
> 193.114 microseconds per iteration
> expect:~$ set s [lsort -integer $l]; puts foo
> foo
> expect:~$ time {lsearch -all -sorted -exact $s [expr {int(rand()*39)}]} 1000
> 170.89 microseconds per iteration
> expect:~$ set s [lsort -integer $l]; puts foo
> foo
> expect:~$ time {lsearch -all -sorted -integer $s [expr {int(rand()*39)}]} 1000
> 103.633 microseconds per iteration
> expect:~$ time {lsearch -all -integer -exact $s [expr {int(rand()*39)}]} 1000
> 104.209 microseconds per iteration
> expect:~$ time {lsearch -all -integer -exact $l [expr {int(rand()*39)}]} 1000
> 106.351 microseconds per iteration
> expect:~$

Hi heinrichmartin

update code with your comment and test result below

set lst [lmap v [lrepeat 3125 1] {expr {int($v * [::tcl::mathfunc::rand]*39)}} ]

##### each number +id %39 first char title id
proc adv_chg_no_range4 {id lst} {
set new_lst [lindex $lst 0]
for {set i 1} {$i < [llength $lst]} {incr i} {
set tmp_val [expr {([lindex $lst $i] + $id -1) % 39} ]
if {$tmp_val == 0} {set tmp_val 39}
lappend new_lst $tmp_val
}
return $new_lst
}

proc adv_chg_no_range5 {id lst} {
set new_lst [lindex $lst 0]
incr id -1
lappend new_lst {*}[lmap v [lrange $lst 1 end] {
expr {(($v+$id)%-39)+39}
}]
return $new_lst
}

proc adv_chg_no_range6 {id lst} {
set new_lst [lindex $lst 0]
incr id -1
for {set i 1} {$i < [llength $lst]} {incr i} {
lappend new_lst [expr {(([lindex $lst $i]+$id)%-39)+39} ]
}
return $new_lst
}

puts [time {

foreach x {1 12 18 5 6} {
lsearch -all -exact $lst $x
}

}

]

puts "###combine ##"

puts [time {

foreach x {1 12 18 5 6} {
lsearch -all [adv_chg_no_range4 1 $lst] $x
}

}

]\n

puts "###combine static lst##"

puts [time {
set new [adv_chg_no_range4 1 $lst]
foreach x {1 12 18 5 6} {
lsearch -all $new $x
}

}

]\n

puts "#### regexp"
puts [time {lsearch -all -regexp $lst (^1$|^12$|^18$|^5$|^6$)}]
puts [time {lsearch -all -regexp $lst {^(?:1|12|18|5|6)$}}]
puts "###combine proc 4##"
puts [time {lsearch -all -regexp [adv_chg_no_range4 1 $lst] (^1$|^12$|^18$|^5$|^6$)}]
puts [time {lsearch -all -regexp [adv_chg_no_range4 1 $lst] {^(?:1|12|18|5|6)$}}]
puts "###combine proc 5##"
puts [time {lsearch -all -regexp [adv_chg_no_range5 1 $lst] (^1$|^12$|^18$|^5$|^6$)}]
puts [time {lsearch -all -regexp [adv_chg_no_range5 1 $lst] {^(?:1|12|18|5|6)$}}]
puts [time {lsearch -all -regexp $new {^(?:1|12|18|5|6)$}}]
puts "###combine proc 6##"
puts [time {lsearch -all -regexp [adv_chg_no_range6 1 $lst] (^1$|^12$|^18$|^5$|^6$)}]
puts [time {lsearch -all -regexp [adv_chg_no_range6 1 $lst] {^(?:1|12|18|5|6)$}}]

output

386 microseconds per iteration <<<<<
###combine ##
4807 microseconds per iteration

###combine static lst##
1069 microseconds per iteration <<<<<<<< 5 loop better than regexp but seem not stable ...

#### regexp
1311 microseconds per iteration
703 microseconds per iteration
###combine proc 4##
2550 microseconds per iteration
1797 microseconds per iteration
###combine proc 5##
1814 microseconds per iteration
1426 microseconds per iteration <<<<<< lmap get bests perforamce
942 microseconds per iteration <<<<<<<
###combine proc 6##
2091 microseconds per iteration
1633 microseconds per iteration

could you point me where still can improve .

thanks in advance

BR
Rolance

heinrichmartin 在 2022年11月4日 星期五凌晨12:49:33 [UTC+13] 的信中寫道：
> On Thursday, November 3, 2022 at 12:41:53 PM UTC+1, heinrichmartin wrote:
> > On Thursday, November 3, 2022 at 12:05:37 PM UTC+1, Rolance wrote:
> > > 3. single proc Vs combine proc the time consume not proportional ....
> > > still try to find out which affect momory occupy , not the simply code can get the best perforamce ...
> > > 5times faster than one line (-regexp ) code ....
> > Let me comment with a quote:
> >
> > On Thursday, August 13, 2020 at 9:07:54 AM UTC+2, Arjen wrote:
> > > [...] I do know that such benchmarks are notoriously difficult to get right. [...]
> Btw, here is my quick take on it (including a few cross-checks):
> expect:~$ set l [lmap x [lrepeat 10000 1] {expr {int(rand()*39)}}]; puts foo
> foo
> expect:~$ ll $l
> 10000
> expect:~$ lindex $l 25
> 22
> expect:~$ ::tcl::mathfunc::max {*}$l
> 38
> expect:~$ time {lsearch -all -integer $l [expr {int(rand()*39)}]} 1000
> 230.131 microseconds per iteration
> expect:~$ time {lsearch -all -exact $l [expr {int(rand()*39)}]} 1000
> 193.889 microseconds per iteration
> expect:~$ time {lsearch -all -integer $l [expr {int(rand()*39)}]} 1000
> 230.803 microseconds per iteration
> expect:~$ time {lsearch -all -exact $l [expr {int(rand()*39)}]} 1000
> 193.114 microseconds per iteration
> expect:~$ set s [lsort -integer $l]; puts foo
> foo
> expect:~$ time {lsearch -all -sorted -exact $s [expr {int(rand()*39)}]} 1000
> 170.89 microseconds per iteration
> expect:~$ set s [lsort -integer $l]; puts foo
> foo
> expect:~$ time {lsearch -all -sorted -integer $s [expr {int(rand()*39)}]} 1000
> 103.633 microseconds per iteration
> expect:~$ time {lsearch -all -integer -exact $s [expr {int(rand()*39)}]} 1000
> 104.209 microseconds per iteration
> expect:~$ time {lsearch -all -integer -exact $l [expr {int(rand()*39)}]} 1000
> 106.351 microseconds per iteration
> expect:~$

Hi heinrichmartin

update code with your comment and test result below

set lst [lmap v [lrepeat 3125 1] {expr {int($v * [::tcl::mathfunc::rand]*39)}} ]

##### each number +id %39 first char title id
proc adv_chg_no_range4 {id lst} {
set new_lst [lindex $lst 0]
for {set i 1} {$i < [llength $lst]} {incr i} {
set tmp_val [expr {([lindex $lst $i] + $id -1) % 39} ]
if {$tmp_val == 0} {set tmp_val 39}
lappend new_lst $tmp_val
}
return $new_lst
}

proc adv_chg_no_range5 {id lst} {
set new_lst [lindex $lst 0]
incr id -1
lappend new_lst {*}[lmap v [lrange $lst 1 end] {
expr {(($v+$id)%-39)+39}
}]
return $new_lst
}

proc adv_chg_no_range6 {id lst} {
set new_lst [lindex $lst 0]
incr id -1
for {set i 1} {$i < [llength $lst]} {incr i} {
lappend new_lst [expr {(([lindex $lst $i]+$id)%-39)+39} ]
}
return $new_lst
}

puts [time {

foreach x {1 12 18 5 6} {
lsearch -all -exact $lst $x
}

}

]

puts "###combine ##"

puts [time {

foreach x {1 12 18 5 6} {
lsearch -all [adv_chg_no_range4 1 $lst] $x
}

}

]\n

puts "###combine static lst##"

puts [time {
set new [adv_chg_no_range4 1 $lst]
foreach x {1 12 18 5 6} {
lsearch -all $new $x
}

}

]\n

puts "#### regexp"
puts [time {lsearch -all -regexp $lst (^1$|^12$|^18$|^5$|^6$)}]
puts [time {lsearch -all -regexp $lst {^(?:1|12|18|5|6)$}}]
puts "###combine proc 4##"
puts [time {lsearch -all -regexp [adv_chg_no_range4 1 $lst] (^1$|^12$|^18$|^5$|^6$)}]
puts [time {lsearch -all -regexp [adv_chg_no_range4 1 $lst] {^(?:1|12|18|5|6)$}}]
puts "###combine proc 5##"
puts [time {lsearch -all -regexp [adv_chg_no_range5 1 $lst] (^1$|^12$|^18$|^5$|^6$)}]
puts [time {lsearch -all -regexp [adv_chg_no_range5 1 $lst] {^(?:1|12|18|5|6)$}}]
puts [time {lsearch -all -regexp $new {^(?:1|12|18|5|6)$}}]
puts "###combine proc 6##"
puts [time {lsearch -all -regexp [adv_chg_no_range6 1 $lst] (^1$|^12$|^18$|^5$|^6$)}]
puts [time {lsearch -all -regexp [adv_chg_no_range6 1 $lst] {^(?:1|12|18|5|6)$}}]

output

386 microseconds per iteration <<<<<
###combine ##
4807 microseconds per iteration

###combine static lst##
1069 microseconds per iteration <<<<<<<< 5 loop better than regexp but seem not stable ...

#### regexp
1311 microseconds per iteration
703 microseconds per iteration
###combine proc 4##
2550 microseconds per iteration
1797 microseconds per iteration
###combine proc 5##
1814 microseconds per iteration
1426 microseconds per iteration <<<<<< lmap get bests perforamce
942 microseconds per iteration <<<<<<<
###combine proc 6##
2091 microseconds per iteration
1633 microseconds per iteration

could you point me where still can improve .

thanks in advance

BR
Rolance

Rich 在 2022年11月4日 星期五凌晨3:09:19 [UTC+13] 的信中寫道：
> rola...@gmail.com <rola...@gmail.com> wrote:
> > Hi all
> >
> > mass numbers analysis , need improve speed ...
> >
> > hope someone can give me some hint ,or other way search ....
> As no one here knows what you are trying to achieve, we are limited in
> our ability to offer suggestions.
> > code list below
> >
> >
> > set lst [lmap v [lrepeat 3125 1] {set v [expr int($v * [::tcl::mathfunc::rand]*39)]} ]
> >
> > ##### each number +id %39
> > proc adv_chg_no_range4 {id lst} {
> > set new_lst [lindex $lst 0]
> > for {set i 1} {$i < [llength $lst]} {incr i} {
> > set tmp_val [expr {([lindex $lst $i] + $id -1) % 39} ]
> > if {$tmp_val == 0} {set tmp_val 39}
> > lappend new_lst $tmp_val
> > }
> > return $new_lst
> > }
> >
> >
> >
> >
> > puts [time {
> >
> > foreach x {1 12 18 5 6} {
> > lsearch -all -exact $lst $x
> > }
> >
> > }
> >
> > ]
> >
> > puts "###combine ##"
> >
> > puts [time {
> >
> > foreach x {1 12 18 5 6} {
> > lsearch -all [adv_chg_no_range4 1 $lst] $x
> > }
> >
> > }
> >
> > ]\n
> >
> > puts "#### regexp"
> > puts [time {lsearch -all -regexp $lst (^1$|^12$|^18$|^5$|^6$)}]
> > puts "###combine ##"
> > puts [time {lsearch -all -regexp [adv_chg_no_range4 1 $lst] (^1$|^12$|^18$|^5$|^6$)}
> >
> >
> > output:
> >
> > 328 microseconds per iteration
> > ###combine ##
> > 4928 microseconds per iteration
> Unsurprising here. The first does 5 searches over a static list.
>
> The second makes 5 calls into a proc, that iterates the entire list via
> foreach, returning a new list, and that new list is then searched.
>
> Iterating the entire list, in Tcl, to generate a new list is where most
> of this time difference is being consumed.
> > #### regexp
> > 1341 microseconds per iteration
> > ###combine ##
> > 2525 microseconds per iteration
> Also unsurprising, searches using the regex engine will be slower than
> searches using simple comparisons, because the regex engine does far
> more than simple comparisons.
>
> The time difference between the static list and the newly generated
> list via a proc comments above also apply here.
> > could someone give me direction to overcome speed issue
> If your issue is lsearch speed, then:
>
> 1) only search a static list (i.e., don't recreate the list first
> before searching it)
>
> 2) if your desired results can also be obtained from searching a sorted
> list, then first sort the list (sort only once, then search plural
> times). Using the -sorted option to lsearch causes lsearch to
> perform a binary search of the list, which will be faster than
> without -sorted, which causes lsearch to perform a linear search
> (start at first element, look at each in sequence until found).
>
> But you've failed to describe your actual problem. You've shown a
> solution that does not work for you speed wise, but not described to us
> what you are trying to achieve by this solution you've given. It is
> quite possible there is some alternative way, without using lsearch, to
> achieve your desired result, but we can't read your mind over Usenet to
> know what your actual problem is to even be able to consider some
> alternate.

Hi Rich

1. static list indeed faster , but need recreate lst for each analysis , how can improve this ... release memory ?

2 this actual problem is speed issue , all analysis result can fit request except the consume time , customer want cut half ...
adv_chg_no_range5 is the best performance
5 time loop search is better than regexp , but not stable..
(update code post pre , please refer)

could you point me some better or alterntive way to achieve speed request

thanks in advance
BR
Rolance

* "rola...@gmail.com" <rolance1@gmail.com>
| ##### each number +id %39 first char title id
| proc adv_chg_no_range4 {id lst} {
| set new_lst [lindex $lst 0]
| for {set i 1} {$i < [llength $lst]} {incr i} {
| set tmp_val [expr {([lindex $lst $i] + $id -1) % 39} ]
| if {$tmp_val == 0} {set tmp_val 39}
| lappend new_lst $tmp_val
| }
| return $new_lst
| }
--<snip-snip>--
| proc adv_chg_no_range6 {id lst} {
| set new_lst [lindex $lst 0]
| incr id -1
| for {set i 1} {$i < [llength $lst]} {incr i} {
| lappend new_lst [expr {(([lindex $lst $i]+$id)%-39)+39} ]
| }
| return $new_lst
| }
--<snip-snip>--
| could you point me where still can improve .

Instead of traversing the list by index, use foreach:

for {set i 1} {$i < [llength $lst]} {incr i} {
set elt [lindex $lst $i]
...
}
=>
foreach elt [lrange $lst 1 end] {
...
}

But I have to admit I did not follow this thread to understand what your
ultimate goal is.

HTH
R'

Ralf Fassel 在 2022年11月4日 星期五晚上10:48:51 [UTC+13] 的信中寫道：
> * "rola...@gmail.com" <rola...@gmail.com>
> | ##### each number +id %39 first char title id
> | proc adv_chg_no_range4 {id lst} {
> | set new_lst [lindex $lst 0]
> | for {set i 1} {$i < [llength $lst]} {incr i} {
> | set tmp_val [expr {([lindex $lst $i] + $id -1) % 39} ]
> | if {$tmp_val == 0} {set tmp_val 39}
> | lappend new_lst $tmp_val
> | }
> | return $new_lst
> | }
> --<snip-snip>--
> | proc adv_chg_no_range6 {id lst} {
> | set new_lst [lindex $lst 0]
> | incr id -1
> | for {set i 1} {$i < [llength $lst]} {incr i} {
> | lappend new_lst [expr {(([lindex $lst $i]+$id)%-39)+39} ]
> | }
> | return $new_lst
> | }
> --<snip-snip>--
> | could you point me where still can improve .
> Instead of traversing the list by index, use foreach:
> for {set i 1} {$i < [llength $lst]} {incr i} {
> set elt [lindex $lst $i]
> ...
> }
> =>
> foreach elt [lrange $lst 1 end] {
> ...
> }
>
> But I have to admit I did not follow this thread to understand what your
> ultimate goal is.
>
> HTH
> R'

Hi Ralf

thank for your suggestion , my goal is best lsearch performance
will try foreach will improve how much in multi analysis

BR
Rolance

On Friday, November 4, 2022 at 10:58:40 AM UTC+1, rolance wrote:
> thank for your suggestion , my goal is best lsearch performance
> will try foreach will improve how much in multi analysis

Your claims are inconsistent, lsearch has no foreach.

Your initial problem ("Given a list of integers, find all matching integers fast.") is solved in this thread.
But your issues are somewhere else, e.g. reading data, transforming data, memory management.

Just one example: if you cannot accept multiple copies of your GBs of data, then you must transform the values in place (for & lindex & lset) or process them in a stream (i.e. do not create a list at all).

https://www.youtube.com/watch?v=c33AZBnRHks might describe an unexpectedly close problem (but we still don't know your exact objective). Anyway, the video contains quite some lessons about data handling/analysis.

heinrichmartin 在 2022年11月4日 星期五晚上11:16:27 [UTC+13] 的信中寫道：
> On Friday, November 4, 2022 at 10:58:40 AM UTC+1, rolance wrote:
> > thank for your suggestion , my goal is best lsearch performance
> > will try foreach will improve how much in multi analysis
> Your claims are inconsistent, lsearch has no foreach.
>
> Your initial problem ("Given a list of integers, find all matching integers fast.") is solved in this thread.
> But your issues are somewhere else, e.g. reading data, transforming data, memory management.
>
> Just one example: if you cannot accept multiple copies of your GBs of data, then you must transform the values in place (for & lindex & lset) or process them in a stream (i.e. do not create a list at all).
>
> https://www.youtube.com/watch?v=c33AZBnRHks might describe an unexpectedly close problem (but we still don't know your exact objective). Anyway, the video contains quite some lessons about data handling/analysis.

Hi heinrichmartin

thanks for your advice and reference video

my exact objective is improve the lsearch speed and your suggestion already help to raise 20% performance than original code , the lsearch is the key factor for the analysis program
in my statement contain some memory managemt may hace side effect , process them in a stream (over 1.6G have alloc issue ..) or multiple copies already try not better than existing code....
or you have better ideal for improve speed , accept all suggestion ^^
thanks

BR
Rolance

Ralf Fassel <ralfixx@gmx.de> wrote:
> But I have to admit I did not follow this thread to understand what your
> ultimate goal is.

The OP has been asked what they are trying to achieve, multiple times.

No reply has ever done more than post yet another block of hard to
follow code with a faint "help me make this faster" request.

rola...@gmail.com <rolance1@gmail.com> wrote:
> Ralf Fassel ? 2022?11?4? ?????10:48:51 [UTC+13] ??????
>> * "rola...@gmail.com" <rola...@gmail.com>
>> | could you point me where still can improve .
>> Instead of traversing the list by index, use foreach:
>> for {set i 1} {$i < [llength $lst]} {incr i} {
>> set elt [lindex $lst $i]
>> ...
>> }
>> =>
>> foreach elt [lrange $lst 1 end] {
>> ...
>> }
>>
>> But I have to admit I did not follow this thread to understand what your
>> ultimate goal is.
>>
>> HTH
>> R'
>
> Hi Ralf
>
> thank for your suggestion , my goal is best lsearch performance
> will try foreach will improve how much in multi analysis

No, that is not the answer to Ralf's question.

That is your current half-baked solution, but tells us nothing about
what you are trying to do beyond "faster lsearch". If we knew why you
were doing the lsearch (i.e., what the outer algorithm that is
searching this list is attempting to do) we might be able to suggest an
alternative.

As it is, you have a solution that does not work for you in your view,
and are only asking us to help tweak your solution -- without even
telling us enough to understand what that solution happens to be doing.

rola...@gmail.com <rolance1@gmail.com> wrote:
> Rich ? 2022?11?4? ?????3:09:19 [UTC+13] ??????
>> rola...@gmail.com <rola...@gmail.com> wrote:
>> > Hi all
>> >
>> > mass numbers analysis , need improve speed ...
>> >
>> Unsurprising here. The first does 5 searches over a static list.
>>
>> The second makes 5 calls into a proc, that iterates the entire list via
>> foreach, returning a new list, and that new list is then searched.
>>
>> Iterating the entire list, in Tcl, to generate a new list is where most
>> of this time difference is being consumed.
>> > #### regexp
>> > 1341 microseconds per iteration
>> > ###combine ##
>> > 2525 microseconds per iteration
>> Also unsurprising, searches using the regex engine will be slower than
>> searches using simple comparisons, because the regex engine does far
>> more than simple comparisons.
>>
>> The time difference between the static list and the newly generated
>> list via a proc comments above also apply here.
>> > could someone give me direction to overcome speed issue
>> If your issue is lsearch speed, then:
>>
>> 1) only search a static list (i.e., don't recreate the list first
>> before searching it)
>>
>> 2) if your desired results can also be obtained from searching a sorted
>> list, then first sort the list (sort only once, then search plural
>> times). Using the -sorted option to lsearch causes lsearch to
>> perform a binary search of the list, which will be faster than
>> without -sorted, which causes lsearch to perform a linear search
>> (start at first element, look at each in sequence until found).
>>
>> But you've failed to describe your actual problem. You've shown a
>> solution that does not work for you speed wise, but not described to us
>> what you are trying to achieve by this solution you've given. It is
>> quite possible there is some alternative way, without using lsearch, to
>> achieve your desired result, but we can't read your mind over Usenet to
>> know what your actual problem is to even be able to consider some
>> alternate.
>
>
> Hi Rich
>
> 1. static list indeed faster , but need recreate lst for each
> analysis , how can improve this ... release memory ?

Please explain to us why you need to recreate the list for each
analysis. We see no reason yet why this is necessary (and don't simply
say "because I need to do so" -- that will not be an acceptable
answer).

You can't 'release memory' manually with Tcl, that is all automatic.

> 2 this actual problem is speed issue , all analysis result can fit
> request except the consume time , customer want cut half ...

No, the actual problem is whatever it is you are trying to do. You've
never told us that, other than a meaningless "analysis". If you had
told us the actual problem, we would then bee ablle

> adv_chg_no_range5 is the best performance
> 5 time loop search is better than regexp , but not stable..
> (update code post pre , please refer)
>
> could you point me some better or alterntive way to achieve speed
> request

Not unless you explain why you need to recreate the list, and what
outer reason you need to iterate the list each time to recreate it
instead of re-creating one copy then searching that plural times.

And, if you'd ever bother to tell us what you are really trying to do,
there might be a better faster way with a change in how you represent
the data. But you've never given us anything but your vague
statements, so there is no way for us to recognize a superior way of
representing the data that would increase speed (assuming such a way
does exist).

Rich 在 2022年11月5日 星期六凌晨2:30:01 [UTC+13] 的信中寫道：
> rola...@gmail.com <rola...@gmail.com> wrote:
> > Rich ? 2022?11?4? ?????3:09:19 [UTC+13] ??????
> >> rola...@gmail.com <rola...@gmail.com> wrote:
> >> > Hi all
> >> >
> >> > mass numbers analysis , need improve speed ...
> >> >
> >> Unsurprising here. The first does 5 searches over a static list.
> >>
> >> The second makes 5 calls into a proc, that iterates the entire list via
> >> foreach, returning a new list, and that new list is then searched.
> >>
> >> Iterating the entire list, in Tcl, to generate a new list is where most
> >> of this time difference is being consumed.
> >> > #### regexp
> >> > 1341 microseconds per iteration
> >> > ###combine ##
> >> > 2525 microseconds per iteration
> >> Also unsurprising, searches using the regex engine will be slower than
> >> searches using simple comparisons, because the regex engine does far
> >> more than simple comparisons.
> >>
> >> The time difference between the static list and the newly generated
> >> list via a proc comments above also apply here.
> >> > could someone give me direction to overcome speed issue
> >> If your issue is lsearch speed, then:
> >>
> >> 1) only search a static list (i.e., don't recreate the list first
> >> before searching it)
> >>
> >> 2) if your desired results can also be obtained from searching a sorted
> >> list, then first sort the list (sort only once, then search plural
> >> times). Using the -sorted option to lsearch causes lsearch to
> >> perform a binary search of the list, which will be faster than
> >> without -sorted, which causes lsearch to perform a linear search
> >> (start at first element, look at each in sequence until found).
> >>
> >> But you've failed to describe your actual problem. You've shown a
> >> solution that does not work for you speed wise, but not described to us
> >> what you are trying to achieve by this solution you've given. It is
> >> quite possible there is some alternative way, without using lsearch, to
> >> achieve your desired result, but we can't read your mind over Usenet to
> >> know what your actual problem is to even be able to consider some
> >> alternate.
> >
> >
> > Hi Rich
> >
> > 1. static list indeed faster , but need recreate lst for each
> > analysis , how can improve this ... release memory ?
> Please explain to us why you need to recreate the list for each
> analysis. We see no reason yet why this is necessary (and don't simply
> say "because I need to do so" -- that will not be an acceptable
> answer).
>
> You can't 'release memory' manually with Tcl, that is all automatic.
> > 2 this actual problem is speed issue , all analysis result can fit
> > request except the consume time , customer want cut half ...
> No, the actual problem is whatever it is you are trying to do. You've
> never told us that, other than a meaningless "analysis". If you had
> told us the actual problem, we would then bee ablle
> > adv_chg_no_range5 is the best performance
> > 5 time loop search is better than regexp , but not stable..
> > (update code post pre , please refer)
> >
> > could you point me some better or alterntive way to achieve speed
> > request
> Not unless you explain why you need to recreate the list, and what
> outer reason you need to iterate the list each time to recreate it
> instead of re-creating one copy then searching that plural times.
>
> And, if you'd ever bother to tell us what you are really trying to do,
> there might be a better faster way with a change in how you represent
> the data. But you've never given us anything but your vague
> statements, so there is no way for us to recognize a superior way of
> representing the data that would increase speed (assuming such a way
> does exist).

Hi Rich

thanks for your advice .

("Given a list of integers, find all matching integers fast." with position ) is what I look for.
this main program is customize lottary prediction and analysis system ,
customer made some rule to recreate list number , and find the best position hit the target , also reference history record up to "N" previous hit.

that is what i need recreate it each time.... original program for N phase 3125x3125x39x1 time comparison upto 7hr..
with some shortcut and optimize code already down to 396 sec. but customer not satisify ---> need 60 sec with single thread... his ideal cal qty 3125x3125x39x600 for one time...

previousily he tell me other C++ program can achieve (but different rule, my code more rules)

already separate data create with mass file , only source file and change each number +1 for 39 sift range...

do it's limitation of tcl , or some way can faster calculate .

BR
Rolance

rola...@gmail.com <rolance1@gmail.com> wrote:
> Hi Rich
>
> thanks for your advice .
>
> ("Given a list of integers, find all matching integers fast." with
> position ) is what I look for. this main program is customize
> lottary prediction and analysis system , customer made some rule to
> recreate list number , and find the best position hit the target ,
> also reference history record up to "N" previous hit.
>
> that is what i need recreate it each time.... original program for N
> phase 3125x3125x39x1 time comparison upto 7hr.. with some
> shortcut and optimize code already down to 396 sec. but customer not
> satisify ---> need 60 sec with single thread... his ideal cal qty
> 3125x3125x39x600 for one time...

Do you mean it searches for the positions in 228 515 625 000 (228
billion) total numbers?

For a list that takes 396 sec, what is the 'llength' result of running
llength on that list?

> previousily he tell me other C++ program can achieve (but different
> rule, my code more rules)

C++ is also a compiled program. That very likely gives it a
performance edge from the start.

> already separate data create with mass file , only source file and
> change each number +1 for 39 sift range...
>
> do it's limitation of tcl , or some way can faster calculate .

So you have a list of length X (what is a typical X value?) of numbers
from 1 to 39, and you want to find all occurrences of a given number
and return the positions of all those numbers in that list?

I.e, consider this code:

$ rlwrap tclsh
% package require sqlite3
3.35.5
% sqlite3 db :memory:
% db eval {create table list (id integer primary key, num integer);}

This below inserts five million numbers that are randomly chosen
between 1 and 39:

% for {set i 0} {$i < 5000000} {incr i} { db eval "insert into list (num) values ([expr {int(rand()*39+1)}]);"}

Create an index on the "num" column:

% db eval {create index idx on list(num);}

Do some "searching", the 'result' of these queries will be the
"position" of each value being requested:

% time {db eval {select id from list where num = 20;}}
22530 microseconds per iteration
% time {db eval {select id from list where num = 20;}}
22827 microseconds per iteration
% time {db eval {select id from list where num = 27;}}
22856 microseconds per iteration
% time {db eval {select id from list where num = 5;}}
22711 microseconds per iteration

Pretty consistent, about 22.5ms to find the "positions" of all the
numbers equal to 20 (or 27 or 5) in the "list" of five million
possibilities. Memory consumption, as reported by top, is 332Meg.

This is what I meant when I asked you to tell us the problem you were
trying to solve, instead of giving us your "solution", keeping the
actual problem secret, and asking us to help fix the solution. You do
yourself no favors that way, and prevent us from being able to suggest
superior alternatives.

In the code above I am finding the "positions" of numbers in an
"ordered list" of five million entries in about 22.5ms above. Now,
granted, I am not doing anything with those positions, but the
alternate "lsearch" above is extremely fast.

Rich 在 2022年11月5日 星期六上午10:30:18 [UTC+13] 的信中寫道：
> rola...@gmail.com <rola...@gmail.com> wrote:
> > Hi Rich
> >
> > thanks for your advice .
> >
> > ("Given a list of integers, find all matching integers fast." with
> > position ) is what I look for. this main program is customize
> > lottary prediction and analysis system , customer made some rule to
> > recreate list number , and find the best position hit the target ,
> > also reference history record up to "N" previous hit.
> >
> > that is what i need recreate it each time.... original program for N
> > phase 3125x3125x39x1 time comparison upto 7hr.. with some
> > shortcut and optimize code already down to 396 sec. but customer not
> > satisify ---> need 60 sec with single thread... his ideal cal qty
> > 3125x3125x39x600 for one time...
> Do you mean it searches for the positions in 228 515 625 000 (228
> billion) total numbers?
>
> For a list that takes 396 sec, what is the 'llength' result of running
> llength on that list?
> > previousily he tell me other C++ program can achieve (but different
> > rule, my code more rules)
> C++ is also a compiled program. That very likely gives it a
> performance edge from the start.
> > already separate data create with mass file , only source file and
> > change each number +1 for 39 sift range...
> >
> > do it's limitation of tcl , or some way can faster calculate .
> So you have a list of length X (what is a typical X value?) of numbers
> from 1 to 39, and you want to find all occurrences of a given number
> and return the positions of all those numbers in that list?
>
> I.e, consider this code:
>
> $ rlwrap tclsh
> % package require sqlite3
> 3.35.5
> % sqlite3 db :memory:
> % db eval {create table list (id integer primary key, num integer);}
>
> This below inserts five million numbers that are randomly chosen
> between 1 and 39:
>
> % for {set i 0} {$i < 5000000} {incr i} { db eval "insert into list (num) values ([expr {int(rand()*39+1)}]);"}
>
> Create an index on the "num" column:
>
> % db eval {create index idx on list(num);}
>
> Do some "searching", the 'result' of these queries will be the
> "position" of each value being requested:
>
> % time {db eval {select id from list where num = 20;}}
> 22530 microseconds per iteration
> % time {db eval {select id from list where num = 20;}}
> 22827 microseconds per iteration
> % time {db eval {select id from list where num = 27;}}
> 22856 microseconds per iteration
> % time {db eval {select id from list where num = 5;}}
> 22711 microseconds per iteration
>
> Pretty consistent, about 22.5ms to find the "positions" of all the
> numbers equal to 20 (or 27 or 5) in the "list" of five million
> possibilities. Memory consumption, as reported by top, is 332Meg.
>
> This is what I meant when I asked you to tell us the problem you were
> trying to solve, instead of giving us your "solution", keeping the
> actual problem secret, and asking us to help fix the solution. You do
> yourself no favors that way, and prevent us from being able to suggest
> superior alternatives.
>
> In the code above I am finding the "positions" of numbers in an
> "ordered list" of five million entries in about 22.5ms above. Now,
> granted, I am not doing anything with those positions, but the
> alternate "lsearch" above is extremely fast.

hi Rich

great thanks for your advice

will change data structure to sqlite get faster speed .

BR
Rolance

rola...@gmail.com 在 2022年11月5日 星期六上午11:31:28 [UTC+13] 的信中寫道：
> Rich 在 2022年11月5日 星期六上午10:30:18 [UTC+13] 的信中寫道：
> > rola...@gmail.com <rola...@gmail.com> wrote:
> > > Hi Rich
> > >
> > > thanks for your advice .
> > >
> > > ("Given a list of integers, find all matching integers fast." with
> > > position ) is what I look for. this main program is customize
> > > lottary prediction and analysis system , customer made some rule to
> > > recreate list number , and find the best position hit the target ,
> > > also reference history record up to "N" previous hit.
> > >
> > > that is what i need recreate it each time.... original program for N
> > > phase 3125x3125x39x1 time comparison upto 7hr.. with some
> > > shortcut and optimize code already down to 396 sec. but customer not
> > > satisify ---> need 60 sec with single thread... his ideal cal qty
> > > 3125x3125x39x600 for one time...
> > Do you mean it searches for the positions in 228 515 625 000 (228
> > billion) total numbers?
> >
> > For a list that takes 396 sec, what is the 'llength' result of running
> > llength on that list?
> > > previousily he tell me other C++ program can achieve (but different
> > > rule, my code more rules)
> > C++ is also a compiled program. That very likely gives it a
> > performance edge from the start.
> > > already separate data create with mass file , only source file and
> > > change each number +1 for 39 sift range...
> > >
> > > do it's limitation of tcl , or some way can faster calculate .
> > So you have a list of length X (what is a typical X value?) of numbers
> > from 1 to 39, and you want to find all occurrences of a given number
> > and return the positions of all those numbers in that list?
> >
> > I.e, consider this code:
> >
> > $ rlwrap tclsh
> > % package require sqlite3
> > 3.35.5
> > % sqlite3 db :memory:
> > % db eval {create table list (id integer primary key, num integer);}
> >
> > This below inserts five million numbers that are randomly chosen
> > between 1 and 39:
> >
> > % for {set i 0} {$i < 5000000} {incr i} { db eval "insert into list (num) values ([expr {int(rand()*39+1)}]);"}
> >
> > Create an index on the "num" column:
> >
> > % db eval {create index idx on list(num);}
> >
> > Do some "searching", the 'result' of these queries will be the
> > "position" of each value being requested:
> >
> > % time {db eval {select id from list where num = 20;}}
> > 22530 microseconds per iteration
> > % time {db eval {select id from list where num = 20;}}
> > 22827 microseconds per iteration
> > % time {db eval {select id from list where num = 27;}}
> > 22856 microseconds per iteration
> > % time {db eval {select id from list where num = 5;}}
> > 22711 microseconds per iteration
> >
> > Pretty consistent, about 22.5ms to find the "positions" of all the
> > numbers equal to 20 (or 27 or 5) in the "list" of five million
> > possibilities. Memory consumption, as reported by top, is 332Meg.
> >
> > This is what I meant when I asked you to tell us the problem you were
> > trying to solve, instead of giving us your "solution", keeping the
> > actual problem secret, and asking us to help fix the solution. You do
> > yourself no favors that way, and prevent us from being able to suggest
> > superior alternatives.
> >
> > In the code above I am finding the "positions" of numbers in an
> > "ordered list" of five million entries in about 22.5ms above. Now,
> > granted, I am not doing anything with those positions, but the
> > alternate "lsearch" above is extremely fast.
> hi Rich
>
> great thanks for your advice
>
> will change data structure to sqlite get faster speed .
>
>
> BR
> Rolance

hi Rich

below code with my test result
could you point me what wrong same code with different output

package require sqlite3

console show

set lst [lmap v [lrepeat 3125 1] {expr {int($v * [::tcl::mathfunc::rand]*39)}} ]

proc adv_chg_no_range5 {id lst} {
set new_lst [lindex $lst 0]
incr id -1
lappend new_lst {*}[lmap v [lrange $lst 1 end] {
expr {(($v+$id)%-39)+39}
}]
return $new_lst
}

puts "#### db ####"

sqlite3 db :memory:

db eval {create table list (id integer primary key, num integer);}

for {set i 0} {$i < 3125} {incr i} { db eval "insert into list (num) values ([expr {int(rand()*39+1)}]);"}

db eval {create index idx on list(num);}

puts [time {db eval {select id from list where num = 20;}}]
puts [time {db eval {select id from list where num = 1;}}]
puts [time {db eval {select id from list where num = 36;}}]
puts [time {db eval {select id from list where num = 6;}}]
puts [time {db eval {select id from list where num = 23;}}]

db close

puts "#### db1 ####"

sqlite3 db1 :memory:
db1 eval {create table list (id integer primary key, num integer);}

#### use $lst performance not ideal ---> mark use same data source
#foreach x [adv_chg_no_range5 1 $lst] {
# db1 eval "insert into list (num) values ($x);"
#}

for {set i 0} {$i < 3125} {incr i} { db1 eval "insert into list (num) values ([expr {int(rand()*39+1)}]);"}

puts [time {db1 eval {select id from list where num = 20;}}]
puts [time {db1 eval {select id from list where num = 1;}}]
puts [time {db1 eval {select id from list where num = 36;}}]
puts [time {db1 eval {select id from list where num = 6;}}]
puts [time {db1 eval {select id from list where num = 23;}}]

db1 close

####output ###

#### db ####
36 microseconds per iteration
86 microseconds per iteration
89 microseconds per iteration
92 microseconds per iteration
93 microseconds per iteration
#### db1 #### <<<<<< over 3 times
195 microseconds per iteration
240 microseconds per iteration
219 microseconds per iteration
221 microseconds per iteration
234 microseconds per iteration

BR
Rolance

rola...@gmail.com <rolance1@gmail.com> wrote:
> rola...@gmail.com ? 2022?11?5? ?????11:31:28 [UTC+13] ??????
>> Rich ? 2022?11?5? ?????10:30:18 [UTC+13] ??????
>> > I.e, consider this code:
>> >
>> > $ rlwrap tclsh
>> > % package require sqlite3
>> > 3.35.5
>> > % sqlite3 db :memory:
>> > % db eval {create table list (id integer primary key, num integer);}
>> >
>> > This below inserts five million numbers that are randomly chosen
>> > between 1 and 39:
>> >
>> > % for {set i 0} {$i < 5000000} {incr i} { db eval "insert into list (num) values ([expr {int(rand()*39+1)}]);"}
>> >
>> > Create an index on the "num" column:
>> >
>> > % db eval {create index idx on list(num);}
>> >
>> > Do some "searching", the 'result' of these queries will be the
>> > "position" of each value being requested:
>> >
>> > % time {db eval {select id from list where num = 20;}}
>> > 22530 microseconds per iteration
>> > % time {db eval {select id from list where num = 20;}}
>> > 22827 microseconds per iteration
>> > % time {db eval {select id from list where num = 27;}}
>> > 22856 microseconds per iteration
>> > % time {db eval {select id from list where num = 5;}}
>> > 22711 microseconds per iteration
>> >
>> > Pretty consistent, about 22.5ms to find the "positions" of all the
>> > numbers equal to 20 (or 27 or 5) in the "list" of five million
>> > possibilities. Memory consumption, as reported by top, is 332Meg.
>
> hi Rich
>
> below code with my test result
> could you point me what wrong same code with different output

db1 and db2 are not the same code.

Your db2 code omits creating an index on the num column.

Without the index sqlite has to scan all the rows in the table.

With the index it can refer to the index and (effectively) directly
pull out the matching rows.

That is the reason for the time difference. The index consumes some
up-front time to build, in order to significantly accelerate lookups
later.

Rich 在 2022年11月5日 星期六下午3:06:51 [UTC+13] 的信中寫道：
> rola...@gmail.com <rola...@gmail.com> wrote:
> > rola...@gmail.com ? 2022?11?5? ?????11:31:28 [UTC+13] ??????
> >> Rich ? 2022?11?5? ?????10:30:18 [UTC+13] ??????
> >> > I.e, consider this code:
> >> >
> >> > $ rlwrap tclsh
> >> > % package require sqlite3
> >> > 3.35.5
> >> > % sqlite3 db :memory:
> >> > % db eval {create table list (id integer primary key, num integer);}
> >> >
> >> > This below inserts five million numbers that are randomly chosen
> >> > between 1 and 39:
> >> >
> >> > % for {set i 0} {$i < 5000000} {incr i} { db eval "insert into list (num) values ([expr {int(rand()*39+1)}]);"}
> >> >
> >> > Create an index on the "num" column:
> >> >
> >> > % db eval {create index idx on list(num);}
> >> >
> >> > Do some "searching", the 'result' of these queries will be the
> >> > "position" of each value being requested:
> >> >
> >> > % time {db eval {select id from list where num = 20;}}
> >> > 22530 microseconds per iteration
> >> > % time {db eval {select id from list where num = 20;}}
> >> > 22827 microseconds per iteration
> >> > % time {db eval {select id from list where num = 27;}}
> >> > 22856 microseconds per iteration
> >> > % time {db eval {select id from list where num = 5;}}
> >> > 22711 microseconds per iteration
> >> >
> >> > Pretty consistent, about 22.5ms to find the "positions" of all the
> >> > numbers equal to 20 (or 27 or 5) in the "list" of five million
> >> > possibilities. Memory consumption, as reported by top, is 332Meg.
> >
> > hi Rich
> >
> > below code with my test result
> > could you point me what wrong same code with different output
> db1 and db2 are not the same code.
>
> Your db2 code omits creating an index on the num column.
>
> Without the index sqlite has to scan all the rows in the table.
>
> With the index it can refer to the index and (effectively) directly
> pull out the matching rows.
>
> That is the reason for the time difference. The index consumes some
> up-front time to build, in order to significantly accelerate lookups
> later.

hi Rich

thank for the detail explanation ,
single test program have great performance , but in real multi-program implement speed not better than previous Lsearch code .....
still debug what factor will affect speed ...

thanks for great help , if you have some hint about program interactive affect , please point me

BR
Rolance

rola...@gmail.com <rolance1@gmail.com> wrote:
> Rich ? 2022?11?5? ?????3:06:51 [UTC+13] ??????
>> rola...@gmail.com <rola...@gmail.com> wrote:
>> Your db2 code omits creating an index on the num column.
>>
>> Without the index sqlite has to scan all the rows in the table.
>>
>> With the index it can refer to the index and (effectively) directly
>> pull out the matching rows.
>>
>> That is the reason for the time difference. The index consumes some
>> up-front time to build, in order to significantly accelerate lookups
>> later.
>
> hi Rich
>
> thank for the detail explanation ,
> single test program have great performance , but in real
> multi-program implement speed not better than previous Lsearch code
> ..... still debug what factor will affect speed ...

I also asked how long the list was in the real world program, and as
you have done so many times in this thread, you ignored that question
entirely. If you continue ignoring direct questions that would allow
us to help you I will plonk you.

In the real program, how long is the list that is being searched?

> thanks for great help , if you have some hint about program
> interactive affect , please point me

We can't help if you do not give us the information we need to be able
to effectively help.