자바 배열 순서

Question

https://school.programmers.co.kr/learn/courses/30/lessons/42897이 문제를 자바로 풀다가 2차원 배열로 풀었을 때, 한 경우는 시간초과, 하나는 정상 통과가 되서 우연인지 아니면 어떤 원리가 있어서 그런건지 궁금해서 남깁니다.int[][] dp &#61; new int[2][N]; -> 통과int[][] dp &#61; new int[N][2]; -> 시간초과이렇게 나오는데, 나머지 과정은 정말 다 같습니다. 다른 언어로 해도 그런가 싶어서 C&#43;&#43;로 해봤는데 둘다 통과가 되더라고요?왜 그런건지 알 수 있을까요?? &#96;&#96;&#96; int N &#61; money.length; int[][] dp &#61; new int[2][N]; -------다른 점이 이 부분 입니다. dp[0][0] &#61; money[0]; dp[0][1] &#61; money[1] > money[0] ? money[1] : money[0]; dp[1][1] &#61; money[1]; for (int i &#61; 2; i < N - 1; i&#43;&#43;) { dp[0][i] &#61; dp[0][i-1] >&#61; dp[0][i-2] &#43; money[i] ? dp[0][i-1] : dp[0][i-2] &#43; money[i]; dp[1][i] &#61; dp[1][i-1] >&#61; dp[1][i-2] &#43; money[i] ? dp[1][i-1] : dp[1][i-2] &#43; money[i]; } dp[1][N-1] &#61; dp[1][N-2] >&#61; dp[1][N-3] &#43; money[N-1] ? dp[1][N-2] : dp[1][N-3] &#43; money[N-1]; &#96;&#96;&#96;

머리가아파요 · Answer

코드가 다를 확률이 높음. 둘을 바꾸면 다른 부분도 다 바껴야 함...majority에 따른 성능 차이는 분명히 있지만 코테 합불을 가를 정도로 극단적이지는 않음....

빙수빙수 · Answer

여러가지 이유를 생각해볼 수 있는데,첫번째는 GC때문인거 같네요. 첫번째 줄은 N이 커짐에 따라 할당해야하는 객체의 수가 늘어나지 않지만, 두번째 줄은 N이 커짐에 따라 할당해야하는 배열 객체수가 늘어납니다. 할당이라는 것이, 배우셨는지는 모르겠지만 그 간단함에 비해서 필요한 연산이 많습니다. int 배열이기 때문에 배열 이외의 추가적인 할당은 없기 때문에, 이 차이는 매우 큽니다. 이 부분은 C&#43;&#43;에는 없고 자바 등의 메모리 관리 언어에만 있습니다.두번째는 배열이 조각남에 따라 접근시에 캐시미스가 일어날 수 있기 때문입니다.물론, 이건 순수히 추측의 영역이고, JMH로 실험을 몇개 돌려보지 않는 이상 정확히 알 수 없을 수도 있습니다.

한안아 · Answer

잘 모르겠고요.동일한 프로그램을 실행해도 PC 상태에 따라 성능이 달라집니다.테스트를 여러번 해보세요.&#61;&#61;> 아래를 보면 데이터 연속성에 의한 캐시 문제로 처음소스가 효율이 좋다고 하네요.주의 : GPT놈이 구라를 쳤을 가능성도 있음.캐시 지역성 (Cache Locality): 캐시는 데이터를 빠르게 읽어오기 위한 임시 저장소입니다. 연속된 메모리에 접근할 때 성능이 향상됩니다. 따라서 첫 번째 예시에서 dp &#61; new int[2][N]은 이러한 캐시 지역성을 더 잘 활용할 수 있습니다.행 기반 메모리 접근 (Row-major order): 자바의 2차원 배열은 행 기반으로 저장됩니다. 즉, 연속된 행의 요소들이 연속된 메모리 공간에 저장됩니다. 따라서 첫 번째 예시에서는 이러한 구조를 활용하여 성능을 향상시킬 수 있습니다.캐시 효율 (Cache Efficiency): 캐시가 더 효과적으로 사용될 수 있도록 데이터를 구성하는 것이 중요합니다. 연속된 배열 요소에 접근하는 것이 성능 향상에 도움이 됩니다.따라서 int[][] dp &#61; new int[2][N]의 경우, 캐시 효율적으로 연속된 메모리에 접근하므로 성능이 더 좋을 수 있습니다. 반면 int[][] dp &#61; new int[N][2]의 경우, 각 행이 연속된 메모리에 저장되지 않아 캐시 효율이 떨어져 시간이 더 걸릴 수 있습니다.물론 실제로는 상황에 따라 다를 수 있습니다. 특정한 사용 사례나 하드웨어 환경에서는 성능 차이가 미미하거나 반대의 결과를 보일 수 있습니다. 그러므로 성능을 비교할 때는 항상 실제 상황에서 테스트하는 것이 가장 좋습니다.

자바 배열 순서

3개의 답변

Q&A 목록