Python cho người Việt

Python cho người Việt

Danh sách nhảy cóc (Skip List)

written by Phan Đắc Anh Huy, on May 1, 2014 10:01:00 PM.

Giới thiệu

Qua các lượt bài trước, chúng ta đã thảo luận về thuận toán tìm kiếm nhị phân và ngăn (partition). Cả hai thuận toán này đều dựa trên cấu trúc dữ liệu mảng (array) vốn rất quen thuộc với chúng ta.

Ngoài ra, hai thuật toán trên được xếp vào nhóm thuật toán tất định (determistic algorithm). Các thuật toán thuộc nhóm này thỏa mãn hai điều kiện:

  • Luôn trả về kết quả giống nhau nếu được cung cấp cùng một dữ liệu đầu vào.

  • Các trạng thái (state) trong quá trình tính toán phải giống nhau với cùng một dữ liệu đầu vào.

Trong bài viết này tác giả đề cập đến cấu trúc dữ liệu "Danh Sách Nhảy Cóc" (Skip List), cơ chế hoạt động của cấu trúc dữ liệu này (bao gồm các thao tác Thêm, Xóa, Tìm Kiếm) phụ thuộc vào yếu tố ngẫu nhiên vì vậy nó được xếp vào nhóm thuật toán ngẫu tính (randomized algorithm), trái ngược với nhóm thuật toán tất định.

Mục đích

Một cấu trúc dữ liệu đơn giản nhưng hiệu quả trên các tác vụ cơ bản: Thêm, Xóa và Tìm Kiếm.

Định nghĩa

Danh sách nhảy cóc S là một tập hợp các danh sách S[0], S[1] ... S[N-1]. Để dễ hình dung chúng ta xem mỗi danh sách con tương ứng với một "tầng", trong đó 0 là tầng thấp nhất, cho đến N-1 là tầng cao nhất. Danh sách nhảy cóc luôn thỏa mãn các điều kiện:

  • Mỗi danh sách con chứa các giá trị theo thứ tự tăng dần.

  • Phần từ đầu và cuối mỗi danh sách con đều là NULL.

  • Danh sách ở tầng cao hơn là dãy con của danh sách tầng dưới.

Ví dụ một trạng thái của danh sách nhảy cóc chứa dãy số 12, 23, 34, 46, 64, 78, 89

S[3]    NULL             23                                              NULL
S[2]    NULL             23                      64                      NULL
S[1]    NULL             23      34              64      78              NULL 
S[0]    NULL     12      23      34      46      64      78      80      NULL

Tìm kiếm trong danh sách

Gọi K là giá trị cần tìm kiếm. Ý tưởng chính của thuật toán là cố gắng duyệt càng xa càng tốt trên tầng cao hơn và tiếp tục ở tầng thấp hơn cho đến khi không thể duyệt được nữa.

Thuật toán bắt đầu từ phần tử đầu tiên, tầng trên cùng của danh sách. Duyệt theo quy luật:

  • Nhảy sang phần tử kế tiếp trên cùng tầng nếu phần tử tiếp theo đó khác NULL và bé hơn hoặc bằng K.

  • Nếu không thể di chuyển trên cùng tầng được nữa:

    • Dừng duyệt nếu như đang ở tầng thấp nhất.

    • Ngược lại, nhảy xuống phần tử ngay bên dưới ở tầng tiếp theo.

Sau khi kết thúc duyệt danh sách, nếu phần tử hiện tại bằng K, thuật toán kết luận tìm được K, ngược lại K không tồn tại trong danh sách.

Ví dụ dưới đây minh họa việc tìm kiếm K = 85 trong danh sách S tại trạng thái được mô tả ở phần trước:

S[3]    NULL -------> 23                                        NULL
S[2]    NULL          23  ----------->  64                      NULL
S[1]    NULL          23    34          64 -> 78 -> 83          NULL 
S[0]    NULL    12    23    34    46    64    78    83    90    NULL

Giải thích:

Bước Tầng hiện tại Phần tử hiện tại Phần tử kế tiếp Di chuyển
1 S[3] NULL 23 Nhảy sang phần tử kế tiếp vì 23 <= K
2 S[3] 23 NULL Nhảy xuống tầng dưới vì phần tử kế tiếp bằng NULL
3 S[2] 23 64 Nhảy sang phần tử kế tiếp vì 64 <= K
4 S[2] 64 NULL Nhảy xuống tầng dưới vì phần tử kế tiếp bằng NULL
5 S[1] 64 78 Nhảy sang phần tử kế tiếp vì 78 <= K
6 S[1] 78 83 Nhảy sang phần tử kế tiếp vì 83 <= K
7 S[1] 83 NULL Nhảy xuống tầng dưới vì phần tử kế tiếp bằng NULL
8 S[0] 83 90 Dừng thuật toán vì 90 > K

Dựa vào giá trị của phần tử cuối cùng, chúng ta kết luận không tìm thấy giá trị 85 trong danh sách. Mặt khác, nếu chúng ta tìm K = 83, các bước duyệt trên danh sách sẽ giống hệt như vậy ngoại trừ việc thuật toán sẽ kết thúc ở bước thứ 7 và chúng ta tìm được K.

Để ý các bước duyệt, chúng ta thấy thuật toán đã “nhảy cóc” qua các phần tử 12, 34 và 46.

Thêm phần tử vào danh sách

Gọi H là giá trị của phần tử cần thêm vào danh sách S. Thuật toán được mô tả như sau:

  • Bước 1: Thực hiện việc tìm kiếm H trong S và lưu lại các vị trí cuối cùng trên mỗi tầng trong khi duyệt: p[N-1], p[N-2] … p[1], p[0] tương ứng với tầng N-1, N-2, ... 1, 0.

  • Bước 2: Nếu H đã tồn tại trong danh sách S, kết thúc thuật toán.

  • Bước 3: Thêm phần tử giá trị H vào sau p[0].

  • Bước 4: Tung một đồng xu

    • Nếu được mặt ngửa, di chuyển lên tầng trên và thêm phần tử giá trị H vào sau vị trí tương ứng ở tầng này. (p[1] nếu là tầng 1, p[2] nếu là tầng 2, …..).

    • Nếu được mặt xấp, dừng thuật toán.

  • Bước 5: Quay lại bước 4.

Lưu ý tại bước 4, thuật toán phải tạo tầng mới nếu đồng xu hiện mặt ngửa và chúng ta đang ở tầng trên cùng.

Xóa phần tử khỏi danh sách

Gọi H là giá trị của phần tử cần phải xóa khỏi danh sách S. Thuật toán khá tương tự với việc thêm phần tử:

  • Bước 1: Thực hiện việc tìm kiếm H trong S và lưu lại các vị trí cuối cùng trên mỗi tầng trong khi duyệt: p[N-1], p[N-2] … p[1], p[0]

  • Bước 2: Nếu không tìm thấy H, thuật toán kết thúc.

  • Bước 3: Ngược lại, xóa tất cả các phần tử tại vị trí p[N-1], p[N-2] … p[1], p[0] khỏi danh sách.

  • Bước 4: Xóa tất cả các tầng trống (tầng chỉ có hai phần tử NULL ở đầu và cuối)

Cài đặt

Chúng ta định nghĩa một phần tử của danh sách nhảy cóc như sau:

class SkipListNode(object):

    def __init__(self, value):
        self.value = value
        self.next  = None
        self.down  = None

Như các bạn thấy, với mỗi phần tử ngoài giá trị cần lưu, chúng ta chỉ quan tâm đến phần tử kế tiếp (bên phải) và phần tử tương ứng nằm ở tầng dưới.

Kế tiếp, định nghĩa danh sách nhảy cóc với hàm khởi tạo:

class SkipList(object):

    def __init__(self):
        self.head = SkipListNode(None)

Lớp SkipList sử dụng biến head để lưu phần tử đầu tiên của tầng cao nhất, đây luôn là vị trí bắt đầu khi chúng ta duyệt danh sách.

Dễ thấy rằng tác vụ Thêm và Tìm Kiếm đều cần phải duyệt qua danh sách với cùng một cách để tìm một giá trị, vì vậy chúng ta định nghĩa hàm _search để có thể dùng chung cho cả hai như sau:

    def _search(self, value):
        last_nodes   = []
        current_node = self.head

        while True:
            if current_node.next is not None and current_node.next.value <= value:
                current_node = current_node.next
            else:
                last_nodes.append(current_node)
                if current_node.down is not None:
                    current_node = current_node.down
                else:
                    break
        return last_nodes

Cách hoạt động của hàm này được mô tả ở mục Tìm kiếm trong danh sách, giá trị trả về là danh sách p[N-1], p[N-2], ... p[0] tương ứng với phần tử cuối cùng được duyệt đến tại các tầng N-1, N-1, ... 0

Lúc này hàm search của chúng ta khá đơn giản, chỉ cần kiểm tra giá trị của phần tử cuối cùng được trả về bởi _search:

    def search(self, value):
        last_nodes = self._search(value)

        if last_nodes[-1].value == value:
            return value

        return None

Hàm insert để thêm phần tử vào danh sách:

    def insert(self, new_value):

        last_nodes = self._search(new_value)

        # Stop if the value is already there in the list
        if last_nodes[-1].value == new_value:
            return 

        last_created_node = None
        while True:
            new_node = SkipListNode(new_value)

            if len(last_nodes) > 0:
                last_node       = last_nodes.pop()
                new_node.next   = last_node.next
                last_node.next  = new_node
            else:
                new_head       = SkipListNode(None)
                new_head.down  = self.head
                new_head.next  = new_node
                new_node.next  = None
                self.head      = new_head

            new_node.down      = last_created_node
            last_created_node  = new_node

            # We are flipping the coin now 
            if random.randint(0, 1) != 0:
                break

Và cuối cùng là hàm remove để xóa phần tử khỏi danh sách:

    def remove(self, value):
        current_node = self.head

        while True:
            if current_node.next is not None and current_node.next.value <= value:
                if current_node.next.value < value:
                    current_node = current_node.next
                else: 
                    current_node.next = current_node.next.next

                if current_node.value is None and current_node.next is None\ 
                    and current_node.down is not None:
                    self.head = current_node.down
            else:
                if current_node.down is not None:
                    current_node = current_node.down
                else:
                    break

Về cơ bản hàm này khá giống hàm _search: chúng ta vẫn duyệt từ head để tìm kiếm giá trị value. Điểm khác biệt là, nếu tìm thấy value ở bất kỳ tầng nào, chúng ta tiến hành xóa phần tử khỏi tầng đó đồng thời xóa luôn tầng này nếu không còn phần tử (khác NULL) nào khác.

Độ phức tạp

  • Trung bình:

    • Bộ nhớ cần thiết: O(n)

    • Thời gian tìm kiếm, thêm, xóa: O(logn)

  • Tệ nhất:

    • Bộ nhớ cần thiết: O(n*logn)

    • Thời gian tìm kiếm, thêm, xóa: O(n)

Bàn luận thêm

  • Các bạn có thể thấy ở thao tác Thêm phần tử, danh sách không thay đổi nếu chúng ta thêm một phần tử vốn đã có sẵn trong danh sách. Điều này đồng nghĩa với việc chúng ta mặc định các phần tử là đôi một khác nhau. Hãy sửa lại các đoạn mã ở trên để danh sách nhảy cóc của chúng ta có thể hỗ trợ các phần tử giống nhau.

  • Để ý rằng độ phức tạp của Danh Sách Nhảy Cóc tương đương với Cây Nhị Phân, ngoại trừ việc Danh Sách Nhảy Cóc sử dụng nhiều bộ nhớ hơn. Bạn đọc có thể chỉ ra điểm nhỉnh hơn của Danh Sách Nhảy Cóc không ? (Gợi ý: chuyện gì xảy ra đối với hai danh sách khi có nhiều tiến trình muốn thêm phần tử vào danh sách cùng một lúc ?)

  • Hãy viết hàm in ra trạng thái của danh sách nhảy cóc.

  • Hãy viết hàm in ra các phần tử của danh sách nhảy cóc.

Chương trình đường hầm HTTP bằng Python

written by Phan Đắc Anh Huy, on Jan 14, 2014 1:43:00 AM.

(Bài gửi đến PCNV từ cộng tác viên Vũ Khuê. Xin cảm ơn bạn.)

Giới thiệu

Có những lúc bạn cần kết nối đến máy chủ ngoài mạng nội bộ ở một cổng không thuộc những giao thức ứng dụng phổ biến như HTTP hay HTTPS (cổng 80 hoặc 443). Nhưnng điều đáng buồn là tường lửa chặn yêu cầu đến những cổng ngoài 80 hoặc 443. Khi đó, điều bạn có thể làm là thiết lập một chương trình trên một máy ngoại mạng. Chưong trình này nhận yêu cầu tử cổng 80 hoặc 443 và chuyển nó đến cổng và máy chủ thực sự. Việc này thường được gọi là thiết lập đường hầm (tunneling).

Trên thực tế, chương trình ssh với tuỳ chọn -L thường được sử dụng cho nhiệm vụ này. Tuy nhiên trong bài này chúng ta sẽ viết chương trinh đường hầm này dựa trên giao thức HTTP. Mục đích chính là miêu tả việc xử lý dữ liệu mạng tầm thấp với Python.

Cấu trúc

Chương trình này gồm 2 thành phần máy khách (client) và máy chủ (server)

  • Tunnel.py: thành phần máy khách. Thành phần này nhận yêu cầu từ một cổng nhất định và bọc dữ liệu này duới dạng một yêu cầu HTTP rồi gửi đến thành phần máy chủ.
  • Tunneld.py: thành phần máy chủ. Thành phần thực chất là một máy chủ HTTP (HTTP server). Khi có yêu cầu gửi đến, nó sẽ đọc yêu cầu này và thực hiện tác vụ tương ứng. Ví dụ như thực hiện kết nối với một máy khác hoặc chuyển dữ liệu từ tải của yêu cầu HTTP đến máy này.

Để thiết lập đường hầm, chạy 2 thành phần như sau:

python tunnel.py -p [client_listen_port] -h [target_host]:[target_port]
python tunneld.py -p [server_listen_port]

Một ứng dụng muốn gửi yêu cầu đến máy nào đó (target_host), nó cần gửi yêu cầu đó thông qua cổng mà tunnel.py được khởi tạo với (client_listen_port).

Triển khai

Bạn có thể tìm thấy mã chương trình tại đây: https://github.com/khuevu/http-tunnel.

Tunnel.py

Thành phần này nghe ở một cổng nhất định. Nó có 2 tiểu trình (thread) riêng biệt để nhận và trả lời yêu cầu:

	...
	BUFFER = 1024 * 50

	#set global timeout
	socket.setdefaulttimeout(30)

	class SendThread(threading.Thread):

	    """
	    Thread to send data to remote tunneld
	    """
	    ...

	    def run(self):
	        while not self.stopped():
	        	# receive data and send to through tunnel
	            data = self.socket.recv(BUFFER)
	            self.conn.send(data)
	    ...

	class ReceiveThread(threading.Thread):

	    """
	    Thread to receive data from remote tunneld
	    """
	    ...

	    def run(self):
	        while not self.stopped():
	            data = self.conn.receive()
	            self.socket.sendall(data)

	    ...

Hằng số BUFFER là lượng dữ liệu theo byte mà chường trình sẽ nhận từ ứng dụng trước khi gửi qua đường hầm. Có thể có nhiều ứng dụng kết nối với chương trình tunnel.py. Vì thế, ta cần tạo kết nối riêng cho mỗi ứng dụng. Dưới đây là đoạn mã của lớp Connection:

class Connection():
    
    def __init__(self, connection_id, remote_addr):
        self.id = connection_id
        self.http_conn = httplib.HTTPConnection(remote_addr['host'], remote_addr['port'])
    ...

    def create(self, target_addr):
        params = urllib.urlencode({"host": target_addr['host'], "port": target_addr['port']})
        headers = {"Content-Type": "application/x-www-form-urlencoded", "Accept": "text/plain"}

        self.http_conn.request("POST", self._url("/" + self.id), params, headers)

        response = self.http_conn.getresponse()
        response.read()
        if response.status == 200:
            print 'Successfully create connection'
            return True 
        else:
            print 'Fail to establish connection: status %s because %s' % (
                response.status, response.reason)
            return False 

    def send(self, data):
        params = urllib.urlencode({"data": data})
        headers = {"Content-Type": "application/x-www-form-urlencoded", "Accept": "text/plain"}
        try: 
            self.http_conn.request("PUT", self._url("/" + self.id), params, headers)
            response = self.http_conn.getresponse()
            response.read()
            print response.status 
        except (httplib.HTTPResponse, socket.error) as ex:
            print "Error Sending Data: %s" % ex

    def receive(self):
        try: 
            self.http_conn.request("GET", "/" + self.id)
            response = self.http_conn.getresponse()
            data = response.read()
            if response.status == 200:
                return data
            else: 
                print "GET HTTP Status: %d" % response.status
                return ""
        except (httplib.HTTPResponse, socket.error) as ex:
            print "Error Receiving Data: %s" % ex
            return "" 

    ...

Như bạn thấy ở đây, Connection có những hàm để thiết lập đường hầm, gửi và nhận dữ liệu. Sự tưong tác này được xây dựng trên giao thức HTTP. Cụ thể là:

  • POST request: yêu cầu thiết lập kết nối.
  • PUT request: gửi dữ liệu qua kết nối.
  • GET request: nhận kết nối.
  • DELETE request: kết thúc kết nối.

Sẽ rõ ràng hơn khi ta nhìn vào mã của tunneld.py, thành phần nhận những yêu cầu HTTP này:

class ProxyRequestHandler(BaseHTTPRequestHandler):
    ...

    BUFFER = 1024 * 50 

    def _get_connection_id(self):
        return self.path.split('/')[-1]
    ...

    def do_GET(self):
        """GET: Read data from TargetAddress and return to client through http response"""
        s = self._get_socket()
        if s:
            try:
                data = s.recv(self.BUFFER)
                print data
                self.send_response(200)
                self.end_headers()
                if data:
                    self.wfile.write(data)
        ...

    def do_POST(self):
        """POST: Create TCP Connection to the TargetAddress"""
        id = self._get_connection_id() 

        length = int(self.headers.getheader('content-length'))
        req_data = self.rfile.read(length)
        params = cgi.parse_qs(req_data, keep_blank_values=1) 
        target_host = params['host'][0]
        target_port = int(params['port'][0])

        print 'Connecting to target address: %s % s' % (target_host, target_port)
        #open socket connection to remote server
        s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
        s.connect((target_host, target_port))
        s.settimeout(7)
        print 'Successfully connected'
        #save socket reference
        self.sockets[id] = s
        try: 
            self.send_response(200)
            self.end_headers()
        except socket.error, e:
            print e

    def do_PUT(self):
        """Read data from HTTP Request and send to TargetAddress"""
        id = self._get_connection_id()
        s = self.sockets[id]
        length = int(self.headers.getheader('content-length'))
        data = cgi.parse_qs(self.rfile.read(length), keep_blank_values=1)['data'][0] 
        try: 
            s.sendall(data)
            self.send_response(200)
        ...

    def do_DELETE(self): 
        self._close_socket()
        self.send_response(200)
        self.end_headers()

Ở đây, ProxyRequestHandler chính là một máy chủ HTTP, nhận và xử lý những yêu cầu cơ bản của HTTP.

  • do_POST: hàm này xử lý những yêu cầu POST. Nó sẽ lấy thông tin về máy đối tượng (tên miền, cổng) và tạo kết nối TCP đến máy đó. Nó trả về trạng thái 200 nếu kết nối này thành công.
  • do_GET: hàm này lấy dữ liệu từ kết nối đã được thiết lập với máy đối tương trong do_POST. Sau đó nó trả dữ liệu này trong trả lời HTTP của yêu cầu GET.
  • do_PUT: hàm này lấy nhận yêu cầu PUT, đọc dữ liệu từ tải của yêu cầu đó và gửi qua kết nối nói trên.
  • do_DELETE: hàm này đóng kết nối với máy đối tượng.

Thử nghiệm chương trình

Chúng ta sẽ thử chương trình này bằng việc kết nối với một IRC server thông qua chương trình. Trước hết, thiết lập đường hầm cần thiết. Tại một máy ngoại mạng, không bị chặn bởi tường lửa, chạy:

python tunneld.py -p 80

Tại máy nội mạng chạy:

python tunnel.py -p 8889 -h mayngoaimang:80 irc.freenode.net:6667

Như vậy ta đã thiết lập một đương hầm ở cổng 8889 qua máy ngoại mạng đến IRC server ở cổng 6667. Yêu cầu đến cổng 6667 thường bị chặn bởi tường lửa. Để thử nghiệm, ta kết nối đến cổng 8889 và gửi yêu cầu theo giao thức IRC:

nc localhost 8889
NICK abcxyz
USER abcxyz abcxyz irc.freenode.net :abcxyz

(nc - netcat - là một công cụ giúp bạn gửi giữ liệu trên TCP: http://www.irongeek.com/i.php?page=backtrack-3-man/netcat).

Ta nhận được trả lời thông báo kết nối thành công:

:calvino.freenode.net NOTICE * :*** Looking up your hostname...
:calvino.freenode.net NOTICE * :*** Checking Ident
:calvino.freenode.net NOTICE * :*** Found your hostname
:calvino.freenode.net NOTICE * :*** No Ident response
NICK abcxyz
USER abcxyz abcxyz irc.freenode.net :abcxyz
:calvino.freenode.net 001 abcxyz :Welcome to the freenode Internet Relay Chat Network abcxyz
:calvino.freenode.net 002 abcxyz :Your host is calvino.freenode.net[ ... /6667], running version ircd-seven-1.1.3
:calvino.freenode.net 003 abcxyz :This server was created Sun Dec 4 2011 at 14:42:47 CET
:calvino.freenode.net 004 abcxyz calvino.freenode.net ircd-seven-1.1.3 DOQRSZaghilopswzCFILMPQbcefgijklmnopqrstvz bkloveqjfI
:calvino.freenode.net 005 abcxyz CHANTYPES=# EXCEPTS INVEX CHANMODES=eIbq,k,flj,CFLMPQcgimnprstz CHANLIMIT=#:120 PREFIX=(ov)@+ MAXLIST=bqeI:100 MODES=4 NETWORK=freenode KNOCK STATUSMSG=@+ CALLERID=g :are supported by this server
:calvino.freenode.net 005 abcxyz CASEMAPPING=rfc1459 CHARSET=ascii NICKLEN=16 CHANNELLEN=50 TOPICLEN=390 ETRACE CPRIVMSG CNOTICE DEAF=D MONITOR=100 FNC TARGMAX=NAMES:1,LIST:1,KICK:1,WHOIS:1,PRIVMSG:4,NOTICE:4,ACCEPT:,MONITOR: :are supported by this server
:calvino.freenode.net 005 abcxyz EXTBAN=$,arx WHOX CLIENTVER=3.0 SAFELIST ELIST=CTU :are supported by this server
:calvino.freenode.net 251 abcxyz :There are 232 users and 70582 invisible on 31 servers
:calvino.freenode.net 252 abcxyz 45 :IRC Operators online
:calvino.freenode.net 253 abcxyz 10 :unknown connection(s)
:calvino.freenode.net 254 abcxyz 34513 :channels formed
:calvino.freenode.net 255 abcxyz :I have 6757 clients and 1 servers
:calvino.freenode.net 265 abcxyz 6757 10768 :Current local users 6757, max 10768
:calvino.freenode.net 266 abcxyz 70814 83501 :Current global users 70814, max 83501
:calvino.freenode.net 250 abcxyz :Highest connection count: 10769 (10768 clients) (2194912 connections received)
...

Kết

Như vậy chúng ta đã đi qua một chương trình xử lý dữ liệu mạng với Python. Chương trình chủ yếu làm việc với dữ liệu thông qua socket API. Một điều quan trọng khác mà bài viết này đề cập đến là sự tách biệt giữa giao thức ứng dụng và dữ liệu gửi trên giao thức đó. Chúng ta có thể vận chuyển dữ liệu mà thông thường đuợc gửi bằng giao thức này qua một giao thức khác.

Chú ý: Chương trình chỉ có mục đích thí nghiệm và không phù hợp với chạy thực dụng.

Thuật toán đẹp: Tìm chuỗi Boyer-Moore-Horspool

written by Nguyễn Thành Nam, on Jan 9, 2014 2:35:00 PM.

Mục đích

Tìm chính xác (exact match) chuỗi con (substring) trong một chuỗi dài hơn.

Ý tưởng chính

Gọi chuỗi cần tìm là P (pattern), và chuỗi dài là T (text).

So sánh ngược P trong T, nghĩa là ta sẽ so sánh ký tự cuối của P trước, sau đó so sánh ký tự kế cuối, và lần lượt như vậy đến ký tự đầu tiên trong P. Gọi vị trí trong T để bắt đầu so sánh hai chuỗi là i. Việc so sánh sẽ so sánh lần lượt T[i] với ký tự cuối của P, rồi T[i-1] với ký tự kế cuối của P, v.v...

Nếu việc so sánh ngược vượt qua được ký tự đầu tiên trong P, ta đã tìm được P trong T.

Nếu việc so sánh ngược bị thất bại, ta sẽ căn P cho khớp với T[i] và thử lại việc so sánh ngược. Điều này tương đương với việc dịch chuyển i đến vị trí xa hơn trong T. Đây là ý tưởng chủ chốt của thuật toán BMH.

  • Nếu T[i] không có trong P, thì ta có thể dịch chuyển i đến vị trí i + len(P).
  • Nếu vị trí cuối cùng của T[i] trong P là x thì ta dịch chuyển i đến vị trí i + len(P) - x - 1.
Trạng thái bắt đầu

             i
             |
             v
+-+-+-+-+-+-+-+-+-+-+-+-+
| | | | |d|b|a| | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+

    +-+-+-+-+-+
    |a|a|c|b|a|
    +-+-+-+-+-+

------------------------------------------

So sánh tiếp tục

             i
             |
             v
+-+-+-+-+-+-+-+-+-+-+-+-+
| | | | |d|b|a| | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+
             =
    +-+-+-+-+-+
    |a|a|c|b|a|
    +-+-+-+-+-+

------------------------------------------

So sánh tiếp tục

             i
             |
             v
+-+-+-+-+-+-+-+-+-+-+-+-+
| | | | |d|b|a| | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+
           = =
    +-+-+-+-+-+
    |a|a|c|b|a|
    +-+-+-+-+-+

------------------------------------------

So sánh sai

             i
             |
             v
+-+-+-+-+-+-+-+-+-+-+-+-+
| | | | |d|b|a| | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+
         ! = =
    +-+-+-+-+-+
    |a|a|c|b|a|
    +-+-+-+-+-+

------------------------------------------

Căn P theo T[i]...

             i
             |
             v
+-+-+-+-+-+-+-+-+-+-+-+-+
| | | | |d|b|a| | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+
             |
          +-+-+-+-+-+
          |a|a|c|b|a|
          +-+-+-+-+-+

------------------------------------------

... cũng có nghĩa là dịch chuyển i

                   i
                   |
                   v
+-+-+-+-+-+-+-+-+-+-+-+-+
| | | | |d|b|a| | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+

          +-+-+-+-+-+
          |a|a|c|b|a|
          +-+-+-+-+-+

Để cài đặt hai bước trên, người ta thường dùng một mảng chứa vị trí cuối cùng của các ký tự trong P trừ ký tự cuối cùng (P[ : -1]).

Ví dụ

Giả sử chúng ta muốn tìm chuỗi needle trong chuỗi find the needle in the haystack.

Trước khi bắt đầu, ta sẽ lập bảng vị trí cuối của các ký tự trong P[ : -1].

Ký tựVị tríDiễn giải
n0
e2Ta chọn vị trí của ký tự thứ hai.
d3
l4

Và sự thay đổi ở các bước của thuật toán. Vì độ dài của P là 6, nên i sẽ bắt đầu từ vị trí 5. Trong bảng dưới, chữ đậm là ký tự trùng nhau của T và P, chữ gạch dưới là các ký tự đang xét.

iTT[i]Diễn giải
5find the needle in the haystacktt không có trong bảng. Dịch i lên 11 (5 + 6).
11find the needle in the haystackee có trong bảng. Dịch i lên 14 (11 + 6 - 2 - 1).
14find the needle in the haystackeTìm thấy. e có trong bảng. Dịch i lên 17 (14 + 6 - 2 - 1).
17find the needle in the haystacknn có trong bảng. Dịch i lên 22 (17 + 6 - 0 - 1).
22find the needle in the haystackkhoảng trắngkhoảng trắng không có trong bảng. Dịch i lên 28 (22 + 6).
28find the needle in the haystackaa không có trong bảng. Dịch i lên 34 (28 + 6). Dừng việc tìm kiếm vì đã xét hết chuỗi.

Độ phức tạp

Thời gian chạy: Tệ nhất là O(n*m), với n là độ dài của T và m là độ dài của P. Trung bình là O(n). Và tốt nhất là dưới tuyến tính (sublinear) vì thuật toán có thể nhảy qua nhiều ký tự. Trong ví dụ trên, ta chỉ cần 12 phép so sánh để tìm chuỗi needle (6 ký tự) trong chuỗi find the needle in the haystack (31 ký tự).

Bộ nhớ cần thiết: O(n) với n là số ký tự trong bảng chữ cái (ví dụ như 256 giá trị của một byte, hoặc nếu bảng chữ cái là Unicode thì có thể sẽ nhiều hơn 60000 giá trị) vì chúng ta cần tạo bảng vị trí các ký tự trong P.

Thuật toán BMH là thuật toán tìm chuỗi chính xác tổng quát nhất, nhanh nhất, và đơn giản nhất.

Thuật toán đẹp: Partition (ngăn)

written by Nguyễn Thành Nam, on Jan 1, 2014 12:34:00 AM.

Mục đích

Chia một mảng ra thành hai cụm: một cụm thỏa điều kiện, và cụm còn lại.

Cài đặt

Sử dụng mảng phụ

def partition(a, pred):
    head = [x for x in a if pred(x)]
    tail = [x for x in a if not pred(x)]
    return head + tail, len(head)

Không dùng mảng phụ

Ý tưởng chính là sử dụng một biến phụ chứa vị trí trong mảng A mà nếu phần tử đang xét thỏa điều kiện sẽ được chuyển vào.

def partition(a, pred):
    okay_idx = 0
    for i, x in enumerate(a):
        if pred(x):
            a[okay_idx], a[i] = a[i], a[okay_idx] # swap
            okay_idx += 1
    return a, okay_idx

Độ phức tạp

Thời gian chạy: O(n)

Bộ nhớ cần thiết: O(n) nếu sử dụng mảng phụ, hoặc O(1) nếu không

Ứng dụng

Ứng dụng nổi tiếng nhất là thuật toán QuickSort do Tony Hoare sáng tạo ra. Thuật toán QuickSort sắp xếp một mảng với độ phức tạp trung bình là O(n*logn) với n là số lượng phần tử trong mảng. Độ phức tạp trong trường hợp xấu nhất có thể là O(n*n).

Sau đây là một cài đặt dễ hiểu của QuickSort. Cài đặt này chỉ dùng để thể hiện ý tưởng chứ không nên dùng trong các ứng dụng.

Ý tưởng chủ đạo là lấy ra một phần tử nào đó trong A (tức là A' chỉ còn N-1 phần tử) gọi là pivot, ngăn A' thành hai cụm (một cụm nhỏ hơn pivot, một cụm còn lại). Tiếp tục gọi đệ quy để sắp xếp hai cụm đó và nối chúng lại với nhau thông qua pivot.

def quicksort(a):
    if len(a) <= 1:
        return a
    pivot = a[-1]
    a, pivot_idx = partition(a[ : -1], lambda x: x <= pivot)
    return quicksort(a[ : pivot_idx]) + [pivot] + quicksort(a[pivot_idx : ])

import itertools
for l in range(8):
    a = range(l)
    for p in itertools.permutations(a):
        p = list(p)
        assert quicksort(p) == a

Bài toán mở rộng

  1. Cho một mảng số nguyên A. Tìm K phần tử nhỏ nhất trong A.
  2. Cho một mảng số nguyên A và một số nguyên X. Đếm số tập hợp 2-phần-tử trong mảng A có tổng nhỏ hơn hoặc bằng X.

Các bạn có thể trao đổi về cách giải bài các bài toán mở rộng này với độ phức tạp trung bình O(n) trong diễn đàn.

Thuật toán đẹp: Tìm nhị phân

written by Nguyễn Thành Nam, on Dec 27, 2013 1:13:00 PM.

Mục đích

Tìm phần tử X trong một mảng đã được sắp xếp.

Ý tưởng chính

Chia mảng ra thành 3 cụm: cụm bên trái, phần tử ở giữa, và cụm bên phải. So sánh X với phần tử ở giữa. Nếu X bằng với phần tử ở giữa thì ta đã tìm được X trong mảng. Nếu X lớn hơn thì tìm X trong cụm bên phải. Nếu X nhỏ hơn thì tìm X trong cụm bên trái.

Hiệu quả

Thời gian thực hiện: O(logn)

Bộ nhớ cần thiết: O(1)

Cài đặt

Cài đặt đệ quy

def bin_search(x, a, left_idx, right_idx):
    if left_idx > right_idx:
        return -1
    mid_idx = left_idx + (right_idx - left_idx) // 2
    mid = a[mid_idx]
    if x == mid:
        return mid_idx
    elif x < mid:
        return bin_search(x, a, left_idx, mid_idx - 1)
    else:
        return bin_search(x, a, mid_idx + 1, right_idx)

assert bin_search(0, [0], 0, 0) == 0
assert bin_search(0, [1], 0, 0) == -1
assert bin_search(0, [0, 1], 0, 1) == 0
assert bin_search(1, [0, 1], 0, 1) == 1
assert bin_search(2, [0, 1], 0, 1) == -1

Cài đặt vòng lặp

def bin_search(x, a, left_idx, right_idx):
    while left_idx <= right_idx:
        mid_idx = left_idx + (right_idx - left_idx) // 2
        mid = a[mid_idx]
        if mid == x:
            return mid_idx
        elif x < mid:
            right_idx = mid_idx - 1
        else:
            left_idx = mid_idx + 1
    return -1

Tham khảo thêm

Mô-đun bisect trong thư viện chuẩn của Python.

Một số bài toán mở rộng

  1. Mảng đã được sắp xếp nhưng đã bị xoay vòng (ví dụ [4, 5, 6, 7, 1, 2, 3]).
  2. Mảng 2 chiều đã được sắp xếp theo dòng, và cột (a[i][j] < a[i + 1][j] và a[i][j] < a[i][j + 1]).

Các bạn có thể trao đổi ý tưởng giải quyết các bài toán mở rộng này trong diễn đàn.

Kết quả cuộc thi giải toán lần II

written by vithon, on Apr 18, 2013 11:29:51 PM.

Cảm ơn sự hưởng ứng nhiệt tình của các bạn với cuộc thi giải toán lần II của PCNV.

Lần này nhóm nhận được sự sự tham gia của năm bạn Phạm Ngọc Quang Nam, Nguyễn Văn Nam, Vũ Khuê, Hoàng Quốc Thịnh, và Đậu Duy Khánh.

Bài của bạn Thịnh:

09:03:48 ~/tmp/pell2$ python3.3 thinhhq.py | python timer.py > thinhhq.txt
09:04:22 ~/tmp/pell2$ python checker.py < thinhhq.txt
Max 448985
09:04:30 ~/tmp/pell2$ python3.3 thinhhq.py | python timer.py > thinhhq.txt2
09:05:04 ~/tmp/pell2$ python checker.py < thinhhq.txt2
Max 449905
09:05:08 ~/tmp/pell2$ python3.3 thinhhq.py | python timer.py > thinhhq.txt3
09:05:39 ~/tmp/pell2$ python checker.py < thinhhq.txt3
Max 449421

Bài của bạn Văn Nam:

09:05:46 ~/tmp/pell2$ python3.3 namnv.py | python timer.py > namnv.txt
09:07:12 ~/tmp/pell2$ python checker.py < namnv.txt
Max 1394855
09:07:28 ~/tmp/pell2$ python3.3 namnv.py | python timer.py > namnv.txt2
09:07:47 ~/tmp/pell2$ python checker.py < namnv.txt2
Max 1394855
09:08:00 ~/tmp/pell2$ python3.3 namnv.py | python timer.py > namnv.txt3
09:08:19 ~/tmp/pell2$ python checker.py < namnv.txt3
Max 1394855

Bài của bạn Khanh:

09:12:49 ~/tmp/pell2$ python3.3 khanhdd.py | python timer.py > khanhdd.txt
Traceback (most recent call last):
  File "khanhdd.py", line 13, in <module>
    print (a1,' ',b1)
BrokenPipeError: [Errno 32] Broken pipe
09:13:27 ~/tmp/pell2$ python checker.py < khanhdd.txt
ERROR:root:Format
Traceback (most recent call last):
  File "checker.py", line 16, in <module>
    n, k = map(long, line.split())
ValueError: too many values to unpack

Bài của bạn Khuê

09:14:37 ~/tmp/pell2$ python3.3 khuev.py | python timer.py > khuev.txt
  File "khuev.py", line 35
    print "n: %d - k: %d" % (-b / 2, k)
                        ^
SyntaxError: invalid syntax

Bài của bạn Quang Nam:

09:15:19 ~/tmp/pell2$ python3.3 nampnq.py | python timer.py > nampnq.txt
  File "nampnq.py", line 5
    print "n=%d, k=%d" % (n,k)
                     ^
SyntaxError: invalid syntax

Mã nguồn và bản lưu kết quả của cuộc thi có thể được tải về từ https://docs.google.com/file/d/0B5X03CmpgiFeMkNubXlGNFlCMjQ/edit?usp=sharing.

Như vậy, bạn Văn Nam đã thắng giải kỳ này. Xin chúc mừng bạn Văn Nam.

Bạn Văn Nam gửi thư cho admin@ cho biết mẫu áo bạn chọn, và thông tin bưu điện để nhóm PCNV có thể gửi áo về cho bạn.

Cuộc thi giải toán bằng Python

written by vithon, on Mar 31, 2013 9:18:00 AM.

Trong lần thi trước (http://www.vithon.org/2010/05/24/phat-d%E1%BB%99ng-cu%E1%BB%99c-thi-gi%E1%BA%A3i-toan-b%E1%BA%B1ng-python), chúng ta đánh giá chương trình dựa trên số lượng cặp N, K tìm được.

Tiêu chí của lần thi này là in ra cặp số N, K lớn nhất có thể tìm được trong 30 giây. Cặp số cuối cùng được in ra trong 30 giây sẽ được xem là cặp số lớn nhất và dùng để đánh giá các chương trình với nhau.

Giải thưởng của kỳ thi lần này sẽ là một áo thun do bạn Nguyễn Thành Nam đã tặng nhóm PCNV trong lần đi PyCon vừa qua. Các bạn có thể xem qua các áo giải thưởng (trừ EdX cỡ L, các áo khác cỡ M, chỉ được chọn 1) ở URL sau:

https://drive.google.com/folderview?id=0B5X03CmpgiFeNzNJN09qZnd2Sk0&usp=sharing

Các bài tham dự gửi bằng thư điện tử về cho admin@ hạn chót trong ngày 14 tháng 04 năm 2013. Nhằm khuyến khích việc sử dụng Python 3, các bài tham gia kỳ thi này sẽ được chấm trên Python 3.3. Mòng các bạn chú ý yêu cầu này.

Quyết định của người chấm là cuối cùng. Xin miễn nhận khiếu nại.

Ghi nhớ về PyCon 2013

written by vithon, on Mar 18, 2013 1:01:06 PM.

Hội thảo PyCon 2013 vừa kết thúc vào Chủ Nhật, ngày 18 tháng 03 năm 2013 vừa rồi tại Trung tâm Hội nghị Santa Clara, bang California, Mỹ.

Hội thảo lần này diễn ra vào các ngày thứ sáu, thứ bảy, và Chủ Nhật với khoảng 100 bài tham luận và 2500 người tham dự đến từ tất cả các châu lục trên trái đất. Trong đó, khoảng 20% là nữ giới!

Nhóm PCNV có một thành viên tham gia hội thảo lần này, và họ có một số nhận xét chính như sau:

1. Hội thảo có nhiều chuyên mục phù hợp với mọi lứa tuổi, mọi ngành nghề, mọi giới tính. Có cả những em thiếu niên khoảng 10 đến 12 tuổi tham gia hội thảo. Một số các em đã biết Python còn đứng lớp chỉ dạy Python cho các em khác. Thậm chí có một số em đã trình bày sản phẩm của chính mình trong phân mục tự giới thiệu (poster session), cùng với gần trăm sản phẩm khác từ các công ty lớn cũng như các chuyên gia trong ngành. Nữ giới chiếm gần 20% người tham gia hội thảo. Một số cá nhân trên 60 tuổi cũng thấy xuất hiện tại hội thảo. Thậm chí cả người chuyển đổi giới tính cũng có mặt! Có thể khẳng định chắc chắn rằng Python thu hút được sự quan tâm của tất cả mọi người.

2. Hội thảo năm nay có sự xuất hiện của nhiều nhóm nữ giới như CodeChix, WomanWhoCode, PyLadies, LadyCoders. Đây là một tín hiệu đáng mừng. So với các ngôn ngữ lập trình đa dụng khác, có lẽ Python là ngôn ngữ thu hút nữ giới nhiều nhất!

3. Hội thảo năm nay có một sự ngạc nhiên thú vị. Mỗi cá nhân tham dự hội thảo được tặng một thiết bị Rasberry Pi miễn phí! Điều này cho thấy Python có một vị trí quan trọng trong thị trường phần cứng nghiệp dư, kinh tế. Trong hội thảo cũng thiết lập một "Phòng nghiên cứu Rasberry Pi" để hướng dẫn cách cài đặt và sử dụng thiết bị đó. Một số người tham dự

4. Các bài tham luận chớp nhoáng (lightning talks) cho thấy Python có khả năng ứng dụng rộng rãi và đáng ngạc nhiên. Một số ví dụ điển hình như sử dụng Python để điều khiển hệ thống đèn LED nhấp nháy, sử dụng Python trên các hệ máy Atari, sử dụng Python để thông dịch và gỡ rối mã Lisp/Scheme.

5. Lập trình viên Python có khả năng Rap không thua kém các ca sĩ chuyên nghiệp! Đoạn phim bên dưới quay lại cảnh Larry Hastings, thành viên nòng cốt trong nhóm phát triển Python, hát bài rap tự chế trước phiên tham luận chớp nhoáng.

http://youtu.be/rKiySLUrYQ8

6. Bạn Nguyễn Thành Nam có mặt tại hội thảo đã chụp tấm hình tự sướng này.

https://docs.google.com/file/d/0B5X03CmpgiFeb3pfMTlIVlBCQ3M/edit?usp=sharing

Bạn Nam cũng đã ủng hộ một số món quà nhỏ cho nhóm PCNV dùng để khuyến khích các bạn đã có bài viết đóng góp cho nhóm. Nhóm PCNV sẽ gửi trực tiếp cho các bạn.

Cảnh báo: Cẩn thận khi sử dụng pip trong mạng

written by vithon, on Feb 4, 2013 2:37:20 AM.

Pip (http://pypi.python.org/pypi/pip), cũng như một số các công cụ sử dụng mô-đun có sẵn urllib, urllib2, httplib, có thể bị tấn công kẻ ở giữa (man-in-the-middle) và làm thay đổi nội dung của gói tin nhận được.

Lý do là khi truy cập vào một địa chỉ HTTPS hoặc các giao thức SSL/TLS, các mô-đun có sẵn này không kiểm tra chứng từ (certificate) của máy chủ để xác nhận máy chủ đó đúng là máy chủ chương trình cần truy cập. Điều này cho phép một kẻ thứ ba giả dạng máy chủ và thay đổi nội dung gói tin yêu cầu cũng như trả lời.

Do đó, người sử dụng cần cẩn trọng khi sử dụng các công cụ như pip trong một mạng không an toàn.

Thông tin thêm có thể được tham khảo tại:

http://www.reddit.com/r/Python/comments/17rfh7/warning_dont_use_pip_in_an_untrusted_network_a/

Kể từ Python 3.2, các mô-đun có sẵn liên quan đến SSL/TLS đã có thêm chức năng kiểm tra chứng từ nhưng chức năng này phải được tự kích hoạt.

Chương trình PyCon US 2013

written by vithon, on Jan 18, 2013 11:04:06 PM.

Chương trình hội thảo PyCon năm nay đã được công bố vào bốn ngày trước.

https://us.pycon.org/2013/schedule/

Sau nhiều tuần đánh giá các bài tham luận, chương trình của hội thảo cuối cùng đã được thống nhất. Năm nay số lượng người tham dự tăng đột ngột và 1000 vé bán trước (early bird) đã không còn nữa. Tổng lượng vé bán ra được giới hạn ở mức 2500 vé. Nếu bạn muốn tham dự hội thảo, bạn cần phải mua vé ngay bây giờ. Hội thảo bắt đầu từ ngày 13 đến ngày 21 tháng 03.

So với năm ngoái, hội thảo năm nay có thêm một chuyên mục thứ sáu, nâng tổng số bài tham luận lên 114 bài. Các bài điểm của hội thảo sẽ được trình bày bởi những nhân vật tên tuổi như Eben Upton, Jessica McKellar, Raymond Hettinger, và Guido van Rossum.

PS: Nếu không có điều kiện tham dự hội thảo, các bạn cũng có thể xem phim quay lại tại http://pyvideo.org.