From: Benny M. <ben...@gm...> - 2009-11-07 09:27:49
|
2009/11/6 Gerald Britton <ger...@gm...>: > Just thinking out loud here. What about using dictionaries instead of > lists? You'd have to use some sort of compound key for uniqueness and > ordering, I suppose, and it would use more memory. All operations are > amortized O(1) though. The key retrieval things are already dictionaries. The parts that need an ordering are in lists. You need to store the order as you need to know what is the item on path [400, 124], so group node 400, subnode 124. Benny > > On Fri, Nov 6, 2009 at 4:04 PM, Benny Malengier > <ben...@gm...> wrote: >> Nick, >> >> I have been working on personview today, >> http://www.gramps-project.org/bugs/view.php?id=3275 >> It looks nice, but I see a problem: on_iter_next is too slow. >> >> I see two possible solutions: >> >> 1/do like in flatbasemodel, and add an index like the handle2index >> map. This could be added as data in self.tree, as the third entry. >> Then on_iter_next(iter) would do: index = tree[iter][2] +1, and see if >> that exists in children to return it. >> Problem is the same as in flatbasemodel: on insert and delete: update >> the affected indexes. Not too bad, it is done in memory (see how >> adding/deleting is quick is eg eventview), but still annoying. >> >> 2/go for a linked list approach. The linked list would be done with a >> class Node, as in >> http://stackoverflow.com/questions/280243/python-linked-list >> In this setup, self.tree[iter] = (level, Node), where Node.key = iter, >> and Node.next links to the next Node and >> self.children[iter] = a list of Node which also form a correct linked list. >> In this setup on_iter_next(iter) would do: retrun self.tree[iter][1].next() >> The advantage over 1/ is that on insert and delete, no loops to update >> indexes must be performed, but the code for insert/delete has to be >> done once correctly :-) >> >> Any preferences or other ideas? >> To see that above is a problem in the present implementation, some timings: >> >> GRAMPS 3.1 on 30000+ Persons: >> 8594: DEBUG: _PeopleModel.py: line 316: PeopleModel rebuild_data 4.24 sec >> 8595: DEBUG: _PeopleModel.py: line 296: PeopleModel __init__ 4.24 sec >> 8688: DEBUG: PersonView.py: line 555: PersonView build_tree 4.32 sec >> 8688: DEBUG: PersonView.py: line 556: setting model 0.07 sec >> 39118: DEBUG: PersonView.py: line 773: PersonView person_removed 4.65 sec >> 56205: DEBUG: PersonView.py: line 746: PersonView person_added 4.75 sec >> >> GRAMSP trunk with my patchset: >> 8281: DEBUG: treebasemodel.py: line 285: PeopleModel rebuild_data 4.72 sec >> 8281: DEBUG: treebasemodel.py: line 169: PeopleModel __init__ 4.72 sec >> 11897: DEBUG: listview.py: line 256: PersonView build_tree 8.29 sec >> 11897: DEBUG: listview.py: line 261: parts 4.72 , 0.01 , 3.56 , 0.0 , 0.0 >> 60672: DEBUG: listview.py: line 624: PersonView row_add 0.0 sec >> 72629: DEBUG: treebasemodel.py: line 465: PeopleModel add_row_by_handle 0.01 sec >> 179444: DEBUG: treebasemodel.py: line 485: PeopleModel >> delete_row_by_handle 0.11 sec >> 179444: DEBUG: listview.py: line 655: PersonView row_delete 0.11 sec >> >> So the row add and row delete are now instantanious (5 sec to 0.1sec) >> which is what we want to achieve, building the data is a bit more >> expensive (4.24 to 4.72) which is completely acceptable, but showing >> the treeview itself (which happens on attach of the model) goes from >> 0.07 sec to 3.56. >> In other words, we need something as good as the old NodeTreeMap with >> it's path2iter and iter2path to make the iter operations faster. >> Sorting on the columns also suffers from this. >> >> Some other attention points: >> 1/ remove_node should use del, not a temporary list. Should also be >> recusive as deleting a leaf can mean removing all upper groups. >> 2/ I'd like to keep in memory the entire map so as not to hit the >> database on search and filter, just like in the flatbasemodel >> 3/ not sure how reverse works with this rows_reordered call. This is >> not done in flatbasemodel and seems to work fine. Here setting up the >> sequence for call to rows_reodered takes quite some work. >> >> My preference goes at the moment towards committing this patch, and >> then doing further changes. The patchset just becomes too large to >> handle otherwise. >> >> Benny >> >> ------------------------------------------------------------------------------ >> Let Crystal Reports handle the reporting - Free Crystal Reports 2008 30-Day >> trial. Simplify your report design, integration and deployment - and focus on >> what you do best, core application coding. Discover what's new with >> Crystal Reports now. http://p.sf.net/sfu/bobj-july >> _______________________________________________ >> Gramps-devel mailing list >> Gra...@li... >> https://lists.sourceforge.net/lists/listinfo/gramps-devel >> > > > > -- > Gerald Britton > |