Dear Squeakers,
I have the following problem: Please imagine objects as a directed graph. What I want to do is to run a method exactly once for each object. I can do it in O(N*log(N)) time by using a tree or other datastructures. It seems it's impossible to do it in O(N). The reason for that is there is a comment in Object class which says I should not extend it by adding any additional instance variables. Additional points: 1. I want to be able to do this for ANY object, so subclassing and adding an instance variable to a subclass won't work. (imagine for example, that I need to create an extension of Smalltalk which should work with all current Smalltalk classes, or something like that) 2. I cannot create an isomorphic graph with some other objects (of a special class created by me), because I do not know how to detect sharing of subobjects and cycles. Is there a nice solution of this problem? What would happen if I add an instance variable to Object (besides more memory used)? Do you think adding one instance variable to Object class as a standard feature of Squeak's library would break anything. This variable could be used for example in veryDeepCopy etc. Maybe it's not a good idea... Kind regards, Mateusz _______________________________________________ Beginners mailing list [hidden email] http://lists.squeakfoundation.org/mailman/listinfo/beginners |
On Thu, 27 Sep 2012, Mateusz Grotek wrote:
> Dear Squeakers, > I have the following problem: > Please imagine objects as a directed graph. > What I want to do is to run a method exactly once for each object. I can > do it in O(N*log(N)) time by using a tree or other datastructures. It > seems it's impossible to do it in O(N). The reason for that is there is > a comment in Object class which says I should not extend it by adding > any additional instance variables. The common solution to your problem is to use an IdentitySet to hold already visited objects. Since it is a hash table, and hash tables offer O(1) average access time, therefore your algorithm will have O(N) average runtime cost. If your object graph is expected to be larger than a few thousand objects, then I suggest you to give my LargeIdentitySet a try, which offers better performance in that case: http://leves.web.elte.hu/squeak/LargeIdentitySet.st > > Additional points: > 1. I want to be able to do this for ANY object, so subclassing and > adding an instance variable to a subclass won't work. (imagine for > example, that I need to create an extension of Smalltalk which should > work with all current Smalltalk classes, or something like that) > 2. I cannot create an isomorphic graph with some other objects (of a > special class created by me), because I do not know how to detect > sharing of subobjects and cycles. > > Is there a nice solution of this problem? What would happen if I add an > instance variable to Object (besides more memory used)? Do you think > adding one instance variable to Object class as a standard feature of > Squeak's library would break anything. This variable could be used for > example in veryDeepCopy etc. Maybe it's not a good idea... The system would hang. The VM has some expectations for the slots of some classes. For example it expects that the 3rd slot of a Process is its myList instance variable. If you add an instance variable to Object, then the index of the myList variable will be the 4 instead of 3. Levente > > Kind regards, > Mateusz > _______________________________________________ > Beginners mailing list > [hidden email] > http://lists.squeakfoundation.org/mailman/listinfo/beginners > _______________________________________________ Beginners mailing list [hidden email] http://lists.squeakfoundation.org/mailman/listinfo/beginners |
Free forum by Nabble | Edit this page |