Обсуждение: pgsql: Avoid use of float arithmetic in bipartite_match.c.
Avoid use of float arithmetic in bipartite_match.c. Since the distances used in this algorithm are small integers (not more than the size of the U set, in fact), there is no good reason to use float arithmetic for them. Use short ints instead: they're smaller, faster, and require no special portability assumptions. Per testing by Greg Stark, which disclosed that the code got into an infinite loop on VAX for lack of IEEE-style float infinities. We don't really care all that much whether Postgres can run on a VAX anymore, but there seems sufficient reason to change this code anyway. In passing, make a few other small adjustments to make the code match usual Postgres coding style a bit better. Branch ------ REL9_5_STABLE Details ------- http://git.postgresql.org/pg/commitdiff/4022f94c350f96fc5feff0503d3e2f2f6f9086cc Modified Files -------------- src/backend/lib/bipartite_match.c | 75 +++++++++++++++++++++++-------------- src/include/lib/bipartite_match.h | 16 ++++---- 2 files changed, 55 insertions(+), 36 deletions(-)
Hi, On 2015-08-23 17:02:35 +0000, Tom Lane wrote: > Avoid use of float arithmetic in bipartite_match.c. > > Since the distances used in this algorithm are small integers (not more > than the size of the U set, in fact), there is no good reason to use float > arithmetic for them. Use short ints instead: they're smaller, faster, and > require no special portability assumptions. Yea, makes sense. Thanks. > In passing, make a few other small adjustments to make the code match > usual Postgres coding style a bit better. Not sure why you replaced n by k? Anyway, it's not a complete replacement afaics: /* * Given a bipartite graph consisting of nodes U numbered 1..nU, nodes V * numbered 1..nV, and an adjacency map of undirected edges in the form - * adjacency[u] = [n, v1, v2, v3, ... vn], we wish to find a "maximum + * adjacency[u] = [k, v1, v2, v3, ... vk], we wish to find a "maximum * cardinality matching", which is defined as follows: a matching is a subset * of the original edges such that no node has more than one edge, and a * matching has maximum cardinality if there exists no other matching with a the nodes are 1..n, so the adjacency list should be as well (or the other way round). Andres
Andres Freund <andres@anarazel.de> writes:
> Not sure why you replaced n by k?
I thought it was possible to confuse it with the "n"'s used in the
previous line to denote the graph sizes.
> the nodes are 1..n, so the adjacency list should be as well (or the
> other way round).
No, I meant them to be different. Do you think the other way is better?
regards, tom lane
On 2015-08-23 13:30:45 -0400, Tom Lane wrote: > Andres Freund <andres@anarazel.de> writes: > > Not sure why you replaced n by k? > > I thought it was possible to confuse it with the "n"'s used in the > previous line to denote the graph sizes. > > > the nodes are 1..n, so the adjacency list should be as well (or the > > other way round). > > No, I meant them to be different. Do you think the other way is better? Well, using the same index seemed to comfortably explain that the size of the individual adjacency mappings depends on the number of nodes in V. But for that to really make sense there'd need to be a different indexes for U/V, which I now see wasn't the case case before either. As currently used they'll be the same anyway... - Andres