On Apr 11, 2007, at 6:42 PM, Fargo Holiday wrote: >>>> Imagine the 10,000 elements are arranged, not in a line, but in a >>>> circle. You keep track of two numbers, representing where in the >>>> circle the head and tail of your list are. When these meet, you >>>> extract the first 5,000 elements from the list, moving the tail up. >>>> Now, because it's a ring, you have room in front of the head of the >>>> list for another 5,000 elements. Lather, rinse and repeat. >>>> >>>> >>> Ah, ok. Too simple for my un-caffeinated mind. Here's another >>> "brilliant" question to display the depth of my experience: What is >>> the >>> advantage of doing it this way, versus a looping remove? Don't >>> you end >>> up doing essentially the same task when extracting? >>> >> >> The original question was about speed. This is fast because you don't >> have to shift or even remove elements. You just move the head and >> tail pointers around and reuse the elements of the array. You could >> just naively use the array, rediming and whatever you want to. But >> this will be hundreds of times faster than that. >> > Ahhhh, ok. See, now that I've had a day of colas and naps while > commuting, I finally understand. I didn't realize you were talking > about > just re-using the elements, but instead had imagined that you were > speaking of still reading and removing elements. > > That's really handy. I vaguely recall doing something like that with a > bitfield in C/C++, but it had faded way into the background to join > other concepts I'd learned and never used enough.
Worth mentioning also: you didn't say what you were keeping in the array. But if it's objects, then there's another speedup available to you: rather than creating and destroying the objects in the array, just reuse them. Give them an Initialize call that sets them back what a new object looks like, and when you don't need them any more, just reinitialize them. Or even don't; and just set their state to whatever you need the first time you reuse them. If they need to refer to more objects in turn, possibly reuse them as well. This way, you're not hitting up the memory manager all the time. This will also give you a significant speedup. If you're keeping strings, you could try to do something similar: say, use a memoryblock to keep each string, set to the biggest size you expect them to be. There are other similar reuse strategies available to you: for example, connection pooling if any of this is network-related. Oh, and note this: you can implement the reuse thing by having the objects put themselves into a pool array in their destructor. By doing that, there is a reference to them again, and they won't get reclaimed. I recently checked this with Mars, and he said that this would work just fine. Regards, Guyren G Howe Relevant Logic LLC guyren-at-relevantlogic.com ~ http://relevantlogic.com REALbasic, PHP, Ruby/Rails, Python programming PostgreSQL, MySQL database design and consulting Technical writing and training _______________________________________________ Unsubscribe or switch delivery mode: <http://www.realsoftware.com/support/listmanager/> Search the archives: <http://support.realsoftware.com/listarchives/lists.html>
