Re: [perl-python] problem: reducing comparison
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 -- http://mail.python.org/mailman/listinfo/python-list
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 [EMAIL PROTECTED] http://xahlee.org/PageTwo_dir/more.html -- http://mail.python.org/mailman/listinfo/python-list
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 [EMAIL PROTECTED] http://xahlee.org/PageTwo_dir/more.html -- http://mail.python.org/mailman/listinfo/python-list
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 [EMAIL PROTECTED] http://xahlee.org/PageTwo_dir/more.html -- http://mail.python.org/mailman/listinfo/python-list
Re: [perl-python] problem: reducing comparison
This could have been a really unique thread: 15 messages, 1 author -- http://mail.python.org/mailman/listinfo/python-list
Re: [perl-python] problem: reducing comparison
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 [EMAIL PROTECTED] http://xahlee.org/PageTwo_dir/more.html -- http://mail.python.org/mailman/listinfo/python-list
Re: [perl-python] problem: reducing comparison
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 -- http://mail.python.org/mailman/listinfo/python-list
[perl-python] problem: reducing comparison
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 [EMAIL PROTECTED] 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 -- http://mail.python.org/mailman/listinfo/python-list