Doug,

Indeed, second apply_filter comparing with the first causes speedup.

However, these tests are difficult. I can only explain your results by the fact that the distant relative has few ancestors in the tree, while the close relative has many.

A test with a distant relative only being related on level 15 of each should make all algorithms the same speed, with the original the fastest, mine a bit slower due to check overhead of second filter in first, and iterative still somewhat slower due to the stack overhead.

So all depends on the data. If the question is, 'get all relationships', then everything must be checked anyway, and the new code should win, as at maximum all person's in the database are accessed (actually loops in first person mean double checking, but that could be optimized out of the code).  If the question is, get the first found relationship, an iterative approach would be better if there is a close relationship, otherwise ....

Not sure what the best path is...

Anyway, allowing an interrupt to the calculation as you suggest on bug tracker would be welcome. Hitting the interrupt would then gracefully stop the lookup.

Benny

2007/10/24, Douglas S. Blank <dblank@cs.brynmawr.edu>:
Benny,

I tried the new code on the 2 ** 15 full family tree, and the speed-up is
significant:

Algorithm          Close Relative  Distant Relative
----------------   --------------  ----------------
original           53 seconds       8 seconds
benny's            9.5 seconds      9.5 seconds
iterative (wrong)  instant          11 seconds

I think that this speed up is due to the second apply_filter which
compares with the first?

This code is so complicated, I don't think it could be turned into an
iterative version. But I think a variation could be constructed that uses
ideas from both, and could be much simpler.

I'll keep looking at it; thanks!

-Doug

On Tue, October 23, 2007 5:36 pm, Benny Malengier wrote:
> Hi,
>
> I checked in changes to the relationship calculating code to trunk.
> I intend to improve on the work, but have some other duties first, and
> wanted this away for now.
>
> First, the new algorithm to calculate relationships has following
> improvements:
>
> 1/loop detection before running out of memory
> 2/find all relationships in all families if so asked, not only the first
> family
> 3/distinction between non-birth relationships and birth relationships
> 4/not only relationship string is returned, but also the family number
> 5/depth is a parameter
> 6/find all relationships, so if your aunt is your grandmother and your
> stephmother, you can retrieve that.
>
> For translators: the idea is translators should _not_ inherit the
> get_relationship() and get_relationship_... methods. They should only be
> present in Relationship.py.
>
> Translators should only translate def get_single_relationship_string() in
> the rel_xx.py
> This method is based upon the plural method added by Brian. If
> functionality
> for a language is missing, then it should be added in the parameters given
> to all languages.
>
> At the moment the code should behave as with the old code, as a wrapper is
> added around new code to transform it to the old return values.
>
> I will however start to change some parts to make use of the new code
> instead of the wrapper, eg a get_relationship_extended, and migrate code
> to
> that.
>
> If an english native speaker could extend the
> get_single_relationship_string() so that in case the relation is non-birth
> the correct relation is returned (that is, stephchild, ....), I would be
> gratefull. It is not yet used, but should be in the future
>
>
> Benny
> -------------------------------------------------------------------------
> This SF.net email is sponsored by: Splunk Inc.
> Still grepping through log files to find problems?  Stop.
> Now Search log events and configuration files using AJAX and a browser.
> Download your FREE copy of Splunk now >>
> http://get.splunk.com/_______________________________________________
> Gramps-devel mailing list
> Gramps-devel@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/gramps-devel
>


--
Douglas S. Blank
Associate Professor, Bryn Mawr College
http://cs.brynmawr.edu/~dblank/
Office: 610 526 6501