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
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:
- 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 Beginners@lists.squeakfoundation.org http://lists.squeakfoundation.org/mailman/listinfo/beginners
beginners@lists.squeakfoundation.org
-
Levente Uzonyi -
Mateusz Grotek