Abstractions
in [Lisp]
|
From: RG on 5 Aug 2010 12:11 In article <8bvcqmFbo1U1(a)mid.individual.net>, Pascal Costanza <pc(a)p-cos.net> wrote: > On 05/08/2010 02:36, RG wrote: > > In article<8budnhFdg0U1(a)mid.individual.net>, > > Pascal Costanza<pc(a)p-cos.net> wrote: > > > >> On 05/08/2010 00:55, RG wrote: > >>> In article<8btsioFb3bU1(a)mid.individual.net>, > >>> Pascal Costanza<pc(a)p-cos.net> wrote: > >>> > >>>> On 04/08/2010 19:20, RG wrote: > >>>>> In article<9mpzkx2ibyb.fsf(a)runa.se>, bjorn(a)runa.se (Björn Lindberg) > >>>>> wrote: > >>>>> > >>>>>> RG<rNOSPAMon(a)flownet.com> writes: > >>>>>> > >>>>>>> In article<9mplj8mkewt.fsf(a)runa.se>, bjorn(a)runa.se (Björn Lindberg) > >>>>>>> wrote: > >>>>>>> > >>>>>>>> RG<rNOSPAMon(a)flownet.com> writes: > >>>>>>>> > >>>>>>>>> In article<9mpwrs7kipq.fsf(a)runa.se>, bjorn(a)runa.se (Björn Lindberg) > >>>>>>>>> wrote: > >>>>>>>>> > >>>>>>>>>>> It all boils down to some common sense. Just like we use + rather > >>>>>>>>>>> than > >>>>>>>>>>> fixnum+, bignum+, float+, double+, it's often convenient to use > >>>>>>>>>>> ELT > >>>>>>>>>>> rather than AREF or NTH. > >>>>>>>>>> > >>>>>>>>>> No, these are two completely different topics. We do not use > >>>>>>>>>> generic > >>>>>>>>>> arithmetic operators to delay an implementation choice of which > >>>>>>>>>> number > >>>>>>>>>> type to use. > >>>>>>>>> > >>>>>>>>> Huh?!? This seems to me to be the *only* reason to use generic > >>>>>>>>> arithmetic. What else is it good for? > >>>>>>>> > >>>>>>>> To write code that can accept differing types of numbers at > >>>>>>>> run-time. > >>>>>>> > >>>>>>> And how is that not "delaying an implementation choice" (to run-time) > >>>>>>> on > >>>>>>> which number type to use? > >>>>>> > >>>>>> Let us be careful not to have this discussion stray from the topic, > >>>>>> and > >>>>>> consider the context in which that comment was made. If you think that > >>>>>> Alessio's 'typed arithmetics' are similar in nature to what I was > >>>>>> outlining in the post he replied to, can you please explain that > >>>>>> further? > >>>>> > >>>>> The original context was snipped out. I presume you're referring to > >>>>> this: > >>>>> > >>>>>> If I may interject, I do see value in abstraction, but it will usually > >>>>>> take a different form than what you propose. > >>>>>> > >>>>>> Let's say that we in our program have objects of the kind foo, indexed > >>>>>> by bar, stored in collections bork. You do not want to prematurely > >>>>>> select the implementation of bork to be either hash tables, alists or > >>>>>> something else. You now write accessors like ADD-FOO, FIND-FOO, and > >>>>>> the > >>>>>> like, essentially creating an ADT specific to the program. This ADT > >>>>>> encapsulates whatever implementation is chosen for bork, making change > >>>>>> later easy. The advantages of this approach are plenty: The accessors > >>>>>> can be written to fit the semantics of foo, bar and bork, rather than > >>>>>> shoe-horning the behaviour of those into some generic collections > >>>>>> framework. It makes the code much more descriptive of what it is doing > >>>>>> than if it is sprinkled with "generic" REF calls, which from a > >>>>>> documentation perspective is even worse than having it filled with > >>>>>> calls > >>>>>> to GETHASH. > >>>>> > >>>>> Alessio's typed arithmetic operators seem to me to be exactly analogous > >>>>> to your typed collections operators. ADD-FOO (presumably) only adds > >>>>> objects of type FOO. In fact, just change FOO to FIXNUM and you've got > >>>>> Alessio's example nearly verbatim. > >>>> > >>>> I think Björn actually meant something like register-observer and > >>>> deregister-observer. [1] Something like this: > >>>> > >>>> (defclass observable-mixin () > >>>> ((observers :initform '()))) > >>>> > >>>> ;; specializing on standard-class here is not standard-compliant > >>>> ;; but good enough for illustration purposes > >>>> (defmethod (setf slot-value-using-class) :after > >>>> ((class standard-class) (object observable-mixin) slot) > >>>> ;; the following should pass more information > >>>> ;; but you get the idea > >>>> (mapc #'notify (slot-value object 'observers))) > >>>> > >>>> (defmethod register-observer ((object observable-mixin) observer) > >>>> (pushnew observer (slot-value object 'observers))) > >>>> > >>>> (defmethod deregister-observer ((object observable-mixin) observer) > >>>> (setf (slot-value object 'observers) > >>>> (remove observer (slot-value object 'observers)))) > >>>> > >>>> Replacing the list with a vector here is downright trivial, because it's > >>>> nicely abstracted away behind the register/deregister protocol. > >>> > >>> No, replacing a list with a vector is trivial because you only have ten > >>> lines of code. In fact, to replace lists with vectors you would need to > >>> change four of your ten lines of code. If your code base were 10,000 > >>> LOC instead of 10, changing 40% of it to change an implementation would > >>> feel like more of a chore. > >> > >> In my 10 lines of code I have four definitions referring to a single > >> list container. So are you saying that in 10000 lines of code, I would > >> have 4000 definitions referring to that single list container? I'm > >> wondering what kind of code that would be... ;) > > > > Why do they all have to refer to that one list container? Why could you > > not have 1000 different kinds of containers, each of which requires the > > same 10-line boilerplate, and all of which might have to be changed > > under the right circumstances? I'm working with a system right now that > > pretty much fits that description. (It's a financial system.) > > Why would the all require the same change at the same time? They might not. But as the data volume grows, the number of objects that fill each different kind of container grows at more or less the same rate. Also... > If they all require the same boilerplate, why didn't you write a macro > to generate it? Then you would have greatly reduced the workload again... It's not my code. But such a macro would not have solved the problem in this particular case. This is a system that manages financial data feeds from around the world. It is live 24x7. Down time is somewhere between extremely expensive and disastrous depending on when it occurs. When you change representation you not only have to change the code, you also have to convert the currently-live data structures. So a macro that generated accessors would not by itself be enough. You would either have to reboot the system after every change, or write additional code to convert the currently-live data structures in situ. And this is not an uncommon situation in high-availability applications. rg
From: Pascal Costanza on 5 Aug 2010 12:28 On 05/08/2010 18:11, RG wrote: > In article<8bvcqmFbo1U1(a)mid.individual.net>, > Pascal Costanza<pc(a)p-cos.net> wrote: > >> On 05/08/2010 02:36, RG wrote: >>> In article<8budnhFdg0U1(a)mid.individual.net>, >>> Pascal Costanza<pc(a)p-cos.net> wrote: >>> >>>> On 05/08/2010 00:55, RG wrote: >>>>> In article<8btsioFb3bU1(a)mid.individual.net>, >>>>> Pascal Costanza<pc(a)p-cos.net> wrote: >>>>> >>>>>> On 04/08/2010 19:20, RG wrote: >>>>>>> In article<9mpzkx2ibyb.fsf(a)runa.se>, bjorn(a)runa.se (Björn Lindberg) >>>>>>> wrote: >>>>>>> >>>>>>>> RG<rNOSPAMon(a)flownet.com> writes: >>>>>>>> >>>>>>>>> In article<9mplj8mkewt.fsf(a)runa.se>, bjorn(a)runa.se (Björn Lindberg) >>>>>>>>> wrote: >>>>>>>>> >>>>>>>>>> RG<rNOSPAMon(a)flownet.com> writes: >>>>>>>>>> >>>>>>>>>>> In article<9mpwrs7kipq.fsf(a)runa.se>, bjorn(a)runa.se (Björn Lindberg) >>>>>>>>>>> wrote: >>>>>>>>>>> >>>>>>>>>>>>> It all boils down to some common sense. Just like we use + rather >>>>>>>>>>>>> than >>>>>>>>>>>>> fixnum+, bignum+, float+, double+, it's often convenient to use >>>>>>>>>>>>> ELT >>>>>>>>>>>>> rather than AREF or NTH. >>>>>>>>>>>> >>>>>>>>>>>> No, these are two completely different topics. We do not use >>>>>>>>>>>> generic >>>>>>>>>>>> arithmetic operators to delay an implementation choice of which >>>>>>>>>>>> number >>>>>>>>>>>> type to use. >>>>>>>>>>> >>>>>>>>>>> Huh?!? This seems to me to be the *only* reason to use generic >>>>>>>>>>> arithmetic. What else is it good for? >>>>>>>>>> >>>>>>>>>> To write code that can accept differing types of numbers at >>>>>>>>>> run-time. >>>>>>>>> >>>>>>>>> And how is that not "delaying an implementation choice" (to run-time) >>>>>>>>> on >>>>>>>>> which number type to use? >>>>>>>> >>>>>>>> Let us be careful not to have this discussion stray from the topic, >>>>>>>> and >>>>>>>> consider the context in which that comment was made. If you think that >>>>>>>> Alessio's 'typed arithmetics' are similar in nature to what I was >>>>>>>> outlining in the post he replied to, can you please explain that >>>>>>>> further? >>>>>>> >>>>>>> The original context was snipped out. I presume you're referring to >>>>>>> this: >>>>>>> >>>>>>>> If I may interject, I do see value in abstraction, but it will usually >>>>>>>> take a different form than what you propose. >>>>>>>> >>>>>>>> Let's say that we in our program have objects of the kind foo, indexed >>>>>>>> by bar, stored in collections bork. You do not want to prematurely >>>>>>>> select the implementation of bork to be either hash tables, alists or >>>>>>>> something else. You now write accessors like ADD-FOO, FIND-FOO, and >>>>>>>> the >>>>>>>> like, essentially creating an ADT specific to the program. This ADT >>>>>>>> encapsulates whatever implementation is chosen for bork, making change >>>>>>>> later easy. The advantages of this approach are plenty: The accessors >>>>>>>> can be written to fit the semantics of foo, bar and bork, rather than >>>>>>>> shoe-horning the behaviour of those into some generic collections >>>>>>>> framework. It makes the code much more descriptive of what it is doing >>>>>>>> than if it is sprinkled with "generic" REF calls, which from a >>>>>>>> documentation perspective is even worse than having it filled with >>>>>>>> calls >>>>>>>> to GETHASH. >>>>>>> >>>>>>> Alessio's typed arithmetic operators seem to me to be exactly analogous >>>>>>> to your typed collections operators. ADD-FOO (presumably) only adds >>>>>>> objects of type FOO. In fact, just change FOO to FIXNUM and you've got >>>>>>> Alessio's example nearly verbatim. >>>>>> >>>>>> I think Björn actually meant something like register-observer and >>>>>> deregister-observer. [1] Something like this: >>>>>> >>>>>> (defclass observable-mixin () >>>>>> ((observers :initform '()))) >>>>>> >>>>>> ;; specializing on standard-class here is not standard-compliant >>>>>> ;; but good enough for illustration purposes >>>>>> (defmethod (setf slot-value-using-class) :after >>>>>> ((class standard-class) (object observable-mixin) slot) >>>>>> ;; the following should pass more information >>>>>> ;; but you get the idea >>>>>> (mapc #'notify (slot-value object 'observers))) >>>>>> >>>>>> (defmethod register-observer ((object observable-mixin) observer) >>>>>> (pushnew observer (slot-value object 'observers))) >>>>>> >>>>>> (defmethod deregister-observer ((object observable-mixin) observer) >>>>>> (setf (slot-value object 'observers) >>>>>> (remove observer (slot-value object 'observers)))) >>>>>> >>>>>> Replacing the list with a vector here is downright trivial, because it's >>>>>> nicely abstracted away behind the register/deregister protocol. >>>>> >>>>> No, replacing a list with a vector is trivial because you only have ten >>>>> lines of code. In fact, to replace lists with vectors you would need to >>>>> change four of your ten lines of code. If your code base were 10,000 >>>>> LOC instead of 10, changing 40% of it to change an implementation would >>>>> feel like more of a chore. >>>> >>>> In my 10 lines of code I have four definitions referring to a single >>>> list container. So are you saying that in 10000 lines of code, I would >>>> have 4000 definitions referring to that single list container? I'm >>>> wondering what kind of code that would be... ;) >>> >>> Why do they all have to refer to that one list container? Why could you >>> not have 1000 different kinds of containers, each of which requires the >>> same 10-line boilerplate, and all of which might have to be changed >>> under the right circumstances? I'm working with a system right now that >>> pretty much fits that description. (It's a financial system.) >> >> Why would the all require the same change at the same time? > > They might not. But as the data volume grows, the number of objects > that fill each different kind of container grows at more or less the > same rate. Also... > >> If they all require the same boilerplate, why didn't you write a macro >> to generate it? Then you would have greatly reduced the workload again... > > It's not my code. But such a macro would not have solved the problem in > this particular case. This is a system that manages financial data > feeds from around the world. It is live 24x7. Down time is somewhere > between extremely expensive and disastrous depending on when it occurs. > When you change representation you not only have to change the code, you > also have to convert the currently-live data structures. So a macro > that generated accessors would not by itself be enough. You would > either have to reboot the system after every change, or write additional > code to convert the currently-live data structures in situ. And this is > not an uncommon situation in high-availability applications. Are you seriously saying that in such an application, a random access operator (like elt) is used on lists, or that it would ever makes sense to use elt on lists in the future? An O(n) operation? I find that very hard to believe... Pascal -- My website: http://p-cos.net Common Lisp Document Repository: http://cdr.eurolisp.org Closer to MOP & ContextL: http://common-lisp.net/project/closer/
From: RG on 5 Aug 2010 13:01 In article <8c0750FaueU1(a)mid.individual.net>, Pascal Costanza <pc(a)p-cos.net> wrote: > On 05/08/2010 18:11, RG wrote: > > In article<8bvcqmFbo1U1(a)mid.individual.net>, > > Pascal Costanza<pc(a)p-cos.net> wrote: > > > >> On 05/08/2010 02:36, RG wrote: > >>> In article<8budnhFdg0U1(a)mid.individual.net>, > >>> Pascal Costanza<pc(a)p-cos.net> wrote: > >>> > >>>> On 05/08/2010 00:55, RG wrote: > >>>>> In article<8btsioFb3bU1(a)mid.individual.net>, > >>>>> Pascal Costanza<pc(a)p-cos.net> wrote: > >>>>> > >>>>>> On 04/08/2010 19:20, RG wrote: > >>>>>>> In article<9mpzkx2ibyb.fsf(a)runa.se>, bjorn(a)runa.se (Björn Lindberg) > >>>>>>> wrote: > >>>>>>> > >>>>>>>> RG<rNOSPAMon(a)flownet.com> writes: > >>>>>>>> > >>>>>>>>> In article<9mplj8mkewt.fsf(a)runa.se>, bjorn(a)runa.se (Björn Lindberg) > >>>>>>>>> wrote: > >>>>>>>>> > >>>>>>>>>> RG<rNOSPAMon(a)flownet.com> writes: > >>>>>>>>>> > >>>>>>>>>>> In article<9mpwrs7kipq.fsf(a)runa.se>, bjorn(a)runa.se (Björn > >>>>>>>>>>> Lindberg) > >>>>>>>>>>> wrote: > >>>>>>>>>>> > >>>>>>>>>>>>> It all boils down to some common sense. Just like we use + > >>>>>>>>>>>>> rather > >>>>>>>>>>>>> than > >>>>>>>>>>>>> fixnum+, bignum+, float+, double+, it's often convenient to use > >>>>>>>>>>>>> ELT > >>>>>>>>>>>>> rather than AREF or NTH. > >>>>>>>>>>>> > >>>>>>>>>>>> No, these are two completely different topics. We do not use > >>>>>>>>>>>> generic > >>>>>>>>>>>> arithmetic operators to delay an implementation choice of which > >>>>>>>>>>>> number > >>>>>>>>>>>> type to use. > >>>>>>>>>>> > >>>>>>>>>>> Huh?!? This seems to me to be the *only* reason to use generic > >>>>>>>>>>> arithmetic. What else is it good for? > >>>>>>>>>> > >>>>>>>>>> To write code that can accept differing types of numbers at > >>>>>>>>>> run-time. > >>>>>>>>> > >>>>>>>>> And how is that not "delaying an implementation choice" (to > >>>>>>>>> run-time) > >>>>>>>>> on > >>>>>>>>> which number type to use? > >>>>>>>> > >>>>>>>> Let us be careful not to have this discussion stray from the topic, > >>>>>>>> and > >>>>>>>> consider the context in which that comment was made. If you think > >>>>>>>> that > >>>>>>>> Alessio's 'typed arithmetics' are similar in nature to what I was > >>>>>>>> outlining in the post he replied to, can you please explain that > >>>>>>>> further? > >>>>>>> > >>>>>>> The original context was snipped out. I presume you're referring to > >>>>>>> this: > >>>>>>> > >>>>>>>> If I may interject, I do see value in abstraction, but it will > >>>>>>>> usually > >>>>>>>> take a different form than what you propose. > >>>>>>>> > >>>>>>>> Let's say that we in our program have objects of the kind foo, > >>>>>>>> indexed > >>>>>>>> by bar, stored in collections bork. You do not want to prematurely > >>>>>>>> select the implementation of bork to be either hash tables, alists > >>>>>>>> or > >>>>>>>> something else. You now write accessors like ADD-FOO, FIND-FOO, and > >>>>>>>> the > >>>>>>>> like, essentially creating an ADT specific to the program. This ADT > >>>>>>>> encapsulates whatever implementation is chosen for bork, making > >>>>>>>> change > >>>>>>>> later easy. The advantages of this approach are plenty: The > >>>>>>>> accessors > >>>>>>>> can be written to fit the semantics of foo, bar and bork, rather > >>>>>>>> than > >>>>>>>> shoe-horning the behaviour of those into some generic collections > >>>>>>>> framework. It makes the code much more descriptive of what it is > >>>>>>>> doing > >>>>>>>> than if it is sprinkled with "generic" REF calls, which from a > >>>>>>>> documentation perspective is even worse than having it filled with > >>>>>>>> calls > >>>>>>>> to GETHASH. > >>>>>>> > >>>>>>> Alessio's typed arithmetic operators seem to me to be exactly > >>>>>>> analogous > >>>>>>> to your typed collections operators. ADD-FOO (presumably) only adds > >>>>>>> objects of type FOO. In fact, just change FOO to FIXNUM and you've > >>>>>>> got > >>>>>>> Alessio's example nearly verbatim. > >>>>>> > >>>>>> I think Björn actually meant something like register-observer and > >>>>>> deregister-observer. [1] Something like this: > >>>>>> > >>>>>> (defclass observable-mixin () > >>>>>> ((observers :initform '()))) > >>>>>> > >>>>>> ;; specializing on standard-class here is not standard-compliant > >>>>>> ;; but good enough for illustration purposes > >>>>>> (defmethod (setf slot-value-using-class) :after > >>>>>> ((class standard-class) (object observable-mixin) slot) > >>>>>> ;; the following should pass more information > >>>>>> ;; but you get the idea > >>>>>> (mapc #'notify (slot-value object 'observers))) > >>>>>> > >>>>>> (defmethod register-observer ((object observable-mixin) observer) > >>>>>> (pushnew observer (slot-value object 'observers))) > >>>>>> > >>>>>> (defmethod deregister-observer ((object observable-mixin) observer) > >>>>>> (setf (slot-value object 'observers) > >>>>>> (remove observer (slot-value object 'observers)))) > >>>>>> > >>>>>> Replacing the list with a vector here is downright trivial, because > >>>>>> it's > >>>>>> nicely abstracted away behind the register/deregister protocol. > >>>>> > >>>>> No, replacing a list with a vector is trivial because you only have ten > >>>>> lines of code. In fact, to replace lists with vectors you would need > >>>>> to > >>>>> change four of your ten lines of code. If your code base were 10,000 > >>>>> LOC instead of 10, changing 40% of it to change an implementation would > >>>>> feel like more of a chore. > >>>> > >>>> In my 10 lines of code I have four definitions referring to a single > >>>> list container. So are you saying that in 10000 lines of code, I would > >>>> have 4000 definitions referring to that single list container? I'm > >>>> wondering what kind of code that would be... ;) > >>> > >>> Why do they all have to refer to that one list container? Why could you > >>> not have 1000 different kinds of containers, each of which requires the > >>> same 10-line boilerplate, and all of which might have to be changed > >>> under the right circumstances? I'm working with a system right now that > >>> pretty much fits that description. (It's a financial system.) > >> > >> Why would the all require the same change at the same time? > > > > They might not. But as the data volume grows, the number of objects > > that fill each different kind of container grows at more or less the > > same rate. Also... > > > >> If they all require the same boilerplate, why didn't you write a macro > >> to generate it? Then you would have greatly reduced the workload again... > > > > It's not my code. But such a macro would not have solved the problem in > > this particular case. This is a system that manages financial data > > feeds from around the world. It is live 24x7. Down time is somewhere > > between extremely expensive and disastrous depending on when it occurs. > > When you change representation you not only have to change the code, you > > also have to convert the currently-live data structures. So a macro > > that generated accessors would not by itself be enough. You would > > either have to reboot the system after every change, or write additional > > code to convert the currently-live data structures in situ. And this is > > not an uncommon situation in high-availability applications. > > Are you seriously saying that in such an application, a random access > operator (like elt) is used on lists, or that it would ever makes sense > to use elt on lists in the future? An O(n) operation? > > I find that very hard to believe... Do you also find it hard to believe than that anyone would ever use an AList or a Plist in production code? ASSOC and GETF are also O(n) operations, no? Or that it might make sense to use an O(n) operation if it is in a part of the system that runs is rarely used and is not mission-critical? In this particular case I have no idea what's really going on under the hood. Like I said, it's not my code. (In this case I'm a user, not a developer.) But what difference does it make what the particular issue happens to be? Do you seriously doubt that representations in production applications often need to be changed after deployment to meet unanticipated demands or to support new features? And that down time can be expensive, and in some cases even catastrophic? rg
From: Pascal Costanza on 6 Aug 2010 05:04 On 05/08/2010 19:01, RG wrote: > In article<8c0750FaueU1(a)mid.individual.net>, > Pascal Costanza<pc(a)p-cos.net> wrote: > >> On 05/08/2010 18:11, RG wrote: >>> In article<8bvcqmFbo1U1(a)mid.individual.net>, >>> Pascal Costanza<pc(a)p-cos.net> wrote: >>> >>>> If they all require the same boilerplate, why didn't you write a macro >>>> to generate it? Then you would have greatly reduced the workload again... >>> >>> It's not my code. But such a macro would not have solved the problem in >>> this particular case. This is a system that manages financial data >>> feeds from around the world. It is live 24x7. Down time is somewhere >>> between extremely expensive and disastrous depending on when it occurs. >>> When you change representation you not only have to change the code, you >>> also have to convert the currently-live data structures. So a macro >>> that generated accessors would not by itself be enough. You would >>> either have to reboot the system after every change, or write additional >>> code to convert the currently-live data structures in situ. And this is >>> not an uncommon situation in high-availability applications. >> >> Are you seriously saying that in such an application, a random access >> operator (like elt) is used on lists, or that it would ever makes sense >> to use elt on lists in the future? An O(n) operation? >> >> I find that very hard to believe... > > Do you also find it hard to believe than that anyone would ever use an > AList or a Plist in production code? ASSOC and GETF are also O(n) > operations, no? That's a bad comparison. An alternative to alists and plists is hash tables, but hash tables are slower than alists or plists if there are less than 50 (or so) mappings. In contrast, arrays are always faster for random access than lists. > Or that it might make sense to use an O(n) operation if > it is in a part of the system that runs is rarely used and is not > mission-critical? That can happen, sure. > In this particular case I have no idea what's really going on under the > hood. Like I said, it's not my code. (In this case I'm a user, not a > developer.) But what difference does it make what the particular issue > happens to be? Do you seriously doubt that representations in > production applications often need to be changed after deployment to > meet unanticipated demands or to support new features? And that down > time can be expensive, and in some cases even catastrophic? I don't doubt that run-time changes are important, to the contrary. I still believe that the collections is the wrong level of abstraction to make such changes. You're right in that you may not have any other opportunity in badly designed code. Pascal -- My website: http://p-cos.net Common Lisp Document Repository: http://cdr.eurolisp.org Closer to MOP & ContextL: http://common-lisp.net/project/closer/
From: Thomas A. Russ on 6 Aug 2010 12:09
Pascal Costanza <pc(a)p-cos.net> writes: > On 05/08/2010 19:01, RG wrote: > > Do you also find it hard to believe than that anyone would ever use an > > AList or a Plist in production code? ASSOC and GETF are also O(n) > > operations, no? > > That's a bad comparison. An alternative to alists and plists is hash > tables, but hash tables are slower than alists or plists if there are > less than 50 (or so) mappings. In contrast, arrays are always faster for > random access than lists. And in fact in some of our code where performance was an issue we ended up writing an auto-switching data structure. We had particular lookup lists (dictionaries) where many were short but occasionally longer ones would pop up. This depended on some runtime actions so it wasn't predictable. So our solution was to build an abstract data structure that would use ALISTs until the (empirically determined) performance thresdhold was reached and then substituting a hash table internally to hold the data. I suppose that makes this tale an endorsement of the ADD-FOO and GET-FOO technique. -- Thomas A. Russ, USC/Information Sciences Institute |