[일반] 파이썬에서 dfs쓸때 visited

[지젼(gkrdls)]

visited 구현할 때 리스트로 구현했었는데

지피티가 set으로 구현하는게 더 빠르대여

왜그런거에요?

그냥 탐색하는게 set이 더 빨라서 그런건가요?

- dc official App

[익명(118.235)]

지피티 걸러라

[익명(apg2fwpfgsz5)]

지피티는 한입으로 두말할 수 있는애라서 일단 뭔가 정보를 말했다면 그게 내 경우에서 맞는지 의심부터 해봐야 함. 정답은 문제마다 다르다임. 만약 vis 갱신을 일부만 해도 된다면, list로 하는것보다 빠르게 작동하니까 일부만 채울 수 있는 set으로 하는게 더 빠르다고 말했다고 논리적으로 틀린말은 아님. 그런데 거의 대부분 set이 훨씬 느림. 해싱은 엄청나게 느린 O(1)이기 때문에, vis가 sparse하지 않을 것 같다면 list가 맞음. 그러므로 PS의 맥락에선 걍 list가 set보다 빠르다가 정답

[익명(apg2fwpfgsz5)]

이런식으로의 가능성을 의심하지 못할거 같으면 제발 gpt로 공부 ㄴㄴ

[지젼(gkrdls)]

좋은답변 감사합니다 - dc App

[익명(118.235)]

거의 대부분 훨씬 느리다? 동의 안 됨. 파이썬 오버헤드의 대부분은 객체를 오브젝트 담은 포인터로 관리하는 데서 옴. 특히나 작은 정수 hash에 넣으면 자기 자신임

[익명(apg2fwpfgsz5)]

그러네. 나도 파이썬의 배열 접근 자체가 엄청 느린걸 알고 있었는데, 그걸 해싱 자체가 느린것처럼 표현한게 있는듯.

[익명(apg2fwpfgsz5)]

배열 접근이 느리다라고 하는 개념을 더 확장해서 객체의 포인터의 관리가 느린거였다 라고보면 더 정확하게 이해가 되는듯. 지적 감사

[익명(49.165)]

뭔진 모르겠는데 gpt가 초보 망치는듯 - dc App