【ITニュース解説】[1] Algorithm Showdown: Python vs. JavaScript - Group Anagrams

この記事は、与えられた文字列の配列の中から、アナグラム（文字の並び替えによって別の単語になる単語）をグループ化するというプログラミングの問題を、PythonとJavaScriptという異なる二つのプログラミング言語でどのように解決するかを比較検討している。システムエンジニアを目指す上で、このようなアルゴリズムの問題を様々な言語で解く経験は、各言語の特性を理解し、効率的なコードを書くための基礎となる。

まず、アナグラムとは何かを明確にする。例えば、「eat」「tea」「ate」はすべて同じ文字（e, a, t）で構成されており、これらの文字を並び替えることで互いに生成できるため、アナグラムの関係にある。この問題をプログラミングで解決するには、入力として与えられた文字列の配列から、これらのアナグラムの関係にある文字列を見つけ出し、同じグループにまとめる必要がある。具体的には、入力が ["eat","tea","tan","ate","nat","bat"] のような配列であれば、出力は [["bat"],["nat","tan"],["ate","eat","tea"]] のように、アナグラムごとにグループ化された配列となる。

この問題を解くための基本的な考え方は、各文字列がどのような文字で構成されているかを「特徴」として捉え、その特徴が同じ文字列を同一のグループにまとめるというものである。ここでいう「特徴」とは、文字列に含まれる各アルファベットの出現回数を指す。例えば、「eat」「tea」「ate」はいずれも「aが1回、eが1回、tが1回」という構成を持っている。この文字の出現回数を記録した情報を「キー」として利用し、同じキーを持つ文字列を一つのグループとして格納していくのだ。この目的のために、プログラミングでは「ハッシュマップ」「辞書」「連想配列」あるいはJavaScriptでは「Map」と呼ばれるデータ構造を用いる。これらは「キー」と「値」をセットで保存できる便利な仕組みである。

Pythonでのアプローチでは、まず collections モジュールから defaultdict をインポートして利用する。defaultdict(list) は、存在しないキーにアクセスしようとしたときに、自動的に空のリストをそのキーに割り当ててくれるため、キーの存在チェックを毎回書く手間が省けて便利である。

具体的な処理の流れを見ていくと、まず入力された文字列の配列を一つずつループで処理する。各文字列に対して、その文字列に含まれる各アルファベットの出現回数をカウントするための配列（長さ26で、初期値はすべて0）を用意する。なぜ26かというと、英語のアルファベットがaからzまで26種類あるためである。例えば、文字列「s」に含まれる「char」という文字の出現回数をカウントするには、ord(char) - ord('a') という計算を使う。ord() 関数は文字のASCIIコード（コンピュータが文字を認識するための数値）を返すため、ord('a') を基準（0番目のインデックス）として引くことで、「a」が0、「b」が1、…、「z」が25というように、配列のインデックスに変換できる。この計算結果のインデックスに対応する場所の値を1増やすことで、文字の出現回数を記録していく。

全ての文字の出現回数を数え終わると、count 配列にはその文字列の特徴が数値の並びとして記録される。Pythonでは、この数値の配列（リスト）を直接ハッシュマップのキーとして使うことはできないが、リストを tuple(count) のようにタプルに変換することでキーとして利用可能となる。タプルは変更できない（イミュータブルな）データ構造であり、そのためハッシュマップのキーとして適している。こうして作成したキーを result という defaultdict に渡し、対応するリストに現在の文字列を追加していく。全ての文字列の処理が終わったら、result.values() をリストに変換して返すことで、アナグラムのグループがまとめられた結果が得られる。

一方、JavaScriptでのアプローチも基本的な考え方はPythonと共通している。まず const result = new Map(); でMapオブジェクト（Pythonの辞書に相当）を初期化する。

JavaScriptでも同様に、入力された文字列を一つずつループで処理し、各文字列に含まれるアルファベットの出現回数を数えるための配列を new Array(26).fill(0) で作成する。文字の出現回数をカウントするロジックも char.charCodeAt(0) - 'a'.charCodeAt(0) のように、Pythonとほぼ同じ原理でインデックスを計算し、配列の値をインクリメントしていく。

Pythonと異なるのは、この出現回数を記録した配列をMapのキーとして使う方法である。JavaScriptの配列は直接Mapのキーとして利用できないため、count.join(',') のように配列の要素をカンマで区切った文字列に変換してキーとして用いる。例えば、[1, 0, 1, 0, ...] のような配列は "1,0,1,0,..." のような文字列に変換される。そして、Pythonの defaultdict とは異なり、JavaScriptのMapではキーが存在するかどうかのチェックを明示的に行う必要がある。if (!result.has(key)) でキーの存在を確認し、存在しなければ result.set(key, []) で新しい空の配列をそのキーに対応付けて作成する。その後、result.get(key).push(s) で現在の文字列を、そのキーに対応する配列に追加する。全ての処理が終わったら、Array.from(result.values()) を使って、Mapに格納されたアナグラムのグループだけを取り出し、配列として返す。

この二つの言語での実装を比較すると、いくつかの特徴が見えてくる。Pythonでは、ハッシュマップのキーとしてタプルを自然に利用でき、defaultdict のおかげでキーの存在確認を省略できる点が簡潔さを生む。対してJavaScriptでは、配列を文字列に変換してキーとし、Mapにキーが存在しない場合の初期化を明示的に記述する必要がある。

パフォーマンスの観点から見ると、両方の実装とも時間計算量と空間計算量が共にO(n×m)であると分析されている。ここで「n」は入力される文字列の総数、「m」は文字列の平均的な長さを意味する。これは、各文字列（n個）に対して、その文字列の文字を一つずつ調べてカウントする処理（文字列の長さmに比例）を行うため、全体の処理時間がn×mに比例するということを示している。また、結果を格納するための空間（メモリ）も、最悪の場合にはn個の文字列それぞれに対してその文字カウント配列（長さmに比例）を保持する必要があるため、同様にn×mに比例するという意味である。

この比較からわかるように、同じ問題を解決するためのアルゴリズムの核心部分は言語によらず共通しているが、具体的な実装の書き方や利用できる便利な機能、あるいはデータ構造の扱いに違いがある。システムエンジニアにとって、これらの言語ごとの特性を理解し、状況に応じて適切なツールや書き方を選択する能力は非常に重要である。