Atcoder Biginner Contest 224 C問題がTLEになるので、どの処理で時間がかかっているかご教示いただきたいです

Question

前提・実現したいこと

お世話になっております。

Atcoder Biginner Contest 224 C問題についての質問です。（問題文は以下のURLです。）
https://atcoder.jp/contests/abc224/tasks/abc224_c
私は全ての組み合わせに対して、3点が一直線上に並んでいない=線分ABとACの傾きが異なっているならば三角形としてカウントするという方針で回答を作成しました。
しかし、以下のコードを提出するとテストケース23個中15個がTLEとなってしまいます。（WAは出ないのでロジック的には問題ないはずです。）
以下のコードのどの処理で時間がかかっているかご教示いただきたいです。

どうぞ、よろしくお願いいたします。

該当のソースコード

import itertools
n = int(input())
a = [list(map(int, input().split())) for l in range(n)]
count = 0
for comb in list(itertools.combinations(a,3)):
    if (comb[0][1] - comb[1][1]) * (comb[1][0] - comb[2][0]) != (comb[1][1] - comb[2][1]) * (comb[0][0] - comb[1][0]):
        count += 1
print(count)

Answer 1

map をリスト化している部分で時間が掛かっていて、timeit で計測すると30万倍程度の差があります。そこはリスト化する必要はなく、イテレータのままでよいのではないでしょうか(for comb in itertools.combinations(a,3):)。もっとも、これで TLE が解消するかどうかは判りませんが。。。(最大で 300C3 = 4,455,100 通りの組み合わせを試す事になりますので)。

import random
import itertools
import timeit

N = 300
a = [random.sample(range(10000), 2) for _ in range(N)]

print(timeit.timeit(
  '_ = itertools.combinations(a, 3)',
  number=10, globals=globals()))

print(timeit.timeit(
  '_ = list(itertools.combinations(a, 3))',
  number=10, globals=globals()))

# 単位は秒(second)
8.799019269645214e-06
2.7610603279899806

Comments

[kado1234]

ありがとうございます！
「list(itertools.combinations(a,3))」からlistを外したらかなり速くなりました！

実行時間こんなに違うんですね。。！

Answer 2

この手の計算をitertools.combinationsでやると、あちらこちらで同じ計算をやるので無駄が多いですね。
itertools.combinationsを使わない方向で考えた方が良いでしょう。

Comments

[kado1234]

ご回答ありがとうございます！
itertools.combinationsよりもfor文でループさせたほうが速いみたいですね！
ちょっとfor文使った組み合わせの作り方も考えてみます！

Answer 3

とりあえず、以下のlistは不要なので削除しましょう。

for comb in list(itertools.combinations(a,3)):

それでも遅ければ、aをジェネレータ式にしてみましょう。
a = (list(map(int, input().split())) for l in range(n))
何回か計測を繰り返したら、実行時間に差が無くなってしまったので取り下げます。すみません。

Comments

[kado1234]

ありがとうございます！
「list(itertools.combinations(a,3))」からlistを外したらかなり速くなりました！

[kado1234]

みなさんご回答ありがとうございます！
どの回答もめちゃありがたいですが、actorbugさんが一番最初に回答してくださったので、baとさせていただきます！

[kado1234]

初歩的な質問で申し訳ないのですが、
「a = (list(map(int, input().split())) for l in range(n))」をジェネレータ式に変形するとしたら、どのようなコードになるんでしょうか。
もしご迷惑でなければご教示お願いいたします。（ご迷惑であればスルーしていただいて大丈夫です。）

[actorbug]

ごめんなさい。ジェネレータ式に変更しても速度はほとんど変わりませんでした。
なお、その式はすでにジェネレータ式に書き換えた後のものになります。

[kado1234]

ご回答ありがとうございます！
なるほど、こういう形をジェネレータ式というのですね。。
質問する前に文法をもう少し学ぶべきでした。
お手数おかけいたしました！