#15367: Empty lists while creating parents
---------------------------+-------------------------
Reporter: roed | Owner:
Type: defect | Status: new
Priority: major | Milestone: sage-5.13
Component: memleak | Resolution:
Keywords: | Merged in:
Authors: | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
Dependencies: | Stopgaps:
---------------------------+-------------------------
Comment (by nbruin):
Replying to [comment:8 SimonKing]:
> Replying to [comment:6 nbruin]:
> > Given that we should bound the fill ratio by about 60%-70%, that would
not be enough.
>
> What is the theory behind this choice?
A reasonable start is [http://en.wikipedia.org/wiki/Hash_table wikipedia].
We're currently using "separate chaining" which degrades fairly gracefully
with increasing load factor, so perhaps the 60-70 load factor isn't as
strict as the phase transition that open addressing undergoes around that
point. You could experiment and tune a reasonable trade-off (the idea is
that any time you don't hit what you're looking for on the first try,
you've basically lost. Hash conflict resolution should rarely be
necessary).
The other design limitation is that reshaping is expensive (O(size of
dict)), so that should happen rarely. That means that if you increase the
number of bins, you have to do so by a lot.
--
Ticket URL: <http://trac.sagemath.org/ticket/15367#comment:12>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/groups/opt_out.
