Pythonでログファイルのデータを並べ替える方法

問題の概要

ログの配列が与えられているとします。配列内の各エントリは、スペースで区切られた単語からなる文字列です。各ログの最初の単語は英数字で構成される識別子（ID）であり、その後には以下のいずれかの種類の文字列が続きます。

1. ID以降の各単語が小文字の英字のみで構成されている
2. ID以降の各単語が数字のみで構成されている

前者を「文字ログ（letter-log）」、後者を「数字ログ（digit-log）」と呼びます。なお、各ログにはIDの後に必ず1つ以上の単語が存在することが保証されています。

並べ替えのルール

求められるのは、次の条件に従ってログを並べ替え、最終的な順序を返すことです。

• すべての文字ログは、すべての数字ログよりも前に配置する
• 文字ログ同士は、識別子を除いた部分を辞書順（lexicographical order）でソートする。内容が同一の場合は識別子を使って順序を決める
• 数字ログは入力されたときの元の順序を維持する

たとえば、入力が logs = ["dig1 9 2 5 2", "let1 art can", "dig2 4 8", "let2 own kit dig", "let3 art zero"] の場合、出力は ["let1 art can", "let3 art zero", "let2 own kit dig", "dig1 9 2 5 2", "dig2 4 8"] となります。

解き方の手順

この問題は、次の手順で解くことができます。

• 文字ログ用のリスト words と、数字ログ用のリスト nums を用意する
• 各ログに対して以下を繰り返す
  • ログをスペースで分割し、単語のリスト s を作る
  • 2番目の単語が数字であれば、そのログを nums の末尾に追加する
  • そうでなければ、識別子と残りの部分をタプルとして words に格納する
• words を「本文を第1キー、識別子を第2キー」としてソートし、再びスペース区切りの文字列に戻す
• words と nums を連結して返す

それでは、実際の実装を見てみましょう。

Pythonでの実装例

class Solution:
    def reorderLogFiles(self, logs):
        words = []
        nums = []
        for log in logs:
            s = log.split()
            if s[1].isdigit():
                nums.append(log)
            else:
                words.append((s[0], ' '.join(s[1:])))
        words = sorted(words, key=lambda x: (x[1], x[0]))
        return [' '.join(w) for w in words] + nums

ob = Solution()
print(ob.reorderLogFiles(["dig1 9 2 5 2", "let1 art can", "dig2 4 8",
                          "let2 own kit dig", "let3 art zero"]))

入力

["dig1 9 2 5 2", "let1 art can", "dig2 4 8", "let2 own kit dig", "let3 art zero"]

出力

['let1 art can', 'let3 art zero', 'let2 own kit dig', 'dig1 9 2 5 2', 'dig2 4 8']

まとめ

このアルゴリズムでは、まずログを文字ログと数字ログに振り分けます。文字ログは sorted() 関数とラムダ式を組み合わせ、「本文を第1キー、識別子を第2キー」としてソートすることで、要件通りの順序を実現しています。数字ログはリストへ追加した順序のまま保持されるため、元の順序が自然に保たれる点もポイントです。なお、ソート処理はループの外で一度だけ行うことで、効率的な実装になります。計算量は、ログの総数をNとすると O(N log N) 程度に収まります。