On Wed, May 28, 2008 at 10:46:45AM +0200, Tomeu Vizoso wrote: > On Tue, May 27, 2008 at 6:44 PM, Michael Stone <[EMAIL PROTECTED]> wrote: > > On Tue, May 27, 2008 at 09:15:39AM +0200, Tomeu Vizoso wrote: > >> + for bundle in self._bundles: > >> + if new_bundle.get_bundle_id() == bundle.get_bundle_id(): > > > > Why are we performing repeated linear search instead of storing bundles > > in a datastructure with sub-linear containment lookups (e.g. a set or a > > hashtable)? > > Because the patch is simpler this way. Why do you think that using a > set or a table might be better here?
Because my algorithm (store a dict mapping bundle id to biggest version yet seen) makes the same decisions yours does with one hash table lookup instead of O(n) string comparisons? NB: naive implementations (i.e. where you decide to create both the list and the dict) will have creation and maintenance costs in space and time which could exceed the benefit gained by from cheaper lookups. I haven't studied the code in enough detail to see what the most appropriate data structures are. Question: does our implementation ever pay attention to the order of the entries in self._bundles? > > Why exclude old bundle versions? > > Eben's new design makes very clear that several versions of the same > bundle need to be installed and the user can manage them as wanted. > When I started implementing this some months ago, I found some > problems with identifying bundles other than by its bundle_id. See: > > http://lists.laptop.org/pipermail/sugar/2008-April/004893.html > > I even proposed some patches that partially address this: > > http://lists.laptop.org/pipermail/sugar/2008-April/004894.html > http://lists.laptop.org/pipermail/sugar/2008-April/004895.html > http://lists.laptop.org/pipermail/sugar/2008-April/004896.html > > Those patches were not reviewed because it was considered better to > wait for the discussion about bundle identification to be settled. Heh. Fair enough. > > Have you reviewed any of the bundle commentaries that Eben, Jameson, and > > I have been writing? > > > > http://wiki.laptop.org/go/User:Mstone/Commentaries/Bundles_1 > > http://wiki.laptop.org/go/User:Mstone/Commentaries/Bundles_2 > > Haven't had time to fully read. Can someone summarize the conclusion? I'll see if I can come up with something for you. Michael _______________________________________________ Sugar mailing list Sugar@lists.laptop.org http://lists.laptop.org/listinfo/sugar
