From: Robert Klemme Date: 2003-05-28T17:14:52+09:00 Subject: Re: Binary Tree vs. Hash "Hal E. Fulton" schrieb im Newsbeitrag news:064901c32486$95db4a20$0300a8c0@austin.rr.com... > ----- Original Message ----- > From: "Robert Klemme" > Newsgroups: comp.lang.ruby > To: "ruby-talk ML" > Sent: Tuesday, May 27, 2003 11:49 AM > Subject: Re: Binary Tree vs. Hash > > [snip discussion of "sorted" flag for arrays] > > I can see both sides of this. I think the > original idea has some merit. > > As I see it, the @sorted flag would be set > only when a sort was done, and it would be > unset when any operation was done NOT > guaranteeing preservation of sorting. I had a different understanding, but maybe I was wrong. Must reread the thread... > One problem I see is the potential ambiguity > of "sorted" -- we can apply any sorting > technique we like to an array, right? And not > all of these are conducive to a speedup unless > we do an internal Schwartzian transform. Yeah, that's a major point, as I tried to point out. Imagine foo=[] foo << 5 << 2 << -1 << 7 p foo foo.sort!{|a,b| a<=>b} p foo p foo.sorted? foo.sort!{|a,b| b<=>a} p foo p foo.sorted? printing [5, 2, -1, 7] [-1, 2, 5, 7] true [7, 5, 2, -1] true Anybody reading the sorted flag must know at the same time, which ordering was applied. So you have to record some of the information outside this array which IMHO is not a good idea. > An overall better approach might be a SortedArray > inheriting from Array -- it could even have its own > definitions of << and so on that would preserve > sorting. And the method of sorting would (could/ > should/might?) be fixed on an instance basis. Exactly, apart the problems with []= remain, as others have pointed out. robert