Perl算法大师：探索编程艺术

5星 · 超过95%的资源需积分: 10 95 浏览量更新于2024-07-20 收藏 6.16MB PDF 举报

"《Mastering Algorithms with Perl》是一本由Jon Orwant、Jarkko Hietaniemi和John MacDonald合著的IT专业书籍，专注于Perl编程语言在算法设计与实现中的应用。这本书出版于1999年，由O'Reilly & Associates, Inc.发行，享有版权并受到美国法律保护。封面插图由Lorrie LeJeune创作。该书是O'Reilly系列的"Nutshell Handbook"之一，专为程序员提供深入理解算法原理和如何用Perl语言高效实现的实用指南。书中强调了Perl作为一种强大的脚本语言，在处理各种算法问题时的独特优势和灵活性。作者们以其丰富的经验，引导读者从基础的算法概念开始，逐步探索并掌握Perl中的数据结构、控制流程和高级算法技巧。本书结构清晰，涵盖了算法分析（如时间复杂度和空间复杂度）、排序与搜索算法（如冒泡排序、二分查找）、图算法、动态规划等核心内容，同时提供了大量实例和代码示例，便于读者理解和实践。此外，书中还探讨了如何利用Perl的模块系统、正则表达式和函数式编程特性来优化算法实现。编辑们——Andy Oram和Jon Orwant——确保了内容的专业性和准确性，而生产编辑Melanie Wang负责了整个出版过程的管理和质量把控。《Mastering Algorithms with Perl》自首次印刷以来，一直是学习和提升Perl编程算法能力的权威参考书籍，对于希望在IT领域深入研究算法或寻求在实际项目中运用Perl的开发者来说，是一本不可或缺的工具书。需要注意的是，书中的某些商标，如Nutshell Handbook logo、O'Reilly logo以及狼与Perl算法关联的形象，都是O'Reilly & Associates, Inc.的注册商标。书中提到的产品名称和制造商的标识，如果标注为商标，是为了表明其合法所有权。这本手册旨在提供有价值的技术信息，帮助读者在Perl的世界里探索算法的艺术。"

What Do All Those Funny Symbols Mean?

What you've just seen is the definition of a subroutine, which by itself won't do anything. You

use it by including the subroutine in your program and then providing it with the two

parameters it needs: \@array and $word. \@array is a reference to the array named

@array.

The first line, sub binary_search {, begins the definition of the subroutine named

"binary_search". That definition ends with the closing brace } at the very end of the code.break

Page 4

Next, my ($array, $word) = @_;, assigns the first two subroutine arguments to the

scalars $array and $word. You know they're scalars because they begin with dollar signs.

The my statement declares the scope of the variables—they're lexical variables, private to this

subroutine, and will vanish when the subroutine finishes. Use my whenever you can.

The following line, my ($low, $high) = ( 0, @$array - 1 ); declares and

initializes two more lexical scalars. $low is initialized to 0—actually unnecessary, but good

form. $high is initialized to @$array - 1, which dereferences the scalar variable

$array to get at the array underneath. In this context, the statement computes the length

(@$array) and subtracts 1 to get the index of the last element.

Hopefully, the first argument passed to binary_search() was a reference to an array.

Thanks to the first my line of the subroutine, that reference is now accessible as $array, and

the array pointed to by that value can be accessed as @$array.

Then the subroutine enters a while loop, which executes as long as $low <= $high; that

is, as long as our window is still open. Inside the loop, the word to be checked (more

precisely, the index of the word to be checked) is assigned to $try. If that word precedes our

target word,

we assign $try + 1 to $low, which shrinks the window to include only the

elements following $try, and we jump back to the beginning of the while loop via the

next. If our target word precedes the current word, we adjust $high instead. If neither word

precedes the other, we have a match, and we return $try. If our while loop exits, we know

that the word isn't present, and so undef is returned.

References

The most significant addition to the Perl language in Perl 5 is references, their use is described

in the perlref documentation bundled with Perl. A reference is a scalar value (thus, all

references begin with a $) whose value is the location (more or less) of another variable. That

variable might be another scalar, or an array, a hash, or even a snippet of Perl code. The

advantage of references is that they provide a level of indirection. Whenever you invoke a

subroutine, Perl needs to copy the subroutine arguments. If you pass an array of ten thousand

elements, those all have to be copied. But if you pass a reference to those elements as we've

done in binary_search(), only the reference needs to be copied. As a result, the

subroutine runs faster and scales up to larger inputs better.

More important, references are essential for constructing complex data structures, as you'll see

in Chapter 2, Basic Data Structures.break

Precedes in ASCII order, not dictionary order! See the section "ASCII Order" in Chapter 4, Sorting.

Page 5

You can create references by prefixing a variable with a backslash. For instance, if you have

an array @array = (5, "six", 7), then \@array is a reference to @array. You can

assign that reference to a scalar, say $arrayref = \@array, and now $arrayref is a

reference to that same (5, "six", 7). You can also create references to scalars

($scalarref = \$scalar), hashes ($hashref = \%hash), Perl code

($coderef = \&binary_search), and other references ($arrayrefref =

\$arrayref). You can also construct references to anonymous variables that have no

explicit name: @cubs = ('Winken', 'Blinken', 'Nod') is a regular array, with a

name, cubs, whereas ['Winken', 'Blinken', 'Nod'] refers to an anonymous

array. The syntax for both is shown in Table 1-1.

Table 1-1. Items to Which References Can Point

Type Assigning a Reference

to a Variable

Assigning a Reference

to an Anonymous Variable

scalar

$ref = \$scalar $ref = \1

list

$ref = \@arr $ref = [ 1, 2, 3 ]

hash

$ref = \%hash $ref = { a=>1, b=>2, c=>3 }

subroutine

$ref = \&subr $ref = sub { print "hello, world\n" }

Once you've "hidden" something behind a reference, how can you access the hidden value?

That's called dereferencing, and it's done by prefixing the reference with the symbol for the

hidden value. For instance, we can extract the array from an array reference by saying @array

= @$arrayref, a hash from a hash reference with %hash = %$hashref, and so on.

Notice that binary_search() never explicitly extracts the array hidden behind $array

(which more properly should have been called $arrayref). Instead, it uses a special

notation to access individual elements of the referenced array. The expression

$arrayref->[8] is another notation for ${$arrayref}[8], which evaluates to the

same value as $array[8]: the ninth value of the array. (Perl arrays are zero-indexed; that's

why it's the ninth and not the eighth.)

Adapting Algorithms

Perhaps this subroutine isn't exactly what you need. For instance, maybe your data isn't an

array, but a file on disk. The beauty of algorithms is that once you understand how one works,

you can apply it to a variety of situations. For instance, here's a complete program that reads in

a list of words and uses the same binary_search() subroutine you've just seen. We'll

speed it up later.break

#!/usr/bin/perl

# bsearch - search for a word in a list of alphabetically ordered words

Page 6

# Usage: bsearch word filename

$word = shift; # Assign first argument to $word

chomp( @array = <> ); # Read in newline-delimited words,

# truncating the newlines

($word, @array) = map lc, ($word, @array); # Convert all to lowercase

$index = binary_search(\@array, $word); # Invoke our algorithm

if (defined $index) { print "$word occurs at position $index.\n" }

else { print "$word doesn't occur.\n" }

sub binary_search {

my ($array, $word) = @_;

my $low = 0;

my $high = @$array - 1;

while ( $low <= $high ) {

my $try = int( ($low+$high) / 2 );

$low = $try+1, next if $array->[$try] lt $word;

$high = $try-1, next if $array->[$try] gt $word;

return $try;

}

return;

}

This is a perfectly good program; if you have the /usr/dict/words file found on many Unix

systems, you can call this program as bsearch binary /usr/dict/words, and it'll

tell you that "binary" is the 2,514th word.

Generality

The simplicity of our solution might make you think that you can drop this code into any of your

programs and it'll Just Work. After all, algorithms are supposed to be general: abstract

solutions to families of problems. But our solution is merely an implementation of an

algorithm, and whenever you implement an algorithm, you lose a little generality.

Case in point: Our bsearch program reads the entire input file into memory. It has to so that

it can pass a complete array into the binary_search() subroutine. This works fine for

lists of a few hundred thousand words, but it doesn't scale well—if the file to be searched is

gigabytes in length, our solution is no longer the most efficient and may abruptly fail on

machines with small amounts of real memory. You still want to use the binary search

algorithm—you just want it to act on a disk file instead of an array. Here's how you might do

that for a list of words stored one per line, as in the /usr/dict/words file found on most Unix

systems:break

return if compare( $line, $word );

return $low;

}

sub compare { # $word1 needs to be lowercased; $word2 doesn't.

my ($word1, $word2) = @_;

$word1 =

s/\W//g; $word1 = lc($word1);

return $word1 cmp $word2;

}

Our once-elegant program is now a mess. It's not as bad as it would be if it were implemented

in C++ or Java, but it's still a mess. The problems we have to solvecontinue

Page 8

in the Real World aren't always as clean as the study of algorithms would have us believe. And

yet there are still two problems the program hasn't addressed.

First of all, the words in /usr/dict/words are of mixed case. For instance, it has both abbot

and Abbott. Unfortunately, as you'll learn in Chapter 4, the lt and gt operators use ASCII

order, which means that abbot follows Abbott even though abbot precedes Abbott in

the dictionary and in /usr/dict/words. Furthermore, some words in /usr/dict/words contain

punctuation characters, such as A&P and aren't. We can't use lt and gt as we did before;

instead we need to define a more sophisticated subroutine, compare(), that strips out the

punctuation characters (s/\W//g, which removes anything that's not a letter, number, or

underscore), and lowercases the first word (because the second word will already have been

lowercased). The idiosyncracies of our particular situation prevent us from using our

binary_search() out of the box.

Second, the words in /usr/dict/words are delimited by newlines. That is, there's a newline

character (ASCII 10) separating each pair of words. However, our program can't know their

precise locations without opening the file. Nor can it know how many words are in the file

without explicitly counting them. All it knows is the number of bytes in the file, so that's how

the window will have to be defined: the lowest and highest byte offsets at which the word

might occur. Unfortunately, when we seek() to an arbitrary position in the file, chances are

we'll find ourselves in the middle of a word. The first $line = <$file> grabs what

remains of the line so that the subsequent $line = <$file> grabs an entire word. And of

course, all of this backfires if we happen to be near the end of the file, so we need to adopt a

quick-and-dirty linear search in that event.

These modifications will make the program more useful for many, but less useful for some.

You'll want to modify our code if your search requires differentiation between case or

punctuation, if you're searching through a list of words with definitions rather than a list of

mere words, if the words are separated by commas instead of newlines, or if the data to be

searched spans many files. We have no hope of giving you a generic program that will solve

every need for every reader; all we can do is show you the essence of the solution. This book

is no substitute for a thorough analysis of the task at hand.

Efficiency

www.allitebooks.com

剩余738页未读，继续阅读

ibelievemylove

粉丝: 2
资源: 15

Perl算法大师：探索编程艺术

Mastering Algorithms with C Examples

Mastering.Algorithms.with.Perl-examples

programming perl, 3rd edition

精通Perl算法

Perl编程：算法实战指南

Perl算法大师：全面指南

Perl算法大师：探索核心技术

Perl算法大师：高效编程与经典技巧

Perl算法大师指南：清晰实用的编程秘籍

Perl中的数据结构：数组与散列的嵌套应用

最新资源