https://bugs.ruby-lang.org/https://bugs.ruby-lang.org/favicon.ico?17113305112018-03-27T09:45:38ZRuby Issue Tracking SystemRuby master - Feature #14636: `Hash` has a method for accessing the shortest path towards a certain keyhttps://bugs.ruby-lang.org/issues/14636?journal_id=712522018-03-27T09:45:38ZHanmac (Hans Mackowiak)hanmac@gmx.de
<ul></ul><p>i have some thoughts about it ...<br>
if you got a structure like this:</p>
<pre><code class="ruby syntaxhl" data-language="ruby"><span class="p">{</span>
<span class="ss">:a</span> <span class="o">=></span> <span class="p">{</span>
<span class="ss">:name</span> <span class="o">=></span> <span class="s2">"abc"</span>
<span class="p">},</span>
<span class="ss">:b</span> <span class="o">=></span> <span class="p">{</span>
<span class="ss">:name</span> <span class="o">=></span> <span class="s2">"xyz"</span>
<span class="p">},</span>
<span class="p">}</span>
</code></pre>
<p>what does <code>deep_key(:name)</code> return?</p> Ruby master - Feature #14636: `Hash` has a method for accessing the shortest path towards a certain keyhttps://bugs.ruby-lang.org/issues/14636?journal_id=712532018-03-27T10:17:28ZRudySeidinger (Rudy Seidinger)
<ul></ul><p>Hanmac (Hans Mackowiak) wrote:</p>
<blockquote>
<p>i have some thoughts about it ...<br>
if you got a structure like this:</p>
<pre><code class="ruby syntaxhl" data-language="ruby"><span class="p">{</span>
<span class="ss">:a</span> <span class="o">=></span> <span class="p">{</span>
<span class="ss">:name</span> <span class="o">=></span> <span class="s2">"abc"</span>
<span class="p">},</span>
<span class="ss">:b</span> <span class="o">=></span> <span class="p">{</span>
<span class="ss">:name</span> <span class="o">=></span> <span class="s2">"xyz"</span>
<span class="p">},</span>
<span class="p">}</span>
</code></pre>
<p>what does <code>deep_key(:name)</code> return?</p>
</blockquote>
<p>In this case, is the shortest path towards the first key containing the specified parameter, so would be</p>
<pre><code class="ruby syntaxhl" data-language="ruby"><span class="p">[</span><span class="ss">:a</span><span class="p">]</span>
</code></pre> Ruby master - Feature #14636: `Hash` has a method for accessing the shortest path towards a certain keyhttps://bugs.ruby-lang.org/issues/14636?journal_id=712552018-03-27T14:05:36Zshevegen (Robert A. Heiler)shevegen@gmail.com
<ul></ul><p>This reminds me a bit of guide trees in bioinformatics, where<br>
we try to find the shortest path of substring matches to another<br>
string (a bit similar to how BLAST searching works<br>
<a href="https://blast.ncbi.nlm.nih.gov/Blast.cgi" class="external">https://blast.ncbi.nlm.nih.gov/Blast.cgi</a> though I don't know if<br>
they use a guide tree).</p>
<p>Some months ago I was very surprised that this gem was quite<br>
popular:</p>
<p><a href="https://rubygems.org/gems/diff-lcs" class="external">https://rubygems.org/gems/diff-lcs</a></p>
<p>It's actually ranked 6 among the ruby gems, which surprised me<br>
a lot. (I found it accidentally when trying to find faster<br>
algorithms for something involving the levensthein distance).</p>
<p>Anyway to be more on topic - I think it would be a good idea<br>
if ruby by default would make available algorithms and search<br>
patterns that can be quite useful on their own. Not just limited<br>
to the suggestion here but more general too.</p>
<p>I am not sure if class Hash is the way to store these by<br>
default though. I think these are quite specialized use cases<br>
and perhaps they aren't that useful by default. How about<br>
some extensions but these be distributed with core/stdlib<br>
ruby too? Just requiring an explicit require or something<br>
like that; a bit like the did-you-mean gem has, if you look<br>
here:</p>
<p><a href="https://github.com/yuki24/did_you_mean#experimental-features" class="external">https://github.com/yuki24/did_you_mean#experimental-features</a></p>
<p>I was also surprised to find out that rubygems includes<br>
levensthein already, via rubygems/text. :-)</p>
<p>Anyway, I think the main suggestion is perfectly fine so<br>
+1; I am just not sure if it should be on class Hash<br>
by default.</p>
<p>By the way, I hope it will be extensively documented so<br>
that people understand what it is doing. I understand only<br>
like half of what has been written above... ;-)</p> Ruby master - Feature #14636: `Hash` has a method for accessing the shortest path towards a certain keyhttps://bugs.ruby-lang.org/issues/14636?journal_id=712622018-03-28T02:36:15Znobu (Nobuyoshi Nakada)nobu@ruby-lang.org
<ul></ul><p>RudySeidinger (Rudy Seidinger) wrote:</p>
<blockquote>
<p>by using recursion, we avoid the overhead of having the store a temporary hash (tree) to fall-back to whenever the end of a sub-hash is reached.</p>
</blockquote>
<p><code>rb_exec_recursive</code> creates a temporary hash internally to track recursion.<br>
There is no advantage on memory usage, but you don't have to take care of the internal hash by using the function, of course.</p> Ruby master - Feature #14636: `Hash` has a method for accessing the shortest path towards a certain keyhttps://bugs.ruby-lang.org/issues/14636?journal_id=712632018-03-28T02:40:56Znobu (Nobuyoshi Nakada)nobu@ruby-lang.org
<ul></ul><p>RudySeidinger (Rudy Seidinger) wrote:</p>
<blockquote>
<p>In this case, is the shortest path towards the first key containing the specified parameter, so would be</p>
<pre><code class="ruby syntaxhl" data-language="ruby"><span class="p">[</span><span class="ss">:a</span><span class="p">]</span>
</code></pre>
</blockquote>
<p>It is one of the shortest paths, but not only.</p>
<p>An enumerator may be used here,</p>
<pre><code class="ruby syntaxhl" data-language="ruby"><span class="nb">hash</span><span class="p">.</span><span class="nf">path_to_key</span><span class="p">(</span><span class="ss">:name</span><span class="p">)</span> <span class="p">{</span><span class="o">|</span><span class="n">path</span><span class="o">|</span> <span class="o">...</span><span class="p">}</span>
</code></pre>
<p>and</p>
<pre><code class="ruby syntaxhl" data-language="ruby"><span class="nb">hash</span><span class="p">.</span><span class="nf">path_to_key</span><span class="p">(</span><span class="ss">:name</span><span class="p">).</span><span class="nf">first</span>
</code></pre> Ruby master - Feature #14636: `Hash` has a method for accessing the shortest path towards a certain keyhttps://bugs.ruby-lang.org/issues/14636?journal_id=712912018-03-28T09:41:15ZRudySeidinger (Rudy Seidinger)
<ul></ul><p>nobu (Nobuyoshi Nakada) wrote:</p>
<blockquote>
<p>RudySeidinger (Rudy Seidinger) wrote:</p>
<blockquote>
<p>by using recursion, we avoid the overhead of having the store a temporary hash (tree) to fall-back to whenever the end of a sub-hash is reached.</p>
</blockquote>
<p><code>rb_exec_recursive</code> creates a temporary hash internally to track recursion.<br>
There is no advantage on memory usage, but you don't have to take care of the internal hash by using the function, of course.</p>
</blockquote>
<p>Sure. I just thought that the iterative approach would not justify not using recursion. The implementation would be way more complex with no clear advantage. Maintainability might be a more prioritised concern</p> Ruby master - Feature #14636: `Hash` has a method for accessing the shortest path towards a certain keyhttps://bugs.ruby-lang.org/issues/14636?journal_id=712922018-03-28T09:42:50ZRudySeidinger (Rudy Seidinger)
<ul></ul><p>nobu (Nobuyoshi Nakada) wrote:</p>
<blockquote>
<p>RudySeidinger (Rudy Seidinger) wrote:</p>
<blockquote>
<p>In this case, is the shortest path towards the first key containing the specified parameter, so would be</p>
<pre><code class="ruby syntaxhl" data-language="ruby"><span class="p">[</span><span class="ss">:a</span><span class="p">]</span>
</code></pre>
</blockquote>
<p>It is one of the shortest paths, but not only.</p>
<p>An enumerator may be used here,</p>
<pre><code class="ruby syntaxhl" data-language="ruby"><span class="nb">hash</span><span class="p">.</span><span class="nf">path_to_key</span><span class="p">(</span><span class="ss">:name</span><span class="p">)</span> <span class="p">{</span><span class="o">|</span><span class="n">path</span><span class="o">|</span> <span class="o">...</span><span class="p">}</span>
</code></pre>
<p>and</p>
<pre><code class="ruby syntaxhl" data-language="ruby"><span class="nb">hash</span><span class="p">.</span><span class="nf">path_to_key</span><span class="p">(</span><span class="ss">:name</span><span class="p">).</span><span class="nf">first</span>
</code></pre>
</blockquote>
<p>Hmmm, interesting. What would use the block for, in the first scenario? the <code>yield</code> of the block would be execute in which context? inside the enumerator?</p>