Code from
Programming Pearls
Column 1: Programs for sorting integers
bitsort.c -- Sort with bit vectors.
sortints.cpp -- Sort using C++ STL sets.
qsortints.c -- Sort with C library qsort.
bitsortgen.c -- Generate random integers for sorting.
Column 2: Test and time algorithms
rotate.c -- Three ways to rotate the elements of a vector.
The next two program are used in a pipeline to compute all anagrams in a dictionary
sign.c -- Sign each word by its letters in sorted order.
squash.c -- Put each anagram class on a single line.
Column 5: Scaffolding for testing and timing search functions
search.c -- Linear and binary search.
Column 7: Tiny experiment on C run times
timemod0.c -- Edit main to time one operation.
Column 8: Compute the maximum-sum subsequence in an array
maxsum.c -- Time four algs: n3, n2, n log n, n.
Column 9: Code tuning programs
genbins.c -- Profile this, then try a special-purpose allocator.
macfun.c -- Time the cost of macros and functions.
The column also uses rotate.c (Column 2), search.c (Column 5) and maxsum.c (Column 8).
Column 11: Test and time sorting algorithms
sort.cpp -- Mostly C, but also C++ sort function.
SortAnim.java -- Animate those sort functions in Java.
Column 12: Generate a sorted list of random integers
sortedrand.cpp -- Several algorithms for the task.
Column 13: Set representations for the problem in Column 12
sets.cpp -- Several data structures for sets.
genbins.c (Column 9) implements the bin data structure in C.
Column 14: Heaps
priqueue.cpp -- Implement and test priority queues.
The column also uses sort.c (Column 11) for heapsort.
Column 15: Strings
wordlist.cpp -- List words in the file, using STL set.
wordfreq.cpp -- List words in the file, with counts, using STL map.
wordfreq.c -- Same as above, with hash table in C.
longdup.c -- Find long repeated strings in input.
markov.c -- Generate random text from input.
markovhash.c -- Like markov.c, but with hashing.
markovlet.c -- Letter-level markov text, simple algorithm.
Appendix 3: Cost Models
spacemod.cpp -- Space used by various records.
timemod.c -- Table of times used by various C constructs.
You may use this code for any purpose, as long as you leave the copyright notice and book citation attached.
2019-12-21 20:00:40
26KB
编程
1