Large Problems, Small Machines - 1st Edition - ISBN: 9780123390905, 9781483271323

Large Problems, Small Machines

1st Edition

Transforming Your Programs with Advanced Algorithms

Authors: Steve Heller
eBook ISBN: 9781483271323
Imprint: Academic Press
Published Date: 28th April 1992
Page Count: 272
Tax/VAT will be calculated at check-out Price includes VAT (GST)
30% off
30% off
30% off
30% off
30% off
20% off
20% off
30% off
30% off
30% off
30% off
30% off
20% off
20% off
30% off
30% off
30% off
30% off
30% off
20% off
20% off
72.95
51.06
51.06
51.06
51.06
51.06
58.36
58.36
43.99
30.79
30.79
30.79
30.79
30.79
35.19
35.19
54.95
38.47
38.47
38.47
38.47
38.47
43.96
43.96
Unavailable
Price includes VAT (GST)
× DRM-Free

Easy - Download and start reading immediately. There’s no activation process to access eBooks; all eBooks are fully searchable, and enabled for copying, pasting, and printing.

Flexible - Read on multiple operating systems and devices. Easily read eBooks on smart phones, computers, or any eBook readers, including Kindle.

Open - Buy once, receive and download all available eBook formats, including PDF, EPUB, and Mobi (for Kindle).

Institutional Access

Secure Checkout

Personal information is secured with SSL technology.

Free Shipping

Free global shipping
No minimum order.

Description

Large Problems, Small Machines: Transforming Your Programs with Advanced Algorithms describes a practical, real-world approach to program optimization based on advanced algorithms. Topics covered range from how to save storage using a restricted character set and how to speed up access to records by employing hash coding (or "scatter storage") and caching. A selective mailing list system is used to illustrate rapid access to and rearrangement of information selected by criteria specified at run-time.

Comprised of six chapters, this book begins by discussing factors to consider when deciding whether a program needs optimization. In the next chapter, a supermarket price lookup system is used to illustrate how to save storage by using a restricted character set and how to speed up access to records with the aid of hash coding and caching. Attention is paid to rapid retrieval of prices. A selective mailing list system is then used to illustrate rapid access to and rearrangement of information selected by criteria specified at run-time. The book also considers the Huffman coding and arithmetic coding methods of data compression before concluding with a review of the characteristics of the algorithms encountered in previous chapters, as well as the future of the art of optimization.

This monograph will be a useful resource for practicing computer programmers and those who intend to be working programmers.

Table of Contents


Figures

Foreword

Preface

Chapter 1: Let's Cet Small (and Fast): Introduction to Optimization

Deciding Whether to Optimize

Why Optimization Is Necessary

Why Optimization Is Often Neglected

Considering a Hardware Solution

Categories of Optimization

Finding the Critical Resource

Determining How Much Optimization Is Needed

A Real-Life Example

Summary

Radtesth: Include File for Radix40 Routines

Radix40.h: Include File for Radix40 Routines

Ascrad1.c: Radix40 Test Program #1

Ascrad2.c: Radix40 Test Program #2

Ascrad3.c: Radix40 Test Program #3

Ascrad4.c: Radix40 Test Program #4

Radasc.c: Radix40 to Ascii Conversion

Chapter 2: Hash, Cache, and Crunch: A Supermarket Price Lookup System

Introduction

A Possible Solution

Some Random Musings

Starting at the Beginning

Divide and Conquer

Unite and Rule

Knowing When to Stop

Handling Subfile Overflow

Some Drawbacks of Hashing

The Only Good Disk Access

Heading for The Final Lookup

Saving Storage

The Code

Some User-Defined Types

Preparing to Access The Price File

Making a Hash of Things

Searching the File

Wrapping Around at End-of-File

Summary

Problems

Program Listings

Superm.h: Supermarket Pricing Include File

Superm.c: Supermarket Pricing Main Program

Suplook.c: Supermarket Pricing Lookup Routines

Bcdconv.h: BCD Conversion Include File

Bcdconv.c: Conversions to/from BCD

Radix40.c: Conversions to/from Radix40 Representation

Stestgen.c: Generates Test Code File

Supinit.c: Supermarket Pricing File Initialization

Supert.c: Supermarket Pricing Main Program

Chapter 3: Strips, Bits, and Sorts: A Mailing List System

Introduction

A First Approach

Starting the Optimization

Saving Storage with Bitmaps

Increasing Processing Speed

The Law of Diminishing Returns

Strip Mining

Sorting Speed

The Distribution Counting Sort

Multi-Character Sorting

On the Home Stretch

The Code

Determining the Proper Buffer Size

Preparing to Read the Key File

Reading the Key File

Setting a Bit in a Bitmap

Allocate as You Go

Getting Ready to Sort

The Megasort Routine

Finishing Up

Performance

Summary

Problems

Program Listings

Mailx.h: Mailing List Include File

Mailx.c: Mailing List Program

Mail.h: Mailing List Include File

Maily.c: Mailing List Program

Mail.c: Mailing List Program

Megac.c: Distribution Sorting Program

Sorttest.c: Test Sorting Program

Bitfunc.h: Bitmap Header File

Bitfunc.c: Bitmap Functions

Chapter 4: Cn U Rd Ths Okly? A Data Compression Utility

Introduction

Huffman Coding

Half a Bit Is Better Than One

Getting a Bit Excited

A Character Study

Keeping It in Context

Conspicuous Non-Consumption

Receiving the Message

The Code

A Loose Translation

Getting in on the Ground Floor

Gentlemen, Start Your Output

The Main Loop

Encode_Symbol

Update_Model

Finding the Bottlenecks

Dead Slow Ahead

Getting the Correct Answer, Slowly

Some Assembly is Required

Memories Are Made of This

Loop, De-Loop

Odd Man Out

Getting There Is Half the Fun

A Bunch of Real Characters

Summary

Problems

Program Listings

Arith.h: Arithmetic Coding Constants

Model.h: Translation Table Coding Constants and Variables

Encode.c: Encoding Main Module

Encodel.c: Encoding Main Module

Adapt.c: Adaptive Modeling Routines

Arenc.c: Arithmetic Encoding Routines

Longasm.c: Comparison of C and Assembly in Long Arithmetic

Arenc1.c: Arithmetic Encoding Routines, with Assembly

Arenc2.c: Arithmetic Encoding Routines, with Assembly

Decode.c: Decoding Main Module

Decode1.c: Decoding Main Module

Ardec.c: Arithmetic Decoding Routines

Chapter 5: Free at Last: A Customer Database Program with Variable Length Records

Introduction

A Harmless Fixation

Checking Out of the Hotel Procrustes

The Quantum File Access Method

A Large Array

Many Large Arrays

The Light at the End of the Tunnel

The Quantum File Header Record

The Itinerary

Let's Get Physical

Get_Quantum

Find_Buffer

Reading, Writing, and

A Logical Analysis

qf_Open_Quantum_File

qf_Create_Main_Object

Reserve_Available_Quantum

Initialize_Big_Pointer_Array

qf_Store_Item and qf_Get_Item

Add_Item_to_Quantum

Delete_Item_in_Quantum

qf_Close_Quantum_File

Get_Pointer_to_Item

The Grab Bag

Taking it from the Top

Initialize_Quantum_File

Edit_Customer_Records

Summary

Problems

Program Listings

Custdata.h: Customer Data Base Include File

Custdata.c: Customer Database Program

Xmemd.h: Include File to Provide Dummy Extended Memory Allocation Routines

Quantum.h: Quantum File Header

Quantum.c: Quantum File Functions

Chapter 6: Mozart, No; Would You Believe Gershwin?

Introduction

Summary of Characteristics

Some Thoughts on the Future

Why Johnny Can't Estimate

Goodbye for Now

Suggested Approaches to Problems

Ordering Instructions

Index

Details

No. of pages:
272
Language:
English
Copyright:
© Academic Press 1992
Published:
Imprint:
Academic Press
eBook ISBN:
9781483271323

About the Author

Steve Heller

Steve Heller has been a professional programmer for about 25 years, and is the President of Chrysalis Software Corporation, a consulting firm specializing in high-performance software, and practical, down-to-earth instructional materials. He is the author of two excellent books, Efficient C/C++ Programming and Who’s Afraid of C++?.

Affiliations and Expertise

President, Chrysalis Software Corp.