git-basics-tutorial/thinkpython2012.html at master · etyme/git-basics-tutorial

History

660 lines (625 loc) · 45.1 KB

Raw

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

282

283

284

285

286

287

288

289

290

291

292

293

294

295

296

297

298

299

300

301

302

303

304

305

306

307

308

309

310

311

312

313

314

315

316

317

318

319

320

321

322

323

324

325

326

327

328

329

330

331

332

333

334

335

336

337

338

339

340

341

342

343

344

345

346

347

348

349

350

351

352

353

354

355

356

357

358

359

360

361

362

363

364

365

366

367

368

369

370

371

372

373

374

375

376

377

378

379

380

381

382

383

384

385

386

387

388

389

390

391

392

393

394

395

396

397

398

399

400

401

402

403

404

405

406

407

408

409

410

411

412

413

414

415

416

417

418

419

420

421

422

423

424

425

426

427

428

429

430

431

432

433

434

435

436

437

438

439

440

441

442

443

444

445

446

447

448

449

450

451

452

453

454

455

456

457

458

459

460

461

462

463

464

465

466

467

468

469

470

471

472

473

474

475

476

477

478

479

480

481

482

483

484

485

486

487

488

489

490

491

492

493

494

495

496

497

498

499

500

501

502

503

504

505

506

507

508

509

510

511

512

513

514

515

516

517

518

519

520

521

522

523

524

525

526

527

528

529

530

531

532

533

534

535

536

537

538

539

540

541

542

543

544

545

546

547

548

549

550

551

552

553

554

555

556

557

558

559

560

561

562

563

564

565

566

567

568

569

570

571

572

573

574

575

576

577

578

579

580

581

582

583

584

585

586

587

588

589

590

591

592

593

594

595

596

597

598

599

600

601

602

603

604

605

606

607

608

609

610

611

612

613

614

615

616

617

618

619

620

621

622

623

624

625

626

627

628

629

630

631

632

633

634

635

636

637

638

639

640

641

642

643

644

645

646

647

648

649

650

651

652

653

654

655

656

657

658

659

660

<!DOCTYPE html>

<html>

<head>

<title>Dictionaries</title>

</head>

<body>

Toggle navigation

</button>

<a class="navbar-brand" href="#">Think Python - How to Think like a Computer Scientist (2e) by Allen B. Downey</a>

</div>

<div>

</ul>

<div>

</div>

</nav>

<table>

<tr>

</td>

<h1 class="chapter" id="sec129">Chapter&#XA0;11&#XA0;&#XA0;Dictionaries</h1>

This chapter presents another built-in type called a dictionary.

Dictionaries are one of Python&#X2019;s best features; they are the

building blocks of many efficient and elegant algorithms.

<h2 class="section" id="sec130">11.1&#XA0;&#XA0;A dictionary is a mapping</h2>

A dictionary is like a list, but more general. In a list,

the indices have to be integers; in a dictionary they can

be (almost) any type.A dictionary contains a collection of indices, which are called keys, and a collection of values. Each key is associated with a

single value. The association of a key and a value is called a key-value pair or sometimes an item. <a id="hevea_default891"></a>In mathematical language, a dictionary represents a mapping

from keys to values, so you can also say that each key

&#X201C;maps to&#X201D; a value.

As an example, we&#X2019;ll build a dictionary that maps from English

to Spanish words, so the keys and the values are all strings.The function dict creates a new dictionary with no items.

Because dict is the name of a built-in function, you

should avoid using it as a variable name.

<a id="hevea_default893"></a><pre class="verbatim">>>> eng2sp = dict()

>>> eng2sp

{}

</pre>The squiggly-brackets, <code>{}</code>, represent an empty dictionary.

To add items to the dictionary, you can use square brackets:

<a id="hevea_default895"></a><pre class="verbatim">>>> eng2sp['one'] = 'uno'

</pre>This line creates an item that maps from the key

<code>'one'</code> to the value <code>'uno'</code>. If we print the

dictionary again, we see a key-value pair with a colon

between the key and value:<pre class="verbatim">>>> eng2sp

{'one': 'uno'}

</pre>This output format is also an input format. For example,

you can create a new dictionary with three items:<pre class="verbatim">>>> eng2sp = {'one': 'uno', 'two': 'dos', 'three': 'tres'}

</pre>But if you print eng2sp, you might be surprised:<pre class="verbatim">>>> eng2sp

{'one': 'uno', 'three': 'tres', 'two': 'dos'}

</pre>The order of the key-value pairs might not be the same. If

you type the same example on your computer, you might get a

different result. In general, the order of items in

a dictionary is unpredictable.But that&#X2019;s not a problem because

the elements of a dictionary are never indexed with integer indices.

Instead, you use the keys to look up the corresponding values:<pre class="verbatim">>>> eng2sp['two']

'dos'

</pre>The key <code>'two'</code> always maps to the value <code>'dos'</code> so the order

of the items doesn&#X2019;t matter.If the key isn&#X2019;t in the dictionary, you get an exception:

<a id="hevea_default897"></a><pre class="verbatim">>>> eng2sp['four']

KeyError: 'four'

</pre>The len function works on dictionaries; it returns the

number of key-value pairs:

<a id="hevea_default899"></a><pre class="verbatim">>>> len(eng2sp)

</pre>The in operator works on dictionaries, too; it tells you whether

something appears as a key in the dictionary (appearing

as a value is not good enough).

<a id="hevea_default902"></a><pre class="verbatim">>>> 'one' in eng2sp

True

>>> 'uno' in eng2sp

False

</pre>To see whether something appears as a value in a dictionary, you

can use the method values, which returns a collection of

values, and then use the in operator:

<a id="hevea_default904"></a><pre class="verbatim">>>> vals = eng2sp.values()

>>> 'uno' in vals

True

</pre>The in operator uses different algorithms for lists and

dictionaries. For lists, it searches the elements of the list in

order, as in Section&#XA0;<a href="thinkpython2009.html#find">8.6</a>. As the list gets longer, the search

time gets longer in direct proportion.For dictionaries, Python uses an

algorithm called a hashtable that has a remarkable property: the

in operator takes about the same amount of time no matter how

many items are in the dictionary. I explain how that&#X2019;s possible

in Section&#XA0;<a href="thinkpython2022.html#hashtable">B.4</a>, but the explanation might not make

sense until you&#X2019;ve read a few more chapters.

<h2 class="section" id="sec131">11.2&#XA0;&#XA0;Dictionary as a collection of counters</h2>

<a id="hevea_default905"></a>Suppose you are given a string and you want to count how many

times each letter appears. There are several ways you could do it:<ol class="enumerate" type=1><li class="li-enumerate">You could create 26 variables, one for each letter of the

alphabet. Then you could traverse the string and, for each

character, increment the corresponding counter, probably using

a chained conditional.</li><li class="li-enumerate">You could create a list with 26 elements. Then you could

convert each character to a number (using the built-in function

ord), use the number as an index into the list, and increment

the appropriate counter.</li><li class="li-enumerate">You could create a dictionary with characters as keys

and counters as the corresponding values. The first time you

see a character, you would add an item to the dictionary. After

that you would increment the value of an existing item.</li></ol>Each of these options performs the same computation, but each

of them implements that computation in a different way.

<a id="hevea_default906"></a>An implementation is a way of performing a computation;

some implementations are better than others. For example,

an advantage of the dictionary implementation is that we don&#X2019;t

have to know ahead of time which letters appear in the string

and we only have to make room for the letters that do appear.Here is what the code might look like:<pre class="verbatim">def histogram(s):

d = dict()

for c in s:

if c not in d:

d[c] = 1

else:

d[c] += 1

return d

</pre>The name of the function is histogram, which is a statistical

term for a collection of counters (or frequencies).

<a id="hevea_default909"></a>The first line of the

function creates an empty dictionary. The for loop traverses

the string. Each time through the loop, if the character c is

not in the dictionary, we create a new item with key c and the

initial value 1 (since we have seen this letter once). If c is

already in the dictionary we increment d[c].

<a id="hevea_default910"></a>Here&#X2019;s how it works:<pre class="verbatim">>>> h = histogram('brontosaurus')

>>> h

{'a': 1, 'b': 1, 'o': 2, 'n': 1, 's': 2, 'r': 2, 'u': 2, 't': 1}

</pre>The histogram indicates that the letters <code>'a'</code> and <code>'b'</code>

appear once; <code>'o'</code> appears twice, and so on.<a id="hevea_default911"></a>

Dictionaries have a method called get that takes a key

and a default value. If the key appears in the dictionary,

get returns the corresponding value; otherwise it returns

the default value. For example:<pre class="verbatim">>>> h = histogram('a')

>>> h

{'a': 1}

>>> h.get('a', 0)

>>> h.get('b', 0)

</pre>As an exercise, use get to write histogram more concisely. You

should be able to eliminate the if statement.

<h2 class="section" id="sec132">11.3&#XA0;&#XA0;Looping and dictionaries</h2>

<a id="hevea_default915"></a>If you use a dictionary in a for statement, it traverses

the keys of the dictionary. For example, <code>print_hist</code>

prints each key and the corresponding value:<pre class="verbatim">def print_hist(h):

for c in h:

print(c, h[c])

</pre>Here&#X2019;s what the output looks like:<pre class="verbatim">>>> h = histogram('parrot')

>>> print_hist(h)

a 1

p 1

r 2

t 1

o 1

</pre>Again, the keys are in no particular order. To traverse the keys

in sorted order, you can use the built-in function sorted:

<a id="hevea_default917"></a><pre class="verbatim">>>> for key in sorted(h):

... print(key, h[key])

a 1

o 1

p 1

r 2

t 1

</pre>

<h2 class="section" id="sec133">11.4&#XA0;&#XA0;Reverse lookup</h2>

<a id="hevea_default921"></a>Given a dictionary d and a key k, it is easy to

find the corresponding value v = d[k]. This operation

is called a lookup.But what if you have v and you want to find k?

You have two problems: first, there might be more than one

key that maps to the value v. Depending on the application,

you might be able to pick one, or you might have to make

a list that contains all of them. Second, there is no

simple syntax to do a reverse lookup; you have to search.Here is a function that takes a value and returns the first

key that maps to that value:<pre class="verbatim">def reverse_lookup(d, v):

for k in d:

if d[k] == v:

return k

raise LookupError()

</pre>This function is yet another example of the search pattern, but it

uses a feature we haven&#X2019;t seen before, raise. The

raise statement causes an exception; in this case it causes a

LookupError, which is a built-in exception used to indicate

that a lookup operation failed.

<a id="hevea_default926"></a> <a id="hevea_default927"></a>If we get to the end of the loop, that means v

doesn&#X2019;t appear in the dictionary as a value, so we raise an

exception.Here is an example of a successful reverse lookup:<pre class="verbatim">>>> h = histogram('parrot')

>>> key = reverse_lookup(h, 2)

>>> key

'r'

</pre>And an unsuccessful one:<pre class="verbatim">>>> key = reverse_lookup(h, 3)

Traceback (most recent call last):

File "<stdin>", line 1, in <module>

File "<stdin>", line 5, in reverse_lookup

LookupError

</pre>The effect when you raise an exception is the same as when

Python raises one: it prints a traceback and an error message.

<a id="hevea_default930"></a>The raise statement can take a detailed error message as an

optional argument. For example:<pre class="verbatim">>>> raise LookupError('value does not appear in the dictionary')

Traceback (most recent call last):

File "<stdin>", line 1, in ?

LookupError: value does not appear in the dictionary

</pre>A reverse lookup is much slower than a forward lookup; if you

have to do it often, or if the dictionary gets big, the performance

of your program will suffer.

<h2 class="section" id="sec134">11.5&#XA0;&#XA0;Dictionaries and lists</h2>

<a id="invert"></a>Lists can appear as values in a dictionary. For example, if you

are given a dictionary that maps from letters to frequencies, you

might want to invert it; that is, create a dictionary that maps

from frequencies to letters. Since there might be several letters

with the same frequency, each value in the inverted dictionary

should be a list of letters.

<a id="hevea_default932"></a>Here is a function that inverts a dictionary:<pre class="verbatim">def invert_dict(d):

inverse = dict()

for key in d:

val = d[key]

if val not in inverse:

inverse[val] = [key]

else:

inverse[val].append(key)

return inverse

</pre>Each time through the loop, key gets a key from d and

val gets the corresponding value. If val is not in inverse, that means we haven&#X2019;t seen it before, so we create a new

item and initialize it with a singleton (a list that contains a

single element). Otherwise we have seen this value before, so we

append the corresponding key to the list. <a id="hevea_default933"></a>Here is an example:<pre class="verbatim">>>> hist = histogram('parrot')

>>> hist

{'a': 1, 'p': 1, 'r': 2, 't': 1, 'o': 1}

>>> inverse = invert_dict(hist)

>>> inverse

{1: ['a', 'p', 't', 'o'], 2: ['r']}

</pre><blockquote class="figure"><div class="center"><hr class="c019"></div>

<div class="caption"><table class="c001 cellpading0"><tr><td class="c018">Figure 11.1: State diagram.</td></tr>

</table></div>

<div class="center"><hr class="c019"></div></blockquote>Figure&#XA0;<a href="thinkpython2012.html#fig.dict1">11.1</a> is a state diagram showing hist and inverse.

A dictionary is represented as a box with the type dict above it

and the key-value pairs inside. If the values are integers, floats or

strings, I draw them inside the box, but I usually draw lists

outside the box, just to keep the diagram simple.

<a id="hevea_default935"></a>Lists can be values in a dictionary, as this example shows, but they

cannot be keys. Here&#X2019;s what happens if you try:

<a id="hevea_default937"></a><pre class="verbatim">>>> t = [1, 2, 3]

>>> d = dict()

>>> d[t] = 'oops'

Traceback (most recent call last):

File "<stdin>", line 1, in ?

TypeError: list objects are unhashable

</pre>I mentioned earlier that a dictionary is implemented using

a hashtable and that means that the keys have to be hashable.

<a id="hevea_default939"></a>A hash is a function that takes a value (of any kind)

and returns an integer. Dictionaries use these integers,

called hash values, to store and look up key-value pairs.

<a id="hevea_default940"></a>This system works fine if the keys are immutable. But if the

keys are mutable, like lists, bad things happen. For example,

when you create a key-value pair, Python hashes the key and

stores it in the corresponding location. If you modify the

key and then hash it again, it would go to a different location.

In that case you might have two entries for the same key,

or you might not be able to find a key. Either way, the

dictionary wouldn&#X2019;t work correctly.That&#X2019;s why keys have to be hashable, and why mutable types like

lists aren&#X2019;t. The simplest way to get around this limitation is to

use tuples, which we will see in the next chapter.Since dictionaries are mutable, they can&#X2019;t be used as keys,

but they can be used as values.

<h2 class="section" id="sec135">11.6&#XA0;&#XA0;Memos</h2>

<a id="memoize"></a>If you played with the fibonacci function from

Section&#XA0;<a href="thinkpython2007.html#one.more.example">6.7</a>, you might have noticed that the bigger

the argument you provide, the longer the function takes to run.

Furthermore, the run time increases quickly.

<a id="hevea_default942"></a>To understand why, consider Figure&#XA0;<a href="thinkpython2012.html#fig.fibonacci">11.2</a>, which shows

the call graph for fibonacci with n=4:<blockquote class="figure"><div class="center"><hr class="c019"></div>

<div class="caption"><table class="c001 cellpading0"><tr><td class="c018">Figure 11.2: Call graph.</td></tr>

</table></div>

<div class="center"><hr class="c019"></div></blockquote>A call graph shows a set of function frames, with lines connecting each

frame to the frames of the functions it calls. At the top of the

graph, fibonacci with n=4 calls fibonacci with n=3 and n=2. In turn, fibonacci with n=3 calls

fibonacci with n=2 and n=1. And so on.

<a id="hevea_default945"></a>Count how many times fibonacci(0) and fibonacci(1) are

called. This is an inefficient solution to the problem, and it gets

worse as the argument gets bigger.

<a id="hevea_default946"></a>One solution is to keep track of values that have already been

computed by storing them in a dictionary. A previously computed value

that is stored for later use is called a memo. Here is a

&#X201C;memoized&#X201D; version of fibonacci:<pre class="verbatim">known = {0:0, 1:1}

def fibonacci(n):

if n in known:

return known[n]

res = fibonacci(n-1) + fibonacci(n-2)

known[n] = res

return res

</pre>known is a dictionary that keeps track of the Fibonacci

numbers we already know. It starts with

two items: 0 maps to 0 and 1 maps to 1.Whenever fibonacci is called, it checks known.

If the result is already there, it can return

immediately. Otherwise it has to

compute the new value, add it to the dictionary, and return it.If you run this version of fibonacci and compare it with

the original, you will find that it is much faster.

<h2 class="section" id="sec136">11.7&#XA0;&#XA0;Global variables</h2>

<a id="hevea_default948"></a>In the previous example, known is created outside the function,

so it belongs to the special frame called <code>__main__</code>.

Variables in <code>__main__</code> are sometimes called global

because they can be accessed from any function. Unlike local

variables, which disappear when their function ends, global variables

persist from one function call to the next.

<a id="hevea_default949"></a>It is common to use global variables for flags; that is,

boolean variables that indicate (&#X201C;flag&#X201D;) whether a condition

is true. For example, some programs use

a flag named verbose to control the level of detail in the

output:<pre class="verbatim">verbose = True

def example1():

if verbose:

print('Running example1')

</pre>If you try to reassign a global variable, you might be surprised.

The following example is supposed to keep track of whether the

function has been called:

<a id="hevea_default950"></a><pre class="verbatim">been_called = False

def example2():

been_called = True # WRONG

</pre>But if you run it you will see that the value of <code>been_called</code>

doesn&#X2019;t change. The problem is that example2 creates a new local

variable named <code>been_called</code>. The local variable goes away when

the function ends, and has no effect on the global variable.

<a id="hevea_default953"></a>To reassign a global variable inside a function you have to

declare the global variable before you use it:<pre class="verbatim">been_called = False

def example2():

global been_called

been_called = True

</pre>The global statement tells the interpreter

something like, &#X201C;In this function, when I say <code>been_called</code>, I

mean the global variable; don&#X2019;t create a local one.&#X201D;

<a id="hevea_default955"></a>Here&#X2019;s an example that tries to update a global variable:<pre class="verbatim">count = 0

def example3():

count = count + 1 # WRONG

</pre>If you run it you get:

<a id="hevea_default957"></a><pre class="verbatim">UnboundLocalError: local variable 'count' referenced before assignment

</pre>Python assumes that count is local, and under that assumption

you are reading it before writing it. The solution, again,

is to declare count global.

<a id="hevea_default958"></a><pre class="verbatim">def example3():

global count

count += 1

</pre>If a global variable refers to a mutable value, you can modify

the value without declaring the variable:

<a id="hevea_default959"></a><pre class="verbatim">known = {0:0, 1:1}

def example4():

known[2] = 1

</pre>So you can add, remove and replace elements of a global list or

dictionary, but if you want to reassign the variable, you

have to declare it:<pre class="verbatim">def example5():

global known

known = dict()

</pre>Global variables can be useful, but if you have a lot of them,

and you modify them frequently, they can make programs

hard to debug.

<h2 class="section" id="sec137">11.8&#XA0;&#XA0;Debugging</h2>

<a id="hevea_default960"></a>As you work with bigger datasets it can become unwieldy to

debug by printing and checking the output by hand. Here are some

suggestions for debugging large datasets:<dl class="description"><dt class="dt-description">Scale down the input:</dt><dd class="dd-description"> If possible, reduce the size of the

dataset. For example if the program reads a text file, start with

just the first 10 lines, or with the smallest example you can find.

You can either edit the files themselves, or (better) modify the

program so it reads only the first n lines.If there is an error, you can reduce n to the smallest

value that manifests the error, and then increase it gradually

as you find and correct errors.</dd><dt class="dt-description">Check summaries and types:</dt><dd class="dd-description"> Instead of printing and checking the

entire dataset, consider printing summaries of the data: for example,

the number of items in a dictionary or the total of a list of numbers.A common cause of runtime errors is a value that is not the right

type. For debugging this kind of error, it is often enough to print

the type of a value.</dd><dt class="dt-description">Write self-checks:</dt><dd class="dd-description"> Sometimes you can write code to check

for errors automatically. For example, if you are computing the

average of a list of numbers, you could check that the result is

not greater than the largest element in the list or less than

the smallest. This is called a &#X201C;sanity check&#X201D; because it detects

results that are &#X201C;insane&#X201D;.

<a id="hevea_default962"></a>Another kind of check compares the results of two different

computations to see if they are consistent. This is called a

&#X201C;consistency check&#X201D;.</dd><dt class="dt-description">Format the output:</dt><dd class="dd-description"> Formatting debugging output

can make it easier to spot an error. We saw an example in

Section&#XA0;<a href="thinkpython2007.html#factdebug">6.9</a>. The pprint module provides

a pprint function that displays built-in types in

a more human-readable format (pprint stands for

&#X201C;pretty print&#X201D;).

<a id="hevea_default965"></a></dd></dl>Again, time you spend building scaffolding can reduce

the time you spend debugging.

<h2 class="section" id="sec138">11.9&#XA0;&#XA0;Glossary</h2>

<dl class="description"><dt class="dt-description">mapping:</dt><dd class="dd-description"> A relationship in which each element of one set

corresponds to an element of another set.

<a id="hevea_default967"></a></dd><dt class="dt-description">dictionary:</dt><dd class="dd-description"> A mapping from keys to their

corresponding values.

<a id="hevea_default968"></a></dd><dt class="dt-description">key-value pair:</dt><dd class="dd-description"> The representation of the mapping from

a key to a value.

<a id="hevea_default969"></a></dd><dt class="dt-description">item:</dt><dd class="dd-description"> In a dictionary, another name for a key-value

pair.

<a id="hevea_default970"></a></dd><dt class="dt-description">key:</dt><dd class="dd-description"> An object that appears in a dictionary as the

first part of a key-value pair.

<a id="hevea_default971"></a></dd><dt class="dt-description">value:</dt><dd class="dd-description"> An object that appears in a dictionary as the

second part of a key-value pair. This is more specific than

our previous use of the word &#X201C;value&#X201D;.

<a id="hevea_default972"></a></dd><dt class="dt-description">implementation:</dt><dd class="dd-description"> A way of performing a computation.

<a id="hevea_default973"></a></dd><dt class="dt-description">hashtable:</dt><dd class="dd-description"> The algorithm used to implement Python

dictionaries.

<a id="hevea_default974"></a></dd><dt class="dt-description">hash function:</dt><dd class="dd-description"> A function used by a hashtable to compute the

location for a key.

<a id="hevea_default975"></a></dd><dt class="dt-description">hashable:</dt><dd class="dd-description"> A type that has a hash function. Immutable

types like integers,

floats and strings are hashable; mutable types like lists and

dictionaries are not.

<a id="hevea_default976"></a></dd><dt class="dt-description">lookup:</dt><dd class="dd-description"> A dictionary operation that takes a key and finds

the corresponding value.

<a id="hevea_default977"></a></dd><dt class="dt-description">reverse lookup:</dt><dd class="dd-description"> A dictionary operation that takes a value and finds

one or more keys that map to it.

<a id="hevea_default978"></a></dd><dt class="dt-description">raise statement:</dt><dd class="dd-description"> A statement that (deliberately) raises an exception.

<a id="hevea_default980"></a></dd><dt class="dt-description">singleton:</dt><dd class="dd-description"> A list (or other sequence) with a single element.

<a id="hevea_default981"></a></dd><dt class="dt-description">call graph:</dt><dd class="dd-description"> A diagram that shows every frame created during

the execution of a program, with an arrow from each caller to

each callee.

<a id="hevea_default983"></a></dd><dt class="dt-description">memo:</dt><dd class="dd-description"> A computed value stored to avoid unnecessary future

computation.

<a id="hevea_default984"></a></dd><dt class="dt-description">global variable:</dt><dd class="dd-description"> A variable defined outside a function. Global

variables can be accessed from any function.

<a id="hevea_default985"></a></dd><dt class="dt-description">global statement:</dt><dd class="dd-description"> A statement that declares a variable name

global.

<a id="hevea_default987"></a></dd><dt class="dt-description">flag:</dt><dd class="dd-description"> A boolean variable used to indicate whether a condition

is true.

<a id="hevea_default988"></a></dd><dt class="dt-description">declaration:</dt><dd class="dd-description"> A statement like global that tells the

interpreter something about a variable.

<h2 class="section" id="sec139">11.10&#XA0;&#XA0;Exercises</h2>

<div class="theorem">Exercise&#XA0;1&#XA0;&#XA0;

<a id="hevea_default991"></a>Write a function that reads the words in words.txt and

stores them as keys in a dictionary. It doesn&#X2019;t matter what the

values are. Then you can use the in operator

as a fast way to check whether a string is in

the dictionary.If you did Exercise&#XA0;<a href="thinkpython2011.html#wordlist1">10</a>, you can compare the speed

of this implementation with the list in operator and the

bisection search.</div><div class="theorem">Exercise&#XA0;2&#XA0;&#XA0;

<a id="setdefault"></a>Read the documentation of the dictionary method setdefault

and use it to write a more concise version of <code>invert_dict</code>.

Solution: <a href="http://thinkpython2.com/code/invert_dict.py">http://thinkpython2.com/code/invert_dict.py</a>.

<a id="hevea_default993"></a></div><div class="theorem">Exercise&#XA0;3&#XA0;&#XA0;

Memoize the Ackermann function from Exercise&#XA0;<a href="thinkpython2007.html#ackermann">2</a> and see if

memoization makes it possible to evaluate the function with bigger

arguments. Hint: no.

Solution: <a href="http://thinkpython2.com/code/ackermann_memo.py">http://thinkpython2.com/code/ackermann_memo.py</a>.

<a id="hevea_default995"></a></div><div class="theorem">Exercise&#XA0;4&#XA0;&#XA0;

<a id="hevea_default996"></a>If you did Exercise&#XA0;<a href="thinkpython2011.html#duplicate">7</a>, you already have

a function named <code>has_duplicates</code> that takes a list

as a parameter and returns True if there is any object

that appears more than once in the list.Use a dictionary to write a faster, simpler version of

<code>has_duplicates</code>.

Solution: <a href="http://thinkpython2.com/code/has_duplicates.py">http://thinkpython2.com/code/has_duplicates.py</a>.</div><div class="theorem">Exercise&#XA0;5&#XA0;&#XA0;

<a id="hevea_default998"></a>Two words are &#X201C;rotate pairs&#X201D; if you can rotate one of them

and get the other (see <code>rotate_word</code> in Exercise&#XA0;<a href="thinkpython2009.html#exrotate">5</a>).Write a program that reads a wordlist and finds all the rotate

pairs. Solution: <a href="http://thinkpython2.com/code/rotate_pairs.py">http://thinkpython2.com/code/rotate_pairs.py</a>.</div><div class="theorem">Exercise&#XA0;6&#XA0;&#XA0;

<a id="hevea_default1000"></a>Here&#X2019;s another Puzzler from Car Talk

(<a href="http://www.cartalk.com/content/puzzlers">http://www.cartalk.com/content/puzzlers</a>):<blockquote class="quote">

This was sent in by a fellow named Dan O&#X2019;Leary. He came upon a common

one-syllable, five-letter word recently that has the following unique

property. When you remove the first letter, the remaining letters form

a homophone of the original word, that is a word that sounds exactly

the same. Replace the first letter, that is, put it back and remove

the second letter and the result is yet another homophone of the

original word. And the question is, what&#X2019;s the word?Now I&#X2019;m going to give you an example that doesn&#X2019;t work. Let&#X2019;s look at

the five-letter word, &#X2018;wrack.&#X2019; W-R-A-C-K, you know like to &#X2018;wrack with

pain.&#X2019; If I remove the first letter, I am left with a four-letter

word, &#X2019;R-A-C-K.&#X2019; As in, &#X2018;Holy cow, did you see the rack on that buck!

It must have been a nine-pointer!&#X2019; It&#X2019;s a perfect homophone. If you

put the &#X2018;w&#X2019; back, and remove the &#X2018;r,&#X2019; instead, you&#X2019;re left with the

word, &#X2018;wack,&#X2019; which is a real word, it&#X2019;s just not a homophone of the

other two words.But there is, however, at least one word that Dan and we know of,

which will yield two homophones if you remove either of the first two

letters to make two, new four-letter words. The question is, what&#X2019;s

the word?

</blockquote>

<a id="hevea_default1003"></a>You can use the dictionary from Exercise&#XA0;<a href="thinkpython2012.html#wordlist2">1</a> to check

whether a string is in the word list.To check whether two words are homophones, you can use the CMU

Pronouncing Dictionary. You can download it from

<a href="http://www.speech.cs.cmu.edu/cgi-bin/cmudict">http://www.speech.cs.cmu.edu/cgi-bin/cmudict</a> or from

<a href="http://thinkpython2.com/code/c06d">http://thinkpython2.com/code/c06d</a> and you can also download

<a href="http://thinkpython2.com/code/pronounce.py">http://thinkpython2.com/code/pronounce.py</a>, which provides a function

named <code>read_dictionary</code> that reads the pronouncing dictionary and

returns a Python dictionary that maps from each word to a string that

describes its primary pronunciation.Write a program that lists all the words that solve the Puzzler.

Solution: <a href="http://thinkpython2.com/code/homophone.py">http://thinkpython2.com/code/homophone.py</a>.</div>

</td>

<h4>Are you using one of our books in a class?</h4> We'd like to know

about it. Please consider filling out <a href="http://spreadsheets.google.com/viewform?formkey=dC0tNUZkMjBEdXVoRGljNm9FRmlTMHc6MA" onClick="javascript: pageTracker._trackPageview('/outbound/survey');">this short survey</a>.

<a rel="nofollow" href="http://www.amazon.com/gp/product/1491938455/ref=as_li_tl?ie=UTF8&camp=1789&creative=9325&creativeASIN=1491938455&linkCode=as2&tag=greenteapre01-20&linkId=2JJH4SWCAVVYSQHO">Think DSP</a><img class="c003" src="http://ir-na.amazon-adsystem.com/e/ir?t=greenteapre01-20&l=as2&o=1&a=1491938455" width="1" height="1" border="0" alt="">

<a rel="nofollow" href="http://www.amazon.com/gp/product/1491929561/ref=as_li_tl?ie=UTF8&camp=1789&creative=9325&creativeASIN=1491929561&linkCode=as2&tag=greenteapre01-20&linkId=ZY6MAYM33ZTNSCNZ">Think Java</a><img class="c003" src="http://ir-na.amazon-adsystem.com/e/ir?t=greenteapre01-20&l=as2&o=1&a=1491929561" width="1" height="1" border="0" alt="">

<a href="http://www.amazon.com/gp/product/1449370780/ref=as_li_qf_sp_asin_tl?ie=UTF8&camp=1789&creative=9325&creativeASIN=1449370780&linkCode=as2&tag=greenteapre01-20">Think Bayes</a><img class="c003" src="http://ir-na.amazon-adsystem.com/e/ir?t=greenteapre01-20&l=as2&o=1&a=1449370780" width="1" height="1" border="0" alt="">

<a rel="nofollow" href="http://www.amazon.com/gp/product/1491939362/ref=as_li_tl?ie=UTF8&camp=1789&creative=9325&creativeASIN=1491939362&linkCode=as2&tag=greenteapre01-20&linkId=FJKSQ3IHEMY2F2VA">Think Python 2e</a><img class="c003" src="http://ir-na.amazon-adsystem.com/e/ir?t=greenteapre01-20&l=as2&o=1&a=1491939362" width="1" height="1" border="0" alt="">

<a href="http://www.amazon.com/gp/product/1491907339/ref=as_li_tl?ie=UTF8&camp=1789&creative=9325&creativeASIN=1491907339&linkCode=as2&tag=greenteapre01-20&linkId=O7WYM6H6YBYUFNWU">Think Stats 2e</a><img class="c003" src="http://ir-na.amazon-adsystem.com/e/ir?t=greenteapre01-20&l=as2&o=1&a=1491907339" width="1" height="1" border="0" alt="">

<a href="http://www.amazon.com/gp/product/1449314635/ref=as_li_tf_tl?ie=UTF8&tag=greenteapre01-20&linkCode=as2&camp=1789&creative=9325&creativeASIN=1449314635">Think Complexity</a><img class="c003" src="http://www.assoc-amazon.com/e/ir?t=greenteapre01-20&l=as2&o=1&a=1449314635" width="1" height="1" border="0" alt="">

</td>

</tr>

</table>

Toggle navigation

</button>

<a class="navbar-brand" href="#">Think Python - How to Think like a Computer Scientist (2e) by Allen B. Downey</a>

</div>

<div>

</ul>

<div>

</div>

</nav></body>

</html>

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

FilesExpand file tree

thinkpython2012.html

Latest commit

History

thinkpython2012.html

File metadata and controls