Re: pgsql: Avoid use of float arithmetic in bipartite_match.c. - Mailing list pgsql-committers

From Andres Freund
Subject Re: pgsql: Avoid use of float arithmetic in bipartite_match.c.
Date
Msg-id 20150823172546.GI8552@awork2.anarazel.de
Whole thread Raw
In response to pgsql: Avoid use of float arithmetic in bipartite_match.c.  (Tom Lane <tgl@sss.pgh.pa.us>)
Responses Re: pgsql: Avoid use of float arithmetic in bipartite_match.c.
List pgsql-committers
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


pgsql-committers by date:

Previous
From: Tom Lane
Date:
Subject: pgsql: Avoid use of float arithmetic in bipartite_match.c.
Next
From: Tom Lane
Date:
Subject: Re: pgsql: Avoid use of float arithmetic in bipartite_match.c.