Large Problems, Small Machines
Transforming Your Programs with Advanced Algorithms
- 1st Edition - April 28, 1992
- Imprint: Academic Press
- Author: Steve Heller
- Language: English
- Paperback ISBN:9 7 8 - 1 - 4 8 3 2 - 4 0 4 8 - 0
- eBook ISBN:9 7 8 - 1 - 4 8 3 2 - 7 1 3 2 - 3
Large Problems, Small Machines: Transforming Your Programs with Advanced Algorithms describes a practical, real-world approach to program optimization based on advanced algorithms.… Read more
Purchase options
Institutional subscription on ScienceDirect
Request a sales quoteLarge 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.
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
- Edition: 1
- Published: April 28, 1992
- No. of pages (eBook): 272
- Imprint: Academic Press
- Language: English
- Paperback ISBN: 9781483240480
- eBook ISBN: 9781483271323
SH
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.Read Large Problems, Small Machines on ScienceDirect