python 시간을 줄이는 테크닉 - min,max를 남발하지 말자(플로이드 워셜에서 주의하기)
16958번: 텔레포트
2차원 평면 위에 N개의 도시가 있다. 일부 도시는 특별한 도시이다. (r1, c1)에 있는 도시에서 (r2, c2)에 있는 도시로 가는 이동 시간은 |r1 - r2| + |c1 - c2|와 같다. 만약, 두 도시가 특별한 도시라면, 텔
www.acmicpc.net
이 문제에서 다음과 같이 제출하면.. 시간 초과로 통과하지 못한다
from sys import stdin
INF = 1e9
def floyd(graph,city):
for k in range(1,n+1):
for a in range(1,n+1):
if k == a:
continue
for b in range(1,n+1):
if a == b:
continue
graph[a][b] = min(graph[a][b],graph[a][k] + graph[k][b])
return graph
n,t = map(int,stdin.readline().split())
graph = [[INF]*(n+1) for _ in range(n+1)]
city = [0]
for _ in range(n):
s,x,y = map(int,stdin.readline().split())
city.append((s,x,y))
for a in range(1,n+1):
for b in range(1,n+1):
if a != b:
x = abs(city[a][1] - city[b][1]) + abs(city[a][2] - city[b][2])
if x > t and city[a][0] == 1 and city[b][0] == 1:
graph[a][b] = t
else:
graph[a][b] = x
graph = floyd(graph,city)
m = int(stdin.readline())
for _ in range(m):
a,b = map(int,stdin.readline().split())
print(graph[a][b])
반면, floyd()함수에서 graph[a][b] = min(graph[a][b],graph[a][k] + graph[k][b])을 if문을 활용한 비교로 고치면..
if graph[a][b] > graph[a][k] + graph[k][b]: graph[a][b] = graph[a][k] + graph[k][b]
통과하게 되는데..
from sys import stdin
INF = 1e9
def floyd(graph,city):
for k in range(1,n+1):
for a in range(1,n+1):
if k == a:
continue
for b in range(1,n+1):
if a == b:
continue
if graph[a][b] > graph[a][k] + graph[k][b]:
graph[a][b] = graph[a][k] + graph[k][b]
return graph
n,t = map(int,stdin.readline().split())
graph = [[INF]*(n+1) for _ in range(n+1)]
city = [0]
for _ in range(n):
s,x,y = map(int,stdin.readline().split())
city.append((s,x,y))
for a in range(1,n+1):
for b in range(1,n+1):
if a != b:
x = abs(city[a][1] - city[b][1]) + abs(city[a][2] - city[b][2])
if x > t and city[a][0] == 1 and city[b][0] == 1:
graph[a][b] = t
else:
graph[a][b] = x
graph = floyd(graph,city)
m = int(stdin.readline())
for _ in range(m):
a,b = map(int,stdin.readline().split())
print(graph[a][b])
그게 그거 아니냐 생각하고 생각없이 min() max()함수 써왔는데 그게 그거가 아닌가보다
Why is max() function so much slower when comparing 2 elements vs direct comparison with an if statement?
By running the below code I get for direct comparison with an if statement almost 4x the speed vs using the max function. I am trying to understand the reason behind this. comparison : 0.63s, max...
stackoverflow.com
min(), max()함수가 단순히 >으로 비교하는것보다 하는 일이 더 많아서 시간 차이가 생기나보다
근데 원소 수가 많아질수록 시간 차이가 줄어든다는게 설명인데 정말 그런가
원소 100개인 리스트 사용해보니까 오히려 min()함수가 압도적으로 빠름
아무튼 조금의 디테일이 의외로 결정적일수 있다는걸 알려주는거라고 해야할까
플로이드 워셜 알고리즘 if문으로 바꿔서 수정해야하나.. 허허
11404번: 플로이드
첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가
www.acmicpc.net
플로이드 워셜을 구현하는 연습문제다.
graph를 구성해서 O(N)으로 먼저 (i,i)는 못가니까 0으로 채워넣고
a에서 b로 가는 가중치 c를 입력받으면서 graph[a][b]값을 최솟값으로 갱신시켜나가고..
여기서 최솟값으로 갱신시켜나간 이유는... 문제에서 "a에서 b로 가는 간선이 하나가 아닐 수 있다"라고 명시해서 그렇다
하나라는게 확실하면 graph[a][b] = c로 하면 되겠지
플로이드 워셜 알고리즘을 수행한다
from sys import stdin
n = int(stdin.readline())
m = int(stdin.readline())
INF = 1000000000000000000
graph = [[INF]*(n+1) for _ in range(n+1)]
for i in range(n+1):
graph[i][i] = 0
for _ in range(m):
a,b,c = map(int,stdin.readline().split())
if graph[a][b] > c:
graph[a][b] = c
for k in range(1,n+1):
for a in range(1,n+1):
for b in range(1,n+1):
graph[a][b] = min(graph[a][b],graph[a][k]+graph[k][b])
for i in range(1,n+1):
for j in range(1,n+1):
if graph[i][j] == INF:
print(0,end=' ')
else:
print(graph[i][j], end= ' ')
print()
예전에 배운 알고리즘 그대로 적용한거인데 min()함수 써서 해가지고 여기도 min()함수 사용했는데
이게 0.7초더라
for k in range(1,n+1):
for a in range(1,n+1):
for b in range(1,n+1):
graph[a][b] = min(graph[a][b],graph[a][k]+graph[k][b])
근데 저 min()을 if문 비교로 바꿔보니.. 0.3초더라고.. 절반이 줄어든다.
from sys import stdin
n = int(stdin.readline())
m = int(stdin.readline())
INF = 1000000000000000000
graph = [[INF]*(n+1) for _ in range(n+1)]
for i in range(n+1):
graph[i][i] = 0
for _ in range(m):
a,b,c = map(int,stdin.readline().split())
if graph[a][b] > c:
graph[a][b] = c
for k in range(1,n+1):
for a in range(1,n+1):
for b in range(1,n+1):
if graph[a][b] > graph[a][k] + graph[k][b]:
graph[a][b] = graph[a][k]+graph[k][b]
for i in range(1,n+1):
for j in range(1,n+1):
if graph[i][j] == INF:
print(0,end=' ')
else:
print(graph[i][j], end= ' ')
print()
여담으로 플로이드 워셜 알고리즘 수행하는 부분을 floyd()함수 정의해서 사용해보면 0.2초정도..?
from sys import stdin
def floyd(graph):
for k in range(1,n+1):
for a in range(1,n+1):
for b in range(1,n+1):
if graph[a][b] > graph[a][k] + graph[k][b]:
graph[a][b] = graph[a][k]+graph[k][b]
return graph
n = int(stdin.readline())
m = int(stdin.readline())
INF = 1000000000000000000
graph = [[INF]*(n+1) for _ in range(n+1)]
for i in range(n+1):
graph[i][i] = 0
for _ in range(m):
a,b,c = map(int,stdin.readline().split())
if graph[a][b] > c:
graph[a][b] = c
graph = floyd(graph)
for i in range(1,n+1):
for j in range(1,n+1):
if graph[i][j] == INF:
print(0,end=' ')
else:
print(graph[i][j], end= ' ')
print()
아무튼 원소 수가 적을때 min()함수를 if문 비교로 바꾸기만 해도 꽤 많은 시간 이득을 볼 수 있다
'알고리즘 > 최단거리 알고리즘' 카테고리의 다른 글
| 특정 위치까지는 함께 이동하고 나머지는 따로 이동할 때 최단거리 구하기 (0) | 2024.03.16 |
|---|---|
| 최단거리가 k의 배수가 되는 경로를 찾는 다익스트라 알고리즘 (0) | 2023.08.02 |
| 우선순위가 2개 이상인 다익스트라 알고리즘 연습 (0) | 2023.07.18 |
| 다익스트라를 응용해서 minimum bottleneck path 문제 기본 배우기 (0) | 2023.07.15 |
| 코딩테스트 복기 - 최단거리를 가장 빠르게 구할 수 있는 0-1 BFS 알고리즘 (0) | 2023.05.22 |
