TIP #313 Published for Peter Spjuth - TCL

Author: Peter Spjuth <peter.spjuth_at_gmail.com>
> it is obviously the case that the location should be
> located through an O(log N) algorithm that takes advantage of this fact
> (binary searching is the most reliable method given that measuring the
> "distance" between two strings is a complex and expensive operation in
> itself).

Can somebody confirm that binary search on Tcl lists is really O(log
n)?
Or, putting it differently, is looking up a list item ([lindex])
really
independent of the list length? I thought it was not.

Donald Arseneau asnd@triumf.ca

On Feb 15, 7:14 pm, peter.spj...@gmail.com wrote:
> On Feb 15, 4:31 pm, fredericbon...@free.fr wrote:
>
> > Now what happens if we provide -lower and -upper sorted list options?
>
> > % set l {1.8 1.9 2.0 2.0 2.1 2.2}
> > % set lpos [lsearch -sorted -lower -real $l 2.0]
> > 2
> > % set upos [lsearch -sorted -upper -real $l 2.0]
> > 3
>
> If you want both the first and the last among equals do:
> set lpos [lsearch -sorted -real $l 2.0]
> set upos [lsearch -bisect -real $l 2.0]
> if {$lpos < 0} {set lpos $upos}

Granted, although this makes the code less readable IMHO. But on
second thought your proposal totally makes sense if the goal is to
find an insertion point for a given value, which after all was the
rationale behind your TIP (versus finding a range of value, which
wasn't). So I'm OK with that.

However, I'm not very fond of -bisect, as -sorted already performs
binary searching, and -bisect sounds like some kind of optimization
over a supposedly naive default searching. May I suggest -insert or -
nearest instead?

Donald Arseneau wrote:
> Author: Peter Spjuth <peter.spjuth_at_gmail.com>
>> it is obviously the case that the location should be
>> located through an O(log N) algorithm that takes advantage of this fact
>> (binary searching is the most reliable method given that measuring the
>> "distance" between two strings is a complex and expensive operation in
>> itself).
>
> Can somebody confirm that binary search on Tcl lists is really O(log
> n)?
> Or, putting it differently, is looking up a list item ([lindex])
> really
> independent of the list length? I thought it was not.

I don't have the source code to hand, so can't confirm definitely, but I
thought Tcl lists were implemented as arrays internally? In which case
it definitely should be O(1) for access, and O(log n) for binary search.

-- Neil

Donal K. Fellows wrote:
> Neil Madden wrote:
>> Kevin Kenny wrote:
>>> For instance,
>>> ::tcl::clock::BSearch finds, among other things, the last change
>>> of time zone at or before a given time.
> [...]
>> Indeed. My own recent experience was in looking up annotations to
>> display while playing back some 3D visualisation data (through Togl).
> [...]
>
> Can these use-cases be added to the TIP please?

If somebody hasn't already done so, I can add these. But will that make
me an author of the TIP? Seems a bit cheeky for such a minor addition...

-- Neil

Neil Madden wrote:
> If somebody hasn't already done so, I can add these. But will that make
> me an author of the TIP? Seems a bit cheeky for such a minor addition...

I can remove someone's author status if they ask me nicely...

Donal.

Neil Madden wrote:
> I don't have the source code to hand, so can't confirm definitely, but I
> thought Tcl lists were implemented as arrays internally?

Correct. Arrays of Tcl_Obj references.

> In which case
> it definitely should be O(1) for access, and O(log n) for binary search.

Correct.

Donal.

Donal K. Fellows wrote:
> Neil Madden wrote:
>> If somebody hasn't already done so, I can add these. But will that
>> make me an author of the TIP? Seems a bit cheeky for such a minor
>> addition...
>
> I can remove someone's author status if they ask me nicely...

OK, added the examples. Please feel free to clean up the formatting (a
"Preview" option would be very nice here!), and remove my name from the
TIP authors (I don't mind appearing in the log, but the TIP is Peter's
work and he deserves sole credit for it).

-- Neil

Donal K. Fellows wrote:
> Neil Madden wrote:
>> I don't have the source code to hand, so can't confirm definitely, but
>> I thought Tcl lists were implemented as arrays internally?
>
> Correct. Arrays of Tcl_Obj references.
>
>> In which case it definitely should be O(1) for access, and O(log n)
>> for binary search.
>
> Correct.

I was tempted to jump in and say, "definitely, [lindex] takes O(1)
time," but then considered the effects of the memory hierarchy
(things like L1 cache eviction). So I wasn't quite willing to make
the unqualified statement, and remained silent rather than take
the time to qualify it properly.

--
73 de ke9tv/2, Kevin

Neil Madden wrote:
> OK, added the examples. Please feel free to clean up the formatting (a
> "Preview" option would be very nice here!), and remove my name from the
> TIP authors (I don't mind appearing in the log, but the TIP is Peter's
> work and he deserves sole credit for it).

Done. Thanks.

Donal.