<br><br><div class="gmail_quote">On Sat, Apr 2, 2011 at 11:50 PM, Michael Snoyman <span dir="ltr"><<a href="mailto:michael@snoyman.com">michael@snoyman.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
<div dir="ltr"><br><br><div class="gmail_quote"><div class="im">On Sun, Apr 3, 2011 at 9:40 AM, Greg Weber <span dir="ltr"><<a href="mailto:greg@gregweber.info" target="_blank">greg@gregweber.info</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
[snip]<div><br><div class="gmail_quote"><div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div class="gmail_quote"><div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div class="gmail_quote"><div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div class="gmail_quote"><div><div></div></div></div></div></blockquote></div>
</div></blockquote>
</div><div>I think you're solving a different problem. Are you talking about the fact that the EntryAuthorIn constructor takes a list instead of a Set? That's not where the slowdown comes from. Actually, for the current backends, a set would needlessly slow things down, since the In constructor simply converts things to SQL and lets the database do the work.</div>
<div><br></div><div>I'm not sure what you're suggesting here to be honest, can you clarify?</div></div></div></blockquote><div><br></div></div><div>An O(m + n) implementation instead of O(m * n) by using constant lookups instead of repeatedly searching through a list.</div>
<div><br></div><div></div></div></div></blockquote></div><div>But where will you use the Set? The slowdown is because we end up with two lists: [(Key one, one)] and [(Key many, many)]. For each (Key one, one), we need to filter the entire [(Key many, many)] to find the records which match each one. As far as the code is concerned, doing the initial filter to the relevant (Key many) values is constant*.</div>
<div><br></div></div></div></blockquote><div><br></div><div> We end up with 2 lists because we are building 2 lists. We should build data structures that allow for an efficient implementation of this function.</div><div>
<br></div><div>Greg</div><div> </div><div> [snip]</div></div>