home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / comp / programm / 3563 < prev    next >
Encoding:
Internet Message Format  |  1993-01-24  |  1.6 KB
  1. Path: sparky!uunet!gatech!usenet.ins.cwru.edu!agate!mickey!bsmith
  2. From: bsmith@mickey.NoSubdomain.NoDomain (Brian Smith)
  3. Newsgroups: comp.programming
  4. Subject: Re: is it possible to find max & next smallest in one pass?
  5. Date: 24 Jan 1993 05:24:27 GMT
  6. Organization: University of California, Berkeley
  7. Lines: 37
  8. Sender: bsmith@mickey (Brian Smith)
  9. Distribution: world
  10. Message-ID: <1jt96b$kc9@agate.berkeley.edu>
  11. References: <1993Jan24.040702.6193@emr1.emr.ca>
  12. NNTP-Posting-Host: mickey.cs.berkeley.edu
  13.  
  14. In article <1993Jan24.040702.6193@emr1.emr.ca>, jagrant@emr1.emr.ca (John Grant) writes:
  15. |> Given an array of values, is it possible to find the maximum of
  16. |> the array and the next smallest value in a single pass?  The reason
  17. |> I want it in one pass, is that the array is actually a data file
  18. |> of a million float values.
  19. |> 
  20. |> If so, I guess the same single pass could also find the min and next
  21. |> highest value too?
  22. |> 
  23.  
  24.  
  25. how about this:
  26.  
  27. /* Keep max2 >= max1 */
  28. max1 = max2 = x[0];
  29. for (i=1; i<N; i++) {
  30.     if (x[i] > max1) {
  31.     if (x[i] > max2) {
  32.         max1 = max2;
  33.         max2 = x[i];
  34.     } else {
  35.         max1 = x[i];
  36.     } 
  37.     }
  38. }
  39. /* At this point, max2 is largest, min1 is next largest */
  40.  
  41. This does 2*N comparisons in the worst case, but (1+epsilon)*N comparisons
  42. in the average case.
  43.  
  44. In an actual implementation, it'd be worth it to unroll the loop a few times
  45. to make it run faster, unless your comparison operator is very slow.
  46.  
  47. -------
  48. Brian C. Smith                arpa:  bsmith@cs.Berkeley.EDU
  49. University of California, Berkeley    uucp: uunet!ucbvax!postgres!bsmith
  50. Computer Sciences Department        phone: (510)642-9585
  51.