[8452] in Perl-Users-Digest
Perl-Users Digest, Issue: 2069 Volume: 8
daemon@ATHENA.MIT.EDU (Perl-Users Digest)
Wed Mar 11 05:07:25 1998
Date: Wed, 11 Mar 98 02:00:39 -0800
From: Perl-Users Digest <Perl-Users-Request@ruby.OCE.ORST.EDU>
To: Perl-Users@ruby.OCE.ORST.EDU (Perl-Users Digest)
Perl-Users Digest Wed, 11 Mar 1998 Volume: 8 Number: 2069
Today's topics:
Re: Anybody want a small puzzle? (M.J.T. Guy)
Re: Are There Any Snazzy Perl Editors for Windows? (Thomas Rock)
Re: Are There Any Snazzy Perl Editors for Windows? <tkho@technologist.com>
Re: Are There Any Snazzy Perl Editors for Windows? (Derek Jones)
dumb question... <ndufort@cadre.sjsu.edu>
Re: Getting date on an NT machine (Vincent Fatica)
Re: Getting date on an NT machine (Vincent Fatica)
interested question <matteo@gate2000.com>
multiple blank lines into one (SenimotBor)
Re: Need help with programming project (Devin L. Ganger)
Re: nslookup? <kwaddell@gate.net>
Re: Performance Question <rjk@coos.dartmouth.edu>
Re: problem with mkdir() and permissions <qdtcall@esb.ericsson.se>
Problems running scripts in Win95 <mpriatel@chat.carleton.ca>
Re: Retriving last item in array. <rick@slicks.demon.co.uk>
Re: Speed of sort routine vs. one-by-one compare (123 (Ken Fox)
Re: Speed of sort routine vs. one-by-one compare (123 (Abigail)
Re: Speed of sort routine vs. one-by-one compare (123 (Abigail)
Re: Speed of sort routine vs. one-by-one compare (123 (Abigail)
Re: Speed of sort routine vs. one-by-one compare (123 <uri@sysarch.com>
Splitting long "sprintf" lines? (Vincent Fatica)
Re: Splitting long "sprintf" lines? (Craig Berry)
Digest Administrivia (Last modified: 8 Mar 97) (Perl-Users-Digest Admin)
----------------------------------------------------------------------
Date: 11 Mar 1998 05:18:31 GMT
From: mjtg@cus.cam.ac.uk (M.J.T. Guy)
Subject: Re: Anybody want a small puzzle?
Message-Id: <6e56r7$klv$1@lyra.csx.cam.ac.uk>
In article <6deqp7$pd0$1@nnrp1.dejanews.com>, <SPC@popstar.com> wrote:
> $startmarker="<!--Begin $file-->";
> if ($FILES[$count] =~ $startmarker ){
Beware of substituting variables like $file into regular expressions.
Have you allowed for the possibility that $file may contain regex special
characters? It's almost always a good idea to protect them with
\Q ... \E like so:
if ($FILES[$count] =~ /<!--Begin \Q$file\E-->/ ){
Mike Guy
------------------------------
Date: Tue, 10 Mar 1998 19:34:31 -0600
From: thomas@x-tekcorp.com (Thomas Rock)
Subject: Re: Are There Any Snazzy Perl Editors for Windows?
Message-Id: <MPG.f6fa62513fb326098968e@news.anet-chi.com>
[This followup was posted to comp.lang.perl.misc and a copy was sent to
the cited author.]
I found UltraEdit to work very nicely. It has all the whiz-bang features
you would want - and, as an added benefit, its *not* vi-like (oooohhhhh,
flame bait!).
Check it out at: www.ultraedit.com
In article <6e1hdh$1lgo$1@ausnews.austin.ibm.com>, rkturner@us.ibm.com
says...
> Are there any text editors for windows that can recognize perl syntax and
> color code and such?
>
>
>
------------------------------
Date: Tue, 10 Mar 1998 23:27:13 -0800
From: Tommy <tkho@technologist.com>
To: scott@softbase.com
Subject: Re: Are There Any Snazzy Perl Editors for Windows?
Message-Id: <35063CD1.1B400EB3@technologist.com>
May be I don't know much about Multi-Edit, or Perl element is an extra,
my Multi-Edit does not support Perl tag. However, it support BASIC, C,
COBOL, and HTML. If you have the Perl's Tag file, could you send it to
me. Thanks.
BTW, I agree Multi-Edit is very well-developed authoring program. Its
"Find and Replace", "Line Numbering", "Hex Mode", and "File Comparing"
functions are superb. You may not find these function on other editors.
scott@softbase.com wrote:
>
> Keith Turner (rkturner@us.ibm.com) wrote:
> > Are there any text editors for windows that can recognize perl syntax and
> > color code and such?
>
> Well, there's GNU Emacs. It's the best thing going for Perl on Windows.
>
> Multi-Edit is a great commercial editor that supports Perl syntax
> highlighting. It has a very Windows look and feel, if you're not
> used to Emacs. It also does really great printing, something
> Emacs doesn't.
>
> For more on Windows editors, check out www.skwc.com/essent/cyberreviews.html
> and look for the text editor review.
>
> Scott
--
Tommy Ho
---------------------------------------------------------------
Email: tkho@technologist.com
URL: http://www.geocities.com/ResearchTriangle/Lab/4670/
WebPager: http://wwp.mirabilis.com/4763891
Virtual Network and Conference available on Request
------------------------------
Date: Wed, 11 Mar 1998 07:26:19 +0100 (GMT)
From: D.G.Jones@scuna.dircon.co.uk (Derek Jones)
Subject: Re: Are There Any Snazzy Perl Editors for Windows?
Message-Id: <m0yCfu8-000481C@scuna.dircon.co.uk>
Hello,
As the author of Learning Tree's Perl course I can confirm that it's
fte. It does colour syntax highlighting for many languages, including
Perl, and the neat thing is it's ported to X11 under UNIX as well giving
us at least one (of three, including vi and emacs), cross-platform editors
in the classes.
Personally, I am a vi die-hard and have been for many years, but I do
find the Perl colour syntax highlighting useful in emacs. Soooo, I use
emacs in vi-emulation mode. There! The best of both worlds. . . 8-)
(On a 1280x1024 screen you can just about get two full page buffers
open side-by-side in emacs under Windows. Better of course if using X
since you have finer control over the fonts.)
BTW, if anyone wants more info. on the Learning Tree Perl course, please
feel free to contact me for more detailed technical input, or dial
1-800-THE-TREE in the US and 0800 282 353 in the UK for a brochure.
In addition, you might want to check out my Web site below (.sig) for
an Advanced Perl 5 course for which the Learning Tree one provides an
excellent base.
Anyway, the URL for fte is:
http://ixtas.fri.uni-lj.si/~markom/fte
(at least in the docs I have.)
It's distributed under both Artistic and GNU licences, just like Perl.
Kind regards
Derek Jones
------------------------------------------------------------------------------
Derek Jones SCUNA Computer Consultancy
16 Edgedale Road, Sheffield
Computer Consultant S7 2BQ UK
SCUNA (Systems,C,UNIX,Networking,Advice) Tel: +44 (0)114 255 5524
Email: D.G.Jones@scuna.dircon.co.uk FAX: +44 (0)114 296 7846
http://ourworld.compuserve.com/homepages/scuna Mobile: +44 (0)468 300 025
------------------------------------------------------------------------------
"You're from *Cyberspace*?" "No I'm from Sheffield, I only work in Cyberspace"
------------------------------
Date: Wed, 11 Mar 1998 00:47:33 -0800
From: ndufort <ndufort@cadre.sjsu.edu>
Subject: dumb question...
Message-Id: <35064FA5.167E@cadre.sjsu.edu>
hi everybody,
i had psoted a first dumb question for a current art project using PERL,
and i have a new one.
i have been able to write the script i want, and it works (which made me
pretty glad, since i don't know PERL at all). but now i would like to
attach my script to one of the hyperlinks on the web page i did for the
assignment (a regular text based page, nothing fancy) so when the user
clicks on the link, he would run the script in the background without
knowing about it (the cript is supposed to check the time and write it
to a file. i have it to work, but i would like to have it activated
when someone clicks on a link).
how should i do this? sorry if my question is dumb, but i don't have
enough time to learn PERL (it's just an art assignment using PERL)
thank you
--
The young (who always want more and have no game to protect),
the artists (who always hunger for the ecstatic moment),
and the alienated (the wise slaves and noble minority groups watching
from the periphery of the society). "High Priest," -- Timothy Leary
------------------------------
Date: Wed, 11 Mar 1998 05:34:47 GMT
From: vefatica@syr.edu (Vincent Fatica)
Subject: Re: Getting date on an NT machine
Message-Id: <35062170.114118163@news.ican.net>
On Tue, 10 Mar 1998 21:49:32 -0500, "Eric Smith" <ecs@talstar.com> wrote:
>Just started porting my perl scripts to NT but how do you tell Perl to get
>the date on an NT machine.
You can extract the info you want from:
($sec,$min,$hr,$mday,$mo,$yr,$wday,$yday,$dst) = localtime(time);
- Vince
___
Vincent Fatica
Syracuse University Mathematics
vefatica@syr.edu
http://barnyard.syr.edu/~vefatica/
------------------------------
Date: Wed, 11 Mar 1998 05:41:06 GMT
From: vefatica@syr.edu (Vincent Fatica)
Subject: Re: Getting date on an NT machine
Message-Id: <350722ed.114499351@news.ican.net>
On Wed, 11 Mar 1998 05:34:47 GMT, vefatica@syr.edu (Vincent Fatica) wrote:
>On Tue, 10 Mar 1998 21:49:32 -0500, "Eric Smith" <ecs@talstar.com> wrote:
>
>>Just started porting my perl scripts to NT but how do you tell Perl to get
>>the date on an NT machine.
>
>You can extract the info you want from:
>
> ($sec,$min,$hr,$mday,$mo,$yr,$wday,$yday,$dst) = localtime(time);
... or, if CMD.EXE is your shell, use `date /t` which returns a string of the
form:
Wed 03-11-1998
- Vince
___
Vincent Fatica
Syracuse University Mathematics
vefatica@syr.edu
http://barnyard.syr.edu/~vefatica/
------------------------------
Date: 11 Mar 1998 09:24:32 GMT
From: "Matteo" <matteo@gate2000.com>
Subject: interested question
Message-Id: <01bd4cce$e6669b60$LocalHost@matteo>
Hi, I'm Matteo from Italy.
I have to produce an interactive CD-ROM on HTML language with research on a
database.
I think I can use a program which emulate a server and consider the browser
as client.
I think there is a program (netsddeserver) by Netscape which does this, but
I'm not sure and I didn't find it on Netscape web site.
Could you please help me?
Write me at:
matteo@gate2000.com
Thank you
Matteo
------------------------------
Date: 11 Mar 1998 08:37:09 GMT
From: tomines@rohan.sdsu.edu (SenimotBor)
Subject: multiple blank lines into one
Message-Id: <6e5ifl$6ij$1@gondor.sdsu.edu>
I'm sure this is a simple newbie question but I've been racking my brain for an answer
and have had no success.
How do you substitute multiple consecutive blank lines for one blank line.
I've tried the following but can't figure out what I'm doing wrong.
s/(^$)+/^$/g
I've also tried
tr/^\x0a//s
based on the premise that x0a is a character that is "squashed" into a single x0a
Thanks in advance for any help
--
Robert Tomines
tomines@rohan.sdsu.edu
------------------------------
Date: 11 Mar 98 08:52:09 GMT
From: devin@premier1.net (Devin L. Ganger)
Subject: Re: Need help with programming project
Message-Id: <slrn6gck39.19b.devin@blacktower.premier1.net>
'Ware the follow-ups, folks.
<flashy-thing!> Remember only that on Tue, 10 Mar 1998 09:00:16 -0500,
in comp.lang.perl.misc Karl Waddell wrote:
Wait, wait.
I'm detecting Obfuscated English here. Maybe I can translate.
> I know this is a discussion group,
I already know that this isn't at all the proper place to do this,
> but I run a small IT Center and I am in need of perl programmers.
but I don't really care, because *my* perceived needs demand instant
gratification, and I can't be bothered to spend the five minutes looking
for the proper place to do this.
> This seemed like a good spot to post the message.
I really don't think that my feeble attempt at Obfuscated English
clouded the issue for anyone but a fool. But then again, I think you
are all fools, since I'm actually entertaining the notion that any of
you would want to work for me after I display my vast contempt for the
social niceties of Usenet.
> Please excuse me if anyone is offended, but I need developers.
If you're offended, too damn tough, 'cause my life is more important
than yours.
Don't you realize just how extremely *stupid* it is to stomp on the
social conventions of the very people you're trying to employ?
--
Devin L. Ganger <devin@premier1.net>
Chief Systems Administrator
Premier1 Internet Services
------------------------------
Date: Wed, 11 Mar 1998 00:16:17 -0500
From: Karl Waddell <kwaddell@gate.net>
Subject: Re: nslookup?
Message-Id: <35061E21.1CFBAE39@gate.net>
Jim Murrell wrote:
>
> I have been trying to write a short perl script
> that takes an IP number and essentially does
> an "nslookup". I would prefer not using the
> system call to do but tried gethostbyaddr
> without too much success. Does anyone have
> an example of some perl code that does this?
>
> Thanks,
> Ling Jen
Jim:
Have you checked out CPAN? See if the Net:DNS module will help you out
there.
Karl Waddell
------------------------------
Date: Mon, 09 Mar 1998 23:32:47 -0500
From: Ronald J Kimball <rjk@coos.dartmouth.edu>
Subject: Re: Performance Question
Message-Id: <3504C271.D6FDBA0F@coos.dartmouth.edu>
I R A Aggie wrote:
>
> In article <1998Mar7.104903.4026@rumba.m.isar.de>, elwood@rumba.m.isar.de
> (Konstantinos Agouros) wrote:
>
> + a) Put the expressions in an array and do something like
> + foreach $exp(@ARRAY)
> + {
> + if($string =~ /$exp/)
> + .....
> +
> + b) Generate one regexp in the form exp1|exp2|exp3|exp4|exp5...
> + and do one match against that.
>
> c)
>
> @matches=grep /$string/, @ARRAY;
> if ($#matches > -1) {
> print "matched!\n";
> } else {
> print "no match!\n";
> }
You've got the regular expression and target string backwards. In the
poster's question, the regexes are in @ARRAY, and the target string is in $string.
--
_ / ' _ / - aka - rjk@coos.dartmouth.edu
( /)//)//)(//)/( Ronald J. Kimball chipmunk@m-net.arbornet.org
/ http://www.ziplink.net/~rjk/
"It's funny 'cause it's true ... and vice versa."
------------------------------
Date: 11 Mar 1998 09:19:29 +0100
From: Calle Dybedahl <qdtcall@esb.ericsson.se>
Subject: Re: problem with mkdir() and permissions
Message-Id: <isk9a1hc6m.fsf@godzilla.kiere.ericsson.se>
lewst@yahoo.com writes:
> why is mkdir() not honoring the permissions mode that I specified?
>From the perlfunc manpage:
# mkdir FILENAME,MODE
# Creates the directory specified by FILENAME, with
# permissions specified by MODE (as modified by
# umask).
Note the bit in parantheses there.
--
Calle Dybedahl, UNIX Sysadmin
qdtcall@esavionics.se http://www.lysator.liu.se/~calle/
------------------------------
Date: Wed, 11 Mar 1998 01:32:56 -0500
From: Mark Priatel <mpriatel@chat.carleton.ca>
Subject: Problems running scripts in Win95
Message-Id: <35063017.D789DE51@chat.carleton.ca>
I'm currently running the FrontPage server, trying to run CGI scripts
locally (through PERL). However whenever I submit a Form and the
script is executed, the HTML page which is created as a result of the
script hangs.
For Example, a simple script which returns the values of the Form
Elements will print out all the
values, and then my browser hangs. I suspect this happens because in
order for my scripts to work in a Windows environment, when the form is
submitted it runs a BAT file instead of .pl file, and this in turn
requires a dos shell which never finishes....
I'd love any help with:
1. Is there anything that seems really odd about what I'm doing? Is
there any way to get around the .BAT files?
2. Is there some way to let the Perl know its at the end of my script?
3. Does cmd32 (which came with the Perl for Windows archive) have
anything to do with a potential solution?
Mark.
mpriatel@chat.carleton.ca
------------------------------
Date: 10 Mar 98 08:32:38 +0000
From: "Rick Townsend" <rick@slicks.demon.co.uk>
Subject: Re: Retriving last item in array.
Message-Id: <527.373T1913T5121973@slicks.demon.co.uk>
On 09-Mar-98 10:52:20, Jonathan Nichols said :
JN> try
JN> $last_value=$array[$#array]
JN> $#array is the index of the last entry in the array.
JN> I'm sure there's a better way, but this works.
This may not be a 'better way':
$last_value=$array[-1]
But it works too. ;-)
--
/\\ rick@slicks.demon.co.uk Sam-Bones \\ //
// \\ A4000 Warp 040 40Mgz Cybervision 64 \\ //
//===\\ home page http://www.slicks.demon.co.uk \\ //
// \\ Team AMIGA \//
--
------------------------------
Date: 11 Mar 1998 03:57:48 GMT
From: kfox@pt0204.pto.ford.com (Ken Fox)
Subject: Re: Speed of sort routine vs. one-by-one compare (123)
Message-Id: <6e523s$t533@eccws1.dearborn.ford.com>
abigail@fnx.com (Abigail) writes:
> Uri Guttman (uri@sysarch.com) wrote:
> ++ abigail@fnx.com (Abigail) writes:
> ++ > It will be linear in the size of the file. For each addition.
> ++
> ++ not always true. depending on how the file is organized. unix has
> ++ bsearch and friends to find records in a sorted file which is O(log2n).
>
> But that's irrelevant. The insertion will take linear time worst
> case. (Average case too).
> ++ copy large blocks until the insert point, insert the new record,
> ++ finish copying with large blocks. you eliminate many of the record
> ++ compares which is what eats up the cpu.
>
> Rubbish. You got to move a linear number of records. That will dominate
> the time spend.
Abigail is right. Uri has some very weird ideas about algorithm
analysis. However, Abigail assumes a naive insertion. If the
insertions are cached in memory and memory is large enough to hold all
insertions, then the physical movement only has to be done once. A very
efficient linear algorithm with nice sequential disk I/O can do all
the insertions at once.
With this change, the "sort" should be O(M log N + N) where M is the
number of records being inserted and N is the size of the existing
database. Assuming M is small, the algorithm should be O(N), which is
what you'd expect.
This is really just a simple merge sort, but instead of sorting the new
records independently and merging two streams, all we're doing is
marking the location where each record should be merged into the main
database.
There's probably some cut-over point at which you might as well just
do the normal merge sort. Abigail can probably compute it for us. ;)
- Ken
--
Ken Fox (kfox@ford.com) | My opinions or statements do
| not represent those of, nor are
Ford Motor Company, Powertrain | endorsed by, Ford Motor Company.
Analytical Powertrain Methods Department |
Software Development Section | "Is this some sort of trick
| question or what?" -- Calvin
------------------------------
Date: 11 Mar 1998 06:37:12 GMT
From: abigail@fnx.com (Abigail)
Subject: Re: Speed of sort routine vs. one-by-one compare (123)
Message-Id: <6e5beo$6pr$1@client2.news.psi.net>
Nick Halloway (snowe@rain.org) wrote on 1653 September 1993 in
<URL: news:Pine.SUN.3.96.980310181927.27587A-100000@coyote.rain.org>:
++
++
++ On 10 Mar 1998, Abigail wrote:
++
++ > Uri Guttman (uri@sysarch.com) wrote on 1652 September 1993 in
++ > <URL: news:x7afayuzlb.fsf@sysarch.com>:
++ > ++ abigail@fnx.com (Abigail) writes:
++ > ++
++ > ++ > What is a binary sort routine?
++
++ What I need to do is to update a file that might have say 50,000 records,
++ with new records occasionally. So it would be on disk, then either
++ read in record-by-record, or all of it would be read into memory.
++
++ By binary insertion,
++ I mean a program that does something like this: Reads the file
++ into memory, looks for the middle of the file, figures out whether the
++ new record belongs above or below the middle of the file, looks for the
++ middle of that half of the file, figures out where the record belongs
++ relative to that middle, etc. If anyone has such a program, I'd
++ appreciate hearing about it.
++
++ For 50,000 records, is it worth doing this, or should the program just
++ read in the file record by record, compare each record to the new record,
++ then write it all out? If it would be likely to take much more than a
++ second to insert the new record with the easy method then programming the
++ binary method would probably be better.
As I explained before, that depends.
First of all, is the state of the file between inserts relevant?
Do you get a record, then have to insert it, do something with
the file, then get the next record, or can you grab all the records
and insert them at once? In the former case, you get an Omega (k * N)
algorithm, as each insert takes linear time (k being the number of
new records, N the number of records already in the file), in the
latter case, you can use an O (k log k + N) algorithm.
Furthermore, it will make a hell of a lot of difference if you have
50,000 records of 10 bytes each, or 50,000 records of 5000 bytes each.
In the former case, you use half a meg of RAM by reading in the entire
file, in the latter case, you use 250 Mb of RAM. If you have 32 Mb on
your machine, you'll notice. And it certainly influences the "is it
worth doing this" question.
Abigail
--
perl5.004 -wMMath::BigInt -e'$^V=new Math::BigInt+qq;$^F$^W783$[$%9889$^F47$|88768$^W596577669$%$^W5$^F3364$[$^W$^F$|838747$[8889739$%$|$^F673$%$^W98$^F76777$=56;;$^U=substr($]=>$|=>5)*(q.25..($^W=@^V))=>do{print+chr$^V%$^U;$^V/=$^U}while$^V!=$^W'
------------------------------
Date: 11 Mar 1998 06:48:31 GMT
From: abigail@fnx.com (Abigail)
Subject: Re: Speed of sort routine vs. one-by-one compare (123)
Message-Id: <6e5c3v$6td$1@client2.news.psi.net>
Uri Guttman (uri@sysarch.com) wrote on 1653 September 1993 in
<URL: news:x73egpvqf2.fsf@sysarch.com>:
++ "John A. Kroll" <krollj@worldnet.att.net> writes:
++
++ > Uri Guttman wrote:
++ >
++ > > in algorithm analysis the comparison is the only thing you count in
++ > > O(). I/O is considered fixed linear overhead as ALL algorithms have to
++ > > move the same dataset into and out of memory. the fact that it may
++ > > dominate real time is IRRELEVANT to the order of the algorithm.
++ > > eventually with a large enough dataset a even a log(n) algorithm will be
++ > > dominated by the comparisons and not the I/O.
++ >
++ > This is not necessarily true, in algorithm analysis you pick an appropriate
++ > unit of work (be it swaps, comparisons, or whatever) to base your O( )
++ > measurement on.
++
++ but as i said ALL algorithms will have the same overhead reading in the
++ file and writing it out again. so it it a constant and you ignore it for
++ analysis.
Could you please cite a reference, preferably from a well known author
(Knuth will do) where it is said that that is common practise?
++ > If the requirement here is to maintain the actual file in sorted order (as
++ > opposed to merely being able to read the records in sorted order on
++ > demand), the cost of moving data on disk will dominate and should
++ > be what you use to compare algorithms.
++
++ but how many compares will be the difference in algorithms not I/O.
Let's compare the number of multiplications between floats! You just
don't ignore one set of operations and then compare algorithms, specially
not if that set of operations dominates the entire algorithm. Else,
selection sort could be said to be faster than heapsort or mergesort,
because it only does a linear number of swaps (and we just forget about
comparisons this time).
++ > Maybe I've misread the requirements. But it seems like the problem
++ > is you have an existing sorted file with 49,999 records in it, now you
++ > need to add the 50,000 record (the previous records for all I know
++ > were added hours ago). In this case insertion sort is probably the best
++ > algorithm to use. The alternative of appending the 50,000 record at the
++ > end and using a general purpose sorting algorithm, will typically perform
++ > many unnecessary record exchanges, raising the cost of the sort.
++
++ very wrong. you would have to read ALL the records in and write them
++ out. here is a much faster algorithm is high level pseudo code:
++
++ (assuming fixed size records you can seek to using perl seek,
++ sorted records in file)
++
++ do binary search on file and locate and save position to insert
++ new record.
++
++ read large block of data from file and save seek location
++
++ write new record in insert point.
++
++ LOOP:
++
++ read next block of data and save ending seek point
++
++ write last block back to file after inserted record or
++ last written block
++
++ continue loop until EOF
++
++ this will only read and write half the file on average. if the file
++ can't be overwritten in place, do the loop over the whole file and
++ insert the record in the correct place.
++
++ yes, in this algorithm the I/O dominates real time. but it is faster
++ than any other algorithm since it does the least record reads and
++ compares and even the least total I/O in the example i wrote.
It's still a linear time program. That you do one step of the program
in O (log n) is nice (and a small improvement), it does *NOT* make it
an O (log n) algorithm.
O (n) + O (log n) = O (n).
Abigail
--
perl -wle '$, = " "; sub AUTOLOAD {($AUTOLOAD =~ /::(.*)/) [0];}
print+Just (), another (), Perl (), Hacker ();'
------------------------------
Date: 11 Mar 1998 07:28:38 GMT
From: abigail@fnx.com (Abigail)
Subject: Re: Speed of sort routine vs. one-by-one compare (123)
Message-Id: <6e5ef6$78d$1@client2.news.psi.net>
Ken Fox (kfox@pt0204.pto.ford.com) wrote on 1653 September 1993 in
<URL: news:6e523s$t533@eccws1.dearborn.ford.com>:
++ abigail@fnx.com (Abigail) writes:
++ > Uri Guttman (uri@sysarch.com) wrote:
++ > ++ abigail@fnx.com (Abigail) writes:
++ > ++ > It will be linear in the size of the file. For each addition.
++ > ++
++ > ++ not always true. depending on how the file is organized. unix has
++ > ++ bsearch and friends to find records in a sorted file which is O(log2n).
++ >
++ > But that's irrelevant. The insertion will take linear time worst
++ > case. (Average case too).
++
++ > ++ copy large blocks until the insert point, insert the new record,
++ > ++ finish copying with large blocks. you eliminate many of the record
++ > ++ compares which is what eats up the cpu.
++ >
++ > Rubbish. You got to move a linear number of records. That will dominate
++ > the time spend.
++
++ Abigail is right. Uri has some very weird ideas about algorithm
++ analysis. However, Abigail assumes a naive insertion. If the
++ insertions are cached in memory and memory is large enough to hold all
++ insertions, then the physical movement only has to be done once. A very
++ efficient linear algorithm with nice sequential disk I/O can do all
++ the insertions at once.
No, that has nothing to do with a naive insertion. It is my impression
that the new records are coming one by one and need to be processed when
arrived. So, we are talking here about inserting *a single* record in
a file, so the file can be used for whatever it is to be used for till
the next record arrives.
++ With this change, the "sort" should be O(M log N + N) where M is the
++ number of records being inserted and N is the size of the existing
++ database. Assuming M is small, the algorithm should be O(N), which is
++ what you'd expect.
++
++ This is really just a simple merge sort, but instead of sorting the new
++ records independently and merging two streams, all we're doing is
++ marking the location where each record should be merged into the main
++ database.
I would say, it's just like building a balanced tree from the N records
and inserting the new ones in it, which leads to a Theta (M log (N + M) + N)
algorithm. But I didn't get the impression that was allowed, as you now
have everything in memory, and break the requirement of the ordered file.
++ There's probably some cut-over point at which you might as well just
++ do the normal merge sort. Abigail can probably compute it for us. ;)
Actually, the merge sort would be a different algorithm. Then you
grab all the to be inserted records, sort them, and merge them
with the sorted file, which leads to a Theta (M log M + N) algorithm.
Abigail
--
perl -we 'print split /(?=(.*))/s => "Just another Perl Hacker\n";'
------------------------------
Date: 11 Mar 1998 03:58:02 -0500
From: Uri Guttman <uri@sysarch.com>
Subject: Re: Speed of sort routine vs. one-by-one compare (123)
Message-Id: <x7sooptxic.fsf@sysarch.com>
abigail@fnx.com (Abigail) writes:
> Ken Fox (kfox@pt0204.pto.ford.com) wrote on 1653 September 1993 in
> <URL: news:6e523s$t533@eccws1.dearborn.ford.com>:
> ++ abigail@fnx.com (Abigail) writes:
> ++ > Uri Guttman (uri@sysarch.com) wrote:
> ++ > ++ abigail@fnx.com (Abigail) writes:
> ++ >
> ++ > Rubbish. You got to move a linear number of records. That will dominate
> ++ > the time spend.
> ++
> ++ Abigail is right. Uri has some very weird ideas about algorithm
i resemble that remark. i happened to have studied algorithm analysis
with ron rivest (the r of rsa).
> ++ analysis. However, Abigail assumes a naive insertion. If the
> ++ insertions are cached in memory and memory is large enough to hold all
> ++ insertions, then the physical movement only has to be done once. A very
> ++ efficient linear algorithm with nice sequential disk I/O can do all
> ++ the insertions at once.
read the problem. a single record inserted into a single file on
disk. no ram caches, buffers etc. show me how to process all the records
without doing the same I/O. my solution at least lowers the number of
record compares. which can add up to signifigant cpu if the compare is
long or complex and the file is large. I/O is usually not cpu intensive
and is a CONSTANT for the purposes of analysis. only when you must
design algorithms where your dataset must be in memory do you need to
deal with it as in tape merge/sort operations.
this problem wants the file sorted all the time and therfore memory size
is irrelevant as long as you can sequentially read the file and find the
record insertion point. in fact if the files were on tape (as in
mainframe) you would have a linear time just to read and write the
file. since you can seek on a disk file you can do the binary search,
bulk copy up to that point, insert the new record and bulk copy the
rest. the other saving trick i said is to just sek to the insertion
point and bulk shift the rest of the file after the inserted
record. this lowers your actual I/O cost while using the fastest search
algorithm FOR THIS PROBLEM.
> No, that has nothing to do with a naive insertion. It is my impression
> that the new records are coming one by one and need to be processed when
> arrived. So, we are talking here about inserting *a single* record in
> a file, so the file can be used for whatever it is to be used for till
> the next record arrives.
>
> I would say, it's just like building a balanced tree from the N records
> and inserting the new ones in it, which leads to a Theta (M log (N + M) + N)
> algorithm. But I didn't get the impression that was allowed, as you now
> have everything in memory, and break the requirement of the ordered file.
hence the need for reading the file in and out for all algorithms for
this problem.
abigail, for someone who never heard of a binary sort, i am amazed how you
pontificate about algorithms.
'nuff said. the problem is solved. end this thread.
uri
--
Uri Guttman SYStems ARCHitecture and Software Engineering
uri@sysarch.com Have Perl, Will Hack
http://www.sysarch.com (781) 643-7504 x*2 FAX: (781) 643-2710
Try the Best Search Engine on the Net --------> http://www.northernlight.com
------------------------------
Date: Wed, 11 Mar 1998 07:13:28 GMT
From: vefatica@syr.edu (Vincent Fatica)
Subject: Splitting long "sprintf" lines?
Message-Id: <35063298.118510168@news.ican.net>
Is it possible to split long sprintf lines? When I try (on UNIX/5.004 or
NT/5.001) to split the line below (as shown), the result (of print) is as shown
further below. Whichever argument of sprintf I split before, ... it becomes
corrupted in the returned string.
$asctime = sprintf("%s %s %2.2d %2.2d:%2.2d:%2.2d 19%2.2d\n",\
$dows[$wday], $mos[$mo], $mday, $hr, $min, $sec, $yr);
SCALAR(0x7c152c) Mar 11 01:45:56 1998
Thank you.
- Vince
___
Vincent Fatica
Syracuse University Mathematics
vefatica@syr.edu
http://barnyard.syr.edu/~vefatica/
------------------------------
Date: 11 Mar 1998 07:53:08 GMT
From: cberry@cinenet.net (Craig Berry)
Subject: Re: Splitting long "sprintf" lines?
Message-Id: <6e5ft4$aq1$1@marina.cinenet.net>
Vincent Fatica (vefatica@syr.edu) wrote:
: Is it possible to split long sprintf lines? When I try (on UNIX/5.004 or
: NT/5.001) to split the line below (as shown), the result (of print) is as shown
: further below. Whichever argument of sprintf I split before, ... it becomes
: corrupted in the returned string.
:
: $asctime = sprintf("%s %s %2.2d %2.2d:%2.2d:%2.2d 19%2.2d\n",\
: $dows[$wday], $mos[$mo], $mday, $hr, $min, $sec, $yr);
:
: SCALAR(0x7c152c) Mar 11 01:45:56 1998
You needn't escape newlines to do a multiline Perl function call; in
almost every case, Perl treats newlines as just another kind of
whitespace. So that would-be newline-escaping \ is actually being
interpreted as the 'reference-of' operator, which operates on
$dows[$wday]. Printing a reference value gets you the SCALAR(...) output
you're seeing.
So, in brief: Drop the \ at the end of the first line and you'll be fine.
By the way, with less than 22 months remaining before 2000, how can you
possibly still be writing code like that '19%2.2d' bit above? Do you
really want your users waking up 7 quarters from now and seeing that it's
the year 19100? Why not aim the gun slightly away from your foot, and
code '%4d' in the format string and '$yr + 1900' in the arg list?
Also, localtime() in a scalar context gets you almost precisely the format
you seem to be trying for. Perhaps you could use that instead, and save
yourself a little work?
HTH...
---------------------------------------------------------------------
| Craig Berry - cberry@cinenet.net
--*-- Home Page: http://www.cinenet.net/users/cberry/home.html
| Member of The HTML Writers Guild: http://www.hwg.org/
"Every man and every woman is a star."
------------------------------
Date: 8 Mar 97 21:33:47 GMT (Last modified)
From: Perl-Request@ruby.oce.orst.edu (Perl-Users-Digest Admin)
Subject: Digest Administrivia (Last modified: 8 Mar 97)
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.
To submit articles to comp.lang.perl.misc (and this Digest), send your
article to perl-users@ruby.oce.orst.edu.
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.
The Meta-FAQ, an article containing information about the FAQ, is
available by requesting "send perl-users meta-faq". The real FAQ, as it
appeared last in the newsgroup, can be retrieved with the request "send
perl-users FAQ". Due to their sizes, neither the Meta-FAQ nor the FAQ
are included in the digest.
The "mini-FAQ", which is an updated version of the Meta-FAQ, is
available by requesting "send perl-users mini-faq". It appears twice
weekly in the group, but is not distributed in the digest.
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 V8 Issue 2069
**************************************
