2. map, filter, reduce for list

참고 블로그 : https://3months.tistory.com/338?category=753896
참고 사이트 : Intermediate python (http://book.pythontips.com/en/latest/)

MAP

  • map(lambda x: 새로운작업 , list)형태로 iterator를 반환하므로 lambda함수로 기존리스트를 수정한 리스트를
    next()로 하나씩 뽑아내거나, list()로 감싸서 한번에 가져올 수 있다.

map 없이새로운 리스트 반환하기

In [2]:
items = [1, 2, 3, 4, 5]
squared = []

for i in items:
    squared.append(i ** 2)

squared
Out[2]:
[1, 4, 9, 16, 25]

map을 사용하여 수정된 리스트를 한번에 반환

In [5]:
items = [1, 2, 3, 4, 5]
(lambda x : x**2, items)
Out[5]:
(<function __main__.<lambda>(x)>, [1, 2, 3, 4, 5])
In [20]:
square_map = map(lambda x : x**2, items)
square_map
Out[20]:
<map at 0x2e668f65f28>
In [37]:
next(map(lambda x : x**2, items))
Out[37]:
1
In [38]:
list(square_map)
Out[38]:
[1, 4, 9, 16, 25]
In [ ]:
 

Filter

  • filter(lambda x : x조건 , list ) 의 형태로 해당 list에서 조건을 만족시키는 요소만 뽑아올 수 있다. 마지막에는 list() 로 감싸줘야 리스트로 가져온다.
  • comprehension 시 if문을 넣는것과 동일 하다
In [39]:
list_ = range(-5, 5)
list_
Out[39]:
range(-5, 5)
In [42]:
filter( lambda x : x <0, list_)
Out[42]:
<filter at 0x2e668f7a4e0>
In [43]:
list( filter( lambda x : x <0, list_) )
Out[43]:
[-5, -4, -3, -2, -1]
In [45]:
## comprehenshion으로 구현
[ x for x in list_ if x<0 ]
Out[45]:
[-5, -4, -3, -2, -1]
In [ ]:
 

Reduce

  • reduce(lambda x, y : x + y, 순서형 자료-**(리스트, 튜플, 문자열)**)의 형태로 순서대로 x와 y에 차면서, 그결과는 x에 누적되고 새로운 순서의 요소는 y에 들어와서 계산.

1부터 100까지 for문으로 합 구하기

In [47]:
sum_ = 0
for i in range(1, 101):
    sum_ += i
    
sum_
Out[47]:
5050

1부터 100까지 reduce로 구하기

In [49]:
from functools import reduce

# (1) + (2) -> 3+ (3)  -> 6+ (4)
reduce(lambda x, y : x+y, range(1, 101))
Out[49]:
5050
In [50]:
# 다른 예제 - 순서형자료에 list대신 문자열
reduce(lambda x, y : y + x, 'abc')
Out[50]:
'cba'

numpy로 쉽게 구하기

  • 리스트들의 합을 np.sum()으로 구하기 마치 칼럼의 합을 쉽게 구하듯이
In [52]:
import numpy as np

np.sum( [x for x in range(1, 101)] )
Out[52]:
5050
In [ ]:
 

[중급1] comprehension 연습

2019. 5. 15. 16:52
1. comprehension - ifelse and if

for문 대체

In [2]:
temp = [2, 3, 4, 5]
temp
Out[2]:
[2, 3, 4, 5]
In [4]:
temp_new = list()
for i in temp:
    temp_new.append(i**2)
    
temp_new
Out[4]:
[4, 9, 16, 25]
In [6]:
temp_new_comp = [ i**2 for i in temp]
temp_new_comp
Out[6]:
[4, 9, 16, 25]

np.array()로 감싸면 어레이도 생성

In [9]:
import numpy as np

np.array( [ i**2 for i in temp] )
Out[9]:
array([ 4,  9, 16, 25])

for문 + if문 대체

  • if else 는 for 문 앞에
    [ 연산 if 조건 else 연산2 for문 ]
  • if만 있으 때는 for 문 뒤에
    [ 연산 for문 if 조건 ]
In [10]:
temp_new = list()

for i in temp:
    if i > 3:
        temp_new.append(i**2)
    else:
        temp_new.append(i)
        
temp_new
Out[10]:
[2, 3, 16, 25]
In [12]:
[ i**2 if i>3 \
else i \
for i in temp]
Out[12]:
[2, 3, 16, 25]
In [13]:
[ i**2 if i>3     else i      for i in temp]
Out[13]:
[2, 3, 16, 25]
In [15]:
[i**2 for i in temp if i>3]
Out[15]:
[16, 25]
In [ ]:
 

이 글은 코드잇의 알고리즘 강의와 오픈소스들을 참고하여 정리한 글입니다^^

알고리즘 평가의 2가지 기준

  1. 시간 : 빨리빨리 => 더 중요
  2. (메모리)공간 => 돈 주고 사면 됨

시간 복잡도(Time Complexity)

컴퓨터 과학에서 알고리즘의 시간평가 방법

  • 걸리는 시간으로는 판단x

  • 데이터(리스트의 원소 개수)가 많아질수록 걸리는시간이 얼마나 급격히 증가하는지
    예를 들어, 리스트의 원소 개수가 10개, 20개, 100개 -> 걸리는 시간 10, 20, 100초라면 -> 걸리는 시간 일정하게 증가

    그러나 알고리즘 B는 걸리는 시간 증가량이 급격하다

    A보다 B의 시간복잡도가 크다.! = A 알고리즘이 시간 복잡도가 더 작은 빠른 알고리즘

시간복잡도 계산을 위한 거듭제곱과 로그

거듭제곱 (Exponentiation)

  • 패턴을 따라가다보면 2의 -1승은 2의 0승(1) / 2 이므로 1/2 임을 알 수 있다.

로그 (Logarithms)

  • a는 밑수 b는 진수 라 부른다.

  • 편하게 생각하기 위해서는 a를 몇번(x) 곱해야 b가 나오는지로 생각한다.

  • 혹은 b를 a로 몇번 나누어야지 1이 되는가? 이다.

  • 컴퓨터 알고리즘 문제에서는 a가 2인 경우가 많다.

  • log2(16)은 16을 2로 몇번 나누어야(몇번 반토막내야) 1이 나오는지 생각해보면, 4번이다.

  • 예를 들어, 길이가 16인 리스트가 있다면, 총 4번 반토막 내어야한다.
    그림으로 예를 들면,

    이 상태에서 총 4번을 반토막 내야 1이 된다.



    log2( ) 를 lg로 쓰기도 한다.

시간복잡도 계산을 위한 1부터 n까지의 합

1부터 n까지의 합을 나열하여 T라 나타내고, 밑줄에 반대로 나열해놓고 더하자

2T = n * (n+1)
T= n(n+1) /2

점근 표기법 (Big-O Notation)

알고리즘은 일반적으로 걸리는시간(X) 인풋에 따라 걸리는 시간의 증가량에 의해 평가된다고 하였다.

하나의 알고리즘은 인풋에 따라 걸리는 시간이 달라진다.
즉, 알고리즘 소요시간 = 인풋크기(n)의 수식으로 나타낼 수 있다.

예를 들어, 아래 리스트를 인풋한다고 가정했을 때 리스트의 길이(n)라면,
알고리즘 소요시간 = 20n+40 or 2n^2 + 8n +157 일수도 있다.

그러나 n에 붙은 숫자들은 컴퓨터의 환경적인 것들에 의해 달라진다.

즉, 수식하나가지고는 하나의 알고리즘을 완벽하게 나타내지는 못한다.

그래서 컴퓨터 과학자들이 다같이 약속한 것이 점근표기법으로 알고리즘을 평가하자는 것이다.

점근표기법의 룰

  1. 만약, 소요시간이 20n+40이라면?

    • n의 영향력이 작은 40 삭제(영향력 젤 큰 항만 남김) -> n앞에 계수 삭제 -> n만남아서 O(n)으로 표기
    • 해당 알고리즘을 Big-O of n 알고리즘이라 부른다.
  2. 소요시간이 2차식이라면?

    • 가장 영향력이 큰 2n^2 만 남김 -> 앞에 계수 삭제 -> O(n^2)
    • Big O of n^2 알고리즘
  3. 20lg(n) + 60 ?

    • 60 없앰 -> 20없앰 -> O(lg(n))
    • Big O of lg(n) 알고리즘

점근표기법을 위와 같이 표기하는 이유?

점근 표기법의 핵심 : n이 엄청 크다고 가정 -> my)낮은차수와 계수는 무시된다.
절대적인 시간보다는 성장성을 보기위함이다.

  • n(input, 리스트의 길이, 원소의 개수)가 얼마 안되면, 굳이 좋은 알고리즘을 쓸 필요가 없다.
  • 골치 아픈 경우는, n이 엄청 컸을 때의 알고리즘이다.

만약, 한 알고리즘의 소요시간이 n(리스트의 길이)에 대한 수식으로 2n^2 + 8n + 157로 나타났다고 가정하자.
그리고 2n^2 과 점근표기법에서 삭제되는 8n+157을 n에 대한 소요시간 그래프로 나타내보자.

  • 처음에는 8n+157의 소요시간이 더 크더라도, 나중에는 2n^2의 소요시간이 압도적으로 커진다.

  • n이 100만 정도로 엄청 커졌을 때, 차이는 두드러진다. 즉, n이 엄청 크다고 가정하면 영향력이 작은 부분은 그냥 무시해버리는 것이 핵심이다.

  • 2n^2이 아니라 0.01n^2이라면??? -> 결과적으로 계수도 무시해도 된다

점근표기법의 의미

O(1) : Big-O of 1 알고리즘은 인풋사이즈(n)에 영향받지 않고 일정하게 1초가 걸린다.

O(n) : 인풋(n) 증가량(n배)과 소요시간이 비례(n배)해서 증가한다.

  • 리스트 크기가 100 -> 1초, 200 -> 2초...

O(n^2) : 인풋(n) 2배 -> 소요시간(n^2) 4배 증가
O(n^3) : 인풋이 n배 -> 소요시간 n^3배 증가

n이 1000까지라면,,,

n이 10000까지라면,,, 더 차이가 난다.

  • O(n^3)은 너무 오래걸리니 안좋은 알고리즘이다.

같은 컴퓨터가 아니라... 오래걸리는 알고리즘에 최고사양 컴퓨터를 배정한다면? 소요시간이 더 줄 수 있다.

그러나, 이것은 리스트의 길이가 적을 때의 이야기이다.
BigO의 핵심은 n이 무수히 크다고 가정하는 것이고,
그 상태에서는 리스트의 길이(n)이 증가함에 따라 소요시간(n) 폭팔적으로 증가하여, 결국은 n의 차수가 높은 O(n^3)이 가장 오래 걸릴 것이다.

즉, 컴퓨터 사양이 아무리 좋아도, 빠른 언어를 사용하여도,
결국 알고리즘이 별로면, 싸구려 컴퓨터보다 느려진다.

VS code 단축키 정리

2019. 5. 13. 21:38
  1. Ctrl + , : 환경설정
  2. Ctrl + K, O : 폴더 열기(해당 프로젝트 열기)
  3. Ctrl + Shift + ~ : 터미널 열기
  4. F2 : 변수이름바꾸기
  5. Ctrl + Shift + G : git탭 열기
  1. nittaku 2019.08.02 21:32 신고

    F1 : 입력창열기
    CTRL + SPACE : 자동완성
    CTRL + F5 : 디버그 실행

이글은 코드잇의 알고리즘 강의와 오픈소스들을 참고하여 정리한 글입니다^^

정렬(Sorting) : 리스트의 원서들을 특정 순서로 정리하는 것

  • 오름차순, 내림차순, 알파벳순
  • python에는 이미 sorted( list ) 내장함수나 리스트의 list..sort() method도 있다.

그냥 sorted()나 .sort()를 쓰면 될 것 같으나 정렬을 왜 배워야 할까?
그 이유는 정렬 자체가 알고리즘의 기초 & 모든 개발자가 알아야할 가장 기본적인 알고리즘이기 때문이다.

  1. 선택 정렬(Selection Sort) : 인덱스에 들어갈 값들을 찾아서 정렬하는 알고리즘으로서,
    가장 작은 값 -> 0번 인덱스
    2번째 작은 값 -> 1번 인덱스
    3번째 작은 값 -> 2번 인덱스 ... 방식으로 정렬한다.
    예를들어,

    • 0번 인덱스에 넣어줄 가장 작은 값을 찾기위해, 0~5번 인덱스의 값들을 확인한 뒤 넣어준다.

    • 0번 인덱스의 값을 볼때는, 4가 가장 최소값이다.

    • 1번 인덱스의 값을 볼때는, 2가 가장 최소값이다.

    • 3번 인덱스의 값을 볼때는, 1가 가장 최소값이다.

    • 5번 인덱스까지 1회전 다봤으면,
      0번 인덱스의 값 <-> 3번 인덱스의 값(최소값)을 교체한다.

    • 이제 1번 인덱스에 들어갈 값을 찾기위해서, 1 ~ 5번 인덱스까지 값을 보고 가장 작은 값과 교체해준다.

    • 마찬가지로 2번 인덱스 -> 2~5번 인덱스의 값 탐색 후 가장 최소값 넣어주기 -> 반복한다.

  1. 삽입 정렬(Insertion Sort) : 이 어떤 인덱스에 들어가야할지 찾는 알고리즘으로서,
    예를 들어, 카드 게임을 한다고 할 때, 이미 정렬된 카드를 가지고 있는 상태에서 딜러가 새로운 카드를 줬을 때, 새로운 카드를 올바른 위치에 삽입(끼워넣는)한다.

my) 0과1 정렬/ 0,1,2 정렬/ 0,1,2,3 정렬 하는데, 마지막값을 기준으로 왼쪽으로 차례차례 비교해나간다.


아래와 같은 리스트가 있다고 가정하자.

- 먼저, 0번과 1번 인덱스만 보고, 정렬한다.

- 다음으로, 0,1,2번 인덱스을 보고, 정렬한다.

- 다음은, 0,1,2,3번 인덱스의 을 보고 정렬한다. 이 때, 3값<->2값, 2<->1값, 1값<->0값순으로 한번씩 비교하는 것 같다.





- 마지막 5번인덱스의 3은,
(1) 9와 비교해서 왼쪽,
(2) 7과 비교해서 왼쪽,
(3) 4와 비교해서 왼쪽, 총 3번을 한칸씩 움직인다.

참고)

  • 이미 거의 정렬된 리스트를 정렬할 때는 삽입 정렬(Insertion Sort)이 가장 빠른 반면,
  • 아예 정반대로 정렬된 리스트의 경우에는 삽입 정렬이 매우 오래 걸린다는 것도 볼 수 있죠.
  • 선택 정렬(Selection Sort)과 합병 정렬(Merge Sort)상황에 영향을 받지 않고 일정한 시간이 소요된다는 점도 주목해 볼 만합니다.
  • 무작위 순서의 리스트를 정렬할 때는 힙 정렬(Heapsort)이 가장 먼저 끝나네요.

구현시 참고 블로그 : http://ejklike.github.io/2017/03/04/sorting-algorithms-with-python.html

  1. 2019.05.11 13:23

    비밀댓글입니다

    • 2019.05.11 14:35

      비밀댓글입니다

+ Recent posts