<div dir="ltr">Hello,<div><br></div><div>While we began discussing Proposal II with Ivan Lazar Miljenovic, I was expecting first to discuss Proposal I, as my short-term goal is to get the PR associated with Proposal I to be merged : <a href="https://github.com/haskell/containers/pull/549" target="_blank" style="font-size:12.8px">https://github.com/haskell/<wbr>containers/pull/549</a></div><div><br></div><div>So please bring forward any remarks / concerns / approvals, for Proposal I in priority!<br></div><div><br></div><div>Thank you,</div><div><br></div><div>Olivier</div><div><br></div></div><div class="gmail_extra"><br><div class="gmail_quote">2018-04-02 13:30 GMT+02:00 Olivier S. <span dir="ltr"><<a href="mailto:olivier.sohn@gmail.com" target="_blank">olivier.sohn@gmail.com</a>></span>:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div><br></div><div>Hello,</div><div><br></div><div>I'm resending this proposal, which is simplified w.r.t the first one, and where I removed a wrong analysis of a benchmark.</div><div><br></div><div>- Proposal I : Optimize the time complexity of (key -> Maybe Vertex) lookups and graph creation <span style="color:rgb(34,34,34);font-family:arial,sans-serif;font-size:small;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial;float:none;display:inline">when keys are Integral and consecutive</span>.</div><div><br></div><div>(The related PR for proposal I is [1], including benchmarks showing the performance improvements.)</div><div><br></div><div>Currently, (key -> Maybe Vertex) lookups returned by graphFromEdges consist of a binary search on an array, with a time complexity of O(log V) (I will use V for "Count of vertices", E for "Count of edges").</div><div><br></div><div>When key is Integral, and keys (of nodes passed to the graph creation function) form a set of /consecutive/ values (for example : [4,5,6,7] or [5,6,4,7]), we can have an O(1) lookup by substracting the value of the smallest key, and checking for bounds.</div><div><br></div><div>Hence, graph creation complexity is improved, and user algorithms using (key -> Maybe Vertex) lookups will see their complexity reduced by a factor of up-to O(log V).</div><div><br></div><div>The PR introduces this lookup and uses it for functions graphFromEdgesWithConsecutiveK<wbr>eys and graphFromEdgesWithConsecutiveA<wbr>scKeys.</div><div><br></div><div>Here is a summary of complexities for (graph creation, lookup function) as they stand in the current state of the PR:</div><div><br></div><div><span style="color:rgb(34,34,34);font-family:arial,sans-serif;font-size:small;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial;float:none;display:inline">- graphFromEdges (the currently existing function):</span></div><div><span style="color:rgb(34,34,34);font-family:arial,sans-serif;font-size:small;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial;float:none;display:inline"><span style="color:rgb(34,34,34);font-family:arial,sans-serif;font-size:small;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial;float:none;display:inline">O( (V+E) * log V ), O(log V)</span></span><br></div><div><span style="color:rgb(34,34,34);font-family:arial,sans-serif;font-size:small;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial;float:none;display:inline">- graphFromEdgesWithConsecutiveK<wbr>eys (new function):</span></div><div><span style="color:rgb(34,34,34);font-family:arial,sans-serif;font-size:small;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial;float:none;display:inline"><span style="color:rgb(34,34,34);font-family:arial,sans-serif;font-size:small;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial;float:none;display:inline">O( E + (V*log V) ), O(1)</span></span><br></div><div><span style="color:rgb(34,34,34);font-family:arial,sans-serif;font-size:small;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial;float:none;display:inline"><span style="color:rgb(34,34,34);font-family:arial,sans-serif;font-size:small;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial;float:none;display:inline"><span style="color:rgb(34,34,34);font-family:arial,sans-serif;font-size:small;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial;float:none;display:inline">- graphFromEdgesWithConsecutiveA<wbr>scKeys (new function) :</span><br></span></span></div><div><span style="color:rgb(34,34,34);font-family:arial,sans-serif;font-size:small;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial;float:none;display:inline"><span style="color:rgb(34,34,34);font-family:arial,sans-serif;font-size:small;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial;float:none;display:inline"><span style="color:rgb(34,34,34);font-family:arial,sans-serif;font-size:small;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial;float:none;display:inline"><span style="color:rgb(34,34,34);font-family:arial,sans-serif;font-size:small;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial;float:none;display:inline">O( V+E ), O(1)</span></span></span></span></div><div><br></div><div>- Proposal II : Deprecate `graphFromEdges` taking [(node, key, [key])] in favor of `graphFromMap` taking (Map key (node,[key]))</div><div><br></div><div>If we pass the same key twice in the list we pass to 'graphFromEdges' it is undefined which node for that key will actually be used.</div><div>Introducing 'graphFromMap', taking a (Map key (node,[key]) would alleviate this issue, through the type used.</div><div><br></div><div>Also, using a Map makes the implementation a bit more "natural" : there is no need for sorting by key, as Map.toAscList gives exactly the sorted list we want.</div><div><br></div><div>We could also deprecate graphFromEdgesWithConsecutiveK<wbr>eys and graphFromEdgesWithConsecutiveA<wbr>scKeys (introduced in proposal I) in favor of graphFromConsecutiveMap.</div><div><br></div><div>About the naming, I propose two different schemes:</div><div><br></div><div>Either:</div><div> - graphFromEdges (takes a List, deprecated, existing function)</div><div> - graphFromEdgesInMap (takes a Map)</div><div> - graphFromEdgesInConsecutiveMap (takes a Map with consecutive keys)</div><div>Or:</div><div> - graphFromEdges (takes a List, deprecated, existing function)</div><div> - graphFromMap</div><div> - graphFromConsecutiveMap</div><div> with these, to reflect the Map / List duality in the naming scheme:</div><div> - graphFromList (takes a List, deprecated, redirects to graphFromEdges)</div><div> - graphFromConsecutiveList (takes a List, deprecated, redirects to graphFromEdgesWithConsecutiveK<wbr>eys)</div><div> - graphFromConsecutiveAscList (takes a List, deprecated, redirects to graphFromEdgesWithConsecutiveA<wbr>scKeys)</div><div><br></div><div>Cheers,</div><div>Olivier Sohn</div><div><br></div><div>[1] <a href="https://github.com/haskell/containers/pull/549" target="_blank">https://github.com/haskell/<wbr>containers/pull/549</a></div><div><br></div></div>
</blockquote></div><br></div>