Python dict indexing보다는 list indexing을 사용해야하는 이유

dict에서 key에 접근하는 시간과 list에서 index로 접근하는 시간은 O(1)인데, 

 

dict의 경우 hash로 구현되어 있어서 key,value가 많은 경우 hash collision으로 인해 list indexing보다 시간이 더 걸릴 수 있다.

 

만약 시간초과 판정을 받는다면 dict indexing을 list indexing으로 바꿀 수 있는지 체크해보자.

 

https://deepdata.tistory.com/960

문자열 해싱(hashing) 기본 개념 배우기

 

https://stackoverflow.com/questions/76649136/explain-worst-case-time-complexity-of-looking-up-item-in-python-set-and-dict-is

Explain worst case time complexity of looking up item in Python set and dict is O(n)

 

 

dict에 key1, key2를 저장하면 어떤 hash function에 의해 hash value가 동일한 값으로 게산된다면...

 

hash table은 이러한 hash collision을 풀어야한다.

 

파이썬의 경우 "separate chaining" 방법으로 hash collision을 해결하고 있는데

 

hash table의 각각 bucket이 아이템의 linked list를 포함하고 있다.

 

만약 hash value가 동일하다면, 동일한 bucket에 여러개의 item을 linked list로 포함하고 있게 된다.

 

만약 dict에서 key를 줘서 어떤 아이템에 접근하고자한다면, 파이썬은 해당 key의 hash value를 계산하고...

 

대응하는 bucket를 찾는다. 그리고 bucket의 linked list를 순회해서 해당 key에 맞는 원소를 내놓는다.

 

하지만 linked list에 여러개의 item이 있다면 파이썬은 원하는 item을 찾을때까지 linked list를 순회하게 된다.

 

따라서 dict에 여러개의 key가 저장될수록 이렇게 hash 충돌이 일어날 가능성이 높아지고, 

 

그런 경우 단일 bucket의 모든 아이템을 순회하여 찾다보니 시간이 오래걸릴 수 있다.

 

SW Expert Academy

SW Expert Academy

 

 

 A[0] = s이고 A[i] = (pA[i-1]+q) mod m으로 만들어지는 수열 A에 대하여, A의 주기를 찾는 문제

 

s,p,q,m이 고정되어있기 때문에... 

 

A[i]를 계산하다가 A[0],A[1],A[2],...,A[j] = k,....,A[i] = k로 나왔다고 하자.

 

그러니까 A[i] = k가 이전에 계산된 값 A[0],A[1],A[2],...A[i-1]중에 존재하는 값이 나온다면...

 

그 뒤부터는 반드시 반복된다.

 

왜냐하면 p,q,m이 고정되어있는 수이기 때문에 A[i-1]에 동일한 수를 넣으면 동일한 결과가 나오기 때문이다.

 

따라서 이전에 계산된 값을 dict에 key는 A[i], value는 index i를 저장해두었다가... 어느 순간 이미 계산된 값이 나온다면

 

그 계산된 값의 이전 index가 j이고 현재 처리해야할 index가 i라면???

 

j부터 i-1번까지 반복된다는 소리이다.

 

T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for t in range(1, T + 1):
    
    s,p,q,m = map(int,input().split())
    
    value = {}
    
    value[s] = 0
    
    i = 1
    
    while 1:
        
        s = (s*p+q)
        s %= m
        
        if value.get(s,-1) == -1:
            
            value[s] = i
        
        else:
            
            j = value[s]
            
            break
            
        i += 1
    
    print(f'#{t} {i-j}')

 

 

 

근데 시간초과가 난다.

 

분명히 맞는것 같은데 시간초과가 난다면 dict에 많은 값을 저장해서 hash 충돌로 인해 시간이 오래걸리는 것일 수 있다.

 

조금 생각해보면...

 

A[0],A[1],A[2],...,A[i-1]까지는 모두 서로 다른 값이 나와야하기 때문에...

 

이 값들을 index로 하는 배열을 이용해서 visited 배열 처리하듯이 해당 index에 1로 표시해두면 된다.

 

그리고 나서, A[i]를 계산하다가 visited[A[i]] != -1이 된다면, 이미 계산된 값이므로.. visited[A[i]] ~ i-1까지 반복된다는 소리이다. 

 

그러면 배열의 크기가 문제인데 mod m의 크기가 m이 1000000이라 나머지는 0~(1000000-1)까지이므로 적절한 크기이다.

 

T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for t in range(1, T + 1):
    
    s,p,q,m = map(int,input().split())
    
    value = [-1]*m
    
    value[s] = 0
    
    i = 1

    while 1:
        
        s = (s*p+q)
        s %= m
        
        if value[s] == -1:
            
            value[s] = i
        
        else:
           
            break
            
        i += 1
        
    print(f'#{t} {i-value[s]}')