집 > 기사 > 백엔드 개발 > Python 집합 유형에 대한 자세한 그래픽 설명(목록 튜플 사전 집합 생성기)

Python 집합 유형에 대한 자세한 그래픽 설명(목록 튜플 사전 집합 생성기)

高洛峰원래의: 2017-03-20 10:24:001948검색

Python 내장 컬렉션 유형에는 list, tuple, set 및 dict가 포함됩니다.

리스트: 배열과 유사하지만 배열보다 강력하며 인덱싱, 슬라이싱, 검색, 추가 등의 기능을 지원합니다.

튜플 튜플: 함수는 리스트와 비슷하지만 일단 생성되면 길이와 요소가 가변적이지 않아(요소의 요소는 여전히 가변적임) 좀 더 가볍고 안전한 리스트인 것 같습니다.

Dictionary dict: 해시 테이블과 동일한 속성을 갖는 키-값 쌍 구조의 해시 테이블입니다. key는 순서가 없고 반복되지 않으며 추가, 삭제, 수정이 편리합니다. 그리고 빠르다.

세트: 순서가 없고 값이 없는 딕셔너리입니다. Java의 HashSet은 HashMap을 사용하여 구현됩니다. 결국, 세트에는 이와 같은 것이 필요하지 않습니다. 값이므로 많은 포인터가 생략됩니다.

생성기:

는 생성기 또는 Python의 특수 데이터 유형 , 실제로는 데이터 구조가 아니며, 알고리즘과 임시 상태만 포함하고 반복 기능을 갖습니다.

먼저 메모리 사용량을 살펴보고 생성기를 사용하여 세트, 딕셔너리, 생성기, 튜플 및 100,000개 요소 목록을 생성합니다. dict, set, list, tuple이 소모하는 메모리는 순차적으로 줄어들며, 생성되는 객체의 크기도 동일합니다. 생성기는 데이터 테이블을 생성하지 않으므로 메모리를 소비할 필요가 없습니다.

import sys
from memory_profiler import profile

@profile
def create_data(data_size):
    data_generator = (x for x in xrange(data_size))
    data_set = {x for x in xrange(data_size)}
    data_dict = {x:None for x in xrange(data_size)}
    data_tuple = tuple(x for x in xrange(data_size))
    data_list = [x for x in xrange(data_size)]
    return data_set, data_dict, data_generator, data_tuple, data_list

data_size = 100000
for data in create_data(data_size):
    print data.__class__, sys.getsizeof(data)

Line #    Mem usage    Increment   Line Contents
================================================
    14.6 MiB      0.0 MiB   @profile
                            def create_data(data_size):
    14.7 MiB      0.0 MiB       data_generator = (x for x in xrange(data_size))
    21.4 MiB      6.7 MiB       data_set = {x for x in xrange(data_size)}
    29.8 MiB      8.5 MiB       data_dict = {x:None for x in xrange(data_size)}
    33.4 MiB      3.6 MiB       data_tuple = tuple(x for x in xrange(data_size))
    38.2 MiB      4.8 MiB       data_list = [x for x in xrange(data_size)]
    38.2 MiB      0.0 MiB       return data_set, data_dict, data_generator, data_tuple, data_list
 
<type &#39;set&#39;> 4194528
<type &#39;dict&#39;> 6291728
<type &#39;generator&#39;> 72
<type &#39;tuple&#39;> 800048
<type &#39;list&#39;> 824464

검색 성능을 다시 살펴보겠습니다. dict와 set은 일정한 검색 시간(O(1))이고 list와 set입니다. 튜플은 선형 검색 시간(O(n))이며 생성기를 사용하여 지정된 크기 요소의 객체를 생성하고 무작위로 생성된 숫자를 사용하여 다음을 찾습니다.

import time
import sys
import random
from memory_profiler import profile

def create_data(data_size):
    data_set = {x for x in xrange(data_size)}
    data_dict = {x:None for x in xrange(data_size)}
    data_tuple = tuple(x for x in xrange(data_size))
    data_list = [x for x in xrange(data_size)]
    return data_set, data_dict, data_tuple, data_list

def cost_time(func):
    def cost(*args, **kwargs):
        start = time.time()
        r = func(*args, **kwargs)
        cost = time.time() - start
        print &#39;find in %s cost time %s&#39; % (r, cost)
        return r, cost  #返回数据的类型和方法执行消耗的时间
    return cost

@cost_time
def test_find(test_data, data):
    for d in test_data:
        if d in data:
            pass
    return data.__class__.__name__

data_size = 100
test_size = 10000000
test_data = [random.randint(0, data_size) for x in xrange(test_size)]
#print test_data
for data in create_data(data_size):
    test_find(test_data, data)

输出：
----------------------------------------------
find in <type &#39;set&#39;> cost time 0.47200012207
find in <type &#39;dict&#39;> cost time 0.429999828339
find in <type &#39;tuple&#39;> cost time 5.36500000954
find in <type &#39;list&#39;> cost time 5.53399991989

100개 요소의 컬렉션, 각각 1000W 검색 . 차이는 매우 분명합니다. 그러나 이러한 난수는 모두 컬렉션에서 찾을 수 있습니다. 생성된 숫자의 절반은 찾을 수 있고 절반은 찾을 수 없도록 난수 방식을 수정합니다. 최악의 검색 예가 절반일 때 리스트와 튜플의 성능이 더욱 저하된다는 인쇄된 정보를 보면 알 수 있습니다.

def randint(index, data_size):
    return random.randint(0, data_size) if (x % 2) == 0 else random.randint(data_size, data_size * 2)

test_data = [randint(x, data_size) for x in xrange(test_size)]

输出：
----------------------------------------------
find in <type &#39;set&#39;> cost time 0.450000047684
find in <type &#39;dict&#39;> cost time 0.397000074387
find in <type &#39;tuple&#39;> cost time 7.83299994469
find in <type &#39;list&#39;> cost time 8.27800011635

요소 수가 10개에서 500개로 증가합니다. 매번 100,000번 검색하는 데 소요되는 시간에 대한 통계를 사용하여 시간 소비 곡선에 맞게 결과는 다음과 같습니다. dict와 set에 요소 수는 항상 있습니다. 요소가 증가함에 따라 dict와 tuple은 선형 증가 시간을 보여줍니다.

import matplotlib.pyplot as plot
from numpy import *

data_size = array([x for x in xrange(10, 500, 10)])
test_size = 100000
cost_result = {}
for size in data_size:
    test_data = [randint(x, size) for x in xrange(test_size)]
    for data in create_data(size):
        name, cost = test_find(test_data, data) #装饰器函数返回函数的执行时间
        cost_result.setdefault(name, []).append(cost)

plot.figure(figsize=(10, 6))
xline = data_size
for data_type, result in cost_result.items():
    yline = array(result)
    plot.plot(xline, yline, label=data_type)

plot.ylabel(&#39;Time spend&#39;)
plot.xlabel(&#39;Find times&#39;)

plot.grid()

plot.legend()
plot.show()