Date: Thu, 4 May 2023 14:18:14 +0000
I think how search has been handled, with the default & algorithm-specific versions, is worth considering.
From: Jeremy Murphy <jeremy.william.murphy_at_[hidden]>
Sent: Sunday, April 23, 2023 11:28 PM
To: sg19_at_[hidden]
Cc: Jens Maurer <jens.maurer_at_[hidden]>; Phil Ratzloff <Phil.Ratzloff_at_[hidden]>; Oliver Rosten <oliver.rosten_at_[hidden]>
Subject: Re: [SG19] D1709: Graph Proposal
You don't often get email from jeremy.william.murphy_at_[hidden]<mailto:jeremy.william.murphy_at_[hidden]>. Learn why this is important<https://aka.ms/LearnAboutSenderIdentification>
EXTERNAL
Hi everyone,
apologies for dropping in unannounced, I'm not sure what the protocol for participation is.
I just had a couple of comments to add on the algorithm naming topic.
The value of having std::sort and std::stable_sort is ease of use -- a user doesn't have to deliberate when they want to get on with the task of sorting arbitrary data. But for the users with specific requirements such as sorting many small arrays, or not caring about the worst-case scenario, they have to pay the cost of generality.
>From memory, some standard implementations have "insertion_sort" in there, but it's not in ::std, so it's not available to the user.
C++17 introduced an overload of std::search that takes a searcher object such as std::boyer_moore or std::boyer_moore_horspool, and also provided the std::default_searcher class that just does the basic algorithm. (Of course they retained the original interface to std::search too.)
>From these examples, I'm suggesting why not have both? I mean, have std::dijkstra and std::bellman_ford, etc, but also have the std::shortest_path(_variant) names that default to the most generally pleasing (whatever that means) algorithm. That would satisfy the users that want to choose their algorithm explicitly and the users that want the language to choose the best algorithm for the problem. You might even design it like std::search, so that the algorithm is passed as a solver to the single interface, i.e. a user might call std::shortest_path(std::dijkstra{}, ...) to explicitly use Dijkstra's algorithm to solve that problem; if the user doesn't explicitly choose a solver then the default is used.
Cheers.
Jeremy
On Sat, 15 Apr 2023 at 02:28, Phil Ratzloff via SG19 <sg19_at_[hidden]<mailto:sg19_at_[hidden]>> wrote:
(Adding Andrew - he's had problems getting added to the SG19 reflector)
From: SG19 <sg19-bounces_at_[hidden]<mailto:sg19-bounces_at_[hidden]>> On Behalf Of Oliver Rosten via SG19
Sent: Friday, April 14, 2023 8:50 AM
To: Jens Maurer <jens.maurer_at_[hidden]<mailto:jens.maurer_at_[hidden]>>
Cc: Oliver Rosten <oliver.rosten_at_[hidden]<mailto:oliver.rosten_at_[hidden]>>; sg19_at_[hidden]<mailto:sg19_at_[hidden]>
Subject: Re: [SG19] D1709: Graph Proposal
EXTERNAL
I think there are some other considerations to bear in mind, which were briefly touched on last night.
To what extent can the problem of dispatch be dealt with implicitly? What I'm getting at here is that in some instances an appropriate concept could do the trick. For example, consider the simple cases where the weights are
(i) int
(ii) unsigned int
There is enough info to always correctly and optimally dispatch case (ii). The first case is harder. In general, we can't assume that Dijskstra will work and so by default we should dispatch to e.g. Bellman-Ford. However, clients may wish to explicitly override this if they know that none of the weights are actually negative.
Perhaps this implies a set of functions
shortest_path (constrained to accept graph-like types satisfying enough requirements for implicit dispatch)
shortest_path_semi_positive_weights (ideally with a nicer name)
shortest_path_negative_weights (ditto)
Oliver
PS Out of curiosity, what is your objection to overload sets? I tend to find them easier to work with in generic code since it's easy to create maps from types to types. However, I typically find maps from types to function invocations more fiddly and a bit clumsier.
On Fri, 14 Apr 2023 at 08:34, Jens Maurer <jens.maurer_at_[hidden]<mailto:jens.maurer_at_[hidden]>> wrote:
On 13/04/2023 22.54, Oliver Rosten via SG19 wrote:
> Hi folks,
>
> Further to today's meeting I wanted to add a further thought about standardizing explicitly named algorithms, such as Dijksrta's.
>
> To recap:
>
> 1. I expressed worry with this direction as I think we should be standardizing what algorithms do, rather than how they do it. I drew an analogy with sort and stable_sort: this is what is standardized, not quick_sort, merge_sort etc. Therefore, my preference is the shortest_path 'driver' approach.
>
> 2. A counter-argument was given that users may wish to specify a particular algorithm since e.g. Dijkstra's is inappropriate if there are negative weights.
>
> That's pretty much where we left it at the meeting.
>
> However, I think what point 2 is really highlighting is that the shortest_path 'driver' algorithm should be sufficiently flexible to disambiguate things like this (and this is true regardless of whether there are explicitly named alternatives). For example, I could imagine an overload set with a tag parameter indicating whether there are negative weights.
Agreed with the general idea, but please let's not have overload sets
with tag parameters if we're not dealing with a constructor and we're
not dealing with an open-ended set of possibilities.
It's "sort" and "stable_sort", thus it should be "shortest_path_positive_weights"
and "shortest_path" (details of names tbd), i.e. functions are differentiated by name.
Jens
From: Jeremy Murphy <jeremy.william.murphy_at_[hidden]>
Sent: Sunday, April 23, 2023 11:28 PM
To: sg19_at_[hidden]
Cc: Jens Maurer <jens.maurer_at_[hidden]>; Phil Ratzloff <Phil.Ratzloff_at_[hidden]>; Oliver Rosten <oliver.rosten_at_[hidden]>
Subject: Re: [SG19] D1709: Graph Proposal
You don't often get email from jeremy.william.murphy_at_[hidden]<mailto:jeremy.william.murphy_at_[hidden]>. Learn why this is important<https://aka.ms/LearnAboutSenderIdentification>
EXTERNAL
Hi everyone,
apologies for dropping in unannounced, I'm not sure what the protocol for participation is.
I just had a couple of comments to add on the algorithm naming topic.
The value of having std::sort and std::stable_sort is ease of use -- a user doesn't have to deliberate when they want to get on with the task of sorting arbitrary data. But for the users with specific requirements such as sorting many small arrays, or not caring about the worst-case scenario, they have to pay the cost of generality.
>From memory, some standard implementations have "insertion_sort" in there, but it's not in ::std, so it's not available to the user.
C++17 introduced an overload of std::search that takes a searcher object such as std::boyer_moore or std::boyer_moore_horspool, and also provided the std::default_searcher class that just does the basic algorithm. (Of course they retained the original interface to std::search too.)
>From these examples, I'm suggesting why not have both? I mean, have std::dijkstra and std::bellman_ford, etc, but also have the std::shortest_path(_variant) names that default to the most generally pleasing (whatever that means) algorithm. That would satisfy the users that want to choose their algorithm explicitly and the users that want the language to choose the best algorithm for the problem. You might even design it like std::search, so that the algorithm is passed as a solver to the single interface, i.e. a user might call std::shortest_path(std::dijkstra{}, ...) to explicitly use Dijkstra's algorithm to solve that problem; if the user doesn't explicitly choose a solver then the default is used.
Cheers.
Jeremy
On Sat, 15 Apr 2023 at 02:28, Phil Ratzloff via SG19 <sg19_at_[hidden]<mailto:sg19_at_[hidden]>> wrote:
(Adding Andrew - he's had problems getting added to the SG19 reflector)
From: SG19 <sg19-bounces_at_[hidden]<mailto:sg19-bounces_at_[hidden]>> On Behalf Of Oliver Rosten via SG19
Sent: Friday, April 14, 2023 8:50 AM
To: Jens Maurer <jens.maurer_at_[hidden]<mailto:jens.maurer_at_[hidden]>>
Cc: Oliver Rosten <oliver.rosten_at_[hidden]<mailto:oliver.rosten_at_[hidden]>>; sg19_at_[hidden]<mailto:sg19_at_[hidden]>
Subject: Re: [SG19] D1709: Graph Proposal
EXTERNAL
I think there are some other considerations to bear in mind, which were briefly touched on last night.
To what extent can the problem of dispatch be dealt with implicitly? What I'm getting at here is that in some instances an appropriate concept could do the trick. For example, consider the simple cases where the weights are
(i) int
(ii) unsigned int
There is enough info to always correctly and optimally dispatch case (ii). The first case is harder. In general, we can't assume that Dijskstra will work and so by default we should dispatch to e.g. Bellman-Ford. However, clients may wish to explicitly override this if they know that none of the weights are actually negative.
Perhaps this implies a set of functions
shortest_path (constrained to accept graph-like types satisfying enough requirements for implicit dispatch)
shortest_path_semi_positive_weights (ideally with a nicer name)
shortest_path_negative_weights (ditto)
Oliver
PS Out of curiosity, what is your objection to overload sets? I tend to find them easier to work with in generic code since it's easy to create maps from types to types. However, I typically find maps from types to function invocations more fiddly and a bit clumsier.
On Fri, 14 Apr 2023 at 08:34, Jens Maurer <jens.maurer_at_[hidden]<mailto:jens.maurer_at_[hidden]>> wrote:
On 13/04/2023 22.54, Oliver Rosten via SG19 wrote:
> Hi folks,
>
> Further to today's meeting I wanted to add a further thought about standardizing explicitly named algorithms, such as Dijksrta's.
>
> To recap:
>
> 1. I expressed worry with this direction as I think we should be standardizing what algorithms do, rather than how they do it. I drew an analogy with sort and stable_sort: this is what is standardized, not quick_sort, merge_sort etc. Therefore, my preference is the shortest_path 'driver' approach.
>
> 2. A counter-argument was given that users may wish to specify a particular algorithm since e.g. Dijkstra's is inappropriate if there are negative weights.
>
> That's pretty much where we left it at the meeting.
>
> However, I think what point 2 is really highlighting is that the shortest_path 'driver' algorithm should be sufficiently flexible to disambiguate things like this (and this is true regardless of whether there are explicitly named alternatives). For example, I could imagine an overload set with a tag parameter indicating whether there are negative weights.
Agreed with the general idea, but please let's not have overload sets
with tag parameters if we're not dealing with a constructor and we're
not dealing with an open-ended set of possibilities.
It's "sort" and "stable_sort", thus it should be "shortest_path_positive_weights"
and "shortest_path" (details of names tbd), i.e. functions are differentiated by name.
Jens
-- SG19 mailing list SG19_at_[hidden]<mailto:SG19_at_[hidden]> https://lists.isocpp.org/mailman/listinfo.cgi/sg19
Received on 2023-05-04 14:18:19