[Time Complexity] Python - Find Value in List vs Set vs Dict

[시간 복잡도] 파이썬 - List vs Set vs Dict 에서 Value 찾기

code n = 100000 n = 1000000 n = 1000000 Time Complexity
x in list 0.000494 0.019270
0.235368
O(n)
list.index(x) 0.000537
0.020288
0.246275
O(n)
for a in list:  if(a==x) 0.010289
0.107806
1.036934
O(n)
x in set 0.000002
0.000002
0.000006
O(1)
list to set 0.115826
0.066516
0.716471
 
x in dict 0.000005
0.000005
0.000004 O(1)
list to dict 0.147385
0.223651
2.232983  

결론

1. Set, Dict 에서 value를 찾을 경우에 시간 복잡도 O(1)로 가장 빠름

2. 다만 List to Set/Dict conversation이 필요한 경우에 일정 값 이하의 n에서는 List를 사용

[Time Complexity] Python - Deque vs List performance comparison (append, appendleft, pop, popleft)

[시간 복잡도] 파이썬 - Deque vs List 퍼포먼스 비교 (append, appendleft, pop, popleft)

code n = 10000 n = 100000 n = 1000000 Time Complexity
list.append() 0.0010249615 0.0093748569 0.0974259377 O(1)
deque.append() 0.0012080669 0.0113868713 0.1131999493 O(1)
list.insert(0,0) 0.0436980724 4.2723989487 430.9322969913 O(n)
deque.appendleft() 0.0010690689 0.0137970448 0.1067051888 O(1)
list.pop() 0.0013749599 0.0134758949 0.1310129166 O(1)
deque.pop() 0.0009977818 0.0100331306 0.1004290581 O(1)
list.pop(0) 0.0262870789 3.5589528084 372.6231980324 O(n)
deque.popleft() 0.0009810925 0.0101020336 0.0985748768 O(1)

결론

1. append와 pop의 경우에는 List와 Deque 둘 다 Time Complexity가 O(n)으로 별차이가 없음

2. appendleftpopleft의 경우에 Deque가 훨씬 빠름

[Time Complexity] Python - Numpy vs List of zeros declaration

[시간 복잡도] 파이썬 - Numpy vs List의 제로 배열 선언 비교

code n = 10000000 n = 100000000 n = 1000000000 Time Complexity
[0] * n 0.0831630230  0.8130910397 8.0924339294 O(n)
[0 for i in xrange(n)] 0.3735442162  3.7914631367  37.1647899151  O(n)
x = [] 
for i in xrange(n):
    x.append(0)
0.9481530190  9.4668169022  94.6755440235  O(n)
numpy.zeros((n,)) 0.0000300407 0.0000290871  0.0000340939  O(1)
numpy.full((n,),0) 0.0420970917 0.4114339352 4.0288629532 O(n)
numpy to list 0.5932991505 5.9227490425 59.9193470478 O(n)

결론

1. 제로 리스트 선언은 numpy.zeros가 가장 빠름

2. 다만 numpy to list 시간 복잡도가 O(n)이므로 리스트로 변환이 필요시에 [0] * n 가 가장 빠름

전자우편 주소:
/^[a-z0-9_+.-]+@([a-z0-9-]+\.)+[a-z0-9]{2,4}$/

URL:
/^(file|gopher|news|nntp|telnet|https?|ftps?|sftp):\/\/([a-z0-9-]+\.)+[a-z0-9]{2,4}.*$/

HTML 태그 - HTML tags:
/\<(/?[^\>]+)\>/

전화 번호 - 예, 123-123-2344 혹은 123-1234-1234:
/(\d{3}).*(\d{3}).*(\d{4})/

날짜 - 예, 3/28/2007 혹은 3/28/07:
/^\d{1,2}\/\d{1,2}\/\d{2,4}$/

jpg, gif 또는 png 확장자를 가진 그림 파일명:
/([^\s]+(?=\.(jpg|gif|png))\.\2)/

1부터 50 사이의 번호 - 1과 50 포함:
/^[1-9]{1}$|^[1-4]{1}[0-9]{1}$|^50$/

16 진수로 된 색깔 번호:
/#?([A-Fa-f0-9]){3}(([A-Fa-f0-9]){3})?/

적어도 소문자 하나, 대문자 하나, 숫자 하나가 포함되어 있는 문자열(8글자 이상 15글자 이하) - 올바른 암호 형식을 확인할 때 사용될 수 있음:
/(?=.*\d)(?=.*[a-z])(?=.*[A-Z]).{8,15}/






숫자만 가능 : [ 0 ~ 9 ] 주의 : 띄어쓰기 불가능
/^[0-9]+$/

 

 이메일 형식만 가능

/^([\w-]+(?:\.[\w-]+)*)@((?:[\w-]+\.)*\w[\w-]{0,66})\.([a-z]{2,6}(?:\.[a-z]{2})?)$/

 

한글만 가능 : [ 가나다라 ... ] 주의 : ㄱㄴㄷ... 형식으로는 입력 불가능 , 띄어쓰기 불가능
/^[가-힣]+$/

 

한글,띄어쓰기만 가능 : [ 가나다라 ... ] 주의 : ㄱㄴㄷ... 형식으로는 입력 불가능 , 띄어쓰기 가능
/^[가-힣\s]+$/

 

영문만 가능 :
/^[a-zA-Z]+$/

 

 영문,띄어쓰기만 가능
/^[a-zA-Z\s]+$/

 

전화번호 형태 : 전화번호 형태 000-0000-0000 만 받는다. ]
/^[0-9]{2,3}-[0-9]{3,4}-[0-9]{4}$/

 

도메인 형태, http:// https:// 포함안해도 되고 해도 되고
/^(((http(s?))\:\/\/)?)([0-9a-zA-Z\-]+\.)+[a-zA-Z]{2,6}(\:[0-9]+)?(\/\S*)?$/

 

도메인 형태, http:// https:// 꼭 포함
/^((http(s?))\:\/\/)([0-9a-zA-Z\-]+\.)+[a-zA-Z]{2,6}(\:[0-9]+)?(\/\S*)?$/

 

도메인 형태, http:// https:// 포함하면 안됨
/^[^((http(s?))\:\/\/)]([0-9a-zA-Z\-]+\.)+[a-zA-Z]{2,6}(\:[0-9]+)?(\/\S*)?$/

 

한글과 영문만 가능
/^[가-힣a-zA-Z]+$/;

 

숫자,알파벳만 가능
/^[a-zA-Z0-9]+$/;

 

주민번호, -까지 포함된 문자열로 검색
/^(?:[0-9]{2}(?:0[1-9]|1[0-2])(?:0[1-9]|[1,2][0-9]|3[0,1]))-[1-4][0-9]{6}$/


Jquery 에서는 $.test() 메서드로,

 PHP 에서는 preg_match() 함수로 사용



정규표현식의 기본 문법

정규표현식은 소프트웨어에 따라서 방식이나 지원 범위가 다를 수 있습니다.

^TheThe로 시작하는 문자열
of despair$of despair로 끝나는 문자열
^abc$abc로 시작하고 abc로 끝나는 문자열 (abc 라는 문자열도 해당됨)
noticenotice가 들어 있는 문자열


ab*a 다음에 b가 0개 이상 (a, ab, abbb 등등)
ab+a 다음에 b가 1개 이상 (ab, abbb 등등)
ab?a 다음에 b가 있거나 없거나 (ab 또는 a)


ab{2}a 다음에 b가 2개 있는 문자열 (abb)
ab{2,}a 다음에 b가 2개 이상 (abb, abbbb 등등)
ab{3,5}a 다음에 b가 3개에서 5개 사이 (abbb, abbbb, 또는 abbbbb)

*+?는 각각 {0,}{1,}{0,1}과 같습니다.

( )는 문자열을 묶음 처리할 때 사용
a(bc)*a 다음에 bc가 0개 이상 (묶음 처리)
a(bc){1,5}a 다음에 bc가 1개에서 5개 사이


hi|hellohi hello가 들어 있는 문자열
(b|cd)efbef 또는 cdef
(a|b)*ca와 b가 섞여서 여러번 나타나고 그뒤에 c가 붙어있는 패턴


. (점)임의의 한 문자
^.{3}$3문자로만 되어 있는 문자열


[ ]괄호 안에 있는 내용 중 임의의 한 문자
[^ ]첫문자로 ^를 쓰면 괄호 내용의 부정. 즉 괄호 안에 포함되지 않는 한 문자
[ab]또는 b (a|b 와 동일한 표현)
[a-d]소문자 a에서 d까지 (a|b|c|d 또는 [abcd] 와 동일)
^[a-zA-Z]영문자로 시작하는 문자열
[0-9]%% 문자 앞에 하나의 숫자가 붙어 있는 패턴
%[^a-zA-Z]%두 % 문자 사이에 영문자가 없는 패턴


특수 문자 자체를 검색하기 및 사용하기
\^^\..
\[[\$$
\((\))
\||\**
\++\??
\{{\\\
\n줄넘김 문자\r리턴 문자
\w알파벳과 _ (언더바)\W알파벳과 _ 가 아닌 것
\s빈 공간(space)\S빈 공간이 아닌 것
\d숫자\D숫자가 아닌 것
\b단어와 단어 사이의 경계\B단어 사이의 경계가 아닌 것
\tTab 문자\xnn16진수 nn에 해당하는 문자

[ ] 안에서는 특수 문자가 모두 효력을 잃게 됩니다.

검색 + 치환을 위한 하부식(부분식)
( )로 둘러싼 부분은 각각 하나의 덩어리로 취급해서,
검색시 ( ) 안에 해당되는 내용들을 변경할 내용에서 그대로 가져다 이용할 수 있습니다.
검색된 각각의 ( )안에 해당되는 내용은 변경할 내용에서 $1, $2, .. 등으로 지정해서 쓸 수 있습니다.
예제) mp3파일 이름 바꾸기
검색 : (.*) - (.*)\.mp3 .*은 길이에 상관없이 임의의 문자열, \.은 점
치환 : $2 - $1.mp3 앞에서 검색한 ( )안에 해당되는 내용끼리 순서 바꾸기
ex) "제목 - 연주자.mp3" Þ "연주자 - 제목.mp3"
앞에서 정의한 하부식을 다시 활용하기 (제가 잘못 이해한 것일 수도 있는데)
\n은 ( ) 하부식 중에서 n번째 하부식을 가리킵니다.
예제) (.+)\1+
\1로 되어 있으니까 첫번째 부분식 (.+)를 가리킵니다. 위 내용을 해석하자면, 일단 (.+)가 있으니까 이에 해당되는 내용을 찾고, \1+이 있으니까 첫번째 부분식 (.+)와 똑같은 내용이 그 뒤에 1번 이상 있는 문자열을 찾습니다.
예제) abab같은 문자열이 위에 해당되는데, 일단 (.+) 즉 임의의 문자열 ab를 찾고 그 뒤에 \1+로 첫번째 부분식을 다시 1번 이상 있는 것을 찾으니까 뒤의 ab가 이에 해당합니다.


변경자 ? 검색 방식 변경
(?i)대소문자 무시 (기본값)
(?-i)대소문자 구분
(?g)"greedy" 모드로 전환 (기본값)
(?-g)"greedy" 모드 해제, 따라서 "+"는 "+?"과 동일한 것으로 인식



  • 작성한 정규식을 바로 확인해 볼 수 있는 곳.
    regexpal.com
  • 정규식 문법
    바로가기


  • 출처: http://gocoding.tistory.com/93 [Developer Factory]

    파이썬 버전 업데이트 이후에 yum이 다음 메시지와 함께 동작이 안되어서 재설치를 하였다.

    yum-no-module-named-yum

    centos 버전에 따라서 centos-VERSION 폴더에서

    i386(32비트) / x86_64(64비트) 확인을 잘해서 package를 설치한다.

    http://mirror.centos.org/centos-6/6/os/x86_64/Packages/


    # rpm -e --nodeps yum
    # rpm -e --nodeps python

    # rpm -Uvh --nodeps --force http://mirror.centos.org/centos-6/6/os/x86_64/Packages/${RPM_FILE_NAME}

    ## RPM_FILE_NAMES

    sudo rpm -Uvh --nodeps --force http://mirror.centos.org/centos-6/6/os/x86_64/Packages/yum-3.2.29-81.el6.centos.noarch.rpm

    sudo rpm -Uvh --nodeps --force http://mirror.centos.org/centos-6/6/os/x86_64/Packages/python-2.6.6-66.el6_8.x86_64.rpm

    sudo rpm -Uvh --nodeps --force http://mirror.centos.org/centos-6/6/os/x86_64/Packages/python-devel-2.6.6-66.el6_8.x86_64.rpm

    sudo rpm -Uvh --nodeps --force http://mirror.centos.org/centos-6/6/os/x86_64/Packages/yum-plugin-fastestmirror-1.1.30-41.el6.noarch.rpm

    sudo rpm -Uvh --nodeps --force http://mirror.centos.org/centos-6/6/os/x86_64/Packages/yum-metadata-parser-1.1.2-16.el6.x86_64.rpm

    sudo rpm -Uvh --nodeps --force http://mirror.centos.org/centos-6/6/os/x86_64/Packages/python-libs-2.6.6-66.el6_8.x86_64.rpm

    yum list python 쳐보면 잘 동작한다.


    - Reference

    http://alloe.tistory.com/64

    pip 에서 버전 충돌이 문제인지 다음과 같은 에러 메세지로 작동이 잘 안되어서 재설치를 하였다.

    pkg_resources.DistributionNotFound: The 'pip==8.1.2' distribution was not found and is required by the application


    wget https://pypi.python.org/packages/e7/a8/7556133689add8d1a54c0b14aeff0acb03c64707ce100ecd53934da1aa13/pip-8.1.2.tar.gz
    
    tar -xzvf pip-8.1.2.tar.gz
    
    cd pip-8.1.2
    
    sudo python setup.py install


    Reference : https://github.com/pypa/pip/issues/3776

    정규식 패턴 표현

    패턴설명예제
    ^이 패턴으로 시작해야 함^abc : abc로 시작해야 함 (abcd, abc12 등)
    $이 패턴으로 종료되어야 함xyz$ : xyz로 종료되어야 함 (123xyz, strxyz 등)
    [문자들]문자들 중에 하나이어야 함. 가능한 문자들의 집합을 정의함.[Pp]ython : "Python" 혹은 "python"
    [^문자들][문자들]의 반대로 피해야할 문자들의 집합을 정의함.[^aeiou] : 소문자 모음이 아닌 문자들
    |두 패턴 중 하나이어야 함 (OR 기능)a | b : a 또는 b 이어야 함
    ?앞 패턴이 없거나 하나이어야 함 (Optional 패턴을 정의할 때 사용)\d? : 숫자가 하나 있거나 없어야 함
    +앞 패턴이 하나 이상이어야 함\d+ : 숫자가 하나 이상이어야 함
    *앞 패턴이 0개 이상이어야 함\d* : 숫자가 없거나 하나 이상이어야 함
    패턴{n}앞 패턴이 n번 반복해서 나타나는 경우\d{3} : 숫자가 3개 있어야 함
    패턴{n, m}앞 패턴이 최소 n번, 최대 m 번 반복해서 나타나는 경우 (n 또는 m 은 생략 가능)\d{3,5} : 숫자가 3개, 4개 혹은 5개 있어야 함
    \d숫자 0 ~ 9\d\d\d : 0 ~ 9 범위의 숫자가 3개를 의미 (123, 000 등)
    \w문자를 의미\w\w\w : 문자가 3개를 의미 (xyz, ABC 등)
    \s화이트 스페이스를 의미하는데, [\t\n\r\f] 와 동일\s\s : 화이트 스페이스 문자 2개 의미 (\r\n, \t\t 등)
    .뉴라인(\n) 을 제외한 모든 문자를 의미.{3} : 문자 3개 (F15, 0x0 등)


    출처 : http://pythonstudy.xyz/python/article/401-%EC%A0%95%EA%B7%9C-%ED%91%9C%ED%98%84%EC%8B%9D-Regex

    참조 : http://www.nextree.co.kr/p4327/

    # 1. Install a package with repository for your system:
    # On CentOS, install package centos-release-scl available in CentOS repository:
    $ sudo yum install centos-release-scl
    
    # On RHEL, enable RHSCL repository for you system:
    $ sudo yum-config-manager --enable rhel-server-rhscl-7-rpms
    
    # 2. Install the collection:
    $ sudo yum install python27
    
    # 3. Start using software collections:
    $ scl enable python27 bash


    - add source to the path

     cp /opt/rh/python27/root/usr/lib/python2.7 /usr/lib/python2.7

     cp /opt/rh/python27/root/usr/bin/python2.7 /usr/bin/

     cp /opt/rh/python27/root/usr/bin/python2.7-config /usr/bin/

     ln -snf /usr/bin/python2.7

     ln -snf /usr/bin/python2.7-config /usr/bin

     cp /opt/rh/python27/root/usr/lib64/libpython2.7.so /usr/lib64/

     cp /opt/rh/python27/root/usr/lib64/libpython2.7.so.1.0 /usr/lib64//usr/lib64/

     cp python27/root/usr/bin/pip2.7 /usr/bin/

     cp /opt/rh/python27/root/usr/bin/easy_install-2.7 /usr/bin/

     easy_install --upgrade pip


    [ref]

    https://github.com/h2oai/h2o-2/wiki/installing-python-2.7-on-centos-6.3.-follow-this-sequence-exactly-for-centos-machine-only

    https://www.softwarecollections.org/en/scls/rhscl/python27/

    'Programming > Python' 카테고리의 다른 글

    pip 설치 및 재설치  (0) 2018.10.22
    [python] 다양한 정규식 패턴 표현  (0) 2018.10.12
    [argparse] FLAGS parser 사용법  (0) 2017.08.24
    matplotlib.pyplot 설치하기  (0) 2017.08.24
    사용자 입력 / 옵션으로 입력 받기  (0) 2017.08.14

    How to use argparse  FLAGS




    apt-get update
    apt-get install python-tk -y (python3-tk : 버전3의 경우)

    * -y : 모든 설치 질문에 동의

    + Recent posts