c8-5 (779528), страница 2
Текст из файла (страница 2)
An exampleis to use the method of Heapsort (§8.3) to make a single pass through an array oflength N while saving the m largest elements. The advantage of the heap structureis that only log m, rather than m, comparisons are required every time a new√elementis added to the candidate list. This becomes a real savings when m > O( N), butit never hurts otherwise and is easy to code. The following program gives the idea.void hpsel(unsigned long m, unsigned long n, float arr[], float heap[])Returns in heap[1..m] the largest m elements of the array arr[1..n], with heap[1] guaranteed to be the the mth largest element. The array arr is not altered. For efficiency, this routineshould be used only when m n.{void sort(unsigned long n, float arr[]);void nrerror(char error_text[]);unsigned long i,j,k;float swap;if (m > n/2 || m < 1) nrerror("probable misuse of hpsel");for (i=1;i<=m;i++) heap[i]=arr[i];sort(m,heap);Create initial heap by overkill! We assume m n.for (i=m+1;i<=n;i++) {For each remaining element...if (arr[i] > heap[1]) {Put it on the heap?heap[1]=arr[i];for (j=1;;) {Sift down.Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5)Copyright (C) 1988-1992 by Cambridge University Press.Programs Copyright (C) 1988-1992 by Numerical Recipes Software.Permission is granted for internet users to make one paper copy for their own personal use.
Further reproduction, or any copying of machinereadable files (including this one) to any servercomputer, is strictly prohibited. To order Numerical Recipes books,diskettes, or CDROMsvisit website http://www.nr.com or call 1-800-872-7423 (North America only),or send email to trade@cup.cam.ac.uk (outside North America).}sel[M+1]=sum/mm;Augment selected set by mean value (fixesshell(M+1,sel);degeneracies), and sort it.sel[M+2]=ahi;for (j=1;j<=M+2;j++) isel[j]=0;Zero the count array.for (i=1;i<=n;i++) {Make another pass through the array.if (arr[i] >= alo && arr[i] <= ahi) {For each in-range element..jl=0;ju=M+2;while (ju-jl > 1) {...find its position among the select byjm=(ju+jl)/2;bisection...if (arr[i] >= sel[jm]) jl=jm;else ju=jm;}isel[ju]++;...and increment the counter.}}j=1;Now we can narrow the bounds to justwhile (kk > isel[j]) {one bin, that is, by a factor of orderalo=sel[j];m.kk -= isel[j++];}ahi=sel[j];8.6 Determination of Equivalence Classes345}}}}CITED REFERENCES AND FURTHER READING:Sedgewick, R.
1988, Algorithms, 2nd ed. (Reading, MA: Addison-Wesley), pp. 126ff. [1]Knuth, D.E. 1973, Sorting and Searching, vol. 3 of The Art of Computer Programming (Reading,MA: Addison-Wesley).8.6 Determination of Equivalence ClassesA number of techniques for sorting and searching relate to data structures whose detailsare beyond the scope of this book, for example, trees, linked lists, etc. These structures andtheir manipulations are the bread and butter of computer science, as distinct from numericalanalysis, and there is no shortage of books on the subject.In working with experimental data, we have found that one particular such manipulation,namely the determination of equivalence classes, arises sufficiently often to justify inclusionhere.The problem is this: There are N “elements” (or “data points” or whatever), numbered1, . .
. , N . You are given pairwise information about whether elements are in the sameequivalence class of “sameness,” by whatever criterion happens to be of interest. Forexample, you may have a list of facts like: “Element 3 and element 7 are in the same class;element 19 and element 4 are in the same class; element 7 and element 12 are in the sameclass, . .
. .” Alternatively, you may have a procedure, given the numbers of two elementsj and k, for deciding whether they are in the same class or different classes. (Recall thatan equivalence relation can be anything satisfying the RST properties: reflexive, symmetric,transitive. This is compatible with any intuitive definition of “sameness.”)The desired output is an assignment to each of the N elements of an equivalence classnumber, such that two elements are in the same class if and only if they are assigned thesame class number.Efficient algorithms work like this: Let F (j) be the class or “family” number of elementj. Start off with each element in its own family, so that F (j) = j. The array F (j) can beinterpreted as a tree structure, where F (j) denotes the parent of j. If we arrange for each familyto be its own tree, disjoint from all the other “family trees,” then we can label each family(equivalence class) by its most senior great-great-.
. .grandparent. The detailed topology ofthe tree doesn’t matter at all, as long as we graft each related element onto it somewhere.Therefore, we process each elemental datum “j is equivalent to k” by (i) tracking jup to its highest ancestor, (ii) tracking k up to its highest ancestor, (iii) giving j to k as anew parent, or vice versa (it makes no difference).
After processing all the relations, we gothrough all the elements j and reset their F (j)’s to their highest possible ancestors, whichthen label the equivalence classes.The following routine, based on Knuth [1], assumes that there are m elemental piecesof information, stored in two arrays of length m, lista,listb, the interpretation beingthat lista[j] and listb[j], j=1...m, are the numbers of two elements which (we arethus told) are related.Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5)Copyright (C) 1988-1992 by Cambridge University Press.Programs Copyright (C) 1988-1992 by Numerical Recipes Software.Permission is granted for internet users to make one paper copy for their own personal use. Further reproduction, or any copying of machinereadable files (including this one) to any servercomputer, is strictly prohibited.
To order Numerical Recipes books,diskettes, or CDROMsvisit website http://www.nr.com or call 1-800-872-7423 (North America only),or send email to trade@cup.cam.ac.uk (outside North America).k=j << 1;if (k > m) break;if (k != m && heap[k] > heap[k+1]) k++;if (heap[j] <= heap[k]) break;swap=heap[k];heap[k]=heap[j];heap[j]=swap;j=k;.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
