Rich 在 2022年11月6日 星期日凌晨2:11:17 [UTC+13] 的信中寫道：
> rola...@gmail.com <rola...@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.

hi Rich

thanks for your advice
only analysis partical list :3125 range 1
code and result below

###############
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
}

proc mark_lott_loc_row_no_sort1 {lott lst} {
set res ""
foreach cp $lott {
foreach x [lsearch -all $lst "$cp"] {
lappend res $x
}
}
return $res
}

proc mark_lott_loc_row_no_sort3_p {lott lst} {
sqlite3 db1 :memory:
db1 eval {create table list (id integer primary key, num integer);}
foreach x [lrange $lst 1 end] {
db1 eval "insert into list (num) values ($x);"
}
db1 eval {create index idx on list(num);}

set res ""
foreach cp $lott {
lappend res {*}[db1 eval {select id from list where num = $cp;}]
}

db1 eval { delete from list; }
db1 close

return $res
}

puts "#### lsearch 3125 range 1 ####"
puts [time {mark_lott_loc_row_no_sort1 {12 16 3 8 36} [adv_chg_no_range5 1 $lst]} 10]

puts "#### sqlite3 3125 range 1####"
puts [time {mark_lott_loc_row_no_sort3_p {12 16 3 8 36} [adv_chg_no_range5 1 $lst]} 10]

##### output #####

#### lsearch 3125 range 1 ####
720.2 microseconds per iteration
#### sqlite3 3125 range 1####
17818.6 microseconds per iteration

BR
Rolance

rola...@gmail.com <rolance1@gmail.com> wrote:
> Rich ? 2022?11?6? ?????2:11:17 [UTC+13] ??????
>> rola...@gmail.com <rola...@gmail.com> wrote:
>> > Rich ? 2022?11?5? ?????3:06:51 [UTC+13] ??????
>> 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.
>
> hi Rich
>
> thanks for your advice
> only analysis partical list :3125 range 1
> code and result below

Contining to evade the question. This is your last chance.

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

> ###############
> 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
> }
>
> proc mark_lott_loc_row_no_sort1 {lott lst} {
> set res ""
> foreach cp $lott {
> foreach x [lsearch -all $lst "$cp"] {
> lappend res $x
> }
> }
> return $res
> }
>
> proc mark_lott_loc_row_no_sort3_p {lott lst} {
> sqlite3 db1 :memory:
> db1 eval {create table list (id integer primary key, num integer);}
> foreach x [lrange $lst 1 end] {
> db1 eval "insert into list (num) values ($x);"
> }
> db1 eval {create index idx on list(num);}
>
> set res ""
> foreach cp $lott {
> lappend res {*}[db1 eval {select id from list where num = $cp;}]
> }
>
> db1 eval { delete from list; }
> db1 close
>
> return $res
> }
>
> puts "#### lsearch 3125 range 1 ####"
> puts [time {mark_lott_loc_row_no_sort1 {12 16 3 8 36} [adv_chg_no_range5 1 $lst]} 10]
>
> puts "#### sqlite3 3125 range 1####"
> puts [time {mark_lott_loc_row_no_sort3_p {12 16 3 8 36} [adv_chg_no_range5 1 $lst]} 10]
>
> ##### output #####
>
> #### lsearch 3125 range 1 ####
> 720.2 microseconds per iteration
> #### sqlite3 3125 range 1####
> 17818.6 microseconds per iteration

I made a small code change to your example, and I get the following
timing on my machine after the change:

#### lsearch 3125 range 1 ####
1180.9 microseconds per iteration
#### sqlite3 3125 range 1####
638.2 microseconds per iteration

However, because you are being so evasive, and failing to answer
direect questions with straightforward answers, I am not going to show
you the change I made.

I will, however, give you a hint. Look at what is *very different*
between the data searched in your mark_lott_loc_row_no_sort1 proc vs.
the data searched in the mark_lott_loc_row_no_sort3_p.

What does one of those proc's do that the other one does not.

When you see what one of them does, that the other does not, then
consider changing the code so the one that is presently doing the
different work no longer is performing that different work. When you
make the change, you'll get simlar timings to what I just got.

However, fail to be straighforward in your next answer, and you will be
plonked ( https://en.everybodywiki.com/Plonk_(Usenet) ). This is your
last and final warning.

Rich 在 2022年11月6日 星期日下午2:41:35 [UTC+13] 的信中寫道：
> rola...@gmail.com <rola...@gmail.com> wrote:
> > Rich ? 2022?11?6? ?????2:11:17 [UTC+13] ??????
> >> rola...@gmail.com <rola...@gmail.com> wrote:
> >> > Rich ? 2022?11?5? ?????3:06:51 [UTC+13] ??????
> >> 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.
> >
> > hi Rich
> >
> > thanks for your advice
> > only analysis partical list :3125 range 1
> > code and result below
> Contining to evade the question. This is your last chance.
> In the real program, how long is the list that is being searched?
> > ###############
> > 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
> > }
> >
> > proc mark_lott_loc_row_no_sort1 {lott lst} {
> > set res ""
> > foreach cp $lott {
> > foreach x [lsearch -all $lst "$cp"] {
> > lappend res $x
> > }
> > }
> > return $res
> > }
> >
> > proc mark_lott_loc_row_no_sort3_p {lott lst} {
> > sqlite3 db1 :memory:
> > db1 eval {create table list (id integer primary key, num integer);}
> > foreach x [lrange $lst 1 end] {
> > db1 eval "insert into list (num) values ($x);"
> > }
> > db1 eval {create index idx on list(num);}
> >
> > set res ""
> > foreach cp $lott {
> > lappend res {*}[db1 eval {select id from list where num = $cp;}]
> > }
> >
> > db1 eval { delete from list; }
> > db1 close
> >
> > return $res
> > }
> >
> > puts "#### lsearch 3125 range 1 ####"
> > puts [time {mark_lott_loc_row_no_sort1 {12 16 3 8 36} [adv_chg_no_range5 1 $lst]} 10]
> >
> > puts "#### sqlite3 3125 range 1####"
> > puts [time {mark_lott_loc_row_no_sort3_p {12 16 3 8 36} [adv_chg_no_range5 1 $lst]} 10]
> >
> > ##### output #####
> >
> > #### lsearch 3125 range 1 ####
> > 720.2 microseconds per iteration
> > #### sqlite3 3125 range 1####
> > 17818.6 microseconds per iteration
> I made a small code change to your example, and I get the following
> timing on my machine after the change:
> #### lsearch 3125 range 1 ####
> 1180.9 microseconds per iteration
> #### sqlite3 3125 range 1####
> 638.2 microseconds per iteration
>
> However, because you are being so evasive, and failing to answer
> direect questions with straightforward answers, I am not going to show
> you the change I made.
>
> I will, however, give you a hint. Look at what is *very different*
> between the data searched in your mark_lott_loc_row_no_sort1 proc vs.
> the data searched in the mark_lott_loc_row_no_sort3_p.
>
> What does one of those proc's do that the other one does not.
>
> When you see what one of them does, that the other does not, then
> consider changing the code so the one that is presently doing the
> different work no longer is performing that different work. When you
> make the change, you'll get simlar timings to what I just got.
>
> However, fail to be straighforward in your next answer, and you will be
> plonked ( https://en.everybodywiki.com/Plonk_(Usenet) ). This is your
> last and final warning.

Hi Rich

let me explain the detail
one section data list in the array 3125x3125x39x1 the total consume time is 396 sec.
(with reverse pyramid optimization only calaulate hit position , if not the total consume upto 7hr)
customer want 3125x3125x39x 600 time not over 12hr ... (the multi-tread the the last option ...)
so the target goal is 3125x3125x39x1 --> within 60 sec (single thread)

the demo proc is "the real program" for reverse pyramid first layer (base) , calculate each time with fix rule change no ....

beacuse customer use different machine with different OS try to get best perforamce , buy latest machine is the last option (but according to experience new noly up 30%~ 40%)

> > #### lsearch 3125 range 1 ####
> > 720.2 microseconds per iteration

> #### sqlite3 3125 range 1####
> 638.2 microseconds per iteration

the new core speed up around 12%~15% , I am not sure after multi-time use the memory occupy if stable or go raise.... some time get alloc error ...

the non-static list affect search time so big ....

or you have other way to show me get faster speed in combine program (var pass , let speed low or memory occupy issue)

hope you can show you have achieved , will implement in real main program

thank in advance

BR
Rolance

On Sunday, November 6, 2022 at 5:39:28 AM UTC+1, rolance wrote:
> Rich 在 2022年11月6日 星期日下午2:41:35 [UTC+13] 的信中寫道：
> > rolance wrote:
> > > #### lsearch 3125 range 1 ####
> > > 720.2 microseconds per iteration
> > > #### sqlite3 3125 range 1####
> > > 17818.6 microseconds per iteration
> > I made a small code change to your example, and I get the following
> > timing on my machine after the change:
> > #### lsearch 3125 range 1 ####
> > 1180.9 microseconds per iteration
> > #### sqlite3 3125 range 1####
> > 638.2 microseconds per iteration
> >
> > However, because you are being so evasive, and failing to answer
> > direect questions with straightforward answers, I am not going to show
> > you the change I made.

Rich, congrats for your patience and that cool way to draw attention to the message :-)

> > However, fail to be straighforward in your next answer, and you will be
> > plonked ( https://en.everybodywiki.com/Plonk_(Usenet) ). This is your
> > last and final warning.

Rolance, I cannot/will not plonk user, but I have been ignoring messages without progress - and I will continue to do so.
But I want to encourage you to *rethink/rephrase* your questions and post them again when you do not see an answer within a few days - writing down the actual problem helped me a lot quite some times, even before ever sending it.
In the end, you can see on clt - even in this thread - that the community is willing to help, even with questions that are not strictly related to Tcl.. (We are just not doing your job entirely.)

Then again, you must start accepting that a full search in an arbitrary list takes O(N) time and O(log N) in a sorted list. Here are a few pointers how to improve the overall timing:

* At the time of lsearch, does the list contain integers already? Note that Tcl has object types under the hood, i.e. EIAS is correct, but Tcl may improve performance where possible.
* Are you unnecessarily keeping references to data? Tcl copies on write, i.e. "freeing" resources might help not only memory but also speed.
* Are you performing identical operations repeatedly/unnecessarily? This does not only refer to the extra work in the loop (that Rich has pointed out), but also think at large scale, i.e. can the problem statement be rewritten to allow more efficient algorithms? (Note that brute force is not the smartest approach when time matters.)
* What data must be calculated live? What parts can be pre-calculated?

On your way from being a coder to becoming a developer, you might want to re-watch the video that I posted earlier - and work out techniques to improve the implementation that were mentioned.
Then compare it to your current problem.

Or think of a chess computer: it cannot calculate all possible moves to any depth. Efficient algorithms must e.g. have thresholds to cut of search branches, reuse sub-trees, use an efficient representation, order possible moves, ... Modern chess computers also use databases for openings and end games, i.e. they do not recalculate everything, but they know many winning/losing positions in advance - and they have efficient ways to look these up.

What next?
If any of my statements was unclear, ask a precise, direct question.
Reconsider your problem statement/requirements and elaborate the overall solution - not just one particular step of one possible approach.
If you get stuck while working things out, give the context and ask a precise question.

heinrichmartin 在 2022年11月7日 星期一晚上10:02:45 [UTC+13] 的信中寫道：
> On Sunday, November 6, 2022 at 5:39:28 AM UTC+1, rolance wrote:
> > Rich 在 2022年11月6日 星期日下午2:41:35 [UTC+13] 的信中寫道：
> > > rolance wrote:
> > > > #### lsearch 3125 range 1 ####
> > > > 720.2 microseconds per iteration
> > > > #### sqlite3 3125 range 1####
> > > > 17818.6 microseconds per iteration
> > > I made a small code change to your example, and I get the following
> > > timing on my machine after the change:
> > > #### lsearch 3125 range 1 ####
> > > 1180.9 microseconds per iteration
> > > #### sqlite3 3125 range 1####
> > > 638.2 microseconds per iteration
> > >
> > > However, because you are being so evasive, and failing to answer
> > > direect questions with straightforward answers, I am not going to show
> > > you the change I made.
> Rich, congrats for your patience and that cool way to draw attention to the message :-)
> > > However, fail to be straighforward in your next answer, and you will be
> > > plonked ( https://en.everybodywiki.com/Plonk_(Usenet) ). This is your
> > > last and final warning.
> Rolance, I cannot/will not plonk user, but I have been ignoring messages without progress - and I will continue to do so.
> But I want to encourage you to *rethink/rephrase* your questions and post them again when you do not see an answer within a few days - writing down the actual problem helped me a lot quite some times, even before ever sending it.
> In the end, you can see on clt - even in this thread - that the community is willing to help, even with questions that are not strictly related to Tcl. (We are just not doing your job entirely.)
>
> Then again, you must start accepting that a full search in an arbitrary list takes O(N) time and O(log N) in a sorted list. Here are a few pointers how to improve the overall timing:
>
> * At the time of lsearch, does the list contain integers already? Note that Tcl has object types under the hood, i.e. EIAS is correct, but Tcl may improve performance where possible.
> * Are you unnecessarily keeping references to data? Tcl copies on write, i.e. "freeing" resources might help not only memory but also speed.
> * Are you performing identical operations repeatedly/unnecessarily? This does not only refer to the extra work in the loop (that Rich has pointed out), but also think at large scale, i.e. can the problem statement be rewritten to allow more efficient algorithms? (Note that brute force is not the smartest approach when time matters.)
> * What data must be calculated live? What parts can be pre-calculated?
>
> On your way from being a coder to becoming a developer, you might want to re-watch the video that I posted earlier - and work out techniques to improve the implementation that were mentioned.
> Then compare it to your current problem.
>
> Or think of a chess computer: it cannot calculate all possible moves to any depth. Efficient algorithms must e.g. have thresholds to cut of search branches, reuse sub-trees, use an efficient representation, order possible moves, ... Modern chess computers also use databases for openings and end games, i.e. they do not recalculate everything, but they know many winning/losing positions in advance - and they have efficient ways to look these up.
>
> What next?
> If any of my statements was unclear, ask a precise, direct question.
> Reconsider your problem statement/requirements and elaborate the overall solution - not just one particular step of one possible approach.
> If you get stuck while working things out, give the context and ask a precise question.

Hi heinrichmartin

thanks for your great detail explainion
your previous suggestion already improve program speed 10%~15%

> Then again, you must start accepting that a full search in an arbitrary list takes O(N) time and O(log N) in a sorted list. Here are a few pointers how to improve the overall timing:
>
> * At the time of lsearch, does the list contain integers already? Note that Tcl has object types under the hood, i.e. EIAS is correct, but Tcl may improve performance where possible.
> * Are you unnecessarily keeping references to data? Tcl copies on write, i.e. "freeing" resources might help not only memory but also speed.
> * Are you performing identical operations repeatedly/unnecessarily? This does not only refer to the extra work in the loop (that Rich has pointed out), but also think at large scale, i.e. can the problem statement be rewritten to allow more efficient algorithms? (Note that brute force is not the smartest approach when time matters.)
> * What data must be calculated live? What parts can be pre-calculated?

1.yes , the list with tile-id in first char , and tail with 3125 (customize rule generate integers) and EIAS mean ?

2.all use unset to clear var when each run get target position , yes increaseing memory will low speed and will get alloc error ...
3. already simpify only calculate target data , is why original time upto 7hr --> optimizate 396 sec
below two program is the key factor for the main program , if simplify adv_chg_no_range5 (by pass or no change lst ) , I can get "14 sec" hit customer target one thread
bast get more and more info within 12hr ( lottery 24 hr open one time ) and the calculate base 3125x3125x39x600x13(ref 13phase)

since I am not family with sqlite3 , need sometime to research as Rich show part .. up performance 15~20%

lsearch command is best solution what i can get now. didn't know if sqlite3 will low speed after multi-time excute ....

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 mark_lott_loc_row_no_sort1 {lott lst} {
set res ""
foreach cp $lott {
foreach x [lsearch -all $lst "$cp"] {
lappend res $x
} }
return $res
}

puts [time {mark_lott_loc_row_no_sort1 {12 16 3 8 36} [adv_chg_no_range5 1 $lst]} 10]
> > 720.2 microseconds per iteration

4. base row data already separate calculated and each phase raw data 26mb x 13 not all source in memory only targeted
generate target position need calculate alive for customer reference , up 2 program is the key for this part.

> On your way from being a coder to becoming a developer, you might want to re-watch the video that I posted earlier - and work out techniques to improve the implementation that were mentioned.
> Then compare it to your current problem.
>
> Or think of a chess computer: it cannot calculate all possible moves to any depth. Efficient algorithms must e.g. have thresholds to cut of search branches, reuse sub-trees, use an efficient representation, order possible moves, ... Modern chess computers also use databases for openings and end games, i.e. they do not recalculate everything, but they know many winning/losing positions in advance - and they have efficient ways to look these up.
> What next?
> If any of my statements was unclear, ask a precise, direct question.
> Reconsider your problem statement/requirements and elaborate the overall solution - not just one particular step of one possible approach.
> If you get stuck while working things out, give the context and ask a precise question.

i know search in an arbitrary list takes times , alrady try several algorithm to test it
in single run it may better , but in combine real program the speed not ideal...
so it may the system code area affect and I didn't how to handle and look for your help ..

this two program combine run time is possible below 120 microseconds per iteration ? with 3125 intergers
or some algorithm can achieve it ?

thanks in advance

BR
Rolance

On Monday, November 7, 2022 at 12:41:08 PM UTC+1, rolance wrote:
> heinrichmartin 在 2022年11月7日 星期一晚上10:02:45 [UTC+13] 的信中寫道：
> > Then again, you must start accepting that a full search in an arbitrary list takes O(N) time and O(log N) in a sorted list. Here are a few pointers how to improve the overall timing:
> >
> > * At the time of lsearch, does the list contain integers already? Note that Tcl has object types under the hood, i.e. EIAS is correct, but Tcl may improve performance where possible.
> > * Are you unnecessarily keeping references to data? Tcl copies on write, i.e. "freeing" resources might help not only memory but also speed.
> > * Are you performing identical operations repeatedly/unnecessarily? This does not only refer to the extra work in the loop (that Rich has pointed out), but also think at large scale, i.e. can the problem statement be rewritten to allow more efficient algorithms? (Note that brute force is not the smartest approach when time matters.)
> > * What data must be calculated live? What parts can be pre-calculated?
> 1.yes , the list with tile-id in first char , and tail with 3125 (customize rule generate integers) and EIAS mean ?

In my reader, it looks like some text is missing from the middle of this line; I am going to comment on keywords.

If your list size was 3126, then you would most likely not have an issue, i..e. you are talking about a several (thousands of) iterations - you should look closely what else happens in that loop (explicitly or implicitly!).

Tcl is specified without data types, i.e. everything is a string (EIAS). Every proc may interpret a value in a different way, e.g. as number, as text, as code, ... Internally (on C level), Tcl generates and caches representations. E.g. Tcl will implicitly parse the number for you and it will stick to the number representation when you do calculations only.

https://wiki.tcl-lang.org/page/everything+is+a+string
https://wiki.tcl-lang.org/page/shimmering

> 2.all use unset to clear var when each run get target position , yes increaseing memory will low speed and will get alloc error ...

There are hidden catches, but also not-so-obvious options, e.g. https://wiki.tcl-lang.org/page/K#c2a6014c2d129837889d8a8000d05e5c3b44e8f6b46cab777c04df8a927bfad2

> 3. already simpify only calculate target data , is why original time upto 7hr --> optimizate 396 sec
> below two program is the key factor for the main program , if simplify adv_chg_no_range5 (by pass or no change lst ) , I can get "14 sec" hit customer target one thread
> bast get more and more info within 12hr ( lottery 24 hr open one time ) and the calculate base 3125x3125x39x600x13(ref 13phase)
>
> since I am not family with sqlite3 , need sometime to research as Rich show part .. up performance 15~20%
>
> lsearch command is best solution what i can get now. didn't know if sqlite3 will low speed after multi-time excute ....
> 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
> }

That requires three list objects (at least temporarily). Note that this does not mean that all list elements are duplicated in memory, just the list of pointers.

But before digging into Tcl internals, why not consider to no have index 0 in the same list? Then maybe https://wiki.tcl-lang.org/page/VecTcl can help.. Do you see how we are _not_ talking about lsearch?

> proc mark_lott_loc_row_no_sort1 {lott lst} {
> set res ""
> foreach cp $lott {
> foreach x [lsearch -all $lst "$cp"] {
> lappend res $x
> }

lappend res {*}[lsearch -all $lst $cp]

> }
> return $res

How will you distinguish which element of res is the position of which cp? Are you sure you want lists, not sets?

> }
> puts [time {mark_lott_loc_row_no_sort1 {12 16 3 8 36} [adv_chg_no_range5 1 $lst]} 10]
> > > 720.2 microseconds per iteration

To get the timing of (loop over) lsearch, try
set lst2 [adv_chg_no_range5 1 $lst]
puts [time {mark_lott_loc_row_no_sort1 {12 16 3 8 36} $lst2} 10]

> 4. base row data already separate calculated and each phase raw data 26mb x 13 not all source in memory only targeted
> generate target position need calculate alive for customer reference , up 2 program is the key for this part.

I am not going to put effort in trying to understand this. There were several hints that you are working on lottery data.
Maybe you want to share the original problem. Just guessing: the lottery draws 5 from 39, millions of sold tickets, a dozen winning ranks, calculate the winners.

> this two program combine run time is possible below 120 microseconds per iteration ? with 3125 intergers
> or some algorithm can achieve it ?

Not a precise question.

heinrichmartin 在 2022年11月8日 星期二凌晨2:33:13 [UTC+13] 的信中寫道：
> On Monday, November 7, 2022 at 12:41:08 PM UTC+1, rolance wrote:
> > heinrichmartin 在 2022年11月7日 星期一晚上10:02:45 [UTC+13] 的信中寫道：
> > > Then again, you must start accepting that a full search in an arbitrary list takes O(N) time and O(log N) in a sorted list. Here are a few pointers how to improve the overall timing:
> > >
> > > * At the time of lsearch, does the list contain integers already? Note that Tcl has object types under the hood, i.e. EIAS is correct, but Tcl may improve performance where possible.
> > > * Are you unnecessarily keeping references to data? Tcl copies on write, i.e. "freeing" resources might help not only memory but also speed.
> > > * Are you performing identical operations repeatedly/unnecessarily? This does not only refer to the extra work in the loop (that Rich has pointed out), but also think at large scale, i.e. can the problem statement be rewritten to allow more efficient algorithms? (Note that brute force is not the smartest approach when time matters.)
> > > * What data must be calculated live? What parts can be pre-calculated?
> > 1.yes , the list with tile-id in first char , and tail with 3125 (customize rule generate integers) and EIAS mean ?
> In my reader, it looks like some text is missing from the middle of this line; I am going to comment on keywords.
>
> If your list size was 3126, then you would most likely not have an issue, i.e. you are talking about a several (thousands of) iterations - you should look closely what else happens in that loop (explicitly or implicitly!).
>
> Tcl is specified without data types, i.e. everything is a string (EIAS). Every proc may interpret a value in a different way, e.g. as number, as text, as code, ... Internally (on C level), Tcl generates and caches representations. E.g. Tcl will implicitly parse the number for you and it will stick to the number representation when you do calculations only.
>
> https://wiki.tcl-lang.org/page/everything+is+a+string
> https://wiki.tcl-lang.org/page/shimmering
> > 2.all use unset to clear var when each run get target position , yes increaseing memory will low speed and will get alloc error ...
> There are hidden catches, but also not-so-obvious options, e.g. https://wiki.tcl-lang.org/page/K#c2a6014c2d129837889d8a8000d05e5c3b44e8f6b46cab777c04df8a927bfad2
> > 3. already simpify only calculate target data , is why original time upto 7hr --> optimizate 396 sec
> > below two program is the key factor for the main program , if simplify adv_chg_no_range5 (by pass or no change lst ) , I can get "14 sec" hit customer target one thread
> > bast get more and more info within 12hr ( lottery 24 hr open one time ) and the calculate base 3125x3125x39x600x13(ref 13phase)
> >
> > since I am not family with sqlite3 , need sometime to research as Rich show part .. up performance 15~20%
> >
> > lsearch command is best solution what i can get now. didn't know if sqlite3 will low speed after multi-time excute ....
> > 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
> > }
> That requires three list objects (at least temporarily). Note that this does not mean that all list elements are duplicated in memory, just the list of pointers.
>
> But before digging into Tcl internals, why not consider to no have index 0 in the same list? Then maybe https://wiki.tcl-lang.org/page/VecTcl can help. Do you see how we are _not_ talking about lsearch?
> > proc mark_lott_loc_row_no_sort1 {lott lst} {
> > set res ""
> > foreach cp $lott {
> > foreach x [lsearch -all $lst "$cp"] {
> > lappend res $x
> > }
> lappend res {*}[lsearch -all $lst $cp]
>
> > }
> > return $res
>
> How will you distinguish which element of res is the position of which cp? Are you sure you want lists, not sets?
> > }
> > puts [time {mark_lott_loc_row_no_sort1 {12 16 3 8 36} [adv_chg_no_range5 1 $lst]} 10]
> > > > 720.2 microseconds per iteration
> To get the timing of (loop over) lsearch, try
> set lst2 [adv_chg_no_range5 1 $lst]
> puts [time {mark_lott_loc_row_no_sort1 {12 16 3 8 36} $lst2} 10]
> > 4. base row data already separate calculated and each phase raw data 26mb x 13 not all source in memory only targeted
> > generate target position need calculate alive for customer reference , up 2 program is the key for this part.
> I am not going to put effort in trying to understand this. There were several hints that you are working on lottery data.
> Maybe you want to share the original problem. Just guessing: the lottery draws 5 from 39, millions of sold tickets, a dozen winning ranks, calculate the winners.
> > this two program combine run time is possible below 120 microseconds per iteration ? with 3125 intergers
> > or some algorithm can achieve it ?
> Not a precise question.

Hi heinrichmartin

thanks for great help for deatil explainion and sufficient reference link
will do deep research in those links

> > That requires three list objects (at least temporarily). Note that this does not mean that all list elements are duplicated in memory, just the list of pointers.
> > But before digging into Tcl internals, why not consider to no have index 0 in the same list? Then maybe https://wiki.tcl-lang.org/page/VecTcl can help. Do you see how we are _not_ talking about lsearch?

due to the lindex 0 tilte-id use for mass column data verification use , customer need use this index to input his verification program and database
will consider if the speed up obviously , will write transfer program for customer use.

> > proc mark_lott_loc_row_no_sort1 {lott lst} {
> > set res ""
> > foreach cp $lott {
> > foreach x [lsearch -all $lst "$cp"] {
> > lappend res $x
> >}

> lappend res {*}[lsearch -all $lst $cp]

> > }
> > return $res

proc updated, thanks for correct performance improve

> How will you distinguish which element of res is the position of which cp? Are you sure you want lists, not sets?

only need combine positions result , will try sets if speed up

> > puts [time {mark_lott_loc_row_no_sort1 {12 16 3 8 36} [adv_chg_no_range5 1 $lst]} 10]
> > > 720.2 microseconds per iteration

> To get the timing of (loop over) lsearch, try
> set lst2 [adv_chg_no_range5 1 $lst]
> puts [time {mark_lott_loc_row_no_sort1 {12 16 3 8 36} $lst2} 10]

performance better original one

716.0 microseconds per iteration
699.0 microseconds per iteration (lappend res {*}[lsearch -all $lst $cp])
327 microseconds per iteration (set lst2 [adv_chg_no_range5 1 $lst])
235.5 microseconds per iteration (puts [time {mark_lott_loc_row_no_sort1 {12 16 3 8 36} $lst2} 10])

> > 4. base row data already separate calculated and each phase raw data 26mb x 13 not all source in memory only targeted
> > generate target position need calculate alive for customer reference , up 2 program is the key for this part.
> I am not going to put effort in trying to understand this. There were several hints that you are working on lottery data.
> Maybe you want to share the original problem. Just guessing: the lottery draws 5 from 39, millions of sold tickets, a dozen winning ranks, calculate the winners.

this customize rule provide by his 20year experience , may not fit other one , also different country have different parameter and reference history hit

> > this two program combine run time is possible below 120 microseconds per iteration ? with 3125 intergers
> > or some algorithm can achieve it ?
> Not a precise question

speed is the key factor , buy latest machine or use mult-machine is the last option , if the code effect already limit ...
customer tell me C++ may have better performance , i tell him tcl also can achieve ..
this is why need" below 120 microseconds per iteration" (1/6) > > > 720.2 microseconds per iteration (original : puts [time {mark_lott_loc_row_no_sort1 {12 16 3 8 36} [adv_chg_no_range5 1 $lst]} 10])

or need open new topic to discuss "best algorithm for search list speed" , achieve 6 times speed compare original (search program)

BR
Rolance

On Tuesday, November 8, 2022 at 11:25:53 AM UTC+1, rolance wrote:
> customer tell me C++ may have better performance , i tell him tcl also can achieve ..
> this is why need" below 120 microseconds per iteration" (1/6) > > > 720.2 microseconds per iteration (original : puts [time {mark_lott_loc_row_no_sort1 {12 16 3 8 36} [adv_chg_no_range5 1 $lst]} 10])

Just don't blame Tcl in the end, i.e. make sure that you will be comparing the same algorithm in both languages!

Anyway, when considering Tcl a layer on top of C, then its value-to-impact-ratio is probably best described as "convenience that tries not to impact speed too much"; but you could also code assembly to remove the overhead of C ...

> or need open new topic to discuss "best algorithm for search list speed" , achieve 6 times speed compare original (search program)

No. https://en.wikipedia.org/wiki/Computational_complexity

Before leaving: I am quite sure that this thread (also) has a language barrier - I am not so sure whether the language is mathematics, computer science, or English ...