This repository was archived by the owner on May 18, 2021. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathindex.html
More file actions
144 lines (141 loc) · 17.6 KB
/
Copy pathindex.html
File metadata and controls
144 lines (141 loc) · 17.6 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
<!DOCTYPE html>
<html>
<head>
<!-- Global site tag (gtag.js) - Google Analytics -->
<script async src="https://www.googletagmanager.com/gtag/js?id=UA-33188271-5"></script>
<script>
window.dataLayer = window.dataLayer || [];
function gtag(){dataLayer.push(arguments);}
gtag('js', new Date());
gtag('config', 'UA-33188271-5');
</script>
<title>Zombie Dev Log</title>
<meta charset="utf-8" />
<link rel="stylesheet" href="css/docutils_solarized_light.css" />
</head>
<body>
<section id="zombie-dev-log">
<h1>Zombie Dev Log</h1>
<p><a href="https://github.com/radustoenescu/zombie-dev">Code sleeps here</a></p>
<a id="day1"></a>
<section id="day-1-optimal-matrix-chain-multiplication">
<h2>Day 1 (Optimal matrix chain multiplication)</h2>
<p>Because I know pretty well the Hanoi tower problem, I started with <a href="https://medium.com/100-days-of-algorithms/day-2-matrix-chain-multiplication-3ae6349c34ab">Day 2</a>.</p>
<p>The <a href="https://en.wikipedia.org/wiki/Matrix_chain_multiplication">Matrix chain multiplication</a> problem is a quite straightforward example of <a href="https://en.wikipedia.org/wiki/Dynamic_programming">Dynamic programming</a>.</p>
<p>I implemented the basic algorithm. Wikipedia also points to a better algorithm, which I only skimmed over since it's quite complex and well beyond what I'm doing here.</p>
<p>It took me:</p>
<blockquote>
<ul>
<li>thinking: 2m</li>
<li>coding: 17m</li>
<li>debugging: 9m</li>
<li>total: 28m</li>
</ul>
</blockquote>
<p>In future I think I can limit debugging greatly since I made some noob mistakes which required quite a bit of looking around the code to fix, but the coding went smooth and I didn't search the documentation that much.</p>
<p>You can find the code in the <a href="https://github.com/radustoenescu/zombie-dev">usual place</a>. Nothing fancy. Maybe the <code>@functools.lru_cache</code> decorator is quite nice to check out since it makes memoization a lot easier to add.</p>
</section>
<a id="day2"></a>
<section id="day-2-counting-set-bits">
<h2>Day 2 (Counting set bits)</h2>
<p>Given an <code>int</code>, how many ones are there in its binary representation.</p>
<p>For example: <code>0b00101</code> -> 2; <code>0b001011101</code> -> 5. You got the idea, easy peasy.</p>
<pre data-language="python"><span class="k">def</span> <span class="nf">count_bits</span><span class="p">(</span><span class="n">n</span><span class="p">):</span>
<span class="n">count</span> <span class="o">=</span> <span class="mi">0</span>
<span class="k">while</span> <span class="n">n</span> <span class="o">></span> <span class="mi">0</span><span class="p">:</span>
<span class="n">count</span> <span class="o">+=</span> <span class="n">n</span> <span class="o">&</span> <span class="mi">1</span>
<span class="n">n</span> <span class="o">>>=</span> <span class="mi">1</span>
<span class="k">return</span> <span class="n">count</span></pre>
<p>It works, but what the hell man?! That's kids stuff.</p>
<p>Right, of course you can do better than that:</p>
<pre data-language="python"><span class="k">def</span> <span class="nf">count_bits_wicked</span><span class="p">(</span><span class="n">n</span><span class="p">):</span>
<span class="n">count</span> <span class="o">=</span> <span class="mi">0</span>
<span class="k">while</span> <span class="n">n</span> <span class="o">></span> <span class="mi">0</span><span class="p">:</span>
<span class="n">n</span> <span class="o">&=</span> <span class="n">n</span> <span class="o">-</span> <span class="mi">1</span>
<span class="n">count</span> <span class="o">+=</span> <span class="mi">1</span>
<span class="k">return</span> <span class="n">count</span></pre>
<p><em>What?</em></p>
<p>Yeah, that's what I thought when I first saw that. I hate bit twiddling. I personally think it cripples the mind of any sane person.</p>
<p>However, this one above is pretty easy to grasp and understand if you try it on a piece of paper.</p>
<p>Here, of course I did that for you:</p>
<img src="img/wicked_bits.jpg" />
<p><em>Rumour has it that every horizontal line is a bitwise and between the current n and n-1. Except from the shortest one(second to last) which is a typo.</em></p>
<p>So you can see how every and operation essentially knocks out one set bit at a time(<em>or one one</em>, if you prefer that).</p>
<p>Thus, the complexity is <code>Theta(bits_set)</code> as opposed to my solution which went through all the bits every time, yielding <code>Theta(bits)</code> in complexity.</p>
<p>This second solution is not mine. On this <a href="https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetKernighan">bit porn</a> site you can learn more about it, and also find more bit twiddling porn if you're into that.</p>
<p><em>No times for this problem since the naive solution took me nothing, and the smart one is not mine.</em></p>
</section>
<a id="day3"></a>
<section id="day-3-the-sieve-of-eratosthenes">
<h2>Day 3 (The Sieve of Eratosthenes)</h2>
<p><strong>SPOILER ALERT: BOY ... IT WAS FUN!</strong></p>
<p>This belongs to <a href="https://medium.com/100-days-of-algorithms/day-5-eratosthenes-sieve-60ab162a1f5b">day 5</a> in the original series.</p>
<p>Ok, this is a pretty simple algorithm, I remember implementing it for the first time in <a href="https://www.facebook.com/Liceul-Teoretic-Alexandru-Ghica-Alexandria-830767510327046/">highschool</a> in Pascal. What makes it simple is that, usually, people implement the, let's call it, <em>bounded Sieve</em> - which generates all the primes up to a limit, and, if the limit is reasonable one can store the whole table in memory, and that's that - you just delete things from it, or mark things as non-prime.</p>
<p>Having said this, if you want to generate primes infinitely(<em>given a certain memory or time budget</em>), the problem gets more interesting - <em>this one I implemented in college, in Scheme, or at least I thought so :)), but I'll stop with the spoilers now.</em></p>
<p>Well, my idea (the one I implemented in college) is to start with an infinite generator containing all natural numbers above 1. At each step you pop one out and filter out its multiples from the generator. Easy-peasy, right?!</p>
<p>So, I came out with this Python3 code:</p>
<pre data-language="python"><span class="kn">import</span> <span class="nn">itertools</span>
<span class="k">def</span> <span class="nf">sieve</span><span class="p">():</span>
<span class="c"># begin with all natural numbers above 1</span>
<span class="n">picker</span> <span class="o">=</span> <span class="n">itertools</span><span class="o">.</span><span class="n">count</span><span class="p">(</span><span class="mi">2</span><span class="p">)</span>
<span class="k">while</span> <span class="bp">True</span><span class="p">:</span>
<span class="c"># take the next available number</span>
<span class="n">v</span> <span class="o">=</span> <span class="nb">next</span><span class="p">(</span><span class="n">picker</span><span class="p">)</span>
<span class="k">yield</span> <span class="n">v</span>
<span class="c"># filter from the generator its multiples</span>
<span class="n">picker</span> <span class="o">=</span> <span class="nb">filter</span><span class="p">(</span><span class="k">lambda</span> <span class="n">x</span><span class="p">:</span> <span class="n">x</span> <span class="o">%</span> <span class="n">v</span> <span class="o">!=</span> <span class="mi">0</span><span class="p">,</span> <span class="n">picker</span><span class="p">)</span></pre>
<p>Aaand it didn't work.</p>
<p>Furthermore, I had no frickin' clue why it didn't. I could see some weird behavior in the debugger - the generator's contents were wrong - but I didn't knew why.</p>
<p>I got a little paranoid, and started doubting I knew the solution, so I double checked by quickly implementing it in Haskell:</p>
<pre data-language="haskell"><span class="nf">sieve</span> <span class="n">remaining</span> <span class="ow">=</span> <span class="n">nextItem</span> <span class="kt">:</span> <span class="n">sieve</span> <span class="p">(</span><span class="n">filter</span> <span class="p">(</span><span class="nf">\</span><span class="n">x</span> <span class="ow">-></span> <span class="n">x</span> <span class="p">`</span><span class="n">mod</span><span class="p">`</span> <span class="n">nextItem</span> <span class="o">/=</span> <span class="mi">0</span><span class="p">)</span> <span class="n">remaining</span><span class="p">)</span>
<span class="kr">where</span>
<span class="n">nextItem</span> <span class="ow">=</span> <span class="n">head</span> <span class="n">remaining</span></pre>
<p>And that one worked. Now I was really puzzled since the Python code was a mere translation of the one in Haskell, I thought maybe I don't understand the inner workings of infinite generators in Python and the <code>filter</code> method <a href="https://stackoverflow.com/questions/55966499/troublesome-filter-behavior-when-implementing-the-sieve-of-eratosthenes-in-pyt">so I asked on Stackoverflow</a>. I found out there that lambdas in Python <a href="https://stackoverflow.com/questions/2295290/what-do-lambda-function-closures-capture">don't work as I expected</a> (as they do in most functional programming languages).</p>
<p>The fix is below:</p>
<p><code>picker = filter(lambda x, prime = v: x % prime != 0, picker)</code></p>
<p>Already this was proving more educative than it looked like in the beginning. But the really fun part starts now. While I was waiting for some light on Stackoveflow, I also looked on Wikipedia for more insight, especially at the, so called, <a href="https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Incremental_sieve">iterative sieve</a> where I found this:</p>
<p><em>Primes can also be produced by iteratively sieving out the composites through divisibility testing by sequential primes, one prime at a time. It is not the sieve of Eratosthenes but is often confused with it, even though the sieve of Eratosthenes directly generates the composites instead of testing for them. Trial division has worse theoretical complexity than that of the sieve of Eratosthenes in generating ranges of primes.</em></p>
<p><strong>BAM!</strong> I wasn't implementing the true algorithm(nor was I back in college). A thing which is pretty clear, now, in retrospect. <a href="http://eprints.whiterose.ac.uk/3784/1/runcimanc1.pdf">My version</a>, which is also pretty famous due to its beautiful implementation, doesn't jump from one multiple to another, simply checks one number after another if it is a multiple(<em>a pretty bad thing, but more on that later</em>). So famous, that I even found a paper about the <a href="https://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf">"unfaithful" vs. the genuine sieve</a>.</p>
<p><strong>Short recap:</strong> at this point I have a working version of the wrong algorithm that generates primes indefinitely. Next, let's code the genuine sieve.</p>
<pre data-language="python"><span class="kn">import</span> <span class="nn">heapq</span>
<span class="c"># In the proper sieve we will cross multiples as we go,</span>
<span class="c"># For each prime we found we'll keep its largest multiple generated</span>
<span class="c"># that wasn't reached so far in our search.</span>
<span class="c">#</span>
<span class="c"># When our iteration reaches a multiple, it gets popped and the next</span>
<span class="c"># multiple is inserted in the heap.</span>
<span class="k">def</span> <span class="nf">proper_sieve</span><span class="p">():</span>
<span class="k">yield</span> <span class="mi">2</span>
<span class="n">crt_number</span> <span class="o">=</span> <span class="mi">3</span>
<span class="n">multiples</span> <span class="o">=</span> <span class="p">[(</span><span class="mi">4</span><span class="p">,</span><span class="mi">2</span><span class="p">)]</span>
<span class="k">while</span> <span class="bp">True</span><span class="p">:</span>
<span class="n">next_multiple</span> <span class="o">=</span> <span class="n">multiples</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span>
<span class="c"># if the next smalles multiple is larger than the number we're currently looking at</span>
<span class="c"># then all the numbers between the two are primes</span>
<span class="c"># we'll report them as such and add their first multiples to the queue</span>
<span class="k">if</span> <span class="n">next_multiple</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span> <span class="o">></span> <span class="n">crt_number</span><span class="p">:</span>
<span class="k">for</span> <span class="n">n</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="n">crt_number</span><span class="p">,</span> <span class="n">next_multiple</span><span class="p">[</span><span class="mi">0</span><span class="p">]):</span>
<span class="k">yield</span> <span class="n">n</span>
<span class="n">heapq</span><span class="o">.</span><span class="n">heappush</span><span class="p">(</span><span class="n">multiples</span><span class="p">,</span> <span class="p">(</span><span class="n">n</span> <span class="o">*</span> <span class="n">n</span><span class="p">,</span> <span class="n">n</span><span class="p">))</span>
<span class="n">crt_number</span> <span class="o">=</span> <span class="n">next_multiple</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span>
<span class="k">else</span><span class="p">:</span>
<span class="c"># otherwise, the current number is not a prime, and we'll pop it</span>
<span class="c"># from the queue, and add the next multiple to the queue</span>
<span class="k">while</span> <span class="n">next_multiple</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span> <span class="o">==</span> <span class="n">crt_number</span><span class="p">:</span>
<span class="n">heapq</span><span class="o">.</span><span class="n">heappop</span><span class="p">(</span><span class="n">multiples</span><span class="p">)</span>
<span class="n">heapq</span><span class="o">.</span><span class="n">heappush</span><span class="p">(</span><span class="n">multiples</span><span class="p">,</span> <span class="p">(</span><span class="n">next_multiple</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span> <span class="o">+</span> <span class="n">next_multiple</span><span class="p">[</span><span class="mi">1</span><span class="p">],</span> <span class="n">next_multiple</span><span class="p">[</span><span class="mi">1</span><span class="p">]))</span>
<span class="n">next_multiple</span> <span class="o">=</span> <span class="n">multiples</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span>
<span class="n">crt_number</span> <span class="o">+=</span> <span class="mi">1</span></pre>
<p>Now you see why it's so easy to fall for the "unfaithful" sieve. This version is much more verbose and contrived, but it has a plus - <em>it's not a different algorithm</em>.</p>
<p>And, yeah, it has another plus - it's much faster than the first.</p>
<p>I printed the first 100 000 primes using both algorithms running:</p>
<p><code>/usr/bin/time -v python3 sieve.py > out</code></p>
<p>Granted this is not the most reliable way of carrying out a micro benchmark, you can check out <a href="https://github.com/radustoenescu/zombie-dev/blob/master/my-100days/sieve.py">the code</a> - which is in the usual place - and test them yourselves, perhaps using a more exact tool such as <a href="https://docs.python.org/3/library/timeit.html">timeit</a>.</p>
<p>The difference was huge: 10 minutes vs. 3 seconds. The memory consumption was also halved.</p>
<p>It took me 6 minutes to code the thing and 5 minutes to test and fix some small problems. It uses one well-known optimization: the first multiple to consider for each prime is the prime squared, instead of the prime doubled(you can see why this works with a pen and paper by stepping through the unoptimized version of the algorithm a couple of times, or by checking Wikipedia). You can do better, for instance avoiding even numbers since they are clearly not primes, and occur often, <em>maybe in the future I'll look into it a bit deeper</em>.</p>
<p>The general idea of the algorithm sits in the comments of the code, further details you can find in the <a href="https://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf">paper</a> I mentioned.</p>
<p>On rosetta code you can find <a href="https://rosettacode.org/wiki/Sieve_of_Eratosthenes#Infinite_generator">another implementation</a> of the same algorithm, which is cleaner, but marginally slower.</p>
</section>
</section>
</body>
</html>