(※ 2010/5/13 보충 목록의 요소 수량을 수정한 경우)

배경.

며칠 전 Atcorder의 ABC 167에서는 다음 문제로 TLE가 연발됐다.
・ABC167D-Teleporter
거리를 순서대로 전화 전송하고 순환할 때 멈추고 나머지 횟수는
제가 눈치챘어요. 모로 찾으면 돼요.
순환하는 ⇔가 다시 한 번 같은 도시에 와서 ⇔가 방문한 도시의 명단에
이렇게 생각하면 돼요. 파이톤X in list에서 처리하는 데 시간이 걸려요.
그 결과 X in set로 대체하시면 됩니다.
속도가 바뀔지 안 바뀔지 신경 쓰여서 조사 결과를 정리했다.

이른바 set형

Python에서 인용 공식 문서
set 대상은 유일한hashable 대상의 무순서 수집입니다.일반적인 용도는 귀속 테스트, 서열에서 중복, 적집, 화집, 차집, 대칭차 (배타 논리와) 등 수학 연산을 제거하는 계산을 포함한다.
컬렉션은 xin set, len(set), forxin set을 지원하는 다른 모음과 같습니다.모음에는 순서가 없기 때문에 삽입된 순서와 요소의 위치를 기록하지 않습니다.따라서 집합은 색인, 슬라이딩, 기타 순서 행위를 지원하지 않습니다.
또한 여기.에서도 간단하고 알기 쉬운 특징을 정리했다.

같은 요소는 하나만 포함한다.

x in set, len(set), for x in set 같은list 작업을 수행할 수 있습니다.

뒤에서 요소 등 변경(tuple 변경 불가,list 변경 가능하기 때문에list에 가깝다)

집합 연산 가능

순서를 지키지 않기 때문에 처음에 넣은 것이 반드시 처음은 아니다

list 대비 "x in set"동작 초고속

중요한 것은 정렬이 반복되지 않은 상태에서 저장된 데이터 형식이다.
따라서 set형의 탐색은 이분 탐색을 이용하여 고속으로 변할 수 있다.

측정 조건

조사list형set형을 위해 다음과 같은 4가지 상황의 탐색을 조사했다.
번호 매기기
데이터 형식
데이터 순서
검색 방법
1list무작위
선형 검색
2list정렬됨
선형 검색
3list정렬됨
이분 탐색
4set(정렬됨)
(2분 탐색)
다른 조건을 동일하게 하기 위해

목록의 원소 수는 10^6달러이며 중복되지 않습니다.

탐색한 요소는 1$1\let\le10^6달러를 만족시킬 것입니다.(절대 발견)

랜덤으로 $10^2달러, $10^3달러, $10^4달러를 생성하여 각각 탐색합니다.

진행됐습니다.

소스 코드

main.py

import time
import random
from collections import deque

num = [i+1 for i in range(1000000)]
num_shaffle = random.sample(num, len(num))
num_set = set(num_shaffle)
#探す対象
target = [random.randint(1, 1000000) for i in range(10000)]

#list型線形探索またはset型
def search_seaquence(L):
    each_time = deque([])

    for i in range(10000):
        #startからelapsed_timeまでの時間差を計測
        start = time.time()
        target[i] in L
        elapsed_time = time.time() - start
        each_time.append(elapsed_time)

    return list(each_time)

#list型二分探索
def search_half(L):
    each_time = deque([])

    for i in range(10000):
        low = 0
        high = len(num) - 1
        start = time.time()

        while low <= high:
            mid = int((low + high) // 2)
            guess = L[mid]
            if guess == target[i]:
                break
            elif guess > target[i]:
                high = mid - 1
            else:
                low = mid + 1

        elapsed_time = time.time() - start
        each_time.append(elapsed_time)
    return list(each_time)


def cal_time(LIS, mode):
    print(mode)
    #合計時間
    sum_time = sum(LIS)
    print ("sum_time:{0}".format(sum_time) + "[sec]")

    return 0


#ランダムlist・線形探索
random_list = search_seaquence(num_shaffle)
cal_time(random_list, 'mode: random list')

#順列list・線形探索
seaquence_list_seq = search_seaquence(num)
cal_time(seaquence_list_seq, 'mode: seaquence list seaquence')

#順列list・二分探索
seaquence_list_half = search_half(num)
cal_time(seaquence_list_half, 'mode: seaquence list half')

#set探索
set_seek = search_seaquence(num_set)
cal_time(set_seek, 'mode: set')

결실

검색 방법
$10^2달러 합계 (sec)
$10^3$개 합계 (sec)
$10^4$개 합계 (sec)
무작위 선형 검색
$5.14$
$4.01\times 10$
$4.65\times 10^2$
정렬 목록 선형 검색
$1.13$
$8.36$
$1.29\times 10^2$
목록 정렬, 2분 검색
$3.46\times 10^{-3}$
$2.03\times 10^{-2}$
$1.16\times 10^{-1}$
set형
$8.44\times 10^{-5}$
$9.92\times 10^{-4}$
$5.45\times 10^{-3}$
무심결에 그것을 도표에 넣으려 했다.

(두 쌍의 도표.)
예상대로 그랬다면 이 주문은 달랐다.
나는 2분 탐색 주문이 $O(\logn)라고 생각하지만 느낌이 많이 다르다.
같은 2분 탐색set형이라도 10달러에서 4달러면 20배가량 빠르다니 의외다.
(자기 코드가 문제일 수도 있음)

[추기] 검색 목표의 요소수를 변경한 상황에 관하여

자세히 생각해 보면 검색 목적지list/set의 요소수를 바꾸지 않으면 주문의 효과가 보이지 않는다
또한, 검색 목표는 10^4달러로 고정되고, 검색 목표 목록의 요소 수는 10^4, 10^5, 10^6달러입니다.
나도 변경된 상황을 조사했다.
검색 방법\목록 요소 수
$10^4$개 합계 (sec)
$10^5달러 합계 (sec)
$10^6$개 합계 (sec)
무작위 선형 검색
$1.68$
$2.58\times 10$
$5.37\times 10^2$
정렬 목록 선형 검색
$9.26\times 10^{-1}$
$1.29\times 10$
$1.34\times 10^2$
목록 정렬, 2분 검색
$8.93\times 10^{-2}$
$1.75\times 10^{-1}$
$1.76\times 10^{-1}$
set형
$5.62\times 10^{-3}$
$4.02\times 10^{-3}$
$1.01\times 10^{-2}$

(두 쌍의 도표.)
주문서와 같다.잘 됐다.
2분 탐색은 오히려 시간을 줄일 수 있는데, 이는 랜덤으로 수색 목적지를 결정하기 때문이다.
이렇게 보면 로그의 주문 강도를 알 수 있습니다.

총결산

중복 데이터를 찾을 때X in list 사용할 수 없음(경고)
그리고 역시 2분 탐색은 빠르다
대량의 데이터에서 특정한 데이터가 있는지 찾을 때도 사용할 수 있다.
다만, set형은 인덱스 정보가 사라진다
나는 그 정보를 원할 때list에 따로 유지하는 방법이 필요하다는 것을 알았다.