Pythonで2つのスパースベクトルの内積を計算するプログラム

問題の概要

ここでは、2つのリストで表現されたスパースベクトル(疎なベクトル)が与えられ、その内積(ドット積)を求めることを考えます。

ベクトルはオブジェクトとして表現され、各要素のリストはオブジェクトのメンバー変数 nums に格納されています。

例えば、入力が以下のような場合を考えてみましょう。

• vector1 = [1, 0, 0, 0, 1]
• vector2 = [0, 0, 0, 1, 1]

このときの出力は 1 になります。内積の計算は次のとおりです。

1 × 0 + 0 × 0 + 0 × 0 + 0 × 1 + 1 × 1 = 1

解決のための手順

この問題を解くには、以下の手順に従います。

• 結果を格納する変数 res を 0 で初期化します。
• vector2 の nums から、インデックス i と値 v を順番に取り出します。
  • v が 0 の場合は、計算しても結果に影響しないためスキップします。
  • それ以外の場合で、vector1 側の nums[i] が 0 のときも、同様に次の反復へ進みます。
  • どちらの値も 0 でない場合は、res := res + v * nums[i](vector1側) を実行して加算します。
• すべての要素を処理したら、res を返します。

Pythonでの実装例

理解を深めるために、以下の実装例を見てみましょう。

class Solution:
    def __init__(self, nums):
        self.nums = nums

    def solve(self, vec):
        res = 0
        for i, v in enumerate(vec.nums):
            if v == 0:
                continue
            elif self.nums[i] == 0:
                continue
            else:
                res += v * self.nums[i]
        return res

ob1, ob2 = Solution([1, 0, 0, 0, 1]), Solution([0, 0, 0, 1, 1])
print(ob1.solve(ob2))

入力

[1, 0, 0, 0, 1], [0, 0, 0, 1, 1]

出力

1

このアプローチのポイント

スパースベクトルとは、ほとんどの要素が 0 であるベクトルのことです。そのため、値が 0 の要素同士の掛け算は必ず 0 になるという性質を利用し、どちらか一方でも 0 である要素の計算を事前にスキップすることで、無駄な演算を減らしています。

このアルゴリズムの計算量は、ベクトルの長さを n とすると O(n) であり、空間計算量は結果を保持する変数のみで済むため O(1) です。さらに大規模なデータでは、非ゼロ要素だけを(インデックス, 値)のペアで保持する方式にすることで、より高速化することも可能です。