home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / comp / lang / cplus / 13064 < prev    next >
Encoding:
Internet Message Format  |  1992-08-30  |  2.5 KB
  1. Xref: sparky comp.lang.c++:13064 comp.std.c++:1119
  2. Path: sparky!uunet!charon.amdahl.com!pacbell.com!att!linac!pacific.mps.ohio-state.edu!zaphod.mps.ohio-state.edu!rpi!gatech!bloom-beacon!eru.mt.luth.se!lunic!sunic!dkuug!daimi!sabroe
  3. From: sabroe@daimi.aau.dk (Morten Sabroe Mortensen)
  4. Newsgroups: comp.lang.c++,comp.std.c++
  5. Subject: Dynamic allocation, -what's fastest?
  6. Message-ID: <1992Aug30.171644.14434@daimi.aau.dk>
  7. Date: 30 Aug 92 17:16:44 GMT
  8. Sender: news@daimi.aau.dk
  9. Organization: DAIMI: Computer Science Department, Aarhus University, Denmark
  10. Lines: 33
  11.  
  12.  
  13.         I'm wondering about making a data-structure, that can sort elements
  14. real quick, -not "on the the run", but after all elements have been inserted!
  15. Now, -quick-sort isn't that bad,- so I could just use a simpel array! Well,
  16. I could, but then I need a limit on the number of elements, I can insert, and
  17. that's not what I want! No, -I'm thinking about a dobble-linked list; it must
  18. be possible to run quick-sort on that! No matter what's best, it's not that
  19. part, I want you to respond to (but, -feel free to do so anyway!).
  20.  
  21.         Now, for some reason I want to make a dobble-linked list of, say,
  22. void-pointers! The usual way to do it, is to have one entry in the list
  23. for each inserted element, right? Would such a structure eat less memory, and
  24. ,-which is, what I'm really after-, less time, if each entry in the list is
  25. an array of some fixed size, -f.ex. big enough to hold 500 elements? WHY DO
  26. I THINK, that it could be, that it's a good strategy to make a list of arrays
  27. of fixed size? Well, how expensive is 'new' and 'delete' really? Would it be
  28. better to allocate many small memory-blocks, or just a few big memory-blocks?
  29. I'm not surprised, if it's equal expensive to allocate blocks of different
  30. sizes! DOES ANYONE KNOW ANYTHING ABOUT HOW EXPENSIVE 'NEW' AND 'DELETE' 
  31. REALLY ARE? WOULD I GAIN ANYTHING, IF I DON'T USE 'NEW' AND 'DELETE' MORE
  32. THAN ABSOLUTELY NESSESARY?
  33.  
  34.         What I want to do with the linked list, is insert a lot of elements,
  35. then sort it all, traverse all elements, delete it all (or, if I get better
  36. performance, delete while traversing), and then start all over with a new set
  37. of elements! It would not give me too much trouble to program these two
  38. different strategies, and then run a test on both of them, BUT I really want
  39. to know about this in teory first!
  40.  
  41.         If anyone knows how time-consuming 'new' and 'delete' are, please
  42. respond! I done through e-mail, I might or might not post a summary!
  43.  
  44.         -- Morten S. M.
  45.