Since the minimum and maximum values of fundamental types are known, can minElement and maxElement shortcut and return that value immediately?

I think such an optimization may break existing code because it may not consume ranges in old code, which may be surprised by it. (?)

I ask because the documentation says "O(n) Exactly n - 1 comparisons are needed."

Ali

P.S. I decided to use my own function instead of minElement; I return 0 immediately on a range of size_t elements.

On Sun, Sep 11, 2022 at 07:40:35PM -0700, Ali Çehreli via Digitalmars-d wrote:
> Since the minimum and maximum values of fundamental types are known, can minElement and maxElement shortcut and return that value immediately?

No, because that value may not appear in the given range.


T

-- 
Having a smoking section in a restaurant is like having a peeing section in a swimming pool. -- Edward Burr

On 9/12/22 04:07, H. S. Teoh wrote:
> On Sun, Sep 11, 2022 at 07:40:35PM -0700, Ali Çehreli via Digitalmars-d wrote:
>> Since the minimum and maximum values of fundamental types are known, can
>> minElement and maxElement shortcut and return that value immediately?
>
> No, because that value may not appear in the given range.
>
>
> T

I am not that silly. :) What I meant is "as soon as they see e.g. 0". Say, at the third element of a million-element range...

Ali

On Monday, 12 September 2022 at 11:46:23 UTC, Ali Çehreli wrote:
> On 9/12/22 04:07, H. S. Teoh wrote:
> > On Sun, Sep 11, 2022 at 07:40:35PM -0700, Ali Çehreli via
> Digitalmars-d wrote:
> >> Since the minimum and maximum values of fundamental types
> are known, can
> >> minElement and maxElement shortcut and return that value
> immediately?
> >
> > No, because that value may not appear in the given range.
> >
> >
> > T
>
> I am not that silly. :) What I meant is "as soon as they see e.g. 0". Say, at the third element of a million-element range...
>
> Ali

In case zero will be the last element - the search should make an extra comparisons “if currentElement = T.minimum” which double operations..
Isn’t it?

On Monday, 12 September 2022 at 11:53:34 UTC, Sergey wrote:
> In case zero will be the last element - the search should make an extra comparisons “if currentElement = T.minimum” which double operations..
> Isn’t it?

Branch prediction makes this extra check basically free.

On Mon, Sep 12, 2022 at 04:46:23AM -0700, Ali Çehreli via Digitalmars-d wrote:
> On 9/12/22 04:07, H. S. Teoh wrote:
> > On Sun, Sep 11, 2022 at 07:40:35PM -0700, Ali Çehreli via Digitalmars-d
> wrote:
> >> Since the minimum and maximum values of fundamental types are known, can minElement and maxElement shortcut and return that value immediately?
> >
> > No, because that value may not appear in the given range.
[...]
> I am not that silly. :) What I meant is "as soon as they see e.g. 0". Say, at the third element of a million-element range...
[...]

Sounds like a good idea.


T

-- 
PNP = Plug 'N' Pray

On Mon, Sep 12, 2022 at 10:15:45AM -0400, Steven Schveighoffer via Digitalmars-d wrote:
> On 9/12/22 7:53 AM, Sergey wrote:
> > On Monday, 12 September 2022 at 11:46:23 UTC, Ali Çehreli wrote:
> > > 
> > > I am not that silly. :) What I meant is "as soon as they see e.g. 0". Say, at the third element of a million-element range...
> > > 
> > 
> > In case zero will be the last element - the search should make an extra comparisons “if currentElement = T.minimum” which double operations..  Isn’t it?
> 
> It could only make comparisons when assigning the "current minimum". I don't think it would cost that much. Complexity would be the same anyway.
> 
> One thing that is worrisome though, is the fact that `min` and `max` aren't always the minimum and maximum bit patterns available. So short-cutting the search might do something you don't want.
> 
> e.g. an enum which defines a bitfield might have values of 1, 2, 4, 8, but instances of the enum might go all the way up to 15 (all bits set). However, the `.max` value would be 8. And in other cases, the enum truly may just be an enum, where the `.max` value is the maximum value, but you'd have to defensively check for the max representable value, making it perform this check for no reason.

I would on principle exclude enums from this optimization.

Besides, enums as bitfields IMO are a code smell; there really should be an "official" bitflags type constructor that takes an enum and creates a bitfield type based on that enum. The constructed type would have .min and .max appropriately defined as 0 and the bitwise OR of all flags, respectively.


> A possibility is to provide an overload that accepts the absolute minimum or maximum, and only then does it do the extra comparisons.
[...]

Please don't. This smells like one of those well-intentioned extensions that 5 years later will have us wondering "how did Phobos become this hairy?".


T

-- 
Debian GNU/Linux: Cray on your desktop.