[전공 서적 번역] Array Based Sequence

Lecture 5 - Array Based Sequence

💡 **Array-Based Sequences**

Contents

1 Python’s Sequence Types

• List, tuple, and str classes.
  • Each supports indexing to access an individual element of a sequence.
  • It uses low-level concpet known as an array to represent the sequence.

2 Low-Level Arrays

컴퓨터 메모리에서 배열을 어떻게 관리할까?

• bits → byte (8 bits).
• 컴퓨터에서는 많은 양의 메모리 bytes를 갖고 있기 때문에 이를 관리하도록 memory address라고 불리는 추상화를 제공한다.
• memory address를 표현하는데, 주소로 표현되는 이진 표현을 사용한다.

• A group of related variables can be stored one after another in a contiguous portion of the computer’s memory.

→ 한 칸이 bytes를 표현, 배열은 연속적인 순서로 변수들의 그룹을 저장한다.

Python internally represents each Unicode character (e.g. “SAMPLE”) with 16 bits (i.e., 2 bytes). 6 characters would be stored in 12 consecutive bytes of memory.

→ 2146~2157 저장.

• 이는 array의 경우 그것의 index를 기반으로 상수의 시간으로 접근하여 호출할 수 있음을 뜻한다.

2-1 Referential Arrays

• String을 배열에 저장해야한다고 생각해보자, String은 서로 다른 길이를 가진다. 파이썬에서는 원래라면 이를 자유롭게 저장시키기 위해 가장 큰 길이를 지닌 문자열에서 그 공간을 미리 예약해놓고 저장하게 해야할 것이다.

• 하지만 이는 공간 낭비이다. 그대신 파이썬은 위와 같은 경우 reference 라는 개념을 사용한다. 배열에 문자열이 저장될 메모리 주소를 저장시키는 것이다.

• 파이썬에서 lists나 tuples은 referential structures 이고, 이 때문에 1개의 list 객체는 여러개의 reference들을 가리킬 수 있다.
• 리스트 슬라이싱을 하는 경우 위 그림과 같이 새로운 리스트 객체가 생성되고 그 안에 들어있는 (불변 객체의 경우) 객체를 가리키게 된다. 즉, 불변 객체의 경우 여러개의 리스트 객체가 가리킬 수 있다.

3 Dynamic Arrays and Amortization

Dynamic Arrays

• Low-level의 배열을 컴퓨터 시스템에서 만들 때는 원래 정확한 사이즈가 선언되어 그 저장소에 연속적인 메모리를 할당할 수 있게 함.

예시) 2146 부터 2157까지 쓰겠다.

• 이와 같은 특징은, 데이터를 중간에 변경하는 것 뿐만 아니라, 추가하고 삭제하는 것도 제한되는 것을 의미한다.

• 이 때, 파이썬의 list class는 흥미로운 기능을 제공한다. 처음에 유저가 길이를 제한했다고 하더라도, element를 리스트에 더 추가하고자 한다면 reserved된 capacity가 만료된다. 파이썬은 이와같은 추상화를 제공하는데 이게 흔히 알려진 dynamic array이다.

• 리스트 클래스의 strategy를 알아보기 위해 저자들은 empirical한 evidence를 보인다. 다음과 같이 코드를 짜서 시퀀스를 표현할 때 리스트 객체가 차지하는 공간을 살펴보자. (3.2에서 더 자세히)

import sys

data=[]
for k in range(n):
    a = len(data)
    b = sys.getsizeof(data)
		print("Length: {0:3d}; Size in bytes: {i:4d}".format(a, b))
		data.append(None)

• Referential array에선 append시, 0-4-16-25 … 으로 사이즈가 변하는 것을 확인할 수 있다. 32 bytes씩 변하는건 테스트 컴퓨터가 8 bytes (i.e., 64-bits number)이기 때문이다.

3.1 파이썬 list class의 구현 형태 정리해보자.

• append - 새로운 배열 생성 후, 데이터를 이전한다.

import ctypes # provides low-level arrays

class DynamicArray:
    """A dynamic array class akin to a simplified Python list."""

    def init (self):
        self._n=0 # count actual elements
        self._capacity = 1 # default array capacity
        self._A = self._make_array(self._capacity) # low-level array
    
    def __len__(self):
        """Return number of elements stored in the array."""
        return self. n

    def __getitem__(self, k):
        """Return element at index k."""
        if not 0 <= k < self._n:
            raise IndexError('invalid index')
        return self._A[k] # retrieve from array

    def append(self, obj):
        """Add object to end of the array."""
        if self._n == self._capacity: # not enough room
            self._resize(self._capacity) # so double capacity
            self._A[self._n] = obj
            self._n += 1

    def _resize(self, c): # nonpublic utitity
        """Resize internal array to capacity c."""
        B = self.make_array(c) # new (bigger) array
        **for k in range(self._n): # for each existing value
            B[k] = self._A[k]**
        self._A=B # use the bigger array
        self._capacity = c
    
    **def _make_array(self, c): # nonpublic utitit
        """Return new array with capacity c."""
        return (c ctypes.py object)()**

		# pop method 추가
		def pop(self, k): # index number
        """ Return pop item and remove k in array."""
        item = self._A[k]
        for j in range(k, self._n-1): # self._n : actural elements 1->1
            self._A[j] = self._A[j+1]
        self._n -= 1
        return item

3.2 Amortized Analysis of Dynamic Arrays

• list 안의 dynamic array에 대해 amortized analysis를 진행.
• 하나씩 원소를 append하게 되면, Ω(n2)
• list class 호출 후 (data), None 객체를 지속적으로 추가하여 리스트 객체의 메모리를 확인.

*None is a special constant in Python that represents the absence of a value or a null value. (None 은 singleton 패턴)

4 Python’s List and Tuple Classes

• List class efficiency
  • Empty list의 append의 경우, 걸리는 시간은 n과 독립적이다.
    • 100개를 더하는데 걸리는 시간이나 100000..를 더하는데 걸리는 시간이 비슷하다.

→ k denote the leftmost index at which they disagree or else k = min($n_1$,$n_2$).

• 왜 이런 Running Time이 나오는지 생각해보자. (배열은 연속된 메모리에 저장되어 인덱스로 저장된 값을 가져올 수 있음을 상기하자.)
  • 이런 원리라면 위의 케이스들의 Running Time의 Big-O 를 이해할 수 있다.

• 마찬가지로 append 뿐만아니라, insert, pop, remove 메서드에 대해 알아보자.
• 이 또한, inserting을 하는 그 자체로는 O(1)인 behavior이나, 배열에서 특정 인덱스의 원소를 삽입 후에 원래 위치에 있던 원소들은 k를 기준으로 모두 뒤로 밀려야한다. (shifting all subsequent elements)
  • 따라서 O(n-k)의 running time이 예상되며, pop(0)은 하한 시간이 n이다.

• 새로운 리스트를 만들 때는, append보단 list comprehesion이 더 빠르게 만들 수있음을 알자.

String class

5 Using Array-Based Sequences

Storing High Scores for a Game

• A sequence of objets 이 저장되어야 할 때, 배열 기반의 자료구조를 이용해서 저장해보자.

• GameEntry 클래스를 만들어 객체마다 score나 name을 반환하는 메소드를 구현하자.

• 이런 객체를 우리는 Scoreboard 를 만들어 저장하고, 이 스코어 보드는 가장 높은 점수를 제한하여 저장할 수 있도록 한다.

  • 여기서 파이썬의 리스트를 이용해서 GameEntry instances들을 관리한다.
    • 초기는 None으로 설정한다.

→ 다음과 같은 모양이 될 것이다.

• add 메서드의 경우 저장하려는 객체에서 1) 점수를 확인하고 2) 보드의 길이가 아직 넘치지 않거나 그 점수가 마지막 점수보다 높으면 good 변수를 활성화한다.
• 이 때, 보드 안에서 점수가 큰 것이 나올 때까지 반복해서 값을 바꿔나가는데, 맨 끝부터 값을 삽입하려는 점수와 비교해서 작으면 끝의 값 자리에 그 이전 값을 저장시켜 자리를 만든다.

Sorting a Sequence

• The insertion-sort algorithm
• Sequence 자료형의 삽입, 삭제 기능들을 다루며, 이와 비슷한 아이디어를 차용하는 정렬 알고리즘을 함께 소개한다.

def insert_sort(arr):
    for i in range(1, len(arr)):
        temp = arr[i]
        j  = i
        while j > 0 and temp < arr[j-1]:
            arr[j] = arr[j-1]
            j-=1
        arr[j] = temp
    return arr

• 그림 도식화

• 버블, 선택 정렬과 함께 $O(n^2)$ 시간복잡도를 가지는 정렬방식이다.
• 세 정렬 모두 i번째부터 마지막 원소자리 까지 쭉 비교해나가는 방식을 취하지만, 각각 취하는 action이 다르다. 예를 들어 버블 정렬의 경우 i번째를 기준으로 i+1번째와 비교하고 그 값이 정렬기준에 부합할 경우 (e.g. 오름차순의 경우 더 작을 경우) 그 결과를 바로 바꾼다. 그렇게 바꾸는 작업을 거품이 이는 모양으로 생각하면 기억하기 더 쉬울 것이다. 선택 정렬의 경우 i번째에서 바로 다음인 i+1만을 비교하는 것이 아니라, 마지막 원소자리까지 계속 비교하고, 가장 작은 (오름차순인 경우) 값을 i번째와 자리를 바꾼다. 앞선 두 정렬은 들어오는 배열 N이 어떤 것이든 상관없이 (e.g. 이미 정렬이 되어있는 배열) 결국, 위와 같은 작업을 무조건 실행하게 된다.
• 하지만, 삽입 정렬은 nested loops의 경우 조건으로 실행이 되기 때문에 모두 정렬된 상태의 배열이 들어오게 되면, 진행되지 않고 이 경우, O(n)의 시간을 가질 수 있다. 그러므로, 삽입 정렬의 시간 복잡도는 최선의 경우 $O(n)$ 그리고 최악의 경우 $O(n^2)$ 를 갖는다고 이야기한다.

6 Multidimensional Data Sets

• Lists, tuples, and strings → 1차원.
• Two dimensional array → matrix
• Python에서 2차원 배열의 형태 : data = [ [22, 18, 709, 5, 33], [45, 32, 830, 120, 750], [4, 880, 45, 66, 61] ]
• Matrix를 올바르게 생성하는 방법.
  • [[0] 3] 3→ X

- [[0]*3 for _ in range(3)] → **O**

• 2차원 배열을 board 처럼 사용한 게임인
  • Tic-Tac-Toe 를 구현해보자.

Tic-Tac-Toe

• 3X3 보드, 2명의 게임자

• X와 O를 보드에 번갈아가며 마크함.

• X부터 시작.

• 어느 한 사람이, 가로-세로-대각선 을 자신의 마크로 모두 채우면 이김.

• 코드 (p.223)

  • TicTacToe class : 보드와, 선수가 속성 (”X” 가 디폴트)
  • 이 때, 호출을 아래와 같이 진행한다.

game = TicTacToe()
game.mark(i,j) # 순서대로 서로 입력.
print(game) # __str__ 
winner = game.wineer()
if winner is None:
   print("Tie") # 비긴경우.
else:
   print(winner, "wins")

Exercise

연습문제는 아래 링크에서 확인 가능하다.

Exercised - 5

---

Term definition

• Immutable or mutable?

• The capacity of an array cannot trivially be increased by expanding into subsequent cells. → Immutable

• The class allows us to add elements to the list with no apparent limit on the overall capacity of the list. → Mutable