Slashdot Mirror
O'Reilly Perl Algorithm Book in August
An anonymous reader wrote in to say that O'Reilly is going
to be shipping a new
Perl Algorithms book
By Jon Orwant, Jarkko Hietaniemi & John Macdonald.
Its not due until August
(why does that feel like years?),
but I'm already stoked. And I'm cranky that I missed Larry
Walls speech at LWCE.
Any guesses to what the cover animal will be? I'm sure ORA are running out of creatures.
Here's a free sort algorithm!
sub mysort { return sort @_; }
Damn, I'm good.
Kick Ass! =P
Well that's new.
I didn't think Perl programmers used algorithms. I thought they just chucked some more punctuation at a problem until it either went away or became so unreadible that no-one can say it doesn't do what it's supposed to...
I was suprised too.
I guess Perl has a sophisticated enough grammer to support the expression of algorithms! I guess that means that every computable function can be written in perl.
Nick is Puff, but I can't remember my password and I don't see a link to get another registration letter sent to my email address.
Another anonymous coward wrote:
I was suprised too.
I guess Perl has a sophisticated enough grammer to support the expression of algorithms! I guess that means that every computable function can be written in perl.
Actually, I'm told that Larry Wall and the regexp czar (some russian or eastern european, can't remember the name) for Perl recently had a bit of an argument when Wall realized that the czar was slowly adding regexp constructs to ultimately be able to write a C compiler as a one long regexp.
:-)
I'm curious as to what's in the algorithm book. Hopefully it's focused on useful stuff. I don't think the world needs a newer, better sorting algorithm implemented in Perl. But, for example, stuff on how to implement MD5 in Perl (this has been done, but a discussion of how it was done would be educational and useful) or other similar projects would be nice.
Some other anonymous coward wrote:
Any guesses to what the cover animal will be? I'm sure ORA are running out of creatures.
Sad to say, O'Reilly will not likely run out of endangered species to put on covers anytime soon.
Sadder to say, when they do run out of endangered species, there are plenty of extinct species for them to put on covers.
Can't these be used with other languages?
Does this mean I can't continue taking the piss out of perl programmers?
I am actually going to have to give them some respect?
Will I have to stop calling them a bunch of glorified data entry clerks...?
No.
Well it's aimed at Perl programmers, remember.
So the algorithms will be stuff like:
loops
sub-routines
selection statements
case statements
I also hear one of the teletubbies has written an introduction for the book...
They waited this long so they could compete with the Monica Lewinksy book...
However, you may have to use a library which supports extendable arrays, hashes, and regexps (and a little imagination for some of the weirder constructs). And if you must use perl regexps you could just embed perl into c :-)
This is an old
version (about 9 months out of date)
of this book's toc....
[1]Preface
About This Book
Chapter-by-Chapter
What You Should Know Before Reading This Book
What You Should Have Before Reading This Book
Online Information
[2]Introduction
What Is An Algorithm?
A Sample Algorithm: Binary Search
What do all those funny symbols mean?
Adapting algorithms
Generality
Efficiency
Space versus Time
Benchmarking
Floating Point Numbers
Temporary Variables
Caching
Evaluating algorithms: O(N) notation
Recurrent themes in algorithms
Recursion
Divide and Conquer
Dynamic Programming
Choosing the Right Representation
[3]DataStructures
Example - An Address
Perl's Data Types
Constructed Data Types
Examples of Basic Data Types
Example of an Object Data Type
Example of a Constructed Data Type
Data Structures Provided By Perl Lists
Queues
Stacks
Dequeues
Perl Arrays - Still More
Data Structures Not Native to Perl
Linked Lists
Linked List Implementation Choices
Tracking Both Ends of Linked Lists
Circular Linked Lists
Doubly-linked Lists
Memory Management and Linked Lists
Infinite Lists
The Cost of Traversal
Binary Trees
Keeping Trees Balanced
Heaps
Binary Heaps
CPAN Heaps Module
[4]Sorting
All Sorts of Sorts
Perl's sort() function
ASCII order
Numeric order
Reverse Order: From Highest To Lowest
Sort::Fields
Sort::Versions
Dictionary order
Deficiency 1: Missing
Internationalization (Locales)
Deficiency 2: Still Missing
Internationalization
Deficiency 3: Lack Of Caching
The Schwartzian Transform
See for yourself - use the Benchmark module
Not Just String Operations
Long Duration Caching
Sorting Hashes Is Not What You Might Think
Sorting Algorithms in Perl
Quadratic Sorting Algorithms
Selection Sort
Minima and Maxima
Bubble Sort
Insertion Sort
Shellsort
Log-Linear Sorting Algorithms
Mergesort
Removing Recursion From
Mergesort
Heapsort
Quicksort
Removing Recursion From
Quicksort
Median, Quartile, Percentile
Non-Comparison Sorts (aka Beating O(N log N))
Radix sorts
Bucket sort
Custom sorts
External Sorting
Hybrid sorts
Sorting Algorithms Summary
n2 sorts
n1.5 sorts
n log n sorts
Linear sorts
Hybrid sorts
How well did we do?
[5]Searching
Lookup Searches
Lookup Search Recommendations
Linear Search
Ransack Search
Binary Search in a List
Proportional Search
Binary Search in a Tree
Should You Use A List Or A Tree For Binary
Searching?
Bushier Trees
Lists
Lists of Lists
B-Trees
Hash Search
Hybrid Searches
Generative Searches
Game Interface
Exhaustive Search
Alternatives to Exhaustive Search in Games
Minimax
Pruning
Alpha-Beta Pruning
Killer Move
Non-Game Dynamic Searches
Greedy Algorithms
Branch and Bound
The A* Algorithm
Dynamic Programming
[6]Sets
Introduction
Venn Diagrams
Defining Sets
Defining Sets Using Hashes
Defining Sets Using Bit Vectors
Set Union and Intersection
Union
Intersection
Set Union And Intersection Using Hashes
Union and Intersection Using Bit Vectors
Set Differences
Set Difference
Set Symmetric Difference
Set Differences Using Hashes
Set Differences Using Bit Vectors
Counting Set Elements
Set Relations
Set Relations Using Hashes
Set Relations Using Bit Vectors
The Set Modules of CPAN
Set::Scalar
Set::IntSpan
Bit::Vector
Set::IntegerRange
Sets of Sets
Power Sets
Power sets Using Hashes
Multisets
Multiset Operations
Fuzzy Sets
[7]Matrices
Introduction
Creating Matrices
Manipulating Individual Elements
Finding The Dimensions of a Matrix
Displaying Matrices
Adding or Multiplying Constants
Adding a Constant to a Matrix
Adding a Matrix to a Matrix
Transposing A Matrix
Multiplying Matrices
Extracting a Submatrix
Combining Matrices
Inverting A Matrix
Computing the Determinant
Gaussian Elimination
The Matrix Chain Product
Further Reading
[8]GraphAlgorithms
Introduction
Vertices
Edges
Direction
Density
Derived Graphs
Graph Traversal
Depth-First Search
Breadth-First Search
Graph Geography: Paths, Islands, and
Bridges
Graph Biology: Trees, Forests, Dags,
Ancestors, and Descendants
Edge Classes
Weights and Other Edge Attributes
Vertex Classes
Connectivity
Graph Representation in Computers
Minimum Spanning Trees
Kruskal's Minimum Spanning Tree
Prim's Minimum Spanning Tree
Shortest Paths
Single-source Shortest Paths
All-pairs Shortest Paths
Transitive Closure
Flow Networks
Ford-Fulkerson
Edmonds-Karp
Traveling Salesman Problem
Graph Modules from CPAN
[9]Strings
String Matching Algorithms
Perl Builtins
Exact Matching
Regular Expressions
Quick Tips for Regular Expressions: Readability
Quick Tips for Regular Expressions: Efficiency
study()
String Matching Algorithms
Naïve matching
Rabin-Karp
Rabin-Karp is a checksum algorithm
Handling huge checksums
Implementing the Rabin-Karp
Further checksum experimentation
Knuth-Morris-Pratt
Boyer-Moore
Shift-Op
Baeza-Yates-Gonnet Shift-OR Exact Matching
Approximate Matching
Baeza-Yates-Gonnet Shift-ADD k mismatches
Wu-Manber k differences
String::Approx
Phonetic Algorithms
Text::Soundex
Text::Metaphone
Stemmming and Inflection
Modules for Stemming and Inflection
Text::Stem
Text::German
Lingua::EN::Conjugate
Lingua::PT::Conjugate
Parsing
Finite Automata
Grammars
Context-free Grammars
Parsing Up and Down
Top-down Parsing
Bottom-Up Parsing
Interpreters and Compilers
Modules for (Lexing and) Parsing
Text::ParseWords
Text::DelimMatch
String::ShellQuote
Parse::Lex
Parse::RecDescent
Special-Purpose Modules
Special-Purpose Tools and Languages
Compression
Run Length Encoding
Huffman Encoding
compress, GNU gzip, pkzip
[10]GeometricAlgorithms
Geometric Formulas
Distance
Euclidean Distance
Manhattan Distance
Triangle
Circle and Sphere
Geometric Algorithms
Polygon Area
Polygon Perimeter
Bounding Box
Accuracy: using e
Range Searching
Clockwise
Line Intersection
Line Intersection In The General Case
Line Intersection In The
Horizontal-Vertical Case
Point in Polygon
Point in Triangle
Point in Quadrangle
Convex Hull
Closest Pair of Points
[11]NumberSystems
Introduction
Integers and Reals
Constants
Pure Integer Arithmetic
Precision
Rounding Numbers
Rounding Up or Down To An Integer
Rounding To The Nearest Integer
Rounding To A Particular Decimal Point
Very Big, Very Small, and Very Exact Numbers
Fractions
Strange Systems
Bits and Bases
Bit Vectors
Complex Numbers
Polar Coordinates
Spherical Coordinates
Cylindrical Coordinates
Dates and Times
Roman Numerals
Trigonometry
Significant Series
Arithmetic and Geometric Progressions
The Fibonacci Sequence
Harmonic Series
The Riemann Zeta Function and Bernoulli Numbers
[12]NumberTheory
Basic Number Theory
Greatest Common Divisor
GCD - Linear Combination
Least Common Multiple
Prime Numbers
Caching - Another Example
Non-Infinite Arithmetic
Modular Arithmetic
Chinese Remainder Theorem
Modular Division
Chinese Remainder Revisited
Treating Chinese Remainders As Integers
Integer Exponentiation
Modular Exponentiation
Miller-Rabin - Prime Generation Revisited
Unsolved Problems
Is The Collatz Conjecture False?
Is There An Odd Perfect Number?
Is the Goldbach Conjecture False?
[13]Cryptography
Encryption
Perfect Encryption - The One-Time Pad
Shared Secret Encryptions
DES - The Data Encryption Standard
IDEA - International Data Encryption Algorithm
Analysis of Shared Secret Encryption
Public Key Encryption
RSA Public Key Encryption
Public Key or Private Key
Integrity and Authentication
Other Issues
[14]Probability
Random Numbers
Don't Forget To Seed Your Generator
Better Randomness
Events
Will the Red Sox win, and will the stock market go
up?
Will neither the Red Sox win nor the stock market
go up?
The Birthday Conundrum
Will the Red Sox win or the stock market go up?
Permutations and Combinations
Permutations
Combinations
Probability Distributions
Expected Value
Rolling Dice: Uniform Distributions
Choosing Snowfall: Uniform Continuous
Distributions
Choosing an element from an array
Picking Random BigInts
Rolling Dice Revisited: Combining Events
Loaded Dice and Gumball Machines: Non-Uniform Discrete
Distributions
Flipping A Coin: The Binomial Distribution
The Binomial Distribution In Poker
Very Large Distributions
If The Red Sox Score Six Runs, They'll Probably Win:
Conditional Probability
The Vaunted Monty Hall Problem
Flipping Coins Over and Over: Infinite Discrete
Distributions
How Much Snow? Continuous Distributions
Many More Distributions
The Bernoulli Distribution
The Beta Distribution
The Cauchy Distribution
The Chi Square Distribution
The Erlang Distribution
The Exponential Distribution
The Gamma Distribution
The Gaussian (Normal) Distribution
The Geometric Distribution
The Hypergeometric Distribution
The Laplace Distribution
The Log Normal Distribution
The Maxwell Distribution
The Pascal Distribution
The Poisson Distribution
The Rayleigh Distribution
The Uniform Distribution
[15]Statistics
Statistical Measures
The Mean
The Median
The Mode
Standard Deviation
Significance Tests
How Sure Is Sure?
The Sign Test
The z test
The t test
The Chi-square test
ANOVA and the F -test
Correlation
Computing the Covariance
Computing the Correlation Coefficient
Fitting a Line to Your Data
[16]NumericalAnalysis
Computing Derivatives and Integrals
Computing The Derivative At A Particular Point
Computing The Jacobian
Computing Definite Integrals
Solving Equations
Root Finding
Simple Roots: Quadratics and Cubics
The Quadratic Formula
Cubic Equations
Approximating roots
Multiple Nonlinear Equations
Interpolation, Extrapolation, and Curve Fitting
Fitting A Polynomial To A Set Of Points
Splines
Cubic Splines
Data Smoothing and Linear Least Squares
[17]FurtherReading
General References For Algorithms
Numerical Methods
Graphs, Graphics, and Geometry
Numerical Methods
String Processing and Parsing
Numerical Methods
General Mathematics
Probability and Statistics
Other References
Correct me if I'm wrong but wasn't O'Reilly supposed to publish a Perl Database book due sometime in March or April. Going back there I can see nothing on the subject. Does anyone know what happened to this book, or am I just seeing things again. A good book on Perl's DBI library would be really great.
I never did understand why I see books with titles like "Algorithms in C", "Algorithms in C++", "Algorithms in (gasp) Visual BASIC"---why not just buy one of the timeless books like the Knuth series, maybe even the Rivest et al. book, and learn the math. By attaching a language to it, the publisher/author usually just tries to attach their book to the latest programming craze; they often spend more time talking about issues specific to that language rather than what's important. I generally think O'Reilly makes some pretty good books, so I won't pass judgment on this one until I see it.
My favorite programming lanauge is pseudocode.
Even though you might have an algorithm down pat, you won't know the efficiency tradeoffs that are appropriate for an implementation in a given language. example:
In C, strlen() is a O(N).
In Perl, the equivalent is O(1).
This fact will probably affect many string-related algorithms you might be interested in.
Thanks. That library would probably remove most of the overhead of this little program called slocate. now I gotta contact the author that I need to remove this silly emebedded perl junk I put in there JUST for the perl regexps and put code using this library in! Yay!
(I just hope this thing's been tested for buffer overflows).
Gwydion Dylan, the open-source Dylan implementation for unix systems has a (largely) perl-compatible regexp library.
http://gwydiondylan.org
Algorithms in perl? What's the point? This is getting absurd. (I guess more are into S&M than I thought.)
Looking through the books TOC, the Dylan programming language has most of the data structures listed built into it already. And the things that weren't in the Dylan standard library would be much easier to write in Dylan anyway. What beat yourself up and do it in Perl?
The main reason that Perl is getting ragged on is that it is being promoted as being able to do nearly anything. Even you are guilty of this:
It not only gets the job done for teeny
sysadmin jobs, it cranks pretty well on "real apps".
Perl may be a great scripting language for some purposes, but I doubt if an operating system, web browser, or even lesser "real apps" would be very viable if written in Perl. Also to me, perl code is not very maintainable for large projects (not that C or C++ code is). There is even an obfusciated Perl contest just like there is for C. Perl just doesn't have the tools to manage complexity in an elegant manner.
From a language design standpoint, Perl is not a pretty language at all.
Quit foolin'.
No one speaks Esperanto.
don't feel bad just because you're stupid! chin up!
i'm glad you posted this! i learned something!
it's a little silly to use perl for an operating system, nobody suggested that. it's also very silly to use C for simple projects and shell automation.
Or even:
sub unique {
local %_;
grep {!$_ {$_} ++} => @_;
}
-- Abigail
It was said:
Gwydion Dylan, the open-source Dylan implementation for unix systems has a (largely) perl-compatible regexp library.
That statement doesn't show any reason to use Dylan instead of Perl. The regexp library is not quite compatable, and on top of that, Dylan seems to be aimed only at Unix system. That makes the score Dylan - Perl 0 - 2 in this match.
-- Abigail
It's true that strlen() in C is O(N), and in Perl the equivalent is O(1), but that shouldn't matter for any well written algorithm. Perl's equivalent (length()) is O(1) because it sacrifices memory for speed; it will store the actual length of the string somewhere.
There's no reason you can't do that in your C program.
-- Abigail
Of course the behavior of any Perl primitives can be duplicated in C. My point was simply that there are non-obvious (to a Perl novice) ways to exploit Perl to implement algorithms efficiently.
Email from Jon O. says it goes into production on April 1 (really) and should be on shelves this summer.... I too pre-ordered one last summer. Those are the lumps you have to be willing to take if you order a not-yet-published book ;) -matt
Off topic slightly, but I thought they had a Qmail book in the pipeline. Where is it????
Long wait.
--Zachary Kessin
Erlang Developer and podcaster
Hrm, what books get the extinct cover animals?
"Mastering Scientific Programming with FORTRAN", also known as "The Dodo Book"...
--
--
Since when did O'Reilly confine themselves to endangered species?
I'm remembering the "Making TeX work" book which has on the cover a European Garden Spider - hardly an endangered species.
I thought that O'Reilly's animals were limited by the set of 19th century wood engravings that they were using as picture sources, though maybe they've moved away from that set.
I suppose I should also mention that you can see the cover by following the link posted in the top article. It appears to be a grey wolf.
Assuming that this book stil contains all of these, I'd buy it just for the statistics algorithms (I have managed to "misplace" my undergrad stats book).
Occasionally it's useful for a TA to be able to show that slight differences in average homework grades by gender aren't statistically significant.
Give it up. I'm *so* sick and tired of people who don't know how to actually program in Perl ragging on it. I program daily in it... real programs, of actual largish size (well over 20,000 lines of code in the entire system of a typical app I just checked). It works like a charm. It provides object-orientation, more available libraries than you can shake a stick at, and the ability to program outside the box when I need to. :-P
Oh, and I don't have to worry about an extra space screwing up my loop constructs
Perl is a real programming language. It not only gets the job done for teeny sysadmin jobs, it cranks pretty well on "real apps".
(Not to slight Dylan, or Python, or Java... they might be cool, too... just not attractive to me at the moment)
It's a strange world -- let's keep it that way
Once again, I already said, I write Perl apps every day. It works. You cannot prove to me it doesn't work, and it's not maintainable, because (duh), for me and my company, *it is*.
:-)
We have great programmers, we all know how to avoid doing stupid stuff, and we write really good code.
The fact that Perl is great for one-off scripts doesn't make it unusable for larger projects at all. Maybe it doesn't suit everyone. Fine, use a language that works for you. But don't be foolish enough to make unjustified claims... we usually call that FUD.
It's a strange world -- let's keep it that way
The PCRE code could use some more optimization, but on the other hand, at least its code is relatively easy to read. There's also the regex engine inside Mozilla's JavaScript implementation, which I know little about.
What would we do without O'Reilly
O'Reilly announced this nearly six months ago - I preordered a copy with the notion that it would be arriving soon after. I guess I was wrong. I can only suspect a major rewrite of some section was required - it is not like O'Reilly to take orders on a book almost a year before it is to be released.
Yep, I ordered this months ago too.
I was wondering what had happened.
-- You've got to get a hat if you want to get ahead.
Private Sub cmdButton1_Click()
If strInsult="glorified data entry clerk" Then
txtBox1="Hey! Stop insulting me!"
Else
txtBox1="Quit picking on me!"
EndIf
End Sub
My favorite programming lanauge is pseudocode.
Can you recommend a good compiler for that?
I'll bet you speak Esperanto, too.
om a language design standpoint, Perl is not a pretty language at all.
Neither is English.
Does this mean I can't continue taking the piss out of perl programmers?
I am actually going to have to give them some respect?
Will I have to stop calling them a bunch of glorified data entry clerks...?
Yep...
...but then again, with all the new users Linux is getting from "going mainstream", there are sure to be at least a couple of VB lusers migrating from Windows who are worth your disrespect.
Of course, calling them "a bunch of glorified data entry clerks" is pretty high praise...
(...for them).
--
- Sean
It's a fine line between trolling and karma-whoring... and I think I just crossed it.
- Sean
What a ridiculous comment. Of course every computable function can be written in Perl. Pretty much any C code can be translated directly into Perl, and this is the way a lot of horrible Perl gets written.
Here's why a Perl algorithm book is worthwhile:
Perl's builtin data structures have features that can be used to great effect in algorithms, particularly hashes. For instance, here's a classic example of an algorithm to remove duplicates from a list, or return the union of two lists:
sub unique {
my %temp = map {$_,1} @_;
return keys %temp;
}
Or, more succinctly:
sub unique {
return keys %{{ map {$_,1} @_ }};
}
This is way different from the algorithm a transplanted C programmer would use. Things that are appropriate in one language aren't necessarily appropriate in another.