diff options
| author | Paul Buetow <paul@buetow.org> | 2024-09-27 23:28:33 +0300 |
|---|---|---|
| committer | Paul Buetow <paul@buetow.org> | 2024-09-27 23:28:33 +0300 |
| commit | 97decc24069b655e0a1d32e3e6217ab0d8653351 (patch) | |
| tree | 6020e7cbfcde170c346f913f6a35f8fd8965bbea /gemfeed | |
| parent | e3f4f9eae027af0af44532aa84826c7f78a04508 (diff) | |
Update content for gemtext
Diffstat (limited to 'gemfeed')
| -rw-r--r-- | gemfeed/2024-03-03-a-fine-fyne-android-app-for-quickly-logging-ideas-programmed-in-golang.gmi | 1 | ||||
| -rw-r--r-- | gemfeed/atom.xml | 810 | ||||
| -rw-r--r-- | gemfeed/index.gmi | 1 |
3 files changed, 525 insertions, 287 deletions
diff --git a/gemfeed/2024-03-03-a-fine-fyne-android-app-for-quickly-logging-ideas-programmed-in-golang.gmi b/gemfeed/2024-03-03-a-fine-fyne-android-app-for-quickly-logging-ideas-programmed-in-golang.gmi index 1d62ffa7..e767ecb3 100644 --- a/gemfeed/2024-03-03-a-fine-fyne-android-app-for-quickly-logging-ideas-programmed-in-golang.gmi +++ b/gemfeed/2024-03-03-a-fine-fyne-android-app-for-quickly-logging-ideas-programmed-in-golang.gmi @@ -54,7 +54,6 @@ E-Mail your comments to `paul@nospam.buetow.org` :-) Other Go related posts are: -=> ./2023-04-09-algorithms-and-data-structures-in-golang-part-1.gmi 2023-04-09 Algorithms and Data Structures in Go - Part 1 => ./2024-03-03-a-fine-fyne-android-app-for-quickly-logging-ideas-programmed-in-golang.gmi 2024-03-03 A fine Fyne Android app for quickly logging ideas programmed in Go (You are currently reading this) => ../ Back to the main site diff --git a/gemfeed/atom.xml b/gemfeed/atom.xml index 3ee013e2..3debfd20 100644 --- a/gemfeed/atom.xml +++ b/gemfeed/atom.xml @@ -1,6 +1,6 @@ <?xml version="1.0" encoding="utf-8"?> <feed xmlns="http://www.w3.org/2005/Atom"> - <updated>2024-09-17T05:21:15+03:00</updated> + <updated>2024-09-27T23:27:37+03:00</updated> <title>foo.zone feed</title> <subtitle>To be in the .zone!</subtitle> <link href="gemini://foo.zone/gemfeed/atom.xml" rel="self" /> @@ -2275,7 +2275,6 @@ http://www.gnu.org/software/src-highlite --> <br /> <span>Other Go related posts are:</span><br /> <br /> -<a class='textlink' href='./2023-04-09-algorithms-and-data-structures-in-golang-part-1.html'>2023-04-09 Algorithms and Data Structures in Go - Part 1</a><br /> <a class='textlink' href='./2024-03-03-a-fine-fyne-android-app-for-quickly-logging-ideas-programmed-in-golang.html'>2024-03-03 A fine Fyne Android app for quickly logging ideas programmed in Go (You are currently reading this)</a><br /> <br /> <a class='textlink' href='../'>Back to the main site</a><br /> @@ -5122,289 +5121,6 @@ no1 in 455 days, 18:52:44 | at Sun Jul 21 07:37:51 2024 </content> </entry> <entry> - <title>Algorithms and Data Structures in Go - Part 1</title> - <link href="gemini://foo.zone/gemfeed/2023-04-09-algorithms-and-data-structures-in-golang-part-1.gmi" /> - <id>gemini://foo.zone/gemfeed/2023-04-09-algorithms-and-data-structures-in-golang-part-1.gmi</id> - <updated>2023-04-09T22:31:42+03:00</updated> - <author> - <name>Paul Buetow aka snonux</name> - <email>paul@dev.buetow.org</email> - </author> - <summary>This is the first blog post about my Algorithms and Data Structures in Go series. I am not a Software Developer in my day job. In my current role, programming and scripting skills are desirable but not mandatory. I have been learning about Data Structures and Algorithms many years ago at University. I thought it would be fun to revisit/refresh my knowledge here and implement many of the algorithms in Go.</summary> - <content type="xhtml"> - <div xmlns="http://www.w3.org/1999/xhtml"> - <h1 style='display: inline' id='algorithms-and-data-structures-in-go---part-1'>Algorithms and Data Structures in Go - Part 1</h1><br /> -<br /> -<span class='quote'>Published at 2023-04-09T22:31:42+03:00</span><br /> -<br /> -<span>This is the first blog post about my Algorithms and Data Structures in Go series. I am not a Software Developer in my day job. In my current role, programming and scripting skills are desirable but not mandatory. I have been learning about Data Structures and Algorithms many years ago at University. I thought it would be fun to revisit/refresh my knowledge here and implement many of the algorithms in Go.</span><br /> -<br /> -<a class='textlink' href='./2023-04-09-algorithms-and-data-structures-in-golang-part-1.html'>2023-04-09 Algorithms and Data Structures in Go - Part 1 (You are currently reading this)</a><br /> -<br /> -<span>This post is about setting up some basic data structures and methods for this blog series. I promise, everything will be easy to follow in this post. It will become more interesting later in this series.</span><br /> -<br /> -<pre> - ,_---~~~~~----._ - _,,_,*^____ _____``*g*\"*, - / __/ /' ^. / \ ^@q f -[ @f | @)) | | @)) l 0 _/ - \`/ \~____ / __ \_____/ \ - | _l__l_ I - } [______] I - ] | | | | - ] ~ ~ | - | | - | | -</pre> -<br /> -<h2 style='display: inline' id='table-of-contents'>Table of Contents</h2><br /> -<br /> -<ul> -<li><a href='#algorithms-and-data-structures-in-go---part-1'>Algorithms and Data Structures in Go - Part 1</a></li> -<li>⇢ <a href='#type-constraints'>Type constraints</a></li> -<li>⇢ <a href='#arraylist'>ArrayList</a></li> -<li>⇢ <a href='#helper-methods'>Helper methods</a></li> -<li>⇢ <a href='#sleep-sort'>Sleep sort</a></li> -<li>⇢ ⇢ <a href='#testing'>Testing</a></li> -</ul><br /> -<h2 style='display: inline' id='type-constraints'>Type constraints</h2><br /> -<br /> -<span>First, the package <span class='inlinecode'>ds</span> (data structures) defines the <span class='inlinecode'>types.go</span>. All examples will either operate on the <span class='inlinecode'>Integer</span> or <span class='inlinecode'>Number</span> type:</span><br /> -<br /> -<!-- Generator: GNU source-highlight 3.1.9 -by Lorenzo Bettini -http://www.lorenzobettini.it -http://www.gnu.org/software/src-highlite --> -<pre><b><font color="#ffffff">package</font></b><font color="#ff0000"> ds</font> - -<b><font color="#ffffff">import</font></b><font color="#ff0000"> </font><font color="#F3E651">(</font> -<font color="#ff0000"> </font><font color="#bb00ff">"golang.org/x/exp/constraints"</font> -<font color="#F3E651">)</font> - -<b><font color="#ffffff">type</font></b><font color="#ff0000"> Integer </font><b><font color="#ffffff">interface</font></b><font color="#ff0000"> </font><font color="#F3E651">{</font> -<font color="#ff0000"> constraints</font><font color="#F3E651">.</font><font color="#ff0000">Integer</font> -<font color="#F3E651">}</font> - -<b><font color="#ffffff">type</font></b><font color="#ff0000"> Number </font><b><font color="#ffffff">interface</font></b><font color="#ff0000"> </font><font color="#F3E651">{</font> -<font color="#ff0000"> constraints</font><font color="#F3E651">.</font><font color="#ff0000">Integer </font><font color="#F3E651">|</font><font color="#ff0000"> constraints</font><font color="#F3E651">.</font><font color="#ff0000">Float</font> -<font color="#F3E651">}</font> - -</pre> -<br /> -<h2 style='display: inline' id='arraylist'>ArrayList</h2><br /> -<br /> -<span>Next comes the <span class='inlinecode'>arraylist.go</span>, which defines the underlying data structure all the algorithms of this series will use. <span class='inlinecode'>ArrayList</span> is just a type alias of a Go array (or slice) with custom methods on it:</span><br /> -<br /> -<!-- Generator: GNU source-highlight 3.1.9 -by Lorenzo Bettini -http://www.lorenzobettini.it -http://www.gnu.org/software/src-highlite --> -<pre><b><font color="#ffffff">package</font></b><font color="#ff0000"> ds</font> - -<b><font color="#ffffff">import</font></b><font color="#ff0000"> </font><font color="#F3E651">(</font> -<font color="#ff0000"> </font><font color="#bb00ff">"fmt"</font> -<font color="#ff0000"> </font><font color="#bb00ff">"math/rand"</font> -<font color="#ff0000"> </font><font color="#bb00ff">"strings"</font> -<font color="#F3E651">)</font> - -<b><font color="#ffffff">type</font></b><font color="#ff0000"> ArrayList</font><font color="#F3E651">[</font><font color="#ff0000">V Number</font><font color="#F3E651">]</font><font color="#ff0000"> </font><font color="#F3E651">[]</font><font color="#ff0000">V</font> - -<b><font color="#ffffff">func</font></b><font color="#ff0000"> NewArrayList</font><font color="#F3E651">[</font><font color="#ff0000">V Number</font><font color="#F3E651">](</font><font color="#ff0000">l int</font><font color="#F3E651">)</font><font color="#ff0000"> ArrayList</font><font color="#F3E651">[</font><font color="#ff0000">V</font><font color="#F3E651">]</font><font color="#ff0000"> </font><font color="#F3E651">{</font> -<font color="#ff0000"> </font><b><font color="#ffffff">return</font></b><font color="#ff0000"> </font><font color="#7bc710">make</font><font color="#F3E651">(</font><font color="#ff0000">ArrayList</font><font color="#F3E651">[</font><font color="#ff0000">V</font><font color="#F3E651">],</font><font color="#ff0000"> l</font><font color="#F3E651">)</font> -<font color="#F3E651">}</font> -</pre> -<br /> -<span>As you can see, the code uses Go generics, which I refactored recently. Besides the default constructor (which only returns an empty <span class='inlinecode'>ArrayList</span> with a given capacity), there are also a bunch of special constructors. <span class='inlinecode'>NewRandomArrayList</span> is returning an <span class='inlinecode'>ArrayList</span> with random numbers, <span class='inlinecode'>NewAscendingArrayList</span> and <span class='inlinecode'>NewDescendingArrayList</span> are returning <span class='inlinecode'>ArrayList</span>s in either ascending or descending order. They all will be used later on for testing and benchmarking the algorithms.</span><br /> -<br /> -<!-- Generator: GNU source-highlight 3.1.9 -by Lorenzo Bettini -http://www.lorenzobettini.it -http://www.gnu.org/software/src-highlite --> -<pre><b><font color="#ffffff">func</font></b><font color="#ff0000"> NewRandomArrayList</font><font color="#F3E651">[</font><font color="#ff0000">V Number</font><font color="#F3E651">](</font><font color="#ff0000">l</font><font color="#F3E651">,</font><font color="#ff0000"> max int</font><font color="#F3E651">)</font><font color="#ff0000"> ArrayList</font><font color="#F3E651">[</font><font color="#ff0000">V</font><font color="#F3E651">]</font><font color="#ff0000"> </font><font color="#F3E651">{</font> -<font color="#ff0000"> a </font><font color="#F3E651">:=</font><font color="#ff0000"> </font><font color="#7bc710">make</font><font color="#F3E651">(</font><font color="#ff0000">ArrayList</font><font color="#F3E651">[</font><font color="#ff0000">V</font><font color="#F3E651">],</font><font color="#ff0000"> l</font><font color="#F3E651">)</font> -<font color="#ff0000"> </font><b><font color="#ffffff">for</font></b><font color="#ff0000"> i </font><font color="#F3E651">:=</font><font color="#ff0000"> </font><font color="#bb00ff">0</font><font color="#F3E651">;</font><font color="#ff0000"> i </font><font color="#F3E651"><</font><font color="#ff0000"> l</font><font color="#F3E651">;</font><font color="#ff0000"> i</font><font color="#F3E651">++</font><font color="#ff0000"> </font><font color="#F3E651">{</font> -<font color="#ff0000"> </font><b><font color="#ffffff">if</font></b><font color="#ff0000"> max </font><font color="#F3E651">></font><font color="#ff0000"> </font><font color="#bb00ff">0</font><font color="#ff0000"> </font><font color="#F3E651">{</font> -<font color="#ff0000"> a</font><font color="#F3E651">[</font><font color="#ff0000">i</font><font color="#F3E651">]</font><font color="#ff0000"> </font><font color="#F3E651">=</font><font color="#ff0000"> </font><font color="#7bc710">V</font><font color="#F3E651">(</font><font color="#ff0000">rand</font><font color="#F3E651">.</font><font color="#7bc710">Intn</font><font color="#F3E651">(</font><font color="#ff0000">max</font><font color="#F3E651">))</font> -<font color="#ff0000"> </font><b><font color="#ffffff">continue</font></b> -<font color="#ff0000"> </font><font color="#F3E651">}</font> -<font color="#ff0000"> a</font><font color="#F3E651">[</font><font color="#ff0000">i</font><font color="#F3E651">]</font><font color="#ff0000"> </font><font color="#F3E651">=</font><font color="#ff0000"> </font><font color="#7bc710">V</font><font color="#F3E651">(</font><font color="#ff0000">rand</font><font color="#F3E651">.</font><font color="#7bc710">Int</font><font color="#F3E651">())</font> -<font color="#ff0000"> </font><font color="#F3E651">}</font> -<font color="#ff0000"> </font><b><font color="#ffffff">return</font></b><font color="#ff0000"> a</font> -<font color="#F3E651">}</font> - -<b><font color="#ffffff">func</font></b><font color="#ff0000"> NewAscendingArrayList</font><font color="#F3E651">[</font><font color="#ff0000">V Number</font><font color="#F3E651">](</font><font color="#ff0000">l int</font><font color="#F3E651">)</font><font color="#ff0000"> ArrayList</font><font color="#F3E651">[</font><font color="#ff0000">V</font><font color="#F3E651">]</font><font color="#ff0000"> </font><font color="#F3E651">{</font> -<font color="#ff0000"> a </font><font color="#F3E651">:=</font><font color="#ff0000"> </font><font color="#7bc710">make</font><font color="#F3E651">(</font><font color="#ff0000">ArrayList</font><font color="#F3E651">[</font><font color="#ff0000">V</font><font color="#F3E651">],</font><font color="#ff0000"> l</font><font color="#F3E651">)</font> -<font color="#ff0000"> </font><b><font color="#ffffff">for</font></b><font color="#ff0000"> i </font><font color="#F3E651">:=</font><font color="#ff0000"> </font><font color="#bb00ff">0</font><font color="#F3E651">;</font><font color="#ff0000"> i </font><font color="#F3E651"><</font><font color="#ff0000"> l</font><font color="#F3E651">;</font><font color="#ff0000"> i</font><font color="#F3E651">++</font><font color="#ff0000"> </font><font color="#F3E651">{</font> -<font color="#ff0000"> a</font><font color="#F3E651">[</font><font color="#ff0000">i</font><font color="#F3E651">]</font><font color="#ff0000"> </font><font color="#F3E651">=</font><font color="#ff0000"> </font><font color="#7bc710">V</font><font color="#F3E651">(</font><font color="#ff0000">i</font><font color="#F3E651">)</font> -<font color="#ff0000"> </font><font color="#F3E651">}</font> -<font color="#ff0000"> </font><b><font color="#ffffff">return</font></b><font color="#ff0000"> a</font> -<font color="#F3E651">}</font> - -<b><font color="#ffffff">func</font></b><font color="#ff0000"> NewDescendingArrayList</font><font color="#F3E651">[</font><font color="#ff0000">V Number</font><font color="#F3E651">](</font><font color="#ff0000">l int</font><font color="#F3E651">)</font><font color="#ff0000"> ArrayList</font><font color="#F3E651">[</font><font color="#ff0000">V</font><font color="#F3E651">]</font><font color="#ff0000"> </font><font color="#F3E651">{</font> -<font color="#ff0000"> a </font><font color="#F3E651">:=</font><font color="#ff0000"> </font><font color="#7bc710">make</font><font color="#F3E651">(</font><font color="#ff0000">ArrayList</font><font color="#F3E651">[</font><font color="#ff0000">V</font><font color="#F3E651">],</font><font color="#ff0000"> l</font><font color="#F3E651">)</font> -<font color="#ff0000"> j </font><font color="#F3E651">:=</font><font color="#ff0000"> l </font><font color="#F3E651">-</font><font color="#ff0000"> </font><font color="#bb00ff">1</font> -<font color="#ff0000"> </font><b><font color="#ffffff">for</font></b><font color="#ff0000"> i </font><font color="#F3E651">:=</font><font color="#ff0000"> </font><font color="#bb00ff">0</font><font color="#F3E651">;</font><font color="#ff0000"> i </font><font color="#F3E651"><</font><font color="#ff0000"> l</font><font color="#F3E651">;</font><font color="#ff0000"> i</font><font color="#F3E651">++</font><font color="#ff0000"> </font><font color="#F3E651">{</font> -<font color="#ff0000"> a</font><font color="#F3E651">[</font><font color="#ff0000">i</font><font color="#F3E651">]</font><font color="#ff0000"> </font><font color="#F3E651">=</font><font color="#ff0000"> </font><font color="#7bc710">V</font><font color="#F3E651">(</font><font color="#ff0000">j</font><font color="#F3E651">)</font> -<font color="#ff0000"> j</font><font color="#F3E651">--</font> -<font color="#ff0000"> </font><font color="#F3E651">}</font> -<font color="#ff0000"> </font><b><font color="#ffffff">return</font></b><font color="#ff0000"> a</font> -<font color="#F3E651">}</font> -</pre> -<br /> -<h2 style='display: inline' id='helper-methods'>Helper methods</h2><br /> -<br /> -<span>The <span class='inlinecode'>FirstN</span> method only returns the first N elements of the <span class='inlinecode'>ArrayList</span>. This is useful for printing out only parts of the data structure:</span><br /> -<br /> -<!-- Generator: GNU source-highlight 3.1.9 -by Lorenzo Bettini -http://www.lorenzobettini.it -http://www.gnu.org/software/src-highlite --> -<pre><b><font color="#ffffff">func</font></b><font color="#ff0000"> </font><font color="#F3E651">(</font><font color="#ff0000">a ArrayList</font><font color="#F3E651">[</font><font color="#ff0000">V</font><font color="#F3E651">])</font><font color="#ff0000"> </font><font color="#7bc710">FirstN</font><font color="#F3E651">(</font><font color="#ff0000">n int</font><font color="#F3E651">)</font><font color="#ff0000"> </font><b><font color="#F35E1E">string</font></b><font color="#ff0000"> </font><font color="#F3E651">{</font> -<font color="#ff0000"> </font><b><font color="#ffffff">var</font></b><font color="#ff0000"> sb strings</font><font color="#F3E651">.</font><font color="#ff0000">Builder</font> -<font color="#ff0000"> j </font><font color="#F3E651">:=</font><font color="#ff0000"> n</font> - -<font color="#ff0000"> l </font><font color="#F3E651">:=</font><font color="#ff0000"> </font><font color="#7bc710">len</font><font color="#F3E651">(</font><font color="#ff0000">a</font><font color="#F3E651">)</font> -<font color="#ff0000"> </font><b><font color="#ffffff">if</font></b><font color="#ff0000"> j </font><font color="#F3E651">></font><font color="#ff0000"> l </font><font color="#F3E651">{</font> -<font color="#ff0000"> j </font><font color="#F3E651">=</font><font color="#ff0000"> l</font> -<font color="#ff0000"> </font><font color="#F3E651">}</font> - -<font color="#ff0000"> </font><b><font color="#ffffff">for</font></b><font color="#ff0000"> i </font><font color="#F3E651">:=</font><font color="#ff0000"> </font><font color="#bb00ff">0</font><font color="#F3E651">;</font><font color="#ff0000"> i </font><font color="#F3E651"><</font><font color="#ff0000"> j</font><font color="#F3E651">;</font><font color="#ff0000"> i</font><font color="#F3E651">++</font><font color="#ff0000"> </font><font color="#F3E651">{</font> -<font color="#ff0000"> fmt</font><font color="#F3E651">.</font><font color="#7bc710">Fprintf</font><font color="#F3E651">(&</font><font color="#ff0000">sb</font><font color="#F3E651">,</font><font color="#ff0000"> </font><font color="#bb00ff">"%v "</font><font color="#F3E651">,</font><font color="#ff0000"> a</font><font color="#F3E651">[</font><font color="#ff0000">i</font><font color="#F3E651">])</font> -<font color="#ff0000"> </font><font color="#F3E651">}</font> - -<font color="#ff0000"> </font><b><font color="#ffffff">if</font></b><font color="#ff0000"> j </font><font color="#F3E651"><</font><font color="#ff0000"> l </font><font color="#F3E651">{</font> -<font color="#ff0000"> fmt</font><font color="#F3E651">.</font><font color="#7bc710">Fprintf</font><font color="#F3E651">(&</font><font color="#ff0000">sb</font><font color="#F3E651">,</font><font color="#ff0000"> </font><font color="#bb00ff">"... "</font><font color="#F3E651">)</font> -<font color="#ff0000"> </font><font color="#F3E651">}</font> - -<font color="#ff0000"> </font><b><font color="#ffffff">return</font></b><font color="#ff0000"> sb</font><font color="#F3E651">.</font><font color="#7bc710">String</font><font color="#F3E651">()</font> -<font color="#F3E651">}</font> -</pre> -<br /> -<span>The <span class='inlinecode'>Sorted</span> method checks whether the <span class='inlinecode'>ArrayList</span> is sorted. This will be used by the unit tests later on:</span><br /> -<br /> -<!-- Generator: GNU source-highlight 3.1.9 -by Lorenzo Bettini -http://www.lorenzobettini.it -http://www.gnu.org/software/src-highlite --> -<pre><b><font color="#ffffff">func</font></b><font color="#ff0000"> </font><font color="#F3E651">(</font><font color="#ff0000">a ArrayList</font><font color="#F3E651">[</font><font color="#ff0000">V</font><font color="#F3E651">])</font><font color="#ff0000"> </font><font color="#7bc710">Sorted</font><font color="#F3E651">()</font><font color="#ff0000"> </font><b><font color="#F35E1E">bool</font></b><font color="#ff0000"> </font><font color="#F3E651">{</font> -<font color="#ff0000"> </font><b><font color="#ffffff">for</font></b><font color="#ff0000"> i </font><font color="#F3E651">:=</font><font color="#ff0000"> </font><font color="#7bc710">len</font><font color="#F3E651">(</font><font color="#ff0000">a</font><font color="#F3E651">)</font><font color="#ff0000"> </font><font color="#F3E651">-</font><font color="#ff0000"> </font><font color="#bb00ff">1</font><font color="#F3E651">;</font><font color="#ff0000"> i </font><font color="#F3E651">></font><font color="#ff0000"> </font><font color="#bb00ff">0</font><font color="#F3E651">;</font><font color="#ff0000"> i</font><font color="#F3E651">--</font><font color="#ff0000"> </font><font color="#F3E651">{</font> -<font color="#ff0000"> </font><b><font color="#ffffff">if</font></b><font color="#ff0000"> a</font><font color="#F3E651">[</font><font color="#ff0000">i</font><font color="#F3E651">]</font><font color="#ff0000"> </font><font color="#F3E651"><</font><font color="#ff0000"> a</font><font color="#F3E651">[</font><font color="#ff0000">i</font><font color="#F3E651">-</font><font color="#bb00ff">1</font><font color="#F3E651">]</font><font color="#ff0000"> </font><font color="#F3E651">{</font> -<font color="#ff0000"> </font><b><font color="#ffffff">return</font></b><font color="#ff0000"> false</font> -<font color="#ff0000"> </font><font color="#F3E651">}</font> -<font color="#ff0000"> </font><font color="#F3E651">}</font> -<font color="#ff0000"> </font><b><font color="#ffffff">return</font></b><font color="#ff0000"> true</font> -<font color="#F3E651">}</font> -</pre> -<br /> -<span>And the last utility method used is <span class='inlinecode'>Swap</span>, which allows swapping the values of two indices in the <span class='inlinecode'>ArrayList</span>:</span><br /> -<br /> -<!-- Generator: GNU source-highlight 3.1.9 -by Lorenzo Bettini -http://www.lorenzobettini.it -http://www.gnu.org/software/src-highlite --> -<pre><b><font color="#ffffff">func</font></b><font color="#ff0000"> </font><font color="#F3E651">(</font><font color="#ff0000">a ArrayList</font><font color="#F3E651">[</font><font color="#ff0000">V</font><font color="#F3E651">])</font><font color="#ff0000"> </font><font color="#7bc710">Swap</font><font color="#F3E651">(</font><font color="#ff0000">i</font><font color="#F3E651">,</font><font color="#ff0000"> j int</font><font color="#F3E651">)</font><font color="#ff0000"> </font><font color="#F3E651">{</font> -<font color="#ff0000"> aux </font><font color="#F3E651">:=</font><font color="#ff0000"> a</font><font color="#F3E651">[</font><font color="#ff0000">i</font><font color="#F3E651">]</font> -<font color="#ff0000"> a</font><font color="#F3E651">[</font><font color="#ff0000">i</font><font color="#F3E651">]</font><font color="#ff0000"> </font><font color="#F3E651">=</font><font color="#ff0000"> a</font><font color="#F3E651">[</font><font color="#ff0000">j</font><font color="#F3E651">]</font> -<font color="#ff0000"> a</font><font color="#F3E651">[</font><font color="#ff0000">j</font><font color="#F3E651">]</font><font color="#ff0000"> </font><font color="#F3E651">=</font><font color="#ff0000"> aux</font> -<font color="#F3E651">}</font> - -</pre> -<br /> -<h2 style='display: inline' id='sleep-sort'>Sleep sort</h2><br /> -<br /> -<span>Let's implement our first algorithm, sleep sort. Sleep sort is a non-traditional and unconventional sorting algorithm based on the idea of waiting a certain amount of time corresponding to the value of each element in the input <span class='inlinecode'>ArrayList</span>. It's more of a fun, creative concept rather than an efficient or practical sorting technique. This is not a sorting algorithm you would use in any production code. As you can imagine, it is quite an inefficient sorting algorithm (it's only listed here as a warm-up exercise). This sorting method may also return false results depending on how the Goroutines are scheduled by the Go runtime. </span><br /> -<br /> -<br /> -<!-- Generator: GNU source-highlight 3.1.9 -by Lorenzo Bettini -http://www.lorenzobettini.it -http://www.gnu.org/software/src-highlite --> -<pre><b><font color="#ffffff">package</font></b><font color="#ff0000"> sort</font> - -<b><font color="#ffffff">import</font></b><font color="#ff0000"> </font><font color="#F3E651">(</font> -<font color="#ff0000"> </font><font color="#bb00ff">"codeberg.org/snonux/algorithms/ds"</font> -<font color="#ff0000"> </font><font color="#bb00ff">"sync"</font> -<font color="#ff0000"> </font><font color="#bb00ff">"time"</font> -<font color="#F3E651">)</font> - -<b><font color="#ffffff">func</font></b><font color="#ff0000"> Sleep</font><font color="#F3E651">[</font><font color="#ff0000">V ds</font><font color="#F3E651">.</font><font color="#ff0000">Integer</font><font color="#F3E651">](</font><font color="#ff0000">a ds</font><font color="#F3E651">.</font><font color="#ff0000">ArrayList</font><font color="#F3E651">[</font><font color="#ff0000">V</font><font color="#F3E651">])</font><font color="#ff0000"> ds</font><font color="#F3E651">.</font><font color="#ff0000">ArrayList</font><font color="#F3E651">[</font><font color="#ff0000">V</font><font color="#F3E651">]</font><font color="#ff0000"> </font><font color="#F3E651">{</font> -<font color="#ff0000"> sorted </font><font color="#F3E651">:=</font><font color="#ff0000"> ds</font><font color="#F3E651">.</font><font color="#ff0000">NewArrayList</font><font color="#F3E651">[</font><font color="#ff0000">V</font><font color="#F3E651">](</font><font color="#7bc710">len</font><font color="#F3E651">(</font><font color="#ff0000">a</font><font color="#F3E651">))</font> - -<font color="#ff0000"> numCh </font><font color="#F3E651">:=</font><font color="#ff0000"> </font><font color="#7bc710">make</font><font color="#F3E651">(</font><b><font color="#ffffff">chan</font></b><font color="#ff0000"> V</font><font color="#F3E651">)</font> -<font color="#ff0000"> </font><b><font color="#ffffff">var</font></b><font color="#ff0000"> wg sync</font><font color="#F3E651">.</font><font color="#ff0000">WaitGroup</font> -<font color="#ff0000"> wg</font><font color="#F3E651">.</font><font color="#7bc710">Add</font><font color="#F3E651">(</font><font color="#7bc710">len</font><font color="#F3E651">(</font><font color="#ff0000">a</font><font color="#F3E651">))</font> - -<font color="#ff0000"> </font><b><font color="#ffffff">go</font></b><font color="#ff0000"> </font><b><font color="#ffffff">func</font></b><font color="#F3E651">()</font><font color="#ff0000"> </font><font color="#F3E651">{</font> -<font color="#ff0000"> wg</font><font color="#F3E651">.</font><font color="#7bc710">Wait</font><font color="#F3E651">()</font> -<font color="#ff0000"> </font><font color="#7bc710">close</font><font color="#F3E651">(</font><font color="#ff0000">numCh</font><font color="#F3E651">)</font> -<font color="#ff0000"> </font><font color="#F3E651">}</font><font color="#F3E651">()</font> - -<font color="#ff0000"> </font><b><font color="#ffffff">for</font></b><font color="#ff0000"> _</font><font color="#F3E651">,</font><font color="#ff0000"> num </font><font color="#F3E651">:=</font><font color="#ff0000"> </font><b><font color="#ffffff">range</font></b><font color="#ff0000"> a </font><font color="#F3E651">{</font> -<font color="#ff0000"> </font><b><font color="#ffffff">go</font></b><font color="#ff0000"> </font><b><font color="#ffffff">func</font></b><font color="#F3E651">(</font><font color="#ff0000">num V</font><font color="#F3E651">)</font><font color="#ff0000"> </font><font color="#F3E651">{</font> -<font color="#ff0000"> </font><b><font color="#ffffff">defer</font></b><font color="#ff0000"> wg</font><font color="#F3E651">.</font><font color="#7bc710">Done</font><font color="#F3E651">()</font> -<font color="#ff0000"> time</font><font color="#F3E651">.</font><font color="#7bc710">Sleep</font><font color="#F3E651">(</font><font color="#ff0000">time</font><font color="#F3E651">.</font><font color="#7bc710">Duration</font><font color="#F3E651">(</font><font color="#ff0000">num</font><font color="#F3E651">)</font><font color="#ff0000"> </font><font color="#F3E651">*</font><font color="#ff0000"> time</font><font color="#F3E651">.</font><font color="#ff0000">Second</font><font color="#F3E651">)</font> -<font color="#ff0000"> numCh </font><font color="#F3E651"><-</font><font color="#ff0000"> num</font> -<font color="#ff0000"> </font><font color="#F3E651">}</font><font color="#F3E651">(</font><font color="#ff0000">num</font><font color="#F3E651">)</font> -<font color="#ff0000"> </font><font color="#F3E651">}</font> - -<font color="#ff0000"> </font><b><font color="#ffffff">for</font></b><font color="#ff0000"> num </font><font color="#F3E651">:=</font><font color="#ff0000"> </font><b><font color="#ffffff">range</font></b><font color="#ff0000"> numCh </font><font color="#F3E651">{</font> -<font color="#ff0000"> sorted </font><font color="#F3E651">=</font><font color="#ff0000"> </font><font color="#7bc710">append</font><font color="#F3E651">(</font><font color="#ff0000">sorted</font><font color="#F3E651">,</font><font color="#ff0000"> num</font><font color="#F3E651">)</font> -<font color="#ff0000"> </font><font color="#F3E651">}</font> - -<font color="#ff0000"> </font><b><font color="#ffffff">return</font></b><font color="#ff0000"> sorted</font> -<font color="#F3E651">}</font> -</pre> -<br /> -<span>This Go code implements the sleep sort algorithm using generics and goroutines. The main function <span class='inlinecode'>Sleep[V ds.Integer](a ds.ArrayList[V]) ds.ArrayList[V]</span> takes a generic <span class='inlinecode'>ArrayList</span> as input and returns a sorted <span class='inlinecode'>ArrayList</span>. The code creates a separate goroutine for each element in the input array, sleeps for a duration proportional to the element's value, and then sends the element to a channel. Another goroutine waits for all the sleeping goroutines to finish and then closes the channel. The sorted result <span class='inlinecode'>ArrayList</span> is constructed by appending the elements received from the channel in the order they arrive. The <span class='inlinecode'>sync.WaitGroup</span> is used to synchronize goroutines and ensure that all of them have completed before closing the channel.</span><br /> -<br /> -<h3 style='display: inline' id='testing'>Testing</h3><br /> -<br /> -<span>For testing, we only allow values up to 10, as otherwise, it would take too long to finish:</span><br /> -<br /> -<!-- Generator: GNU source-highlight 3.1.9 -by Lorenzo Bettini -http://www.lorenzobettini.it -http://www.gnu.org/software/src-highlite --> -<pre><b><font color="#ffffff">package</font></b><font color="#ff0000"> sort</font> - -<b><font color="#ffffff">import</font></b><font color="#ff0000"> </font><font color="#F3E651">(</font> -<font color="#ff0000"> </font><font color="#bb00ff">"fmt"</font> -<font color="#ff0000"> </font><font color="#bb00ff">"testing"</font> - -<font color="#ff0000"> </font><font color="#bb00ff">"codeberg.org/snonux/algorithms/ds"</font> -<font color="#F3E651">)</font> - -<b><font color="#ffffff">func</font></b><font color="#ff0000"> </font><font color="#7bc710">TestSleepSort</font><font color="#F3E651">(</font><font color="#ff0000">t </font><font color="#F3E651">*</font><font color="#ff0000">testing</font><font color="#F3E651">.</font><font color="#ff0000">T</font><font color="#F3E651">)</font><font color="#ff0000"> </font><font color="#F3E651">{</font> -<font color="#ff0000"> a </font><font color="#F3E651">:=</font><font color="#ff0000"> ds</font><font color="#F3E651">.</font><font color="#ff0000">NewRandomArrayList</font><font color="#F3E651">[</font><font color="#ff0000">int</font><font color="#F3E651">](</font><font color="#bb00ff">10</font><font color="#F3E651">,</font><font color="#ff0000"> </font><font color="#bb00ff">10</font><font color="#F3E651">)</font> -<font color="#ff0000"> a </font><font color="#F3E651">=</font><font color="#ff0000"> </font><font color="#7bc710">Sleep</font><font color="#F3E651">(</font><font color="#ff0000">a</font><font color="#F3E651">)</font> -<font color="#ff0000"> </font><b><font color="#ffffff">if</font></b><font color="#ff0000"> </font><font color="#F3E651">!</font><font color="#ff0000">a</font><font color="#F3E651">.</font><font color="#7bc710">Sorted</font><font color="#F3E651">()</font><font color="#ff0000"> </font><font color="#F3E651">{</font> -<font color="#ff0000"> t</font><font color="#F3E651">.</font><font color="#7bc710">Errorf</font><font color="#F3E651">(</font><font color="#bb00ff">"Array not sorted: %v"</font><font color="#F3E651">,</font><font color="#ff0000"> a</font><font color="#F3E651">)</font> -<font color="#ff0000"> </font><font color="#F3E651">}</font> -<font color="#F3E651">}</font> -</pre> -<br /> -<span>As you can see, it takes <span class='inlinecode'>9s</span> here for the algorithm to finish (which is the highest value in the <span class='inlinecode'>ArrayList</span>):</span><br /> -<br /> -<!-- Generator: GNU source-highlight 3.1.9 -by Lorenzo Bettini -http://www.lorenzobettini.it -http://www.gnu.org/software/src-highlite --> -<pre><font color="#ff0000">❯ go </font><b><font color="#ffffff">test</font></b><font color="#ff0000"> </font><font color="#F3E651">.</font><font color="#ff0000">/sort -v -run SleepSort</font> -<font color="#F3E651">===</font><font color="#ff0000"> RUN TestSleepSort</font> -<font color="#ff0000">--- PASS</font><font color="#F3E651">:</font><font color="#ff0000"> TestSleepSort </font><font color="#F3E651">(</font><font color="#bb00ff">9</font><font color="#F3E651">.</font><font color="#ff0000">00s</font><font color="#F3E651">)</font> -<font color="#ff0000">PASS</font> -<font color="#ff0000">ok codeberg</font><font color="#F3E651">.</font><font color="#ff0000">org/snonux/algorithms/sort </font><font color="#bb00ff">9</font><font color="#F3E651">.</font><font color="#ff0000">002s</font> -</pre> -<br /> -<span>I won't write any benchmark for sleep sort; that will be done for the algorithms to come in this series :-).</span><br /> -<br /> -<span>E-Mail your comments to <span class='inlinecode'>paul@nospam.buetow.org</span> :-)</span><br /> -<br /> -<a class='textlink' href='../'>Back to the main site</a><br /> - </div> - </content> - </entry> - <entry> <title>'Never split the difference' book notes</title> <link href="gemini://foo.zone/gemfeed/2023-04-01-never-split-the-difference-book-notes.gmi" /> <id>gemini://foo.zone/gemfeed/2023-04-01-never-split-the-difference-book-notes.gmi</id> @@ -9179,4 +8895,528 @@ GNU/kFreeBSD rhea.buetow.org 8.0-RELEASE-p5 FreeBSD 8.0-RELEASE-p5 #2: Sat Nov 2 </div> </content> </entry> + <entry> + <title>Bash Golf Part 2</title> + <link href="gemini://foo.zone/gemfeed/2022-01-01-bash-golf-part-2.gmi" /> + <id>gemini://foo.zone/gemfeed/2022-01-01-bash-golf-part-2.gmi</id> + <updated>2022-01-01T23:36:15+00:00</updated> + <author> + <name>Paul Buetow aka snonux</name> + <email>paul@dev.buetow.org</email> + </author> + <summary>This is the second blog post about my Bash Golf series. This series is random Bash tips, tricks and weirdnesses I came across. It's a collection of smaller articles I wrote in an older (in German language) blog, which I translated and refreshed with some new content.</summary> + <content type="xhtml"> + <div xmlns="http://www.w3.org/1999/xhtml"> + <h1 style='display: inline' id='bash-golf-part-2'>Bash Golf Part 2</h1><br /> +<br /> +<span class='quote'>Published at 2022-01-01T23:36:15+00:00; Updated at 2022-01-05</span><br /> +<br /> +<span>This is the second blog post about my Bash Golf series. This series is random Bash tips, tricks and weirdnesses I came across. It's a collection of smaller articles I wrote in an older (in German language) blog, which I translated and refreshed with some new content.</span><br /> +<br /> +<a class='textlink' href='./2021-11-29-bash-golf-part-1.html'>2021-11-29 Bash Golf Part 1</a><br /> +<a class='textlink' href='./2022-01-01-bash-golf-part-2.html'>2022-01-01 Bash Golf Part 2 (You are currently reading this)</a><br /> +<a class='textlink' href='./2023-12-10-bash-golf-part-3.html'>2023-12-10 Bash Golf Part 3</a><br /> +<br /> +<pre> + '\ '\ . . |>18>> + \ \ . ' . | + O>> O>> . 'o | + \ .\. .. . | + /\ . /\ . . | + / / . / / .' . | +jgs^^^^^^^`^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ + Art by Joan Stark, mod. by Paul Buetow +</pre> +<br /> +<h2 style='display: inline' id='table-of-contents'>Table of Contents</h2><br /> +<br /> +<ul> +<li><a href='#bash-golf-part-2'>Bash Golf Part 2</a></li> +<li>⇢ <a href='#redirection'>Redirection</a></li> +<li>⇢ <a href='#here'>HERE</a></li> +<li>⇢ <a href='#random'>RANDOM</a></li> +<li>⇢ <a href='#set--x-and-set--e-and-pipefile'& |
