problem: reducing comparison

[Xah Lee]

©someone sent me the following code, which performs identically with
the original reduce. (tested for pairings of comb(n) with large n)
Superb.
©
©def reduce2( pairings, pair ):
©    result={}
©    for i,j in pairings.itervalues():
©        if i in pair: i=pair[0]
©        if j in pair: j=pair[0]
©        if i>j: (i,j) = (j,i)
©        if i!=j: result["%d,%d"%(i,j)] = (i,j)
©    return result
©
©
©def reduce(pairings, pair):
©    ps=pairings.copy(); j=pair;
©    ps.pop("%d,%d"%(j[0],j[1]),0)
©    for k in pairings.itervalues():
©	if (k[0]==j[0]):
©            if (j[1] < k[1]):
©                ps.pop("%d,%d"%(j[1],k[1]),0)
©            else:
©                ps.pop("%d,%d"%(k[1],j[1]),0)
©        if (k[1]==j[0]):
©            if (k[0] < j[1]):
©                ps.pop("%d,%d"%(k[0],j[1]),0)
©            else:
©                ps.pop("%d,%d"%(j[1],k[0]),0)
©    return ps
©
©is reduce2 more efficient? It works entirely differently. I'll have
to think about it... besides algorithmic... onto the minute academic
diddling, i wonder if it is faster to delete entries in dict or add
entries...

 Xah
 xah at xahlee.org
 http://xahlee.org/PageTwo_dir/more.html

Xah Lee wrote:
> here are the answers:
>
> Perl code:
>
> sub reduce ($$) {
> my %hh= %{$_[0]}; # e.g. {'1,2'=>[1,2],'5,6'=>[5,6],...}
> my ($j1,$j2)=($_[1]->[0],$_[1]->[1]);  # e.g. [3,4]
> delete $hh{"$j1,$j2"};
> foreach my $k (keys %hh) {
>         $k=~m/^(\d+),(\d+)$/;
>         my ($k1,$k2)=($1,$2);
>         if ($k1==$j1) {
>             if ($j2 < $k2) {
>                 delete $hh{"$j2,$k2"};
>             }
>             else {
>                 delete $hh{"$k2,$j2"};
>             };
>         };
>         if ($k2==$j1) {
>             if ($k1 < $j2) {
>                 delete $hh{"$k1,$j2"};
>             }
>             else {
>                 delete $hh{"$j2,$k1"};
>             };
>         };
>     }
> return \%hh;
> }
>
> ...
> In imperative languages such as Perl and Python and Java, in general
it
> is not safe to delete elements when looping thru a list-like entity.
> (it screws up the iteration) One must make a copy first, and work
with
> the copy.
>
> Note also that in Python there's already a function called reduce.
(it
> is equivalent to Mathematica's Fold.) In Python, looks like user can
> over-ride default functions.
>
> This post is archived at
> http://xahlee.org/perl-python/pairing_reduce.html
> Possible errata or addenda will appear there.
> 
>  Xah
>  xah at xahlee.org
>  http://xahlee.org/PageTwo_dir/more.html