[perl-python] problem: reducing comparison

Discussion in 'Python' started by Xah Lee, Feb 15, 2005.

  1. Xah Lee

    Xah Lee Guest

    here's a interesting real-world algoritm to have fun with.

    attached below is the Perl documentation that i wrote for a function
    called "reduce", which is really the heart of a larger software.

    The implementation is really simple, but the key is to understand what
    the function should be. I'll post Perl and Python codes tomorrow for
    those interested. If you are a perl programer, try to code it in
    Python. (it's easy.)

    This is brought to you by the Perl-Python a-day community. To
    subscribe, see
    http://xahlee.org/perl-python/python.html

    Xah

    http://xahlee.org/PageTwo_dir/more.html

    -------------------------------

    =pod

    e.g. reduce( $pairings, $a_pair) retured the first argument with some
    pairs deleted.

    Detail:

    we have n things, represented by numbers 1 to n. Some of these are
    identical. We want to partition the range of numbers 1 to n so that
    identical ones are grouped together.

    To begin comparison, we generate a list of pairings that's all
    possible parings of numbers 1 to n. (of course order does not matter,
    and the pairing does not contain repeations) This is the first
    argument to reduce.

    We'll go thru this pairings list one by one and do comparisons, remove
    the pair once it has been compared. However, more pairs can be removed
    if a we find a pair identical.

    For example, suppose we know that 2 and 4 are identical, and if the
    pairing list contains (2,3) and (4,3), one of them can be deleted
    because now 2 and 4 are the same thing.

    (We do this because we expect the comparison operation will be
    expensive.)

    reduce( $pairings, $a_pair) returns a reduced $pairings knowing that
    $a_pair are identical.

    The first argument $pairings must be in the form of a hash. e.g.

    {'1,5' => [1,5],'3,5' => [3,5],'2,4' => [2,4],'4,5' => [4,5],'1,3' =>
    [1,3],'2,5' => [2,5],'1,2' => [1,2],'3,4' => [3,4],'2,3' =>
    [2,3],'1,4' => [1,4]}

    (Note that keys are strings of the pairs separated by a comma.)

    $a_pair is a reference to a list of the form [$a,$b].

    (different pairs may be deleted if the hash's pairs are given in
    different order. i.e. 3,4 instead of 4,3)

    The return value is a reference to a hash.

    The program is deterministic but exactly which pairs are deleted is
    unspecified. If the input is all possible pairs of 2 things out of n,
    maximum reduction is guaranteed.

    =cut
     
    Xah Lee, Feb 15, 2005
    #1
    1. Advertising

  2. Xah Lee

    Xah Lee Guest

    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;
    }


    ©Python code.
    ©
    ©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
    ©

    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

    http://xahlee.org/PageTwo_dir/more.html
     
    Xah Lee, Feb 15, 2005
    #2
    1. Advertising

  3. Xah Lee

    Xah Lee Guest

    Re: problem: reducing comparison

    my Python coding is not experienced. In this case, is
    ps.pop("%d,%d"%(j[1],k[1]),0) out of ordinary?

    if i have long paragraphs of documentation for a function, do i still
    just attach it below the fun def?

    Xah

    Xah Lee wrote:
    > here are the answers:
    >
    > ©Python code.
    > ©
    > ©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
    > ©
    >
    > 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
    >
    > http://xahlee.org/PageTwo_dir/more.html
     
    Xah Lee, Feb 15, 2005
    #3
  4. Xah Lee

    Joe Francia Guest

    Xah Lee wrote:
    > here's a interesting real-world algoritm to have fun with.


    From you? Doubtful.

    Sorry, dude, but you've been replaced by über-troll Ilias Lazaridis.
    Security will escort you to the door.


    --
    Soraia: http://www.soraia.com
     
    Joe Francia, Feb 15, 2005
    #4
  5. Xah Lee

    Xah Lee Guest

    Re: problem: reducing comparison

    ©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

    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
    >
    > http://xahlee.org/PageTwo_dir/more.html
     
    Xah Lee, Feb 16, 2005
    #5
  6. Xah Lee wrote:
    > attached below is the Perl documentation that i wrote for a function
    > called "reduce", which is really the heart of a larger software.


    Don't shadow built-ins. Especially for a function name.
    --
    Michael Hoffman
     
    Michael Hoffman, Feb 16, 2005
    #6
  7. Xah Lee

    Xah Lee Guest

    Re: [perl-python] problem: reducing comparison (correction)

    Xah Lee wrote:
    > 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.


    Correction:
    When looping thru a list-like entity and delete elements in the vary
    list, there's a question whether it will change the iteration. (For
    example, if one loops thru 1 to 9, and deleted 8 while at 2, should the
    loop still do 8?) For some languages and or list entities, the answer
    may be yes or no. However, in imperative languages such as Perl and
    Python and Java, often this is not allowed by the language, partially
    as a protection to safeguard and assume programers as ignoramuses, but
    partially because the internal issues of these languages can't handle
    it.

    The work around in these languages is always to make a copy of the
    list-entity, and work with the copy.

    Xah

    http://xahlee.org/PageTwo_dir/more.html
     
    Xah Lee, Feb 16, 2005
    #7
  8. Xah Lee

    Xah Lee Guest

    Re: [perl-python] problem: reducing comparison (erratum)

    Xah Lee wrote:
    > 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.


    Correction:
    When looping thru a list-like entity and delete elements in the vary
    list, there's a question whether it will change the iteration. (For
    example, if one loops thru 1 to 9, and deleted 8 while at 2, should the
    loop still do 8?) For some languages and or list entities, the answer
    may be yes or no. However, in imperative languages such as Perl and
    Python and Java, often this is not allowed, justified as a protection
    to safeguard programers as ignoramuses, but partially because the
    internal issues of these languages. (These languages have molded a
    generation of programers to question and discourse man-made issues.)

    The work around in these languages is always to make a copy of the
    list-entity, and work with the copy.

    Xah

    http://xahlee.org/PageTwo_dir/more.html
     
    Xah Lee, Feb 16, 2005
    #8
  9. Xah Lee

    Xah Lee Guest

    Re: [perl-python] problem: reducing comparison (erratum)

    Xah Lee wrote:
    > 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.


    Correction:
    When looping thru a list-like entity and delete elements in the vary
    list, there's a question whether it will change the iteration. (For
    example, if one loops thru 1 to 9, and deleted 8 while at 2, should the
    loop still do 8?) This is a design issue. Both behavior are useful. For
    some languages and or list entities, the answer may be yes or no.
    However, in imperative languages such as Perl and Python and Java,
    often modifying a list while looping simply cannot be done, justified
    as a protection to safeguard programers as ignoramuses, but partially
    because the internal issues of these languages. (These languages have
    molded a generation of programers to question and discourse man-made
    complexities.)

    The work around in these languages is always to make a copy of the
    list-entity, and work with the copy.

    Xah

    http://xahlee.org/PageTwo_dir/more.html
     
    Xah Lee, Feb 16, 2005
    #9
  10. Xah Lee

    Guest

    This could have been a really unique thread: 15 messages, 1 author
     
    , Feb 17, 2005
    #10
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Microsoft Communities Team [MSFT]

    Reducing Spam Associated with Posting to Newsgroups

    Microsoft Communities Team [MSFT], Oct 14, 2003, in forum: ASP .Net
    Replies:
    0
    Views:
    442
    Microsoft Communities Team [MSFT]
    Oct 14, 2003
  2. lotmr
    Replies:
    1
    Views:
    524
  3. Shriphani
    Replies:
    2
    Views:
    572
    Ian Kelly
    Jun 1, 2008
  4. Xah Lee
    Replies:
    7
    Views:
    111
  5. Deepu
    Replies:
    1
    Views:
    266
    ccc31807
    Feb 7, 2011
Loading...

Share This Page