[24971] in Perl-Users-Digest
Perl-Users Digest, Issue: 7221 Volume: 10
daemon@ATHENA.MIT.EDU (Perl-Users Digest)
Thu Oct 7 18:11:49 2004
Date: Thu, 7 Oct 2004 15:10:11 -0700 (PDT)
From: Perl-Users Digest <Perl-Users-Request@ruby.OCE.ORST.EDU>
To: Perl-Users@ruby.OCE.ORST.EDU (Perl-Users Digest)
Perl-Users Digest Thu, 7 Oct 2004 Volume: 10 Number: 7221
Today's topics:
Re: Symbolic algebra <goofy_headed_punk@msn.com>
Re: Symbolic algebra <ftoewe@austin.rr.com>
Re: Top 10 list algorithm <nospam@bigpond.com>
Re: Top 10 list algorithm (Anno Siegel)
Re: Top 10 list algorithm <postmaster@castleamber.com>
Re: Top 10 list algorithm <emschwar@pobox.com>
Re: Top 10 list algorithm (Anno Siegel)
Using a variable size with the repetition quantifier (Philippe Aymer)
Re: Using a variable size with the repetition quantifie <pinyaj@rpi.edu>
Re: While query (Charles DeRykus)
Re: While query <mritty@gmail.com>
Digest Administrivia (Last modified: 6 Apr 01) (Perl-Users-Digest Admin)
----------------------------------------------------------------------
Date: Thu, 07 Oct 2004 11:30:01 -0500
From: Brian Troutwine <goofy_headed_punk@msn.com>
Subject: Re: Symbolic algebra
Message-Id: <pan.2004.10.07.16.30.00.2475@msn.com>
On Tue, 05 Oct 2004 23:41:34 +0000, Fred Toewe wrote:
> Never did see a good answer to this one so I played around with it until
> the following evolved. Uses the Math::Polynomial module to simplify the
> math - Gee! what a concept. Fred
>
> use strict;
> use warnings;
> use diagnostics;
> use Math::Polynomial;
>
> Math::Polynomial->verbose(1);
>
> my @Polys;
> my $Total = Math::Polynomial->new();
> my @zeros = (-1,-2,-3,-4,-5);
> my @weights = (1/24,-2/6,6/4,-24/6,120/24);
>
> for my $p (0..4) {
> my $Poly = Math::Polynomial->new(0,1); for my $i (0..4) {
> next if ($i == $p);
> my $Term = Math::Polynomial->new(1, $zeros[$i]); $Poly = $Poly *
> $Term;
> }
> push @Polys, $Poly;
> $Total += $Poly * $weights[$p];
> }
> $"="\n";
> print "\nPolynomials are:\n@Polys\n\n$Total\n";
Neat method, but if you'll notice, the polynomial wasn't the same for
each term. Not a big problem as with a bit of tweaking yours could have
accounted for that (it's a very regular pattern, the trick is just
allowing for a potentially very large set of terms). Actually, I've
figured it out since last I checked here. And I managed to completely
avoid using computer algebra systems or even symbolic variables. Here's
most of my code (@zork is the set of numbers either piped in or read from
a file, as this is a program to analyze patterns from outside):
chomp @zork;
for( my $i = 0; $i <= $#zork; $i++){
my $flag = 0;
my $thisy = Math::BigInt->new($zork[$i]); my $denominator =
Math::BigInt->new(1); for( my $j = 0; $j <= $#zork; $j++){
if ($j != $i){
$denominator->bmul($i - $j);
}}
my @numerator = (0);
for( my $k = 0; $k <= $#zork; $k++){
if ($k != $i){
push @numerator,(-$k);
}}
print "$#numerator\n\n";
for(my $l =0; $l<=$#numerator; $l++){
if($l == 0){
@poly1 = (0,1);
$l++;
}
@poly2 = ($numerator[$l],1);
my @neweq = (0);
for(my $m=0; $m<=$#poly1; $m++){
for(my $n=0; $n<=$#poly2; $n++){
$neweq[$m+$n] += ($poly1[$m] * $poly2[$n]); ##############
}}
@poly1 = @neweq;
}
}
for(my $o=0; $o<=$#poly1; $o++){
my $coef = frac("$thisy","$denominator"); $poly1[$o] *= ($coef);
}
}
for(my $p=0; $p<=$#poly1; $p++){
$equation[$p] += $poly1[$p];
}
}
shift @equation;
my $flag = 0;
for(my $q = $#equation; $q >= 0; $q--){
unless($equation[$q] == 0){
if (($flag != 0) && ($equation[$q] > 0)){
print "+";
}
print $equation[$q];
unless($q == 0){
print "x";
}
if($q > 1){
print "^$q";
}
print "\n\n";
$flag++;
}}
if ($flag == 0){
print "0\n";
}
Essentially, instead of making a (x-5)... I set an array to (-5,...). Then
I make two poly arrays, where the zero position will have the x^0 value,
the one position the x^1, etc. This works very well, until we get up to
high numbers (around expanding 18 binomials).
(If you have any questions as to what certain parts do, please ask,
because it might mean I've got something useless that I haven't caught.)
Anyway, if you'll notice the line of #'s, that's where the program's
breaking at over 17 terms. If somebody could help me out here, I either
need to implement BigInt's or Fraction's and I'm having trouble.
Thanks.
------------------------------
Date: Thu, 07 Oct 2004 20:15:37 GMT
From: "Fred Toewe" <ftoewe@austin.rr.com>
Subject: Re: Symbolic algebra
Message-Id: <Jth9d.2904$iC4.1696@fe2.texas.rr.com>
"Brian Troutwine" <goofy_headed_punk@msn.com> wrote in message
news:pan.2004.10.07.16.30.00.2475@msn.com...
> On Tue, 05 Oct 2004 23:41:34 +0000, Fred Toewe wrote:
>
> > Never did see a good answer to this one so I played around with it until
> > the following evolved. Uses the Math::Polynomial module to simplify the
> > math - Gee! what a concept. Fred
> >
> > use strict;
> > use warnings;
> > use diagnostics;
> > use Math::Polynomial;
> >
> > Math::Polynomial->verbose(1);
> >
> > my @Polys;
> > my $Total = Math::Polynomial->new();
> > my @zeros = (-1,-2,-3,-4,-5);
> > my @weights = (1/24,-2/6,6/4,-24/6,120/24);
> >
> > for my $p (0..4) {
> > my $Poly = Math::Polynomial->new(0,1); for my $i (0..4) {
> > next if ($i == $p);
> > my $Term = Math::Polynomial->new(1, $zeros[$i]); $Poly = $Poly *
> > $Term;
> > }
> > push @Polys, $Poly;
> > $Total += $Poly * $weights[$p];
> > }
> > $"="\n";
> > print "\nPolynomials are:\n@Polys\n\n$Total\n";
>
>
> Neat method, but if you'll notice, the polynomial wasn't the same for
> each term. Not a big problem as with a bit of tweaking yours could have
> accounted for that (it's a very regular pattern, the trick is just
> allowing for a potentially very large set of terms). Actually, I've
> figured it out since last I checked here. And I managed to completely
> avoid using computer algebra systems or even symbolic variables. Here's
> most of my code (@zork is the set of numbers either piped in or read from
> a file, as this is a program to analyze patterns from outside):
>
>
> chomp @zork;
>
> for( my $i = 0; $i <= $#zork; $i++){
> my $flag = 0;
> my $thisy = Math::BigInt->new($zork[$i]); my $denominator =
> Math::BigInt->new(1); for( my $j = 0; $j <= $#zork; $j++){
> if ($j != $i){
> $denominator->bmul($i - $j);
> }}
> my @numerator = (0);
> for( my $k = 0; $k <= $#zork; $k++){
> if ($k != $i){
> push @numerator,(-$k);
> }}
>
> print "$#numerator\n\n";
>
> for(my $l =0; $l<=$#numerator; $l++){
> if($l == 0){
> @poly1 = (0,1);
> $l++;
> }
>
> @poly2 = ($numerator[$l],1);
>
> my @neweq = (0);
>
> for(my $m=0; $m<=$#poly1; $m++){
> for(my $n=0; $n<=$#poly2; $n++){
> $neweq[$m+$n] += ($poly1[$m] * $poly2[$n]); ##############
> }}
> @poly1 = @neweq;
> }
> }
> for(my $o=0; $o<=$#poly1; $o++){
> my $coef = frac("$thisy","$denominator"); $poly1[$o] *= ($coef);
> }
> }
> for(my $p=0; $p<=$#poly1; $p++){
> $equation[$p] += $poly1[$p];
> }
> }
>
> shift @equation;
>
> my $flag = 0;
>
> for(my $q = $#equation; $q >= 0; $q--){
> unless($equation[$q] == 0){
> if (($flag != 0) && ($equation[$q] > 0)){
> print "+";
> }
> print $equation[$q];
>
> unless($q == 0){
> print "x";
> }
> if($q > 1){
> print "^$q";
> }
> print "\n\n";
> $flag++;
> }}
>
> if ($flag == 0){
> print "0\n";
> }
>
>
> Essentially, instead of making a (x-5)... I set an array to (-5,...). Then
> I make two poly arrays, where the zero position will have the x^0 value,
> the one position the x^1, etc. This works very well, until we get up to
> high numbers (around expanding 18 binomials).
>
> (If you have any questions as to what certain parts do, please ask,
> because it might mean I've got something useless that I haven't caught.)
> Anyway, if you'll notice the line of #'s, that's where the program's
> breaking at over 17 terms. If somebody could help me out here, I either
> need to implement BigInt's or Fraction's and I'm having trouble.
>
> Thanks.
I like my solution better even if it did solve the wrong problem.:<)
Cheers,
Fred
------------------------------
Date: Fri, 08 Oct 2004 01:19:27 +1000
From: Gregory Toomey <nospam@bigpond.com>
Subject: Re: Top 10 list algorithm
Message-Id: <2sl543F1lhp4oU1@uni-berlin.de>
Fatted wrote:
> Is there a better (faster) way of implementing my top_sort function?
Your algorithm looks like a sort ie O(n log n).
There is an algorithm that will find the nth sorted element in a list on
O(n) time, so finding the top 10 would be O(n) as well.
But of course I can't google a reference to the algorithm.
gtoomey
------------------------------
Date: 7 Oct 2004 16:06:28 GMT
From: anno4000@lublin.zrz.tu-berlin.de (Anno Siegel)
Subject: Re: Top 10 list algorithm
Message-Id: <ck3pi4$d62$1@mamenchi.zrz.TU-Berlin.DE>
John Bokma <postmaster@castleamber.com> wrote in comp.lang.perl.misc:
> Fatted <fatted@gmail.com> wrote in news:2skvbeF1ivps9U1@uni-berlin.de:
>
> > Anno Siegel wrote:
> >> Fatted <fatted@gmail.com> wrote in comp.lang.perl.misc:
> >>
> >>>Is there a better (faster) way of implementing my top_sort function?
> >>>(Creating a top 10 list of the highest numbers from a large set).
> >>>Or did I get lucky? :)
> >>
> >>
> >> The standard approach to selection of the top k of n elements is
> >> to use a heap.
> >>
> >
> > <snip>
> >
> > > If n is much larger than k, you can even use a simple list instead
> > > of a heap. You either sort it after each insertion, or insert each
> >> element in its place (straight insertion sort).
> >
> > What do you mean by a straight insertion sort?
>
> Since the list is sorted (because you insert in the right place) you can
> use binary search to find the elements location, O(log k), and insert it.
>
> Or I am wrong :-)
That's it.
It is not a good general-purpose sorting algorithm because insertion
means you must move n/2 elements on average to make room for a new
one, so the insertions alone make it an n**2 process.
On the other hand, if you must *keep* a list sorted while adding and
removing elements, it is practically your only choice. In this
particular case it isn't so bad because the list of top-k candidates
is short and remains short.
Anno
------------------------------
Date: 7 Oct 2004 17:48:52 GMT
From: John Bokma <postmaster@castleamber.com>
Subject: Re: Top 10 list algorithm
Message-Id: <Xns957B825AF9475castleamber@130.133.1.4>
anno4000@lublin.zrz.tu-berlin.de (Anno Siegel) wrote in
news:ck3pi4$d62$1@mamenchi.zrz.TU-Berlin.DE:
> John Bokma <postmaster@castleamber.com> wrote in comp.lang.perl.misc:
[ insertion sort ]
> It is not a good general-purpose sorting algorithm because insertion
> means you must move n/2 elements on average to make room for a new
> one, so the insertions alone make it an n**2 process.
Depends on your datastructure of course.
> On the other hand, if you must *keep* a list sorted while adding and
> removing elements, it is practically your only choice. In this
> particular case it isn't so bad because the list of top-k candidates
> is short and remains short.
Bubble sort might out perform normal quicksort if k is small, I guess.
--
John MexIT: http://johnbokma.com/mexit/
personal page: http://johnbokma.com/
Experienced programmer available: http://castleamber.com/
Happy Customers: http://castleamber.com/testimonials.html
------------------------------
Date: Thu, 07 Oct 2004 11:57:46 -0600
From: Eric Schwartz <emschwar@pobox.com>
Subject: Re: Top 10 list algorithm
Message-Id: <etooejeza05.fsf@wilson.emschwar>
anno4000@lublin.zrz.tu-berlin.de (Anno Siegel) writes:
> It is not a good general-purpose sorting algorithm because insertion
> means you must move n/2 elements on average to make room for a new
> one, so the insertions alone make it an n**2 process.
But n=10, so in this case, that doesn't matter much. If you're
developing a general top-N algorithm, that's a much bigger
consideration.
-=Eric
--
Come to think of it, there are already a million monkeys on a million
typewriters, and Usenet is NOTHING like Shakespeare.
-- Blair Houghton.
------------------------------
Date: 7 Oct 2004 21:05:44 GMT
From: anno4000@lublin.zrz.tu-berlin.de (Anno Siegel)
Subject: Re: Top 10 list algorithm
Message-Id: <ck4b38$o86$1@mamenchi.zrz.TU-Berlin.DE>
John Bokma <postmaster@castleamber.com> wrote in comp.lang.perl.misc:
> anno4000@lublin.zrz.tu-berlin.de (Anno Siegel) wrote in
> news:ck3pi4$d62$1@mamenchi.zrz.TU-Berlin.DE:
>
> > John Bokma <postmaster@castleamber.com> wrote in comp.lang.perl.misc:
>
> [ insertion sort ]
>
> > It is not a good general-purpose sorting algorithm because insertion
> > means you must move n/2 elements on average to make room for a new
> > one, so the insertions alone make it an n**2 process.
>
> Depends on your datastructure of course.
In general, yes. In this case, we want a compact list (at least of
pointers) to perform a binary search on.
> > On the other hand, if you must *keep* a list sorted while adding and
> > removing elements, it is practically your only choice. In this
> > particular case it isn't so bad because the list of top-k candidates
> > is short and remains short.
>
> Bubble sort might out perform normal quicksort if k is small, I guess.
Well, bubble sort avoids the overhead of insertion, it swaps elements.
Anno
------------------------------
Date: 7 Oct 2004 13:24:23 -0700
From: aymerphilippe@hotmail.com (Philippe Aymer)
Subject: Using a variable size with the repetition quantifier
Message-Id: <47971ff0.0410071224.3cc8b7d4@posting.google.com>
Hi all,
I'm looking at a PERL regex (if possible) that will be able to use a
repetition quantifier metachar, but the number of repetition is
unknown until runtime.
For example:
X3xyz...
the number 3 give me the number of "repetition" for the next chars
(length of string), something like:
/X(\d)(\w{\1})/
but \1 is not possible within {} the repetition quantifier.
Is there a way to use {} with the repetition number only known from
the regex ?
Thanks,
Phil.
------------------------------
Date: Thu, 7 Oct 2004 17:01:22 -0400
From: Jeff 'japhy' Pinyan <pinyaj@rpi.edu>
Subject: Re: Using a variable size with the repetition quantifier
Message-Id: <Pine.SOL.3.96.1041007165936.20047A-100000@vcmr-86.server.rpi.edu>
On 7 Oct 2004, Philippe Aymer wrote:
>I'm looking at a PERL regex (if possible) that will be able to use a
>repetition quantifier metachar, but the number of repetition is
>unknown until runtime.
>For example:
>
>X3xyz...
>
>the number 3 give me the number of "repetition" for the next chars
>(length of string), something like:
>
>/X(\d)(\w{\1})/
>
>but \1 is not possible within {} the repetition quantifier.
>
>Is there a way to use {} with the repetition number only known from
>the regex ?
Not exactly. You have to do it by some other means. Here are two
examples:
$str =~ /X(\d)/g and $str =~ /\G(\w{$1})/
and
$str =~ /X(\d)((??{ "\\w{$1}" }))/
--
Jeff "japhy" Pinyan % How can we ever be the sold short or
RPI Acacia Brother #734 % the cheated, we who for every service
Senior Dean, Fall 2004 % have long ago been overpaid?
RPI Corporation Secretary %
http://japhy.perlmonk.org/ % -- Meister Eckhart
------------------------------
Date: Thu, 7 Oct 2004 15:38:36 GMT
From: ced@bcstec.ca.boeing.com (Charles DeRykus)
Subject: Re: While query
Message-Id: <I580sC.6EC@news.boeing.com>
In article <slrncluflq.hv.abigail@alexandra.abigail.nl>,
Abigail <abigail@abigail.nl> wrote:
>A. Sinan Unur (usa1@llenroc.ude.invalid) wrote on MMMML September
>MCMXCIII in <URL:news:Xns9575F3378167Aasu1cornelledu@132.236.56.8>:
>}} Abigail <abigail@abigail.nl> wrote in
>}} news:slrnclrjgf.hv.abigail@alexandra.abigail.nl:
>}}
> ....
>
>Eh, no. The assignment is done in scalar context, and you can't have
>lists in scalar context. A list assignment in scalar context returns
>the number of elements on the right hand side of the assignment. And
>that, in this case, is always 1.
>
>This is way a trick like:
>
> my $count = () = $str =~ /foo/g;
>
>works.
>
Could this:
"A list assignment in scalar context returns the number of elements
on the right hand side of the assignment."
be better phrased:
A list assignment in scalar context can be special cased
to return the number of elements on the right hand side of
the assignment, which is why the trick below works:
my $count = () = (""); # count= 1
However an ordinary list assignment in scalar context returns
the final comma operand , e.g.
my $count = (1,2); # count = 2
?
--
Charles DeRykus
------------------------------
Date: Thu, 07 Oct 2004 17:03:26 GMT
From: "Paul Lalli" <mritty@gmail.com>
Subject: Re: While query
Message-Id: <yFe9d.1448$sa.842@trndny07>
"Charles DeRykus" <ced@bcstec.ca.boeing.com> wrote in message
news:I580sC.6EC@news.boeing.com...
>
> Could this:
>
> "A list assignment in scalar context returns the number of elements
> on the right hand side of the assignment."
>
> be better phrased:
>
> A list assignment in scalar context can be special cased
> to return the number of elements on the right hand side of
> the assignment, which is why the trick below works:
>
> my $count = () = (""); # count= 1
>
> However an ordinary list assignment in scalar context returns
> the final comma operand , e.g.
>
> my $count = (1,2); # count = 2
> ?
No, because this isn't a list assignment. By definition, a list
assignment is assigning something to a list. Nothing is being assigned
to a list here. More to the point, there is no "list" in that
expression. There is a scalar being assigned the return value of the
comma operator.
In the first example, the phrase "list assignment in scalar context"
refers to the return value of the assignment expression itself. All
expressions and statements return some sort of value, even those
expressions which themselves assign values.
Paul Lalli
------------------------------
Date: 6 Apr 2001 21:33:47 GMT (Last modified)
From: Perl-Users-Request@ruby.oce.orst.edu (Perl-Users-Digest Admin)
Subject: Digest Administrivia (Last modified: 6 Apr 01)
Message-Id: <null>
Administrivia:
#The Perl-Users Digest is a retransmission of the USENET newsgroup
#comp.lang.perl.misc. For subscription or unsubscription requests, send
#the single line:
#
# subscribe perl-users
#or:
# unsubscribe perl-users
#
#to almanac@ruby.oce.orst.edu.
NOTE: due to the current flood of worm email banging on ruby, the smtp
server on ruby has been shut off until further notice.
To submit articles to comp.lang.perl.announce, send your article to
clpa@perl.com.
#To request back copies (available for a week or so), send your request
#to almanac@ruby.oce.orst.edu with the command "send perl-users x.y",
#where x is the volume number and y is the issue number.
#For other requests pertaining to the digest, send mail to
#perl-users-request@ruby.oce.orst.edu. Do not waste your time or mine
#sending perl questions to the -request address, I don't have time to
#answer them even if I did know the answer.
------------------------------
End of Perl-Users Digest V10 Issue 7221
***************************************
