Pythonの計算量について

Question

2つの要素a,bがn回与えられるとします(もちろんabは毎回異なる値)。
これを2次元配列Xから探します
探し方としては
for i in X:
If a in i
のような要領です。
ab両者とも絶対に多次元配列の中で重複していません。
このような時、aが見つかった場合次からの繰り返しでaを探す必要がないです。
なのでbだけを探すようにしています。
もし、a,b両者とも見つかればp回目(1<=p<=n)の探索は終了でfor文をbreakします。

このような時のp回目の探索において、計算量を減らす目的で、最初に
Aflag=False
Bflag=False
と設定して、見つかったらそれぞれをTrueにしているのですが、
for文の中で毎回これらがTrueかFalseかで4通りの場合分けをして探索時間を減らすようにしたのですが、計算量が多いらしく時間をオーバーしてしまいました。
私の考えでは、
if
elif
elif
else
の中で条件に合わないのはさっと飛ばして条件にあった物だけ処理をするので、人間が一生懸命場合分けをすればその分コンピュータは楽になると思ったのですが違いますでしょうか？

Answer 1

計算量がオーダーのことであれば、定数倍の改善なので効きません。

まず1要素探す場合を考えます。擬似コードで適当に示します。

ターゲット = ...

for 要素 in 対象の配列（1次元）：
    if 要素がターゲットなら:
        indexでも記録しておく
        break

これが平均で対象の配列の要素数/2でできることはおわかりかと思います。

2要素探す場合は、まあ質問文の方式だとこんな感じですか。

ターゲットA = ...
ターゲットB = ...
フラグA = True
フラグB = True

for 要素 in 対象の配列（1次元）：
    if フラグA and 要素がターゲットAなら:
        indexでも記録しておく
        フラグA = False
    elif フラグB and 要素がターゲットBなら:
        indexでも記録しておく
        フラグB = False
    elif フラグAとBがともにFalse:
        break

発想としては適切なフラグを立てて無駄な比較を減らそうということですね。

実は下のコードでもまったく同じです。

ターゲットA = ...
ターゲットB = ...

for 要素 in 対象の配列（1次元）：
    if 要素がターゲットAなら:
        indexでも記録しておく
        break

for 要素 in 対象の配列（1次元）：
    if 要素がターゲットBなら:
        indexでも記録しておく
        break

平均が要素数/2のところこれの2倍ですから、要素数と等しい比較回数になります。いずれにせよO(Xの要素数)です。

「計算コスト」のことであれば、確かに比較回数は1/2にできていますが、余計な条件分岐と真理値計算が入りますからどちらの効果が勝るかで決まります。一般論としては、実測してみないとなんともいえないですね。

Answer 2

質問者さんが2次元の配列といっておられるのは実際には「入れ子になったlist」なはずなのでそう想定します。例えばnumpy.ndarrayだとそもそも行ごとにin演算子で検査せずともa in xで結果がでてしまい、ご質問の工夫の意味が失われてしまいますので。

それはともかく...

人間が一生懸命場合分けをすればその分コンピュータは楽になると思ったのですが違いますでしょうか？

「そのとおり」です。ゆえに「どうしたら計算の手間を少しでも減らせるか」を工夫することは論理を考えるよい訓練になると思います。

他の方が少々否定的に見えるコメントをしておられますが、それはおそらく「かけた手間に対して充分効果があるか」というより進んだ段階のプログラマーの感覚からくるコメントだと思います。

つまり**質問者さんが問いかけたことの答えは「YES」**なんですが、その効果の程度についてよく考えた方がよいということではないでしょうか？

細かい考え方などについては他の方が既に回答しておられるので、自分は「とりあえず実際動かしてみよう」というノリでやってみたことをご紹介しようと思います。

4つの実装例を挙げて実際にやってみます。

def contained_both1(a, b, x):
    a_exists = b_exists = False
    for row in x:
        if a in row:
            a_exists = True
        if b in row:
            b_exists = True
    return a_exists and b_exists

def contained_both2(a, b, x):
    a_exists = b_exists = False
    for row in x:
        if not a_exists and a in row:
            a_exists = True
        if not b_exists and b in row:
            b_exists = True
    return a_exists and b_exists

def contained_both3(a, b, x):
    a_exists = b_exists = False
    for i in range(len(x)):
        row = x[i]
        if a in row:
            a_exists = True
            b_exists = b in row
            break
        if b in row:
            b_exists = True
            break
    else:
        return false
    if a_exists:
        if b_exists:
            return True
        for i in range(i, len(x)):
            if b in x[i]:
                return True
    else:
        for i in range(i, len(x)):
            if a in x[i]:
                return True
    return false

def contained_both4(a, b, x):
    for row in x:
        if a in row:
            break
    else:
        return False
    for row in x:
        if b in row:
            return True
    return False

• (1) contained_both1

何も工夫してない。途中で見つかっても必ず最後までa, b両方を各行から探す

• (2) contained_both2

aやbが以前の行で見つかったらそれ以降の行ではin演算子の判定をスキップ

• (3) contained_both3

aかbが見つかったらいったんループを中断し、それ以降の行から見つかってない方(a or b)だけを探す

• (4) contained_both4

何も工夫してない。ループを2回に分けa, bそれぞれを別のループで探す。ただし途中で見つかったとき単純にbreakできるので(1)よりは早いかも知れないが2回ループを実行するのが遅くなる心配もある

これを100x100の入れ子のlistの中からa, bの見つかる行をいろいろに変えて(1)～(4)をそれぞれ100回実行してみた結果が以下です(1回あたりの検索時間。単位は秒)。

 (1)      (2)      (3)      (4)
 0.195643 0.099513 0.100657 0.097728 平均
 0.002405 0.000975 0.000948 0.000967 標準偏差

hayataka2049さん回答にあるように(2)の工夫により(1)の半分の実行時間で済んでいます。つまり実際に効果がありそうだといえましょう。ただし、少しでもオーバーヘッドを減らそうと意図した(3)は(2)と大差ないです。却ってちょっと遅くなっているようにも見えますが誤差のレベル。そしてなんだかがっかりする結果が(4)です。ほとんど工夫してないのに(2)や(3)より(この測定では)早いという結果が出てしまってますね。

要するに人間が考えると手間を減らしたように見えることでも、実際にコードにすると計算機(言語)の様々な言語機能の性能特性(効率)のバランスによって効果が出たり出なかったりするといえましょう。

---

最後に・・・(というよりここが本題だったりしますが)

計算量が多いらしく時間をオーバーしてしまいました。

質問者さんの工夫は何割かの削減の効果が望めることが実測によっても確認できました。しかしながら(hayataka2049さんがほのめかしておられる?)ように、一般的に最も注目すべき点は計算量のオーダーを下げる工夫であるといえます。

本件の条件をよく見ると「同じXに対して複数回異なるa, bの組に対して検索をする」というのがポイントだと思います。その点に着目してある工夫(5)をした結果を測定してみますと

 (1)      (2)      (3)      (4)      (5)
 0.195643 0.099513 0.100657 0.097728 0.000477 平均
 0.002405 0.000975 0.000948 0.000967 0.000017 標準偏差

このように何割というレベルの削減ではなく何桁というレベルの削減になります。
「時間をオーバー」したというのはどこかのプログラミング問題サイトでの話ではないかと想像します。そのようなサイトでは「計算量のオーダーを下げることで何桁もの削減を工夫すること」がクリアの前提になるだろうと思います。

質問者さんは既に「論理を工夫して計算コストを下げる」取り組みをしておられるわけですが、計算量の考え方を学びもう一歩だけ進んだ(計算量オーダーが低い)アルゴリズムを狙うとよいと思う次第です。

Answer 3

ロジックを見てないので、正確には言えませんが、
たぶん意味がないか、遅くなってるかと想像します。

配列の要素数が、わかりませんがシーケンシャルに検索するより、
ソートしたあとに検索する方が効率的になる可能性があるかと思います。

例えば、要素が1000の場合
シーケンシャルの場合は、500回ですが
ソート済みであれば、10回になります。

場合分け自体に効果が無いとはいいませんが、計算量が減るロジックに、なってるかどうかですね。