Algorithms in a Nutshell

Rate of Growth of Functions | 15

AlgorithmsThe Math of

distinct elements, one at a time, until a desired value,v, is found. For now,

assume that:

• There aren distinct elements in the list


• The element being sought,v, is in the list


• Each element in the list is equally likely to be the valuev
  To understand the performance of SEQUENTIALSEARCH, we must know how
  many elements it examines “on average.” Sincevis known to be in the list and
  each element is equally likely to bev, the average number of examined elements,
  E(n), is the sum of the number of elements examined for each of thenvalues
  divided byn. Mathematically:

The Effect of Encoding on Performance

Assume a program stored information about the periodic table of elements.

Three questions that frequently occur are a)“What is the atomic weight of

element numberN?”, b)“What is the atomic number of the element namedX?”,

and c)“What is the name of element numberN?”. One interesting challenge for

this problem is that as of January 2008, element 117 had not yet been discov-

ered, although element 118, Ununoctium, had been.

Encoding 1 of periodic table: store two arrays,elementName[], whoseithvalue

stores the name of the element with atomic numberi, andelementWeight[],

whoseith value stores the weight of the element.

Encoding 2 of periodic table: store a string of 2,626 characters representing the

entire table. The first 62 characters are:

1 H Hydrogen 1.00794

2 He Helium 4.002602

3 Li Lithium 6.941

The following table shows the results of 32 trials of 100,000 random query invoca-

tions (including invalid ones). We discard the best and worst results, leaving 30

trials whose average execution time (and standard deviation) are shown in

milliseconds:

Weight Number Name

Enc1 2.1±5.45 131.73±8.83 2.63±5.99

Enc2 635.07±41.19 1050.43±75.60 664.13±45.90

As expected, Encoding 2 offers worse performance because each query involves

using string manipulaton operations. Encoding 1 can efficiently processweightand

name queries butnumber queries require an unordered search through the table.

This example shows how different encodings result in vast differences in execu-

tion times. It also shows that designers must choose the operations they would

like to optimize.

En()

1

n

--- i

i= 1

n

∑

nn()+ 1

2 n

---------------------

1

2

---n^1

2

== =+---

Algorithms in a Nutshell
Algorithms in a Nutshell By Gary Pollice, George T. Heineman, Stanley Selkow ISBN:
9780596516246 Publisher: O'Reilly Media, Inc.

Prepared for Ming Yi, Safari ID: [email protected]
Licensed by Ming Yi
Print Publication Date: 2008/10/21 User number: 594243
© 2009 Safari Books Online, LLC. This PDF is made available for personal use only during the relevant subscription term, subject to the Safari Terms of Service. Any other use