home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / comp / lang / perl / 5662 < prev    next >
Encoding:
Internet Message Format  |  1992-09-01  |  2.2 KB
  1. Path: sparky!uunet!cs.utexas.edu!sun-barr!ames!elroy.jpl.nasa.gov!usc!news!netlabs!lwall
  2. From: lwall@netlabs.com (Larry Wall)
  3. Newsgroups: comp.lang.perl
  4. Subject: Re: randomize.c
  5. Message-ID: <1992Sep1.210332.26149@netlabs.com>
  6. Date: 1 Sep 92 21:03:32 GMT
  7. References: <Bts28y.DJA@rahul.net> <AAS.92Aug31133620@rosmer.nr.no> <1992Aug31.183903.4143@cirrus.com>
  8. Sender: news@netlabs.com
  9. Organization: NetLabs, Inc.
  10. Lines: 36
  11. Nntp-Posting-Host: scalpel.netlabs.com
  12.  
  13. In article <1992Aug31.183903.4143@cirrus.com> dhesi@cirrus.com (Rahul Dhesi) writes:
  14. : In <AAS.92Aug31133620@rosmer.nr.no> aas@rosmer.nr.no (Gisle Aas) writes:
  15. : 
  16. : >Why not:    perl -e '@l=<>;print splice(@l,rand($#l),1) while @l'
  17.  
  18. A rand() returns a number *exclusive* of its endpoint, so you'd really want
  19.  
  20.     perl -e 'srand; @l=<>; print splice(@l, rand @l, 1) while @l'
  21.  
  22. : I considered using splice and decided not to take the risk of a
  23. : possibly inefficient implementation.  Later I was told that the perl
  24. : book already has such a program.
  25.  
  26. Unless you know how things are implemented, it's best to try it both
  27. ways and see which is faster.  Most builtins are fairly efficient,
  28. though you can occasionally beat them if you have a problem that's
  29. weird in some way.  This one's weird enough that you might be able
  30. to beat splice by copying the actual strings like you did.  As it happens,
  31. on a sparc the splice wins by about 20%.
  32.  
  33. In general, you can assume that I haven't been totally stupid.  :-)
  34.  
  35. : Just how efficient is splice?  I guess it depends on whether arrays in
  36. : perl are internally implemented as linked lists.
  37.  
  38. Arrays are *not* implemented as linked lists.  That would be tragic.
  39. It would force all subscripting operations (including splice) to be O(n).
  40. Yech.
  41.  
  42. Arrays are implemented in C as an array of pointers to scalar headers
  43. which in turn point to the actual values.  Splice merely needs to copy
  44. some number of pointers to fill the hole.  It figures out whether to
  45. copy up from the front or down from the back.  It's true that that's
  46. also O(n), or maybe O(n/2) or so, but machines are often optimized to
  47. move blocks of memory quickly, and a splice on the middle of an array
  48. is fairly rare as operations go.  Subscripting, however, happens
  49. constantly, so we optimize for that.
  50.  
  51. Larry
  52.