Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Python > [perl-python] problem: reducing comparison

Reply
Thread Tools

[perl-python] problem: reducing comparison

 
 
Xah Lee
Guest
Posts: n/a
 
      02-15-2005
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://www.velocityreviews.com/forums/(E-Mail Removed)
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

 
Reply With Quote
 
 
 
 
Xah Lee
Guest
Posts: n/a
 
      02-15-2005
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
(E-Mail Removed)
http://xahlee.org/PageTwo_dir/more.html

 
Reply With Quote
 
 
 
 
Xah Lee
Guest
Posts: n/a
 
      02-15-2005
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
> (E-Mail Removed)
> http://xahlee.org/PageTwo_dir/more.html


 
Reply With Quote
 
Joe Francia
Guest
Posts: n/a
 
      02-15-2005
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

 
Reply With Quote
 
Xah Lee
Guest
Posts: n/a
 
      02-16-2005
©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
(E-Mail Removed)
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
> (E-Mail Removed)
> http://xahlee.org/PageTwo_dir/more.html


 
Reply With Quote
 
Michael Hoffman
Guest
Posts: n/a
 
      02-16-2005
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
 
Reply With Quote
 
Xah Lee
Guest
Posts: n/a
 
      02-16-2005

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
(E-Mail Removed)
http://xahlee.org/PageTwo_dir/more.html

 
Reply With Quote
 
Xah Lee
Guest
Posts: n/a
 
      02-16-2005
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
(E-Mail Removed)
http://xahlee.org/PageTwo_dir/more.html

 
Reply With Quote
 
Xah Lee
Guest
Posts: n/a
 
      02-16-2005
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
(E-Mail Removed)
http://xahlee.org/PageTwo_dir/more.html

 
Reply With Quote
 
gene.tani@gmail.com
Guest
Posts: n/a
 
      02-17-2005
This could have been a really unique thread: 15 messages, 1 author

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Comparison of 2 files and generating the output based on comparison Deepu Perl Misc 1 02-07-2011 03:09 PM
Price Comparison Service. Best Deal. Special Coupon atBest-Price-Comparison.com rapee Digital Photography 0 03-14-2008 06:46 AM
Reducing master password check? Gusvaldo Firefox 1 04-18-2005 10:31 PM
[perl-python] problem: reducing comparison Xah Lee Perl Misc 7 02-17-2005 03:31 AM
Reducing Spam Associated with Posting to Newsgroups Microsoft Communities Team [MSFT] ASP .Net 0 10-14-2003 10:26 PM



Advertisments