Miscellaneous Matchers for Arrays & Strings

Click here for Part 1

Click here for Part 2

In this series of blogs, we will be going through some of RSpec’s most useful built-in matchers for writing assertions in examples. RSpec is known for its beautiful english-like syntax and matchers are no exception. Whether you’re completely new to testing in Ruby or a unit testing veteran, this guide aims to be a comprehensive introduction/review on some of the most common built-in matchers available to the RSpec library.

In the first two parts of this guide, we looked at some of the most often-used families of RSpec matchers, ranging…


Predicate, All, & Be Matchers

Click here for Part 1

Click here for Part 3

In this series of blogs, we will be going through some of RSpec’s most useful built-in matchers for writing assertions in examples. RSpec is known for its beautiful english-like syntax and matchers are no exception. Whether you’re completely new to testing in Ruby or a unit testing veteran, this guide aims to be a comprehensive introduction/review on some of the most common built-in matchers available to the RSpec library.

Continuing on from Part 1, we will be focusing on three built-in matchers that are based around boolean values and concepts…


Equality & Comparison Matchers

Click here for Part 2

Click here for Part 3

In this series of blogs, we will be going through some of RSpec’s most useful built-in matchers for writing assertions in examples. RSpec is known for its beautiful english-like syntax and matchers are no exception. Whether you’re completely new to testing in Ruby or a unit testing veteran, this guide aims to be a comprehensive introduction/review on some of the most common built-in matchers available to the RSpec library.

In this first part, we will be taking a look at two of the most commonly-used families of matchers: equality and…


Using the let Keyword in Example Groups

RSpec is a popular testing library that has the distinction of being the most popular Ruby gem with over 200 million downloads. It is fantastic for behavior-driven development (BDD) and allows us to improve the quality of our code while acting as living documentation for the codebase. When used correctly, developers who are new to a codebase should be able to learn everything they need to know about the functionality of the program by reading the files inside thespecfolder.

I love RSpec for its beautiful english-like syntax and how it’s designed to test classes and methods in a specific domain…


Understanding the most important method in the React Hooks system

If you have experience with using class components in React, you are probably familiar with the React component lifecycle. Before hooks were introduced to their functional counterparts, lifecycle methods were the only way to mount, update, and unmount components in an application using class components.

With the addition of the useEffect method from the hooks system, we now have an alternative to traditional methods such as componentDidMount, componentWillUnmount, as so on.

image from robert-laws.com

Why Lifecycle Methods?

Remember, the only required method inside a React class component is render(). Apart from that, any lifecycle methods we use are optional. …


Utilizing State and Lifecycle Methods

After spending more than half a year studying the intricacies and weirder parts of vanilla Javascript, making the transition over to React felt monumental. In some ways, it was like the moment my Magikarp finally evolved into a Gyarados as a kid playing Pokemon. In others, it was like reading “The Life-changing Magic of Tidying Up” by Marie Kondo and finally tackling the mess in my room (or code) using logical, pre-established methods and implementing them.

In Marie Kondo’s book, she explains that you should tidy your home by category, not location. This means that instead of cleaning out the…


When I first learned how to make requests to a server using the fetch API, my first reaction was that the code felt clunky. In order to complete a request-response cycle, the .json() method is required after the initial call. Moreover, depending on the type of request you are sending, you may be required to attach additional headers and other attributes in order to return correctly-formatted data.

While fetch is a perfectly acceptable method to use, the reason I immediately switched to Axios.js was primarily because of how clean and efficient it made my code look. I no longer need…


Utilizing the Call Stack in Javascript

In my last post, I introduced the basic concept behind Big O notation and how we use it to analyze the efficiency of our functions. We talked through the differences between calculating time complexity and space complexity as well as gaining an understanding that Big O is generally a practice in measuring general trends rather than precise calculations.

To recap a single idea from Big O, one of the most common ways we work with sets of data, whether it be a string or array, is through iteration. This can occur in the form of while loops, for statements, or…


アルゴリズムの効率を計る方法(日本語と英語で)

Click here for the English version.

プログラミングの基本を勉強していた26歳の私が、初めてコンピューターサイエンスの「アルゴリズム」を聞いたときに、肝を潰しました。毎日夕方になると、パソコンを閉じながら、「もっと高校の数学に集中すべきだった」、「父さんの会社の技師たちがアルゴリズムに苦労しているから、僕なんて無理だ」などとくよくよしました。

私のようなプログラミングの初心者たちは、「オーダー記法」や「時間計算量・空間計算量」のような言葉を聞けば、恐ろしく感じ、自信喪失する方が多いかもしれません。しかし、私にとって、少しぐらいの数字と論理の知識を持ちさえすれば、アルゴリズムの概要は誰でも理解できるものだと信じています。

このブログをもって、アルゴリズム記法の基礎を、読者の皆様にご紹介させていただきたいと思います。自分のプログラミングのレベルと規模が向上するにつれてよく現れるコンセプトの一つ:

ビッグオー記法(Big-O)

ビッグオーの定義

簡単に言うと、ビッグオー記法とは、プログラマーがアルゴリズムの効率を表現する方法のことです。そしてアルゴリズムとは、単にある問題の解決策のことです。それでは私たちの関数の効率は、一体どう計算すればいいのでしょうか。また、その方法はなぜ必要なのでしょうか。

関数かメソッドを定義するとき、同じ問題を解決するには、複数の実装方法があるはずです。下記のJavascript関数をご覧ください。reverseStringという関数は、与えられた文字列stringから逆転した新しい文字列を返します。

一般的な実装の一つ

文字列の逆表示の関数を書き、テストが成功した後、そのままでいいと思う方もいるかもしれませんが、上記の実装は次の同じ関数と比べてどうでしょうか。

Javascriptの組み込みメソッドを使用する実装

この三つ目は?

再帰関数の実装

どれも同じ機能を果たすならば、「一番良い」実装はどのように決定するのでしょうか。コンピューターの出力速度をミリ秒で計ればいいのでしょうか。コードが一番短いので二つ目が良いのでしょうか。なぜ一番を決めなければならないのでしょうか。

この問題を解くのは、ビッグオー記法の用途です。的確な言語を使い、コードの性能について語り、様々な実装の良し悪しも観察することができます。また、コードをデバッグするときに容易く非効率な部分を見出せることも、ビッグオーの強みの一つです。

ビッグオーの計り方

もう一度前の例を見てみましょう。あるプログラムの性能を測るために、実時間演算を使えばいいのでしょうか。この方法では、15年の古いパソコンは最新式のMacBook Proと比べればどうなるでしょうか。たとえ同じブランド、同じ型、同じ年のパソコンを二台比較するとしても、全く等しい演算が手に入れられないのではないでしょうか。より良い方法があります。

ビッグオー記法は、実時間演算ではなく、パソコンの実行する単純な演算を数える計算です。概して言えば「時間計算量」と「空間計算量」を通し、ビッグオー記法を使用します。

次はこの足し算の関数をご覧ください。1から引数の数字 n まで、全ての整数を足して返す機能です。

上記の一つ目のreverseString関数と同じよう、for文を使います。

ビッグオー記法の面から分析しましょう。for文の中で、変数 i を設定し、処理を繰り返すごとに値が増加します。そのfor文のブロックの中では、最中の条件式(i <= n)が成立しなくなるまで、i の現在値を総計の変数 sum に足します。この場合、実行する単純な演算の総数は計算できるのでしょうか。

そうです!n の値をもってできます。

i に初期値1を設定し、 n の値になるまで繰り返すごとに値が増加します。そして n の値により、演算の数も決定できます。これはビッグオーの時間計算量を示すものです。つまり、関数addUpToの時間計算量はO(n)となります。ランタイムの効率が n とともに多少変化するというわけです。

addUpToの別の実装はこちらです。

今回先ほどのfor文の繰り返し処理を使わなくなったので、演算の数「掛け算一つ(*)、足し算一つ(+)、割り算一つ(/)」は n の値にかかわらず一定しています。その結果、for文を使うaddUpToと比べれば一定数の演算を持っています。これはO(1)という時間計算量です。「定数時間」とよく呼ばれています。

時間計算量と空間計算量

さて、引数の値によるアルゴリズムのランタイムを示す時間計算量を習得しましたが、もう一つの計算量は?空間計算量とはアルゴリズムを実行するため、コンピューターのメモリの量を計算することです。要するに、そのプログラムの実行に必要なメモリの容量です。

関数sumArrayでは、数字が入っている配列を受け、全ての要素を足した総計を返します。

以上から、sumArrayは時間計算量のO(n)を持つことがわかってもらえると思います。arrayにある要素の数「ビッグオーの n 」 が増えるにつれて、for文の繰り返すループも蓄積されていきます。ところが、引数の値も繰り返し処理の頻度も、空間計算量を測るのとは関係ありません。「引数の値を除いて測ることを、正確に副空間計算量と呼びます。」

アリゴリズムに必要な容量を計算するには、まずその関数にある数字、文字列、配列といった変数を分析してみます。数値型、文字型、ブール型などの単純なデータ型の場合、O(1)の空間計算量があります。その一方Javascriptの配列、文字列、オブジェクトの場合では、データの大きさによるO(n)の空間計算量になります。

sumArrayの中の変数を集めるとこうなります。

変数arrayが引数なので、空間計算量とは関係ないことにご注意ください。それを含めた場合、O(n)の空間計算量になっていましたが、引数なので触れないことにします。そして、関数sumArrayの実装はO(n)の時間計算量と、O(1)の空間計算量を持っています。仮に関数の中で他の文字列や配列などの変数を設定するとしたら、まさしく計算量が両方O(n)になります。

ビッグオーの用途

プログラムの計算量を表すとき、詳細ではなく、一般の動向が優先されています。結局のところ、ビッグオー記法そのものは、「あやふやな数え方」に他なりません。的確な計算より、概算を通してアルゴリズムの効率を判断するものです。ある変数 n の値の増減に伴う動向を計ることを、ビッグオー記法と言います。

効率の動向により、そのアリゴリズムの実行も大幅に変化する可能性があります。


Measuring the efficiency of algorithms (in English and Japanese)

日本語翻訳はこちらです。

When I first heard the word “algorithm” referenced in computer science as a 26 year old struggling to learn basic code, I dreaded the notion. “I should’ve paid more attention in high school math” and “If the engineers in my dad’s office struggle with this, there’s no hope for me” were a few of the self-defeating thoughts I had as I closed my laptop after a day of studying.

I believe for the majority of beginners like me who are getting their feet wet in programming, phrases such as “searching algorithms” or “time/space complexity” can seem quite intimidating and…

Erik Huang

I am currently a student in the software engineering program at Flatiron school

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store