[28202] in Perl-Users-Digest
Perl-Users Digest, Issue: 9566 Volume: 10
daemon@ATHENA.MIT.EDU (Perl-Users Digest)
Sat Aug 5 14:05:56 2006
Date: Sat, 5 Aug 2006 11:05:06 -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 Sat, 5 Aug 2006 Volume: 10 Number: 9566
Today's topics:
Apache htaccess and perl robertutah@gmail.com
Re: Apache htaccess and perl <David.Squire@no.spam.from.here.au>
Re: Apache htaccess and perl robertutah@gmail.com
Re: Apache htaccess and perl <noreply@gunnar.cc>
Re: Apache htaccess and perl <David.Squire@no.spam.from.here.au>
Re: Apache htaccess and perl robertutah@gmail.com
Re: Apache htaccess and perl robertutah@gmail.com
Bit::Vector::Block_Read() returns too many bits <clydenospamorham@nospamorhamgetofftheline.freeservenospamorham.co.uk>
Re: Bit::Vector::Block_Read() returns too many bits <clydenospamorham@nospamorhamgetofftheline.freeservenospamorham.co.uk>
Re: Get name of user invoking program? <justin.0607@purestblue.com>
Re: Get name of user invoking program? <David.Squire@no.spam.from.here.au>
Re: Hash in inherited object fields not properly access anno4000@radom.zrz.tu-berlin.de
Re: Hash in inherited object fields not properly access <uri@stemsystems.com>
Re: Net::Telnet - Library Application <laff7430@bellsouth.net>
Re: Net::Telnet - Library Application <uri@stemsystems.com>
PERL Script to Load data into an oracle database bony_dev@yahoo.com
Re: PERL Script to Load data into an oracle database <David.Squire@no.spam.from.here.au>
Re: PERL Script to Load data into an oracle database bony_dev@yahoo.com
Re: PERL Script to Load data into an oracle database <David.Squire@no.spam.from.here.au>
Re: PERL Script to Load data into an oracle database <noreply@gunnar.cc>
Re: Pod::Parser not recognising "interior sequences" <news@lawshouse.org>
Re: Reading value from File and using in another file vedpsingh@gmail.com
Re: Recursion anno4000@radom.zrz.tu-berlin.de
Re: Recursion <koko_loko_0@yahoo.co.uk>
Re: Recursion <koko_loko_0@yahoo.co.uk>
Re: Recursion anno4000@radom.zrz.tu-berlin.de
Re: Recursion <bik.mido@tiscalinet.it>
scroll down menu with mechanize <nospam@home.com>
Digest Administrivia (Last modified: 6 Apr 01) (Perl-Users-Digest Admin)
----------------------------------------------------------------------
Date: 5 Aug 2006 10:38:22 -0700
From: robertutah@gmail.com
Subject: Apache htaccess and perl
Message-Id: <1154799502.153855.101280@m73g2000cwd.googlegroups.com>
Hi all
I have a apache running with mod_perl, it is set up with access-control
by a .htaccess-file with more than 1 user in it.
I need to get the username from the one that have logged in. How do I
do that ?
------------------------------
Date: Sat, 05 Aug 2006 18:42:28 +0100
From: David Squire <David.Squire@no.spam.from.here.au>
Subject: Re: Apache htaccess and perl
Message-Id: <eb2la4$j5m$1@gemini.csx.cam.ac.uk>
robertutah@gmail.com wrote:
> Hi all
>
> I have a apache running with mod_perl, it is set up with access-control
> by a .htaccess-file with more than 1 user in it.
>
> I need to get the username from the one that have logged in. How do I
> do that ?
>
It's a standard CGI environment variable: REMOTE_USER
You get access to environment variables in Perl via the %ENV hash.
DS
------------------------------
Date: 5 Aug 2006 10:49:04 -0700
From: robertutah@gmail.com
Subject: Re: Apache htaccess and perl
Message-Id: <1154800144.595042.159700@p79g2000cwp.googlegroups.com>
David Squire skrev:
> robertutah@gmail.com wrote:
> > Hi all
> >
> > I have a apache running with mod_perl, it is set up with access-control
> > by a .htaccess-file with more than 1 user in it.
> >
> > I need to get the username from the one that have logged in. How do I
> > do that ?
> >
>
> It's a standard CGI environment variable: REMOTE_USER
>
> You get access to environment variables in Perl via the %ENV hash.
>
>
> DS
For some resson REMOTE_USER i not in %ENV ?
------------------------------
Date: Sat, 05 Aug 2006 19:51:30 +0200
From: Gunnar Hjalmarsson <noreply@gunnar.cc>
Subject: Re: Apache htaccess and perl
Message-Id: <4jk43cF88jnfU1@individual.net>
robertutah@gmail.com wrote (to comp.lang.perl.modules):
> Hi all
[ the same question as was posted to clpmisc snipped ]
Please do not multi-post!! http://lipas.uwasa.fi/~ts/http/crospost.html
--
Gunnar Hjalmarsson
Email: http://www.gunnar.cc/cgi-bin/contact.pl
------------------------------
Date: Sat, 05 Aug 2006 18:55:57 +0100
From: David Squire <David.Squire@no.spam.from.here.au>
Subject: Re: Apache htaccess and perl
Message-Id: <eb2m3d$klb$1@gemini.csx.cam.ac.uk>
robertutah@gmail.com wrote:
> David Squire skrev:
>
>> robertutah@gmail.com wrote:
>>> Hi all
>>>
>>> I have a apache running with mod_perl, it is set up with access-control
>>> by a .htaccess-file with more than 1 user in it.
>>>
>>> I need to get the username from the one that have logged in. How do I
>>> do that ?
>>>
>> It's a standard CGI environment variable: REMOTE_USER
>>
>> You get access to environment variables in Perl via the %ENV hash.
>>
>>
>> DS
>
> For some resson REMOTE_USER i not in %ENV ?
>
It works for me. Note that it is only set for pages protected using
.htaccess files - which you say you are using.
Please show us some code so that we have some chance of diagnosing your
problem.
DS
------------------------------
Date: 5 Aug 2006 11:00:41 -0700
From: robertutah@gmail.com
Subject: Re: Apache htaccess and perl
Message-Id: <1154800840.955245.238750@h48g2000cwc.googlegroups.com>
Gunnar Hjalmarsson skrev:
> robertutah@gmail.com wrote (to comp.lang.perl.modules):
> > Hi all
>
> [ the same question as was posted to clpmisc snipped ]
>
> Please do not multi-post!! http://lipas.uwasa.fi/~ts/http/crospost.html
>
> --
> Gunnar Hjalmarsson
> Email: http://www.gunnar.cc/cgi-bin/contact.pl
yes Gunnar
Sorry for that
------------------------------
Date: 5 Aug 2006 11:02:39 -0700
From: robertutah@gmail.com
Subject: Re: Apache htaccess and perl
Message-Id: <1154800959.900079.25750@i3g2000cwc.googlegroups.com>
Gunnar Hjalmarsson skrev:
> robertutah@gmail.com wrote (to comp.lang.perl.modules):
> > Hi all
>
> [ the same question as was posted to clpmisc snipped ]
>
> Please do not multi-post!! http://lipas.uwasa.fi/~ts/http/crospost.html
>
> --
> Gunnar Hjalmarsson
> Email: http://www.gunnar.cc/cgi-bin/contact.pl
yes
Sorry
------------------------------
Date: Sat, 05 Aug 2006 14:43:18 GMT
From: "Clyde Ingram" <clydenospamorham@nospamorhamgetofftheline.freeservenospamorham.co.uk>
Subject: Bit::Vector::Block_Read() returns too many bits
Message-Id: <a82Bg.119552$sz1.84204@newsfe6-gui.ntli.net>
I use the Bit::Vector method "new_Hex" to construct a 24-bit vector from a
6-nybble hex string.
Method "Size" verifies it is 24-bits.
But, when I call method "Block_Read", I get back 32 bits. The 8 unexpected
bits are zeroes.
The "unpack" function verifies this.
I enclose a snippet of the Bit::Vector man page, for "Block_Read".
And there is a short program to illustrate the problem.
Can someone explain where the error is?
Thank-you in advance,
Clyde
1. Man page for Bit::Vector::Block_Read():
a.. $buffer = $vector->Block_Read();
This method allows you to export the contents of a given bit vector in one
block.
This is useful when you want to save the contents of a bit vector for later,
for instance in a file.
The advantage of this method is that it allows you to do so in the
compactest possible format, in binary.
The method returns a Perl string which contains an exact copy of the
contents of the given bit vector in "low order byte first" order.
See "syswrite" in perlfunc for how to write the data from this string to a
file.
2. Sample program exhibiting the problem:
#!/bin/perl -w
use strict;
use warnings;
use Bit::Vector;
warn "The Bit::Vector::Block_Read function returns too many bits. Here's
proof.\n\n";
my $hex_string = '012345';
my $lth_hex_string = length $hex_string;
my $nr_bits_hex_string = 4*$lth_hex_string; # 4 bits per nybble
warn "Call new_Hex to create a $nr_bits_hex_string bit vector from
hexadecimal string $hex_string\n";
my $vector = Bit::Vector->new_Hex( $nr_bits_hex_string, $hex_string );
my $vector_size_bits = $vector->Size();
warn "Size of bit vector in bits is $vector_size_bits\n";
warn "Bits set are " . $vector->to_Enum() . "\n";
warn "\nNow call Block_Read to read the bits from the vector to a
bitstream\n";
my $buffer = $vector->Block_Read();
my $lth_buffer_bytes = length $buffer;
my $lth_buffer_bits = 8*$lth_buffer_bytes;
warn "Block_Read of vector returned $lth_buffer_bits bits. Expected
$vector_size_bits\n";
my $unpacked_buffer = unpack("b*", $buffer);
my $lth_unpacked_buffer = length $unpacked_buffer;
warn "unpacked buffer has $lth_unpacked_buffer chars: $unpacked_buffer\n";
------------------------------
Date: Sat, 05 Aug 2006 14:53:40 GMT
From: "Clyde Ingram" <clydenospamorham@nospamorhamgetofftheline.freeservenospamorham.co.uk>
Subject: Re: Bit::Vector::Block_Read() returns too many bits
Message-Id: <Uh2Bg.119581$sz1.73903@newsfe6-gui.ntli.net>
I should have pointed out that I am running:
- ActiveState Perl 5.8.8 build 817
- Bit::Vector 6.3
on Windows XP Professional, SP2
------------------------------
Date: Sat, 05 Aug 2006 12:16:55 -0000
From: Justin C <justin.0607@purestblue.com>
Subject: Re: Get name of user invoking program?
Message-Id: <slrned931m.5d2.justin.0607@moonlight.purestblue.com>
On 2006-08-04, Glenn Jackman <glennj@ncf.ca> wrote:
> At 2006-08-04 08:18AM, Justin C <justin.0511@purestblue.com> wrote:
>>
>> Probably an FAQ. I need to get the user name of who has invoked the
>> program. perldoc -q user doesn't show anything relevant, but perldoc -q
>> uid gives $< ... which gives the numerical id of the user. I need to get
>> the name from this. Is there a straightforward way of doing this or do I
>> have to grep /etc/passwd? ... or is there another way?
>
> my $name = getpwuid $<
Bingo! Great thanks.
Just to confirm, getpwuid $< returns a list, and the rest of the list is
ignored because I've not asked perl to do anything with it? If I'd used:
my @name = getpwuid $<
instead I'd have had a whole list of stuff, where $name[0] is the name?
I suppose I should really try this for myself...
Thanks for the reply.
Justin.
--
Justin C, by the sea.
------------------------------
Date: Sat, 05 Aug 2006 13:58:05 +0100
From: David Squire <David.Squire@no.spam.from.here.au>
Subject: Re: Get name of user invoking program?
Message-Id: <eb24kt$i3f$1@gemini.csx.cam.ac.uk>
Justin C wrote:
> On 2006-08-04, Glenn Jackman <glennj@ncf.ca> wrote:
>> At 2006-08-04 08:18AM, Justin C <justin.0511@purestblue.com> wrote:
>>>
>>> Probably an FAQ. I need to get the user name of who has invoked the
>>> program. perldoc -q user doesn't show anything relevant, but perldoc -q
>>> uid gives $< ... which gives the numerical id of the user. I need to get
>>> the name from this. Is there a straightforward way of doing this or do I
>>> have to grep /etc/passwd? ... or is there another way?
>> my $name = getpwuid $<
>
> Bingo! Great thanks.
>
> Just to confirm, getpwuid $< returns a list, and the rest of the list is
> ignored because I've not asked perl to do anything with it?
Not quite. What getpwuid returns depends on the context in which it is
called. You called it in scalar context. See perldoc -f getpwuid.
If it had returned a list, in scalar context you would have got the last
element of the list, not the first.
> If I'd used:
> my @name = getpwuid $<
> instead I'd have had a whole list of stuff, where $name[0] is the name?
Yes, because this time it is called in list context. In list context it
returns a list where the name is the first element.
> I suppose I should really try this for myself...
Or read the docs...
DS
------------------------------
Date: 5 Aug 2006 12:31:48 GMT
From: anno4000@radom.zrz.tu-berlin.de
Subject: Re: Hash in inherited object fields not properly accessible (5.8.6, RH 7.3)
Message-Id: <4jjhdkF8d4b5U1@news.dfncis.de>
Uri Guttman <uri@stemsystems.com> wrote in comp.lang.perl.misc:
> >>>>> "P" == PeterSShenkin <shenkin@gmail.com> writes:
> P> Uri Guttman wrote:
[...]
> P> Is there by any chance some trick that one can use to obtain the
> P> current state of the iterator without actually iterating?
>
> not from the level of perl code AFAIK.
Devel::Peek::Dump shows the state of a hash iterator.
To track this down you could tie the hash to a derivative of Tie::StdHash
that shouts (eg Carp::Confess) on FIRSTKEY and NEXTKEY. That should
catch any unexpected (and expected) iterations.
Anno
------------------------------
Date: Sat, 05 Aug 2006 12:49:13 -0400
From: Uri Guttman <uri@stemsystems.com>
Subject: Re: Hash in inherited object fields not properly accessible (5.8.6, RH 7.3)
Message-Id: <x7lkq3p1py.fsf@mail.sysarch.com>
>>>>> "a" == anno4000 <anno4000@radom.zrz.tu-berlin.de> writes:
a> Uri Guttman <uri@stemsystems.com> wrote in comp.lang.perl.misc:
>> >>>>> "P" == PeterSShenkin <shenkin@gmail.com> writes:
P> Uri Guttman wrote:
a> [...]
P> Is there by any chance some trick that one can use to obtain the
P> current state of the iterator without actually iterating?
>>
>> not from the level of perl code AFAIK.
a> Devel::Peek::Dump shows the state of a hash iterator.
i am sure that module does xs stuff. so that doesn't contradict what i
said which was from the perl level. i should have said pure perl
level. :)
a> To track this down you could tie the hash to a derivative of
a> Tie::StdHash that shouts (eg Carp::Confess) on FIRSTKEY and
a> NEXTKEY. That should catch any unexpected (and expected)
a> iterations.
that is a good idea.
uri
--
Uri Guttman ------ uri@stemsystems.com -------- http://www.stemsystems.com
--Perl Consulting, Stem Development, Systems Architecture, Design and Coding-
Search or Offer Perl Jobs ---------------------------- http://jobs.perl.org
------------------------------
Date: Sat, 05 Aug 2006 10:49:14 -0400
From: Carl Lafferty <laff7430@bellsouth.net>
Subject: Re: Net::Telnet - Library Application
Message-Id: <td2Bg.9407$l7.5529@bignews5.bellsouth.net>
robic0 wrote:
>
> I would consider myself an expert on such items. Would your company like
> to contract to me for definative hard solution?
> Would be the best thing.
>
Sorry for taking so long to get back to this. We are good for right now.
I appreciate your help.
------------------------------
Date: Sat, 05 Aug 2006 12:54:20 -0400
From: Uri Guttman <uri@stemsystems.com>
To: Carl Lafferty <laff7430@bellsouth.net>
Subject: Re: Net::Telnet - Library Application
Message-Id: <x7hd0rp1hf.fsf@mail.sysarch.com>
>>>>> "CL" == Carl Lafferty <laff7430@bellsouth.net> writes:
CL> robic0 wrote:
>> I would consider myself an expert on such items. Would your company
>> like
>> to contract to me for definative hard solution?
>> Would be the best thing.
>>
CL> Sorry for taking so long to get back to this. We are good for
CL> right now.
CL> I appreciate your help.
you should know that no one here considers him an expert on perl. just
scanning google for some of his vitriolic, abusive and wrong posts will
show you that. that you don't need any perl help right now saved you the
trouble of actually dealing with him. and if you do need perl help,
jobs.perl.org is the place to go.
uri
--
Uri Guttman ------ uri@stemsystems.com -------- http://www.stemsystems.com
--Perl Consulting, Stem Development, Systems Architecture, Design and Coding-
Search or Offer Perl Jobs ---------------------------- http://jobs.perl.org
------------------------------
Date: 5 Aug 2006 03:55:30 -0700
From: bony_dev@yahoo.com
Subject: PERL Script to Load data into an oracle database
Message-Id: <1154775330.780550.127030@i3g2000cwc.googlegroups.com>
Hello,
i am trying to write a perl script to load data in oracle from windows.
has anybody doe this before..please guide me on how to do this..what
modules to use etc..thanks
-bony
------------------------------
Date: Sat, 05 Aug 2006 12:11:31 +0100
From: David Squire <David.Squire@no.spam.from.here.au>
Subject: Re: PERL Script to Load data into an oracle database
Message-Id: <eb1ud3$6c6$1@gemini.csx.cam.ac.uk>
bony_dev@yahoo.com wrote:
> Hello,
>
> i am trying to write a perl script to load data in oracle from windows.
> has anybody doe this before..
Yes.
> please guide me on how to do this..what
> modules to use etc..thanks
You need to learn how to use CPAN. Go to http://search.cpan.org/ and
search for 'oracle'. See the first result.
DS
------------------------------
Date: 5 Aug 2006 08:10:12 -0700
From: bony_dev@yahoo.com
Subject: Re: PERL Script to Load data into an oracle database
Message-Id: <1154790612.435045.114290@i3g2000cwc.googlegroups.com>
can you please provide me with a sample code..i am just trying to gain
more knowledge on this as i am a newbie ..thanks a lot..
-Bony
David Squire wrote:
> bony_dev@yahoo.com wrote:
> > Hello,
> >
> > i am trying to write a perl script to load data in oracle from windows.
> > has anybody doe this before..
>
> Yes.
>
> > please guide me on how to do this..what
> > modules to use etc..thanks
>
> You need to learn how to use CPAN. Go to http://search.cpan.org/ and
> search for 'oracle'. See the first result.
>
>
> DS
------------------------------
Date: Sat, 05 Aug 2006 17:08:58 +0100
From: David Squire <David.Squire@no.spam.from.here.au>
Subject: Re: PERL Script to Load data into an oracle database
Message-Id: <eb2fqq$9ce$1@gemini.csx.cam.ac.uk>
bony_dev@yahoo.com wrote:
[top-posting corrected. Please don't do that]
> David Squire wrote:
>> bony_dev@yahoo.com wrote:
>>> Hello,
>>>
>>> i am trying to write a perl script to load data in oracle from windows.
>>> has anybody doe this before..
>> Yes.
>>
>>> please guide me on how to do this..what
>>> modules to use etc..thanks
>> You need to learn how to use CPAN. Go to http://search.cpan.org/ and
>> search for 'oracle'. See the first result.
>>
> can you please provide me with a sample code..i am just trying to gain
> more knowledge on this as i am a newbie ..thanks a lot..
That is not how this works. Read the posting guidelines for the group.
You make an attempt, and then post here to get help with your code.
People here will help you with your code, not write it for you.
For a start, the DBD::Oracle module documentation (that you should have
found following my earlier hint) contains code examples.
DS
------------------------------
Date: Sat, 05 Aug 2006 18:13:00 +0200
From: Gunnar Hjalmarsson <noreply@gunnar.cc>
Subject: Re: PERL Script to Load data into an oracle database
Message-Id: <4jjualF8ch4nU1@individual.net>
bony_dev@yahoo.com wrote:
> David Squire wrote:
>> bony_dev@yahoo.com wrote:
>>> please guide me on how to do this..what
>>> modules to use etc..thanks
>>
>> You need to learn how to use CPAN. Go to http://search.cpan.org/ and
>> search for 'oracle'. See the first result.
>
> can you please provide me with a sample code..i am just trying to gain
> more knowledge on this as i am a newbie
You seem to be the kind of guy who wants to minimize your own effort at
others' expense. That attitude is not appreciated here; you may want to
try the beginners mailing list instead.
http://lists.cpan.org/showlist.cgi?name=beginners
--
Gunnar Hjalmarsson
Email: http://www.gunnar.cc/cgi-bin/contact.pl
------------------------------
Date: Sat, 05 Aug 2006 08:14:19 +0100
From: Henry Law <news@lawshouse.org>
Subject: Re: Pod::Parser not recognising "interior sequences"
Message-Id: <1154762060.14323.0@proxy00.news.clara.net>
Sisyphus wrote:
> Looking at the Pod::Parser source, 'textblock' calls 'interpolate', which
> calls 'parse_text', which calls 'interior_sequence'. (At least, that appears
> to be *one* pathway to the calling of 'interior_sequence'.)
> But there's nothing in HTMLDoc.pm that's going to lead to
There is now, and it works perfectly. Thank you for that. The answer,
of course, was staring me in the face but it often takes someone else to
point it out.
--
Henry Law <>< Manchester, England
------------------------------
Date: 5 Aug 2006 10:59:21 -0700
From: vedpsingh@gmail.com
Subject: Re: Reading value from File and using in another file
Message-Id: <1154800761.462191.255540@n13g2000cwa.googlegroups.com>
Hi,
Based on the suggestions, I made few changes.
First i thought to do the read and write in file independently.
Writting in file is not a problem.
But I am not able to do reading from a file . Please give your comment.
I am a beginer in perl.
Thanks
--------------------------------
use strict;
use warnings;
my $data_file = 'data.txt';
($data_file) = @ARGV;
open my $read_handle, '<', $data_file or die "Cannot open '$data_file':
";
{
print "@ARGV";
}
close ($read_handle);
----------------------------------
------Error message I am getting
C:\Perl\Myperl>perl read_NOT_DONE.pl
Use of uninitialized value in open at read_NOT_DONE.pl line 5.
Use of uninitialized value in concatenation (.) or string at
read_NOT_DONE.pl li
ne 5.
Cannot open '': at read_NOT_DONE.pl line 5.
------------------------------
Date: 5 Aug 2006 11:01:08 GMT
From: anno4000@radom.zrz.tu-berlin.de
Subject: Re: Recursion
Message-Id: <4jjc3kF87uplU1@news.dfncis.de>
kokolo <koko_loko_0@yahoo.co.uk> wrote in comp.lang.perl.misc:
>
>
> > I found an implementation without sub-arrays:
> > http://www.thescripts.com/forum/thread49795.html
> > changedit so it works and tried it for 99999 elements.
> > It did it in13 seconds while my code does it in 14.
> > How quick it can get at all?
> >
> > kokolo
> >
> I won't spam on this subject any more. I ckecked out a little and realized
> that the code from the link above is
> just a re-written C-code from
> http://linux.wku.edu/~lamonml/algor/sort/quick.html
>
> It doesn't have any Perl flavor and is much harder to read.
> Yes, it's faster but only 1 sec for 100000 elements (13 to 14). I like this
> one much more for the flavor (push, pop) and readibility:
> _____________________________________________________-
> print "Enter the number of elements to sort: \n";
> chomp($size=<STDIN>);
> foreach (1..$size) {push @array,int(rand(1000))}
>
> $start=time();
> @array= qs(@array);
>
> #print "The sorted array:\n @array \n";
> print "$size elementsQuickSorted in ,",time()-$start," seconds.\n";
>
> sub qs {
> my @array=@_;
> my $pivot=$#array;
> my @left;
> my @right;
>
> for ($i=0;$i<$pivot;$i++){
>
> if ($red[$i]<=$red[$pivot]){ unshift @left,$red[$i]}
> else { push @right,$red[$i]}
> }
>
> if ($#left>0){@left=qs(@left)}
> if ($#right>0){@right=qs(@right)}
>
> push @left,($red[$pivot],@right);
> return @left;
> }
Oh puleeze! You posted this code without ever checking it. It isn't
strict-safe (@red and $i are undeclared), and it doesn't work (@array
and @red should be the same arrays). The way it is it returns an
array of undef's instead of a sorted list. It is annoying to have
to spend time correcting trivial coding mistakes, time *you* should
have spent before posting.
The code still makes copies (@left, @right) of partial lists and
glues them together after sorting. The hallmark of standard quicksort
implementations is that they sort *in place*, moving elements around
in the original list.
> ____________________________________________________________________________
> ___________
> I appreciate all advices, those about referencing in particular but I'd
> really appreciate if somebody
> can help me find how quick Perl can get with quicksort.
> C does 100000 elements in less than a second. I'm aware Perl has to be
> slower and that there are builtins,etc. but I'm not asking for general
> advices.
> C-like code does it in 13.
There's nothing particularly C-like in the implementation.
> I believe this is far from Perl limit.
Okay, here is an implementation. It is not highly optimized. In
particular it uses an auxiliary sub partition() to do the pivot
operation. That is because I found that step difficult to get
right, so I isolated it.
sub qs {
my @a = @_;
qs_recurs( \ @a, 0, $#_);
@a;
}
sub qs_recurs {
my ( $a, $from, $to) = @_;
return unless $from < $to;
my $mid = partition( $a, $a->[ $from], $from, $to);
@$a[ $from, $mid] = @$a[ $mid, $from]; # move pivot to middle
qs_recurs( $a, $from, $mid - 1); # sort lower part
qs_recurs( $a, $mid + 1, $to); # sort upper part
}
sub partition {
my ( $a, $pivot, $from, $to) = @_;
while ( $from <= $to ) {
if ( $a->[ $from] > $pivot ) {
@$a[ $from, $to] = @$a[ $to, $from];
-- $to;
} else {
++ $from;
}
}
return $to;
}
Anno
------------------------------
Date: Sat, 5 Aug 2006 13:39:54 +0100
From: "kokolo" <koko_loko_0@yahoo.co.uk>
Subject: Re: Recursion
Message-Id: <eb23it$kjr$1@news.al.sw.ericsson.se>
<anno4000@radom.zrz.tu-berlin.de> wrote in message
news:4jjc3kF87uplU1@news.dfncis.de...
> Oh puleeze! You posted this code without ever checking it. It isn't
> strict-safe (@red and $i are undeclared), and it doesn't work (@array
> and @red should be the same arrays). The way it is it returns an
> array of undef's instead of a sorted list. It is annoying to have
> to spend time correcting trivial coding mistakes, time *you* should
> have spent before posting.
I hate myself for quick-posting. Ihad several versions for testing purposes
and copied a bad one. I'm really sorry,
I'm wasting other people's time that way.
> The code still makes copies (@left, @right) of partial lists and
> glues them together after sorting. The hallmark of standard quicksort
> implementations is that they sort *in place*, moving elements around
> in the original list.
> Okay, here is an implementation. It is not highly optimized. In
> particular it uses an auxiliary sub partition() to do the pivot
> operation. That is because I found that step difficult to get
> right, so I isolated it.
>
> sub qs {
> my @a = @_;
> qs_recurs( \ @a, 0, $#_);
> @a;
> }
>
> sub qs_recurs {
> my ( $a, $from, $to) = @_;
> return unless $from < $to;
> my $mid = partition( $a, $a->[ $from], $from, $to);
> @$a[ $from, $mid] = @$a[ $mid, $from]; # move pivot to middle
> qs_recurs( $a, $from, $mid - 1); # sort lower part
> qs_recurs( $a, $mid + 1, $to); # sort upper part
> }
>
> sub partition {
> my ( $a, $pivot, $from, $to) = @_;
> while ( $from <= $to ) {
> if ( $a->[ $from] > $pivot ) {
> @$a[ $from, $to] = @$a[ $to, $from];
> -- $to;
> } else {
> ++ $from;
> }
> }
> return $to;
> }
>
> Anno
Very, very nice. The sub partition() is the nicest part and is the crucial
improvement.
I was struggling with that part, I didn't want a messy code and I chose to
go with sub-arrays to keep it simple.
Your solution is both elegant and efficient. 100000 in 3 sec.
Thanks a lot for a very educational solution.
kokolo
------------------------------
Date: Sat, 5 Aug 2006 13:49:38 +0100
From: "kokolo" <koko_loko_0@yahoo.co.uk>
Subject: Re: Recursion
Message-Id: <eb2455$kqt$1@news.al.sw.ericsson.se>
> xhoster@gmail.com wrote:
> >
> > That said, your program does seem to be N**2, rather than NlogN, and I
> > see no reason that it should be. Even with all the badness built in, it
> > should still be NlogN, or maybe N(logN)**2, not N**2. I don't quite get
> > it.
>
> OK, I solved the problem. Your sort has a bad worst case performance (on
> an array that is already sorted, reverse sorted, all ties, etc.) because
it
> falls into a N**2 step of just picking off one element per recursion.
> Because of the way you generate data, you have only 1000 distinct values
> and therefore you have a huge number of ties. Once all those ties come
> together into a subarray, sorting that subarray has bad performance. That
> happens over and over again.
>
> I took out the "int" from your data generation, and bang, things got much
> better.
>
> Xho
Now, that was remarkable.
I appreciate a lot the fact you actually tested the code and gave it some
thought and found what was the problem.
Now it looks like N log N and is pretty fast.
thx again
kokolo
------------------------------
Date: 5 Aug 2006 13:52:15 GMT
From: anno4000@radom.zrz.tu-berlin.de
Subject: Re: Recursion
Message-Id: <4jjm4fF89827U1@news.dfncis.de>
kokolo <koko_loko_0@yahoo.co.uk> wrote in comp.lang.perl.misc:
>
> <anno4000@radom.zrz.tu-berlin.de> wrote in message
> news:4jjc3kF87uplU1@news.dfncis.de...
> > Okay, here is an implementation. It is not highly optimized. In
> > particular it uses an auxiliary sub partition() to do the pivot
> > operation. That is because I found that step difficult to get
> > right, so I isolated it.
[snipped, revised version below]
> Very, very nice. The sub partition() is the nicest part and is the crucial
> improvement.
It is also the part that has a serious design flaw. Two, really.
It takes an arbitrary number for the pivot, but quicksort only
works when the pivot is a known element of the unsorted array.
Also, the code in qs_recurs() relies on the fact that the pivot
element won't change its position at the beginning of the array
during partitioning. That's difficult to grant in general and
also nails the choice of the pivot to being the first element.
> I was struggling with that part, I didn't want a messy code and I chose to
> go with sub-arrays to keep it simple.
> Your solution is both elegant and efficient. 100000 in 3 sec.
> Thanks a lot for a very educational solution.
Here is a revised version. The pivot *index* can now be chosen
arbitrarily in the call to partition(), at the cost of an additional
exchange. All moving-about of elements happens in partition(),
qs_recurs() only organizes the calls by choosing the pivot index and
the sub-array limits.
sub qs {
my @a = @_;
qs_recurs( \ @a, 0, $#_);
@a;
}
sub qs_recurs {
my ( $a, $from, $to) = @_;
return unless $from < $to;
my $i_pivot = ($from + $to)/2; # anything between $from and $to
my $mid = partition( $a, $from, $i_pivot, $to);
qs_recurs( $a, $from, $mid - 1);
qs_recurs( $a, $mid + 1, $to);
}
sub partition {
my ( $a, $from, $i_pivot, $to) = @_;
# put pivot in first position (it will remain there)
@$a[ $from, $i_pivot] = @$a[ $i_pivot, $from];
$i_pivot = $from; # save for later
my $pivot = $a->[ $i_pivot];
while ( $from <= $to ) {
if ( $a->[ $from] > $pivot ) {
@$a[ $from, $to] = @$a[ $to, $from];
-- $to;
} else {
++ $from;
}
}
# move pivot element in the middle
@$a[ $i_pivot, $to] = @$a[ $to, $i_pivot];
return $to;
}
As mentioned, this isn't particularly optimized, and the change doesn't
make it faster. Obvious micro-optimizations are
-- avoid unnecessary recursive calls:
qs_recurs( $a, $from, $mid - 1) if $from < $mid - 1; # etc
-- avoid unnecessary exchange operations
@$a[ $from, $to] = @$a[ $to, $from] if $from != $to; # etc
__ inline partition() into qs_recurs()
None of these will make a dramatic difference, and each should be
tried and benchmarked individually. The second one in particular
could be counter-productive.
Anno
------------------------------
Date: 5 Aug 2006 18:38:01 +0200
From: Michele Dondi <bik.mido@tiscalinet.it>
Subject: Re: Recursion
Message-Id: <u9i9d25vhpcnapqde2rie1oohoguerp274@4ax.com>
On Fri, 4 Aug 2006 21:39:46 +0100, "kokolo" <koko_loko_0@yahoo.co.uk>
wrote:
> I'll re-write it to work with in-place swapping and compare it. When I
>wrote the first version, it looked very nice
>and the faster it gets the uglier it is :)
There may be a general lesson in this, don't you guess? :-)
Michele
--
{$_=pack'B8'x25,unpack'A8'x32,$a^=sub{pop^pop}->(map substr
(($a||=join'',map--$|x$_,(unpack'w',unpack'u','G^<R<Y]*YB='
.'KYU;*EVH[.FHF2W+#"\Z*5TI/ER<Z`S(G.DZZ9OX0Z')=~/./g)x2,$_,
256),7,249);s/[^\w,]/ /g;$ \=/^J/?$/:"\r";print,redo}#JAPH,
------------------------------
Date: Sat, 05 Aug 2006 17:48:29 GMT
From: "Nospam" <nospam@home.com>
Subject: scroll down menu with mechanize
Message-Id: <NR4Bg.120016$sz1.73169@newsfe6-gui.ntli.net>
can someone clarify something in the www::mechanize module, to select a
field I understand it would something similar to $mech->field('nameoffield,
$value); however suppose the selection was a scroll down menu? with
javascript : something like <script scr=...
JSActions=[[variable,"response1"],[variable2,"response2"]</script> ?
------------------------------
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 9566
***************************************
