執筆者について
エンジニア歴 3 年目のゆず（@yuzu_49693）です。
この記事では、最近わたしが行なっているアルゴリズムとデータ構造について学んだことの共有を行わせていただきます。
※ 未熟な身ですので誤りもあると思います。良かったらコメントなどでご指摘いただけるとありがたいです。
学んでいる方法
leetcode というサービスをつかって、コーディング面接対策のために解きたい LeetCode 60 問を少しずつ解いております。
問題の解き方はメイン内容ではありませんが、手順を書いておきます。
leetcode をつかったコーディング練習方法
① 問題の解答を 5 分考えて、分からなかったら答えを見る。
② 答えを見て理解できたら、答えを見ずにコーディングする。コードが書けずに 5 分ほど経過したら再度答えを見て確認する。答えを見てしまった全て消して書き直す。これを正解できるまで繰り返す。
③ 完成したコードをリファクタする。まずは自力でリファクタし、その後 AI に評価してもらってリファクタする。完成したら再度全て消す。
④ 時間を測りながら 10 分以内に、もう一度リファクタ後のコードを書き直す。これを 3 回続けてエラーを一回も出さずに書けるまで繰り返す。
⑤ 記述したコードで出てきた、メソッドやライブラリなどについて深掘りする。
⑥ 日にちをおいて、再度問題に挑戦する。
こちらの練習方法は、ソフトウェアエンジニアリング協会さんの勉強会で教えていただいたものとなります。
気になった方は、ぜひソフトウェアエンジニアリング協会さんの勉強会にも参加してみてください。
取り組んだ問題について
ひとつずつ問題について記事化するかは分かりませんが、今回非常に学びがありましたので書くことにしました。
取り組んだ問題は 20. Valid Parenthesesです。
easy レベルの問題となりますが、それでも本当にたくさんの学びがありました。
20. Valid Parentheses
Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
An input string is valid if:
Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Every close bracket has a corresponding open bracket of the same type.
問題の日本語翻訳
文字列 s が '(', ')', '{', '}', '[', ']' の文字のみを含んでいるとき、入力文字列が有効かどうかを判定してください。
入力文字列が有効である条件：
開き括弧は同じ種類の括弧で閉じられなければならない
開き括弧は正しい順序で閉じられなければならない
すべての閉じ括弧には、同じ種類の対応する開き括弧がなければならない
わたしの解答
解答は Java で行なっています。
現場で使っている言語であり、キャッチアップ中なので基本的に今後も Java で解いていく予定です。
最初に解答したコードでは Stack という java の util.class を使って書きました。しかしより新しい ArrayDeque という Class があると AI に教えていただき書き直しています。
ArrayDeque は、LIFO（後入れ先出し）の Stack だけではなく、FIFO（先入れ先出し）のキューにも対応できる、両端操作可能な便利クラスです。
今回はこれを用いて処理を作成しました。
https://docs.oracle.com/javase/jp/8/docs/api/java/util/ArrayDeque.html
この完成したコードに対して、深掘りした内容がこの記事の本編です。
import java.util.ArrayDeque;
class Solution {
public boolean isValid(String s) {
if(s.length() % 2 != 0) return false;
ArrayDeque<Character> stack = new ArrayDeque<>(s.length() / 2);
for(char c : s.toCharArray()) {
if(c == '(' || c == '{' || c == '[' ) {
stack.push(c);
} else {
if(stack.isEmpty()) return false;
char top = stack.pop();
if(!isMatching(c, top)) return false;
}
}
return stack.isEmpty();
}
private boolean isMatching(char closingBracket, char openingBracket) {
if ((closingBracket == ')' && openingBracket != '(')
|| (closingBracket == '}' && openingBracket != '{')
|| (closingBracket == ']' && openingBracket != '[' )) {
return false;
}
return true;
}
}
コードを記述していて気になった点
コードをリファクタする中で、以下の内容について気になりました。
- メモリの再割り当てについて
- ArrayDeque クラスの両端操作はどのように実現しているのか？
2 つの内容について記述すると非常に記事が膨らむため、今回は 1 の内容についてのみ書きます。
leetcode では、完成したプログラムを実際に実行した時のパフォーマンスも表示してくれます。
表示内容を見ると、以下のことがわかります。
実行時間: 2ms - 全体の 96.85% を上回る速度
メモリ使用量: 42.07MB - 全体の 31.42% を上回る効率
パフォーマンス表示してくれるおかげで、よりコードを良くするための思考ができとてもありがたいです。
メモリの再割り当てについて学んだこと
わたしのコードはメモリ使用量のパフォーマンスがあまり良くありません。
これはコードを書き換えたため起こっています。
私が今回非常に面白いと感じた点がこの変更についてです。
どこでそれが発生しているかというと
6 行目の以下のコードとなります。
ArrayDeque<Character> stack = new ArrayDeque<>(s.length() / 2);
最初は、以下のように記述していました。
つまりインスタンス化する際に、メモリ割り当てをデフォルトにしていたのです。
ArrayDeque<Character> stack = new ArrayDeque<>();
その時のパフォーマンスは以下です。
変更前のパフォーマンスの方が高いと分かります。
引数に int を指定した場合と指定しなかった場合の挙動の違いを、Java のソースをみて確認しました。
https://github.com/openjdk/jdk/blob/master/src/java.base/share/classes/java/util/ArrayDeque.java
/**
* Constructs an empty array deque with an initial capacity
* sufficient to hold 16 elements.
*/
// 引数なしのデフォルト
public ArrayDeque() {
elements = new Object[16 + 1];
}
/**
* Constructs an empty array deque with an initial capacity
* sufficient to hold the specified number of elements.
*
* @param numElements lower bound on initial capacity of the deque
*/
// 引数あり
public ArrayDeque(int numElements) {
elements =
new Object[(numElements < 1) ? 1 :
(numElements == Integer.MAX_VALUE) ? Integer.MAX_VALUE :
numElements + 1];
}
引数を指定しない場合、17 要素分（実際要素を保存できるのは 16 個まで）確保してインスタンス化していることが分かります。
ここで疑問となるのは、17 以上の要素を確保しなければならなくなった時どうなるのかです。
メモリの再割り当て
ソースを確認したところ、許容範囲を超えて要素を保存しなければならない場合、より大きいメモリを確保し、オブジェクトを全てコピーしているようです。
では、コピーする時に実行している Arrays.copyOf() はどれくらい重い処理なのか？
https://github.com/openjdk/jdk/blob/320230db5f9ca95f23218704cb2e69521e03852f/src/java.base/share/classes/java/util/Arrays.java
この先は自分で読んでも分からなかったので、Copilot に聞きました。
処理時間は O(n) になるそうです。
私の考えなので間違っているかもしれませんが、
ここまで調べた内容を元に以下の状況が考えられました。
メモリ割り当て時にあまりにも見当違いな値を割り当ててしまった場合、処理実行時に何度もメモリの再割り当てが起こってしまうのではないか？
それにより処理速度がO(n)分遅くなってしまうリスクがありそう。🤔
では、どの程度割り当てれば良いのかですが…
それは実際の要件で想定するしかないのではないかと、私は考えています。
この問題では、引数として渡される文字列の半分より大きい値にはなり得ないとおもったので、渡される文字列の半分をメモリ割り当てとして設定することにしました。
学んだこと
そもそも私は、これまでメモリ割り当てなど気にすることなくコーディングしてきました。
データ構造も今回初めて、スタック型を使いました。
この事により、自分がコーディングする際に必要な思考がおおきく欠落していたことを理解することができました。
コーディング時に、処理フローだけではなくパフォーマンスも考慮した書き方ができるようになること、それを今後も leetcode の問題を解きながら学んでいきたいと思います。
この記事の内容には、私の予想や AI の出力内容も含まれるため、誤りもあると思います。
誤りに気がつきましたら、ご指摘いただけるととても励みになります。
どうぞ、よろしくおねがいいたします。
参考にさせていただいたもの
AI cloude sonnet4
AI Copilot GPT-4.1