<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Toshiya Komoda on Medium]]></title>
        <description><![CDATA[Stories by Toshiya Komoda on Medium]]></description>
        <link>https://medium.com/@toshiyakomoda?source=rss-1cb03c068521------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/2*Ki0SetxW6QSS3JWNZlvArg.jpeg</url>
            <title>Stories by Toshiya Komoda on Medium</title>
            <link>https://medium.com/@toshiyakomoda?source=rss-1cb03c068521------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Wed, 18 Nov 2026 08:17:59 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@toshiyakomoda/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Why rounding error matters even the amount of error seems to be small ?]]></title>
            <link>https://toshiyakomoda.medium.com/why-rounding-error-matters-even-the-amount-of-error-seems-to-be-small-f32d7211d6a8?source=rss-1cb03c068521------2</link>
            <guid isPermaLink="false">https://medium.com/p/f32d7211d6a8</guid>
            <dc:creator><![CDATA[Toshiya Komoda]]></dc:creator>
            <pubDate>Sun, 11 Jul 2021 05:22:45 GMT</pubDate>
            <atom:updated>2021-07-11T05:22:45.740Z</atom:updated>
            <content:encoded><![CDATA[<h3>Why rounding error matters even the amount of error seems to be small ?</h3><p>Let’s imagine we have an e-commerce system. It tracks price values and discount values for items. Example records are</p><p>{item_id: item1, price: 1000, discount: 10},<br>{item_id: item2, price: 2000, discount: 30}, …</p><p>Now, you have to update the records. We will receive new price value for specific item_id. For example,</p><p>{item_id: item1, price: 860}</p><p>is an event you have to process. Thing is we have to update discount values upon the price change while keeping the original discount percentage.</p><p>For example, we’ll update discount value from 10 to 9 for the above price updates according to calculation like (old_discount/old_price) * current_price = round ((860 / 1000 ) * 10) = round(8.6) = 9. Note that both price and discount values are integer.</p><p>Mathematical formula for the discount update is simple if we don’t have rounding.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/370/1*x3rst1qbpGzmD-kAltJXGw.jpeg" /><figcaption>Equation1: updates on discount</figcaption></figure><p>, where d_n is discount value after n time updates and p_n is the price value after n time updates.</p><p>In equation 1, the result should preserve the original discount percentage. It is shown in the following mathematical calculation.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Ysi1IIyNfIwa3h7qRTVNXw.jpeg" /></figure><p>However, in reality, we have rounding. Then, something happens here. For example, if there was price updates of 940 before updates of 860 in the previous example, the final discount value will be different than the previous calculation.</p><p>{price_0: 1000, discount_0: 10}<br>{price_1: 940, discount_1 = round((940/1000) * 10)= round(9.39) = 9}<br>{price_2: 860, discount_2 = round((860/940) * 10)= round(8.23) = 8}</p><p>In the previous calculation, where we only had one price updates of 860, the discount value was 9. But, for the above price updates history, we have 8 for the final discount value even it has the same price of 860.</p><h3>How rounding errors affect the final result</h3><p>As we saw in the previous section, rounding matters. Equation1 in the previous section has to be updated to take the rounding error into account.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/513/1*LGpMOlGMPtn2QCG2OX1HLg.jpeg" /><figcaption>Equation2: discount updates with rounding error</figcaption></figure><p>, where d^r_n is discount value after n time updates with rounding errors, and e_n is a rounding error after n time updates. Rounding error e_n is between -0.5 and 0.5 .</p><p>Interesting thing is that even each rounding error is bounded to between -0.5 and 0.5, it might have bigger effect as it is accumulated over multiple iteration. By substituting equation2 recursively, we can see this accumulation in mathematical equations.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/907/1*3NijIld6_1jvJLD38MKmZA.jpeg" /></figure><p>Here, we are seeing all the errors (with coefficients) sums up. The coefficient <em>(p_k+1 / p_k)</em> is the ratio of price changes for (k+1)-th iteration. As it sums over 1…n-1, the order of total error is O(n).</p><p>Let’s evaluate the value range of coefficients. In general, it could be arbitrary values. For example, if price get 10 times larger, errors might amplified by 10.</p><p>Sometime, we might be able to bound the amount of price change. For example if price updates never get more than 200%, the coefficients for rounding error (p_k+1 / p_k) would be always less than 2. In that case, we can have more strict evaluation for the total rounding errors.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*t7YoVzD-7qBNbST1mSFUpw.jpeg" /></figure><p>The amount of total rounding error is bounded to <em>n, </em>where <em>n</em> is the number of price updates.</p><h3>Avoid rounding errors in the schema design</h3><p>Avoiding the rounding errors is not if we can update schema of the datastore. We might want to add new field ‘discount_percentage’ to preserve the original discount percentage.</p><p>{item_id: item1, price: 1000, discount: 10, discount_percentage: 0.01 }</p><p>or can update the type of discount from integer to type with sufficient precision (e.g. BigDecimal in Java).</p><p>{item_id: item1, price:1000, discount: “10.000”}</p><p>Though this change requires clients logic to do rounding by theirselves.</p><p>In conclusion, don’t underestimate rounding errors. It should be within 0.5 at maximum for each rounding. However, it might accumulate over multiple iteration and end up arbitrary amount of difference.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=f32d7211d6a8" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[What’s the difference between]]></title>
            <link>https://toshiyakomoda.medium.com/whats-the-difference-between-6be4ec2551b6?source=rss-1cb03c068521------2</link>
            <guid isPermaLink="false">https://medium.com/p/6be4ec2551b6</guid>
            <dc:creator><![CDATA[Toshiya Komoda]]></dc:creator>
            <pubDate>Tue, 22 Jun 2021 01:18:13 GMT</pubDate>
            <atom:updated>2021-06-22T01:18:13.322Z</atom:updated>
            <content:encoded><![CDATA[<p>It’s quite common operation to convert a list into a map with particular key. For example, convert a list</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/ee89fb08ed1a178a55920695ce10b483/href">https://medium.com/media/ee89fb08ed1a178a55920695ce10b483/href</a></iframe><p>to a map</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/1e4552fc24f6a5e3be7d4e9c7c351b7d/href">https://medium.com/media/1e4552fc24f6a5e3be7d4e9c7c351b7d/href</a></iframe><p>We have 2 ways to do this in Java. One way is good-old days for-loop.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/cea2d02a02c7123af7b4cba4362386f0/href">https://medium.com/media/cea2d02a02c7123af7b4cba4362386f0/href</a></iframe><p>Alternative is to use stream() interface like</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/c269c8c034dfa3ab6443d58d6cefe133/href">https://medium.com/media/c269c8c034dfa3ab6443d58d6cefe133/href</a></iframe><p>Then, what’s the difference between the former and the latter ?</p><p>O.K. An example below illustrate the answer.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/f18b1e77a476427a16563ae4f7c99889/href">https://medium.com/media/f18b1e77a476427a16563ae4f7c99889/href</a></iframe><p>Yes, duplicate key. The former implementation of loop will override the values on the duplicated key, while the latter implementation will throw java.lang.IllegalStateException: Duplicate key exception.</p><p>There is <a href="https://stackoverflow.com/questions/20363719/java-8-listv-into-mapk-v">a related question on stackoverflow</a>. Looks like people tends to overlook the duplicate key case (sorry, that’s me honestly.). I feel like this is another benefit to use stream() interface as it reminds us of these corner cases.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=6be4ec2551b6" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Environmental Variables Injection with Guice]]></title>
            <link>https://toshiyakomoda.medium.com/environmental-variables-injection-with-guice-bd594b5efbcf?source=rss-1cb03c068521------2</link>
            <guid isPermaLink="false">https://medium.com/p/bd594b5efbcf</guid>
            <category><![CDATA[programming]]></category>
            <dc:creator><![CDATA[Toshiya Komoda]]></dc:creator>
            <pubDate>Wed, 21 Apr 2021 02:59:57 GMT</pubDate>
            <atom:updated>2021-04-21T02:59:57.479Z</atom:updated>
            <content:encoded><![CDATA[<p>Loading environmental values into class is almost always necessary for commercial applications, e.g. loading stage configuration of delivery pipeline. With DI library such as Guice, loading environmental variables can be hidden inside the module class.</p><p>Let’s see the simplest example. We have 2 classes both of which just load the environmental values and return the message string with it. There are slight difference in how they load the value.</p><ul><li>ClassWithEnv: Loading environmental variables directly with System.getenv()</li><li>ClassWithInjectedEnv: Using Guice to load the value of the environmental variables.</li></ul><p>Code snippet.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/46baab784333a61465b7e81feff2eb73/href">https://medium.com/media/46baab784333a61465b7e81feff2eb73/href</a></iframe><p>Which implementation is better ? I think most people agree that using System.getenv() directly in the logic class is not preferable because an environmental variable is essentially a global variable. With the help of DI library, we can encapsulate environmental variables inside the module class and use it through normal dependency injection, which makes codes more modular and unit testable.</p><p>This pattern is simple but quite strong. For example, you might want to add configuration files in your repository and read them according to the environmental variables. This configuration loading logic can be also placed in the module class. This way, you can avoid polluting your business logic with environment specific constants.</p><p>To eliminate the use of “string” and enjoy the benefit of type system, you can use <a href="https://github.com/google/guice/wiki/BindingAnnotations">BindingAnnotation</a></p><p>The version with bindingAnnotation is shown below. Only added/changed classes are shown.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/a94cf44bb9110bbf9f06ec6e9157fc2a/href">https://medium.com/media/a94cf44bb9110bbf9f06ec6e9157fc2a/href</a></iframe><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=bd594b5efbcf" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Test Data Management Strategy]]></title>
            <link>https://toshiyakomoda.medium.com/test-data-management-strategy-4d5aa4a081a7?source=rss-1cb03c068521------2</link>
            <guid isPermaLink="false">https://medium.com/p/4d5aa4a081a7</guid>
            <dc:creator><![CDATA[Toshiya Komoda]]></dc:creator>
            <pubDate>Thu, 18 Feb 2021 13:46:00 GMT</pubDate>
            <atom:updated>2021-02-18T13:46:00.821Z</atom:updated>
            <content:encoded><![CDATA[<p>How do you manage test data in your unit tests or automated API tests ?<br> <br> If you tests API with large input data, for example JSON, it eventually gets harder to manage test data as you add more test cases. Imagine, what happens when you have 1000+ test cases !<br> <br> I think we have 2 common strategies for the test data management.</p><ol><li><strong>Not share test data across test cases</strong>. It’s pretty simple strategy. Each test case has full set of test data independently. They may be managed in the separated files. Advantage of this approach is that there is a clear separation. So, adding new test case is pretty easy and it never get complicated even though you’ll have 1000+ test cases. However, drawback of this approach is also clear. There will be a loooooot of copy and paste. What happens if the API interface changs ? It is hard to add/change field values for all the test cases.</li><li><strong>Share the test data across test cases.</strong> To avoid the problem of copy and paste, you might think of re-using the test data. You prepare default test data, and each test case will override some of the field in the default. It should be easy to update the default data when API interface changes. Also, you can easily understand what the purpose of each test case by looking overridden values. Drawback of this approach is that when you need completely different data than default. You may end up to add another default dataset. Managing multiple default data and override hierarchy would be tedious.</li></ol><p>Basically, I can’t say which is better. It depends. If variation of your test data is small, then “Share the test data” is better because you don’t need to have more than a couple of default data and override hierarchy won’t be complex. On the other hand, if you need more diverse set of test data, “Not share test data” will be more suitable.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=4d5aa4a081a7" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Building Algorithm to Compute Strongly Connected Components (SCC) From Scratch]]></title>
            <link>https://medium.com/swlh/building-algorithm-to-decompose-strongly-connected-components-scc-from-scratch-c411d8b34777?source=rss-1cb03c068521------2</link>
            <guid isPermaLink="false">https://medium.com/p/c411d8b34777</guid>
            <category><![CDATA[computer-science]]></category>
            <category><![CDATA[algorithms]]></category>
            <dc:creator><![CDATA[Toshiya Komoda]]></dc:creator>
            <pubDate>Thu, 28 Jan 2021 12:24:36 GMT</pubDate>
            <atom:updated>2021-02-03T06:54:30.854Z</atom:updated>
            <content:encoded><![CDATA[<h3><strong>Preface</strong></h3><p>When I learned algorithms for strongly connected components (SCC) in the university, like <a href="https://en.wikipedia.org/wiki/Kosaraju%27s_algorithm">Kosaraju’s algorithm</a> or <a href="https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm">Tarjan’s</a>, I could see it works well but had no idea where these come from. I mean these algorithms are so elegant and seems magically come from some genius. Indeed, theoretical basis of computer science today was developed by small number of highly talented people in 1970’s and 80&#39;s. I remember that I felt like I would never be able to come up these noble algorithms.</p><p>Time has passed and now I’m curious about computer science fundamental again. In this article, I try to derive my own algorithm for SCC decomposition from scratch, assuming I forget about Kosaraju’s or Tarjan’s. Though my algorithms were stupid and were not efficient, building algorithm from scratch by myself gave me much deeper insight (and fun!). So, I’d like to share it in this article.</p><h3>Mathematical Definitions of SCC</h3><p>Before all, I need formal definition of strongly connected components (SCC). Let’s take the following graph as an example.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/400/1*LuwTnPCjlKFVYNnnzvSATQ.png" /><figcaption>Figure1. Directed Graph</figcaption></figure><p>In the example graph, there are 9 nodes = {A1, A2, A3, A4, A5, A6, A7, A8, A9} and 12 edges = {(A1, A2), (A1, A5), (A2, A4), (A3, A2), (A4, A3), (A5, A6), (A5, A9), (A6, A7), (A7, A5), (A7, A8), (A9, A10), (A10, A1)}.</p><p>SCC is groups of nodes where nodes in the same group are strongly connected. But, what does “strongly connected” mean? We need some mathematical definition.</p><p><strong>Path</strong>: a chain of edges where each edge starts from the end nodes of previous edge. <br>Example [(A1, A5), (A5, A6), (A6, A7)] is a path from A1 to A6, and A1 is the start node and A7 is the end node of the path. For convenience, we can abbreviate the duplication in the path expression like path(A1, A5, A6, A7).</p><p><strong>Strong Connectivity definition 1: </strong>node1 and node2 are strongly connected, if and only if there is a path from A to B and there is a path from B to A. <br>Example, A1 and A7 is strongly connected as there are path(A1, A5, A6, A7) and path(A7, A5, A9, A10, A1).</p><p>Following definition of the strong connectivity, the example graph is decomposed into 3 components like the below figure.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/400/1*gw-bOV0sg03-M9eonepnOQ.png" /><figcaption>Figure2. strongly connected components</figcaption></figure><p>Alternatively, we can define mathematically equivalent definition of connected nodes with the concept of loop.</p><p><strong>Loop</strong>: a path in which the start node and the end node is identical. <br>Example [(A5, A6), (A6, A7), (A7, A5)] is a loop. As same as path, we can abbreviate the duplication in the expression like loop(A5, A6, A7).</p><p><strong>Strong Connectivity definition 2</strong>: node1 and node2 are connected if and only if there is a loop which includes node1 and node2. <br>Example, A5 and A7 is connected as there is a loop(A5, A6, A7).</p><p>Let me construct algorithms from these 2 definitions of strong connectivity in the following section.</p><h3>Algorithm from definition1: brute force</h3><p><strong>Strong Connectivity definition1: </strong>node1 and node2 are connected, if and only if there is a path from A to B and there is a path from B to A.</p><p>Direct implementation of this definition is straight forward, just simply iterating over all the pair of nodes should be enough.</p><p>Python code below is doing this, in which the input is given with <a href="https://en.wikipedia.org/wiki/DOT_(graph_description_language)">dot</a> format and the output is also in dot with color annotation (nodes in same components are with same colors).</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/4a671c07bdc49d90abf362555d953346/href">https://medium.com/media/4a671c07bdc49d90abf362555d953346/href</a></iframe><p>This implementation is able to correctly compute a given directed graph into SCC. However, obvious problem of this solution is its time complexity. It requires N² times depth first search (DFS) and ended up to O(N³) as a whole, where N is the number of nodes.</p><h3>Algorithm from definition2: Ad hoc loop finding</h3><p><strong>Strong Connectivity definition2</strong>: node1 and node2 are connected if and only if there is a loop which includes node1 and node2.</p><p>Next, let me start with SCC definition2 which uses the concept of loop. Though this definition is mathematically equivalent to the definition1, it’s statement looks different and it’s not as easy as the previous one for implementation. One thing we need to consider is that how to find loops. Also, there is no guarantee that there is 1 to 1 relationships between SCC and the associated loop.</p><p>Fortunately, characteristics of DFS is well studied: Ref: <a href="https://www2.cs.duke.edu/courses/fall17/compsci330/lecture12note.pdf">Lecture note from Duke Univ</a>. We can use DFS to find loops in directed graph. In a nutshell, finding back edge is almost equivalent to finding a loop which defines each SCC. The steps will be look like</p><ol><li>find back edges (u, v) during DFS, which indicates there is a loop starting v. Let’s call it as root node of the loop.</li><li>backtrack the root node of the loop during DFS to find all the member in the loop discovered in step1.</li></ol><p>As member nodes in a loop are in the same SCC, result of step2 will have enough information for SCC decomposition. Though I need to explain subtle details, I’ll give the python code at first.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/8ed21df4e562a90965a056df29efb9d6/href">https://medium.com/media/8ed21df4e562a90965a056df29efb9d6/href</a></iframe><p>Apparently, the implementation is much more complicated than the previous brute force one. This complexity comes from subtle difference on how to handle different types of edges, tree, forward/cross, and back edges during DFS.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/240/1*-cN6wdohSwvXqGU-ZyMYoA.png" /><figcaption>Figure3. Propagation of back edge information for tree edges</figcaption></figure><p>For tree edges, we need to propagate the back edge information from the next node, who has just been visit-completed. In the Figure3, DFS might visit nodes in the order of A1, A2, A3, A4 then find a back edge (A4, A2). Upon the detection of the back edge, it stores A2 to A4.root_node_label. The root_node_label propagates to A3 and A2 as DFS is back tracing. When A2 visiting completes, all of A2, A3, A4 has A2 in their root_node_label. However, it won’t propagate to A1 as A2 is not an ancestor of A1. This control on when we stop the propagation is needed at tree edges.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/216/1*Ok3g1SGqyezpPpjGqRWRRQ.png" /><figcaption>Figure4. Case for Cross Edge</figcaption></figure><p>Figure4 is to show how back edge information propagates for cross edges. In the above graph, DFS might visit nodes in the order of A1, A2, A3, A6, A4 , A5, and then it finds a back edge (A5, A1). The back edge information propagates to A5, A4, A6, A3, A2 as DFS traversal back tracing to A2. At A2, it will visit A7, which is the next neighbor nodes of A2. At A7, it will find a cross edge (A7, A4). Note that cross edge is not traversed, but we need to pass the back edge information A1 from A4 to A7 as A1 is A7’s ancestor. It means that we store A1 to A7’s root_node_label. Note that we need to check if A1 is really an ancestor of A7. Same applies for forward edges.</p><p>At the end of the DFS traversal, each node should have one root_node_label. There are three types of nodes.</p><ul><li>For loop root node (destination of back edge), it has its own label for root_node_label.</li><li>For nodes which consist single node SCC, it has its own label for root_node_label as well.</li><li>For other nodes, it has one of its ancestor’s label for root_node_label.</li></ul><p>It is important to recall that nodes with same root_node_label are in the same SCC. So, it collects root_node_label from each node and make a hash table whose key is the root node and the value is a list of member nodes in the loop.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/265/1*QBVw3qfus1Jsvv6WCZyBCQ.png" /><figcaption>Figure5. Post process of root_node_labels.</figcaption></figure><p>Tricky part is line 136–156. For example, for Figure5, we might get following 2 loops before the post processing if the DFS visiting order is A1, A2, A3, A4, A5, A6.</p><p>{“A1” : set(A6, A5, A2, A1), “A2”: set(A4, A3)}</p><p>Note that the key of the hash is root nodes. As the graph in Figure5 is fully strongly connected graph, we should get one loop {“A1”: set(A6, A5, A2, A1, A4, A3)} if we correctly decompose it into SCC.</p><p>There are 2 back edges (A4, A2) and (A6, A1) in the graph. If (A4, A2) is found before (A6, A1), it stores A2 to A4, A3 and A2’s root_node_label. After (A6, A1) back edge found, it eventually updates A2’s root_node_label to A1 but A3 and A4’s root_node_label remains A2 because the visiting of A3 and A4 has been already completed when the back edge (A6, A1) is found. This is why we saw 2 components without the post processing at line 136–156.</p><p>To mitigate these out-dated labels, we can merge loops who don’t include its root node to the loop who contains the root node.</p><p>It’s been a bit long way but we finally come up with our second algorithm for SCC computation.</p><p>Regarding time complexity, we need only one DFS traversal.That’s good comparing it to N² time traversal in the brute force. However, we need additional computational cost for the post processing of loop merge and it makes the worst case time complexity worse. Merging loops in the post processing takes O(L² * N) at worst case where L is the number of loops detected (= number of back edges found in DFS traversal) and N is the number of nodes. The number of back edges can have O(V) where V is the number of edges, which can be O(N²). So, theoretically, worst case time complexity of second algorithm is worse than brute force, unfortunately.</p><p>However, for graphs who have small number of back edges and if we can consider it as constant, the second algorithm works faster than brute force as we only need DFS traversal once.</p><h3>Back to Tarjan’s Algorithm</h3><p>At the last section, I’d like to re-visit <a href="https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm">Tarjan’s</a> algorithm in order to understand again how noble it is. The next python code is one implementation of Tarjan’s algorithm.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/3867fe0406b2fbccdd5f244ecd81a155/href">https://medium.com/media/3867fe0406b2fbccdd5f244ecd81a155/href</a></iframe><p>Interesting thing I noticed after I came up with my inefficient algorithms is that, in Trajan’s algorithm, lowlink variable plays a role to track the root node of back edges. So, the core idea seems same. Of course, Tarjan’s algorithm has much more sophisticated logic and data structure and better time complexity. Actually, I finally understand that it does quite well in implementing backtracking of back edges, which magically avoid the issues I encountered in my second algorithm.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=c411d8b34777" width="1" height="1" alt=""><hr><p><a href="https://medium.com/swlh/building-algorithm-to-decompose-strongly-connected-components-scc-from-scratch-c411d8b34777">Building Algorithm to Compute Strongly Connected Components (SCC) From Scratch</a> was originally published in <a href="https://medium.com/swlh">The Startup</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[What does surge of software engineer’s salary actually means ?]]></title>
            <link>https://toshiyakomoda.medium.com/what-does-surge-of-software-engineers-salary-actually-means-a11b3a948ed4?source=rss-1cb03c068521------2</link>
            <guid isPermaLink="false">https://medium.com/p/a11b3a948ed4</guid>
            <category><![CDATA[software-development]]></category>
            <dc:creator><![CDATA[Toshiya Komoda]]></dc:creator>
            <pubDate>Thu, 21 Jan 2021 13:55:11 GMT</pubDate>
            <atom:updated>2021-02-19T00:27:07.553Z</atom:updated>
            <content:encoded><![CDATA[<h3>What does surge of software engineer’s salary actually means ?</h3><p>Recently, in my friend community slack, we discussed how much average salaries of software engineers in Japan have been raised in a recent few years. One of my friend, who owns his startup company says that his company has seen sudden increase in hiring cost these 2 years because the average salaries for software engineers has surged.</p><p>The conversation reminds me that, as a software engineer, I feel strong demands on new technology to dramatically increase the engineer productivity. I mean the surge in engineer’s salary indicates that software engineering is requiring specialized skill or real world experiences more and more. In other words, modern systems are much more complicated than the systems developed in old days. It seems very temporary solution to pay more salary to engineers and encourage them to work harder, study harder. This strategy will reach the limitation soon as there is limit of human ability.</p><p>Rather, we should invest same money for new technology to help people develop/manage the software system instead of just paying higher salary to engineers. I don’t have clear idea of how the technology looks like. It might be new programming language or framework or cloud service or something we couldn’t imagine now. But, we definitely need to invest new technology to catch up with modern system’s complexity, which might be already beyond the human intelligence.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=a11b3a948ed4" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Random thought on Distributed Transaction Management]]></title>
            <link>https://toshiyakomoda.medium.com/random-thought-on-distributed-transaction-management-b9f089151309?source=rss-1cb03c068521------2</link>
            <guid isPermaLink="false">https://medium.com/p/b9f089151309</guid>
            <dc:creator><![CDATA[Toshiya Komoda]]></dc:creator>
            <pubDate>Sat, 10 Oct 2020 13:12:25 GMT</pubDate>
            <atom:updated>2020-10-27T08:36:06.539Z</atom:updated>
            <content:encoded><![CDATA[<h3>Distributed Transaction Management : Microservices, Idempotency and Failure Handling</h3><p>Recently, I had a discussion in my team around transaction management in micro-services. It is well known that it’s hard to implement transaction in micro-services oriented architecture. In this article, I try to write down my current understanding of transaction management in micro-services architecture. I’m not doing precise technical discussion. Rather, I’m examining an idea that how to connect the several concepts around the distributed transaction management.</p><h3>Recap: Transaction</h3><p>Let’s recap what’s the transaction at first. Personally, I felt something mysterious and difficult from the term “transaction”. But, I realize tht it’s actually a pretty simple concept.</p><p>Think about a simple example of a system of virtual currency. If the customer earn or spend the virtual currency, we may need to</p><ul><li>write a record in ledger table, and</li><li>write a record in customer balance table.</li></ul><p>Important thing here is, these 2 records in 2 tables have to be in sync. I mean if you find one record for the customer earn/spend in ledger table, you should also find the corresponding record in the customer balance table. This is “transaction”. Transaction is a collection of data operations. And they are either of 1. all operations are successfully done, or 2. none of them succeeded. This characteristic of data management has another name, data consistency. From my experience, consistency management and transaction management are often used exchangeably.</p><p>For the example virtual currency system, in short, we need to avoid the following 2 situations.</p><ol><li>The record exists in ledger table but not in customer balance table</li><li>The record exists in customer balance table but not in ledger table</li></ol><p>So far, nothing is difficult, isn’t it ?</p><h3>RDB Transaction</h3><p>It starts to get complicated when you need to consider failure handling. Yes, computer system, especially I/O, might fail. So, if one of the writes to ledger or customer balance table fails, then there will be inconsistency. This is a problem.</p><p>In traditional Relational Database (RDB), this kind of failure is handled by so-called “transaction”. Yes, I understand the terminology is confusing here. “Transaction” here is the name of functionality provided by RDB instead of the concept of transaction, which I explained in the previous section.</p><p>As yo know, “RDB transaction” works like this. For success case,</p><ol><li>start “transaction”</li><li>write a record to the ledger table</li><li>write a record to the customer balance table</li><li>end “transaction”.</li></ol><p>for failure case,</p><ol><li>start “transaction”</li><li>write a record to the ledger table</li><li>write a record to the customer balance table but it fails!</li><li>rollback. It means the write to the ledger table in step2 is canceled.</li></ol><p>That’s it. It’s still simple and good. Now, we can avoid the inconsistency in the ledger and customer balance tables even in the world where we could fail to write records.</p><h3>Transaction Management in micro-services: Saga</h3><p>The limitation of “RDB transaction” is that we can’t use the nice functionality among multiple databases. And in the micro-services architecture, each database is typically hidden by independent service. So, there is no hope we can make use of good old days “RDB transaction” in order to avoid data inconsistency.</p><p>Let’s say we have 2 different services (or APIs), ledger service and customer balance service instead of 2 tables in single database. Now, we need to call these 2 services through network in order to create a ledger record and customer balance record for the virtual currency management.</p><p>What should I do for the failure handling to avoid the inconsistency without the nice “RDB transaction” ?</p><p>Wait, I already explained what “RDB transaction” is doing when writes fail. We can do the exactly same thing with remote service calls, can’t we ? I mean if one of your service calls fails then cancel all the related service calls. Like this.</p><ol><li>start “transaction”. In micro-services, it is doing nothing.</li><li>call create API of the ledger service</li><li>call create API of the customer balance table but it fails!</li><li>rollback starts. call cancel API of the ledger service to delete record created in step2</li></ol><p>This means that, both the ledger service and the customer balance service need to support cancel (or delete) API in addition to create API. Implementing cancel API might need some effort but it should be not very complicated.</p><p>Although you need to implement a certain amount of extra logic compared to RDB world, the logic is still not complicated. If you detect the API failures, then just cancel the related calls. That’s it.</p><p>This cancel on failure pattern has name of <a href="https://microservices.io/patterns/data/saga.html">“Saga”</a> in the context of micro-services. But, I think it is a straight forward alternative of rollback operation in “RDB transaction”.</p><h3>Further Thinking: What happens if the cancel fails in Saga ?</h3><p>O.K. Now, we have a way to manage transaction in micro-services. That’s good. However, in practice, you have to answer the following question.</p><p>“What happens if the cancel API somehow fails during rollback ?”.</p><p>It is annoying because it’s a recursive question. O.K. we could retry the cancel API when it fails but that retry could also fail. and that retry on the retry could fail again. and fail again and … never ending.</p><p>Here the concept of idempotence comes. I think you’ve already heard a word <a href="https://www.restapitutorial.com/lessons/idempotency.html">idempotence </a>at least once. If the API is idempotent, multiple identical requests has the same effect as making a single request. What does it mean in the context of our virtual currency system?</p><p>Let’s get back to the examples before. for failure case,</p><ol><li>start “transaction”. In micro-services, it is doing nothing.</li><li>call create API of the ledger service</li><li>call create API of the customer balance table but it fails!</li><li>rollback starts. call cancel API of the ledger service to delete record created in step2. <strong>But, the cancel somehow fails so the record in the ledger service remains</strong></li></ol><p>This is the case at stake. After this happens, we have data inconsistency among the 2 tables, the ledger has record but the customer balance doesn’t.</p><p>What happens if we retry the whole operation ?</p><ol><li>start “transaction”. In micro-services, it is doing nothing.</li><li>call create API of the ledger service. <strong>Remember, the API is idempotent now. So, the record in the ledger service doesn’t change at all.</strong></li><li>call create API of the customer balance service. <strong>Wow, it succeeds this time.</strong></li><li>end transaction.</li></ol><p>This is lucky case. Previous failure in the customer balance service was just a temporal failure so the retry works. Important thing here is that we can call the ledger create API multiple times safely without thinking anything because it’s idempotent.</p><p>Oh, wait but what happens if the write to the customer balance table never succeeded ? This can definitely happen in production systems, for example when the input data is invalid and the validation on the customer balance service always fails.</p><p>Let’s simulate this case. This is a bit confusing scenario. Remember that in the first, the customer balance creation failed and the cancel on the ledger also failed.</p><ol><li>start “transaction”. In micro-services, it is doing nothing.</li><li>call create API of the ledger service. <strong>Remember, the API is idempotenct now. So, the record in the ledger service doesn’t change at all.</strong></li><li>call create API of the customer balance service. It fails again due to the invalid data.</li><li>rollback starts. call cancel API of the ledger service to delete record created in step2. <strong>It could fail again or it could succeed.</strong></li></ol><p>Now, we reach the most interesting part of this article. Yes, you are right. The rollback in the second retry might fail. But, it should success with the finite number of retries.</p><p>What do I mean by the finite number of retries ? To explain it, I have to categorize the failure into 2 different classes.</p><ul><li>Retryable Failure: This is typically caused by the server down or network failure. So, after the system get recovered, the request should succeed on retry.</li><li>Unretryable Failure: This is typically caused by invalid data. Because the data is invalid, the service intentionally fails the request. To mitigate this, you need to change the contents of the request so that simple retry of the identical request never succeed.</li></ul><p>I think you already understand. Yes, we have a secret tip when we build our logic with Saga pattern. That is</p><ul><li>Cancel API shouldn’t fail with Unretryable failure.</li></ul><p>Creation APIs can fail with Unretryable failure. But, cancel can’t.</p><h3>Further Further Thinking: What happens if all the failures are retryable ?</h3><p>Last thinking I would like to share is this above question. In other words, if all the creation API never fail with unretryable failure as same to the cancel API, do we still need rollback steps in Saga?</p><p>Given the creation API is idempotent, we don’t need rollback step at all. We can just retry all the steps until all the creation API succeed. The nice thing of this is that we no longer need the cancel APIs. Isn’t it nice ?</p><p>So, the transaction management in micro-services would be much simpler if you can make sure that</p><ul><li>all the creation APIs are idempotent</li><li>all the failures from the creation APIs are retryable</li></ul><p>How can we satisfy the second condition ? The answer is if there is no invalid data in the creation API calls. In other words, if you can validate your request data perfectly in the client of the creation API, we can avoid to call the creation API with invalid data.</p><p>But, you know this is kind of tautology. How can we validate the data perfectly without calling the creation API ? Is it almost identical to have the identical logic inside the creation API ? Is that even possible in the practical situation where the logic is always changing ?</p><p>This issue can be addressed if the creation API provides trial API which test if the contents in the request can be successfully processed or not. The name might be dry-run API or validation API or whatever.</p><p>Very interesting. We now bump into the basic idea of <a href="https://en.wikipedia.org/wiki/Two-phase_commit_protocol">2-phase commit</a>, which is famous protocol to implement distributed transaction management. In the first step of 2 phase commit, the participants make sure that there should be no failure happens from invalid data. Then, if we can make sure that all the participant can create the record successfully, the coordinator instructs all the participants to create the record.</p><p>The whole process for our virtual currency management will be like this.</p><p>For success case,</p><ol><li>start “transaction”. In micro-services, it is doing nothing.</li><li>call trial API of the ledger service. O.K. it succeeded.</li><li>call trail API of the customer balance service. O.K. it succeeded</li><li>call create API of the ledger service. It should succeed at least with multiple number of retries.</li><li>call create API of the customer balance service. It should succeed at least with multiple number of retries.</li><li>No rollback step needed.</li></ol><p>Failure should be caught in the trial step.</p><ol><li>start “transaction”. In micro-services, it is doing nothing.</li><li>call trial API of the ledger service. O.K. it succeeded.</li><li>call trail API of the customer balance service. Sad, it failed.</li><li>No rollback step needed because we didn’t create anything yet.</li></ol><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=b9f089151309" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Matrix Multiplication]]></title>
            <link>https://toshiyakomoda.medium.com/matrix-multiplication-fc1c1a697060?source=rss-1cb03c068521------2</link>
            <guid isPermaLink="false">https://medium.com/p/fc1c1a697060</guid>
            <dc:creator><![CDATA[Toshiya Komoda]]></dc:creator>
            <pubDate>Tue, 05 May 2020 04:07:30 GMT</pubDate>
            <atom:updated>2021-02-19T02:45:33.203Z</atom:updated>
            <content:encoded><![CDATA[<h3>Inverse Matrix Calculation with elementary matrix</h3><p>Just for fun for holidays, I took a look at a linear algebra text book which I used in my university and wrote python code to calculate inverse matrix. I was interested that elementary operations of matrix can be represented by matrix itself. So, I wrote calculation algorithm by using multiplication chain of elementary matrix. I know the implementation has very bad performance (Yes, it’s O(N⁵). surprisingly bad) than <a href="https://en.wikipedia.org/wiki/Gaussian_elimination#Finding_the_inverse_of_a_matrix">gaussian elimination</a> (O(N³)). However, it’s still useful to see elementary matrix based implementation actually works as it is easier to understand the concept of inverse matrix and its calculation methodology.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/5e5bfa53a566749c0813c33e532a7c57/href">https://medium.com/media/5e5bfa53a566749c0813c33e532a7c57/href</a></iframe><p>Examples of Calculated Inverse Matrix</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/3b6de637e63f312c38e88ec3ad3b8507/href">https://medium.com/media/3b6de637e63f312c38e88ec3ad3b8507/href</a></iframe><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=fc1c1a697060" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Guice AssistedInject]]></title>
            <link>https://toshiyakomoda.medium.com/guice-assistedinject-f49b29105651?source=rss-1cb03c068521------2</link>
            <guid isPermaLink="false">https://medium.com/p/f49b29105651</guid>
            <category><![CDATA[dependency-injection]]></category>
            <dc:creator><![CDATA[Toshiya Komoda]]></dc:creator>
            <pubDate>Sun, 17 Nov 2019 11:15:05 GMT</pubDate>
            <atom:updated>2019-11-17T11:23:17.329Z</atom:updated>
            <content:encoded><![CDATA[<h3>Dependency Injection</h3><p>Dependency Injection is a powerful design pattern when you write your systems in object oriented(OO) way. In OO, your system would be divided into a lot of objects which is responsible for small functionality. It allows you to write simple logics and unit tests. However, we have to manage a lot of objects. Those objects might have multiple, nested, and complicated dependency chains. You can do these objects dependency management with plain Java, of course. But, it is getting very painful when the number of objects is getting large. Here, we want more structural way to manage objects dependency. This is where Dependency Injection (DI) and DI library comes.</p><p><a href="https://github.com/google/guice">Guice</a> is one of the most popular DI libraries in Java. A simple example is shown below.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/55bb31a5f0f75d52fd894b518eaa427d/href">https://medium.com/media/55bb31a5f0f75d52fd894b518eaa427d/href</a></iframe><h3>AssistedInject</h3><p>In more complex case, you may want to write a class whose constructor receives</p><ol><li>dynamic instances, which is only known at runtime</li><li>static instances, which can be injected by DI library</li></ol><p>In this case, we can use <a href="https://google.github.io/guice/api-docs/latest/javadoc/index.html?com/google/inject/assistedinject/FactoryModuleBuilder.html">FactoryModuleBuilder</a>. FactoryModuleBuilder will auto-generate Factory class which creates the class whose dependencies have both dynamic and static. A simple example code is shown in the example.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/d8e8c240c10099f2d93b59b61827f72d/href">https://medium.com/media/d8e8c240c10099f2d93b59b61827f72d/href</a></iframe><p>This is kind of a mix of Factory and Dependency Injection. It is officially called <em>AssistedInject</em>. You can find more in <a href="https://github.com/google/guice/wiki/AssistedInject">official Guice document</a>.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=f49b29105651" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[learning central limit theorem]]></title>
            <link>https://toshiyakomoda.medium.com/learning-central-limit-theorem-606dcbf02688?source=rss-1cb03c068521------2</link>
            <guid isPermaLink="false">https://medium.com/p/606dcbf02688</guid>
            <category><![CDATA[statistics]]></category>
            <category><![CDATA[software-development]]></category>
            <dc:creator><![CDATA[Toshiya Komoda]]></dc:creator>
            <pubDate>Mon, 14 Oct 2019 12:16:27 GMT</pubDate>
            <atom:updated>2019-10-14T12:16:27.538Z</atom:updated>
            <content:encoded><![CDATA[<p>Today, A/B tests have become a fundamental tool to evaluate your idea in software improvement. It’s not very difficult to run A/B test on your idea. The problem is that cost is not cheap. I mean that we need real user’s activities and the amount of real user activities are always limited.</p><p>Back to the basics, why we have to collect a certain amount of data to evaluate our to see the hypothesis is correct. For example, does our new feature improve the percentage of customers who buy something on our site by at least 1%. How many samples of A and B are actually needed? We know real user data is very limited. The Less data we need, we would be happier.</p><p>Traditional statistical theory answers this question. You may have heard “central limit theorem”. Honestly, I’m not familiar with statistical theory. According to wikipedia,</p><pre>In <a href="https://en.wikipedia.org/wiki/Probability_theory">probability theory</a>, the <strong>central limit theorem</strong> (<strong>CLT</strong>) establishes that, in some situations, when <a href="https://en.wikipedia.org/wiki/Statistical_independence">independent random variables</a> are added, their properly normalized sum tends toward a <a href="https://en.wikipedia.org/wiki/Normal_distribution">normal distribution</a> (informally a &quot;<em>bell curve</em>&quot;) even if the original variables themselves are not normally distributed</pre><p>Very roughly, it says we can trust the average value observed in A/B tests if we collect enough size of user activity samples. With large samples, we can give the size of maximum errors in our observation by using theory about normal distribution.</p><p>To understand intuitively what the theorem is saying, I wrote a simple python script to draw the probabilistic distributions which comes out from the average of samples from uniform distribution.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/96f411bc99b7416a1ab10002834afaf5/href">https://medium.com/media/96f411bc99b7416a1ab10002834afaf5/href</a></iframe><p>In the following video, we can see that the probabilistic distribution of average value of uniform distribution is converging into normal distribution as the sample size is increasing. (sample sizes are 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024).</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fwww.youtube.com%2Fembed%2FFQd7qiCjoqQ%3Ffeature%3Doembed&amp;url=https%3A%2F%2Fwww.youtube.com%2Fwatch%3Fv%3DFQd7qiCjoqQ&amp;image=https%3A%2F%2Fi.ytimg.com%2Fvi%2FFQd7qiCjoqQ%2Fhqdefault.jpg&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=youtube" width="640" height="480" frameborder="0" scrolling="no"><a href="https://medium.com/media/0a887f3b5c13f35e9a49d988b5af3915/href">https://medium.com/media/0a887f3b5c13f35e9a49d988b5af3915/href</a></iframe><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=606dcbf02688" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>