Giới thiệu

Có 1 người bạn gần đây bắt đầu lập trình với threads và thiết kế chương trình như sau.

Chương trình có đầu vào là một mảng gồm một số phần tử (khoảng vài chục). Chương trình làm nhiệm vụ duyệt từng phần tử trong mảng, tính toán và trả về kết quả đối với từng phần tử. Bạn mình thiết kế chương trình bằng cách với mỗi phần tử trong mảng, bạn tạo một thread và cho thread thực hiện tính toán với phần tử đó.

Khi mình hỏi tại sao bạn lại thiết kế chương trình như thế thì bạn trả lời: các thread sẽ chạy song song nên về lý thuyết càng nhiều thread thì chương trình chạy càng nhanh!

Mình nhận ra bạn mình có về không biết định luật Amdahl, tuy đơn giản nhưng lại là một định luật rát quan trọng trong tính toán song song. Khi hiểu định luật này chắc chắn bạn sẽ có cái nhìn tổng quan hơn về hệ thống máy tính nói chung, và cụ thể là lập trình multithread nói riêng. Trong bài viết này, mình muốn giới thiệu định luật Amdahl.

Định luật Amdahl

Giả sử bạn thay CPU mới có tốc độ cao hơn CPU cũ.

Định luật Amdahl nói rằng sự tằng tốc nhờ cải thiện hiệu năng của CPU = thời gian chạy toàn bộ tác vụ khi sử dụng CPU cũ / thời gian chạy toàn bộ tác vụ khi sử dụng CPU mới.

Độ tăng tốc phụ thuộc vào 2 thừa số:

• Tỉ lệ chương trình có thể cải thiện nhờ CPU mới. Ví dụ chương trình của bạn có 60 tính toán, 20 tính toán có thể được chuyển qua CPU mới (ví dụ CPU mới cung cấp tập lệnh mà CPU không có) như vậy tỉ lệ này là 20/60. Tỉ lệ này luôn nhỏ hơn hoặc bằng 1.
• Độ Tăng tốc thu được thu được từ CPU mới. Ví dụ 20 tính toán ở ví dụ trên ở CPU cũ hết 5s, CPU mới hết 2s, độ tăng tốc sẽ là 5/2

Thời gian chạy với CPU mới = Thời gian chạy CPU cũ * (1 - tỉ lệ chương trình có thể cải thiện nhờ CPU mới + tỉ lệ chương trình có thể cải thiện nhờ CPU mới / độc tăng tốc thu được từ CPU mới).

 Độ tăng tốc tổng thể = Thời gian chạy trên CPU cũ / Thời gian chạy trên CPU mới     
                      = 1 / (1 - tỉ lệ chương trình cải thiện nhờ CPU mới + tỉ lệ chương trình cải thiện nhờ CPU mới / độ tăng tốc thu được từ CPU mới)

Ví dụ 1:

Bạn thay CPU cho máy chủ web. CPU mới chạy nhanh hơn CPU cũ 10 lần. Chương trình web của bạn giả sử tốn 60% cho SQL (I/O) và 40% tính toán (nhận kết quả từ cơ sở dữ liệu, render page). Hỏi tốc độ cải thiện từ việc thay CPU là bao nhiêu?

Giải:

• Tỉ lệ chương trình có thể cải thiện nhờ CPU mới = 0.4
• Độ tăng tốc = 10

Độ tăng tốc tổng thể = 1 / (0.6 + 0.4/10) = 1 / 0.64 = 1.56

Vậy dù rằng CPU có tính nhanh 10 lần thì tốc độ của cả hệ thống chỉ được cải thiện 1.56 lần.

Ví dụ 2:

Hàm căn bậc hai của một số thực được sử dụng rất nhiều trong đồ hoạ máy tính. Giả sử tính toán căn bậc 2 chiếm 20% tổng thời chạy của thao tác đồ hoạ. Bạn muốn tăng tốc độ của hệ thống đồ hoạ của bạn. Có 2 lựa chọn sau đây:

• Mua card đồ hoạ mới với chip tính toán nhanh hơn 10 lần.
• Tăng tốc độ của các thao tác số thực khác lên 1.6 lần (ngoài thao tác tính căn bậc 2). Giả sử tổng số thao tác số thực là 50% (50% tính toán của bạn liên quan đến số thực).

Bạn sẽ đầu tư tiền hay bỏ thời gian và trí não cải thiện các thao tác còn lại.

Giải:

Trường hợp 1, độ tăng tốc = 1 / (0.8 + 0.2 / 10) = 1 / 0.82 = 1.22

Trường hợp 2, độ tăng tốc = 1 / (0.5 + 0.5 / 1.6) = 1.23

Như vậy lựa chọn 2 cho kết quả tốt hơn 1 chút!

Quan sát

Nếu thử quan sát, bạn sẽ thấy từ công thức Amdahl có thể rút ra là độ tăng tốc phụ thuộc cả vào bản chất bài toán. Nếu tỉ lệ có thể tăng tốc được không cao, việc bạn thêm song song cũng không giải quyết vấn đề gì. Nói cách khác nếu tỉ lệ cải thiện nhờ CPU mới = 0 thì độ tăng tốc tổng thể sẽ là 1 / (1 + 0/10) = 1 tức không thay đổi.

Bạn mình sai lầm ở đâu?

Quay trở lợi vấn đề của bạn mình, tại sao mình lại nghĩ việc tăng số thread lên không giải quyết được tốc độ?

Giả sử bạn CPU bạn có 4 cores (Ví dụ Corei7 MQ). Chương trình của bạn sẽ được lập lịch bởi kernel. Nếu bạn dùng 2 threads, tại thời điểm CPU được cấp cho process của bạn, 2 cores sẽ được sử dụng để chạy chương trình. Giả sử chương trình bạn dùng CPU để tính toán 50% thời gian, 50% thời gian còn lại được chia đều cho các cores.

Nếu không dùng thread, chương trình của bạn là 1 chương trình liên tục bình thường, tốc độ sẽ cải thiện sẽ là:

Độ tăng tốc = 1 / (0.5 + 0.5 / 1) = 1 (không tăng tí nào!)

Nếu bạn dùng 2 threads:

Độ tăng tốc = 1 / (0.5 + 0.5 / 2) = 1.33 (Tăng 33%!)

Nếu bạn dùng 4 threads:

Độ tăng tốc = 1 / (0.5 + 0.5 / 4) = 1.6 (Tăng 60%!)

Nếu dùng 8 threads, bạn mong chờ tốc độ tăng tốc là 1.7! Sai lầm! Lý do: giống như quan sát ở trên, bản thân việc chia việc cho CPU không phải là việc làm song song được. Nói cách khác CPU chỉ thực hiện được cùng 1 lúc 4 tác vụ. Nếu có nhiều hơn 4 tác vụ, tỉ lệ thực hiện song song (số task thực hiện đồng thời không đổi, nhưng só task phải thực hiện tăng lên) sẽ giảm khiến hiệu năng toàn hệ thống giảm xuống.

Ví dụ ta có 4 threads, thì số task có thể tận dụng được CPU là 100%. Khi ta có 5 threads, số threads có thể tận dụng được CPU sẽ giảm xuống 80%. Ta có thể xem sự thay đổi về hiệu năng so sánh tương đối với trường hợp 1 thread như sau:

4 threads: Độ tăng tốc = 1 / (0 + 1 / 4) = 4

5 threads: Độ tăng tốc = 1 / (0.2 + 0.8 / 4) = 1 / 0.4 = 2.5

Như vậy độ tăng tốc tương đối với trường hợp chỉ sử dụng 1 thread đã giảm từ 4 lần xuông còn 2.5 lần.

Nói cách khác, khi tất cả các cores đã làm việc thì việc tăng threads sẽ chỉ làm tăng thêm phần không thể tính song song, khiến hiệu năng hệ thống giảm. Ngoài ra còn có các chi phí khác mà ta chưa kể đến như: tạo một thread cũng tốn thời gian, bộ nhớ v.v. Nói cách khác việc tăng thread không làm tăng tốc độ chương trình mà nhiều trường hợp còn làm giảm tốc độ chạy. Suy nghĩ lúc đầu của bạn mình là sai lầm!

Design nhờ định luật Amdahl

Như ở ví dụ 2 ở trên, bạn thấy rằng việc mua card đồ hoạ mới không làm tăng hiệu năng tổng thể như việc tối ưu chương trình. Như vậy ta hoàn toàn có thể thay đổi thiết kế chương trình để làm tăng hiệu năng. Ta xét bài toán ví dụ sau đây:

Nhập n. In ra tất cả các số nhỏ hơn n mà là số nguyên tố.

Dưới góc độ thread, ta có 2 cách design hệ thống (Giả định hệ thống có CPU 4 cores)

• Chia n ra làm 4 phần, mỗi thread thực hiện tìm số nguyên tố trong 1 phần.
• Một biến đếm từ 3 -> n, bước nhảy 2, cho mỗi thread đang rảnh lần lượt kiểm tra xem số hiện tại có phải là số nguyên tố không.

Bạn sẽ chọn cách nào?

Thoạt nhìn có vẻ 2 cách không có gì khác nhau, nhưng nếu để ý sẽ nhận ra là mật độ số nguyên tố không giống nhau. Nói cách khác nếu làm theo cách 1, sẽ có thread rất nhanh hoàn thành (thread phải xử lý vùng ít số nguyên tố), và có những thread phải làm việc rất vất vả (thread phải xử lý vùng có nhiều số nguyên tố). Nói cách khác cách design 1 có tỉ lệ tính toán có thể cải thiện không cao.

Cách 2 thoạt nhìn có vẻ chậm nhưng lại là cách cho tỉ lệ xử lý song song cao hơn, vì việc xử lý từng số một không phụ thuộc và phân bố của số nguyên tố!

Vậy ta nên thiết kế chương trình theo cách 2!

Tổng kết

Bài viết giới thiệu định luật Amdahl, làm rõ ý nghĩa định luật cũng qua 2 ví dụ đồng thời áp dụng định luật Amdahl vào việc thiết kế bài toán đơn giản. Hy vọng qua bài viết bạn hiểu phần nào về đột tăng tốc trong tính toán song song, cũng như biết cách tính toán định lượng để đánh giá các thiết kế (Nhiều khi mua máy mới không hắn đã là tốt!).

Quiz

1. Lý giải tại sao các hệ thống lại thiết kế dùng worker queue!
2. mysql có biến innodb_read_io_threads. Bạn sẽ thiết lập giá trị biến này là bao nhiêu?

Tài liệu tham khảo

1. Định luật Amdahl
2. Computer Architecture, A Quantitative Approach

Introduction

Trong loạt bài viết trước về Full-text search, mình đã giới thiệu về các khái niệm hết sức cơ bản để làm nên một search-engine:

• Phần 1: Giới thiệu cơ bản: Inverted Index
• Phần 2: Kỹ thuật Tokenize
• Phần 3: Tìm kiếm sử dụng Boolean Logic
• Phần 4: Các mô hình Ranking

Trong bài viết này, để khép lại loạt bài về Full-Text search, mình sẽ hướng dẫn cách làm một search engine hết sức đơn giản sử dụng inverted index. Sample code mình sẽ sử dụng Python để cho dễ hiểu.

Code Design

Việc đầu tiên trước khi code chúng ta phải design xem chương trình của chúng ta sẽ gồm những module nào, nhiệm vụ mỗi module ra sao. Để design được thì chúng ta phải làm rõ yêu cầu bài toán và cách giải quyết.

Bài toán trong bài viết này là xây dụng một search engine. Để cho đơn giản chúng ta sẽ xây dựng search engine trên command line, dựa trên đầu vào là các documents với format được định nghĩa trước. Trong bài này, mình sẽ sử dụng một sample nhỏ của twitter data như là input documents. Bài toán được tóm tắt lại như dưới đây:

1
2
3
4
5
6

Input document:
11  superkarafan  superkarafan  http://twitter.com/superkarafan Yes. He is Kendo Kobayashi. One of great JKamilia RT "@nicolexrina:  Is your twitter DP you? I have seen him in ametalk before!"
12  sao_mama  saomama http://twitter.com/sao_mama @miwauknow  持って行きたいけど、北海道からだから重い(T_T)飲むゼリーとかはダメなのかな。「SMT」のときそうしたんだけど・・・

Command-line Interface:
./searcher <word>

Như đã giới thiệu ở loạt bài trước, Full Text Search sử dụng inverted index để lưu lại term và các document chứa term đó:

1

"this" => {D1, D2, D3, D4}

Vì vậy chúng ta cần một module để lưu Structure này, chúng ta sẽ gọi module đó là DocID. DocID sẽ có nhiệm vụ là lưu term và một array để chứa id của các documents mà chứa term đó.

Tuy nhiên chỉ lưu đơn thuần dữ liệu inverted index thì sẽ không đủ, chúng ta cần một module để lưu lại các document và ID của chúng để khi có kết quả tìm kiếm chúng ta có thể present kết quả dễ dàng hơn. Module này chúng ta sẽ gọi là Content. Content sẽ lưu lại Id và nội dung của document.

Chúng ta cũng sẽ cần một module để làm nhiệm vụ phân tích document ra thành các term như đã giới thiệu trong Bài 2: Kỹ thuật Tokenize. Chúng ta sẽ gọi module này là Tokenizer.

Đã có Tokenizer, DocID, Content, chúng ta cần một module sử dụng cả 3 module này để lưu trữ thông tin được tạo ra từ Tokenizer vào DocID và Content, chúng ta sẽ gọi nó là Indexer.

Cuối cùng, chúng ta cần một module sử dụng boolean logic như đã giới thiệu trong Bài 3 để tìm kiếm. Chúng ta sẽ gọi module này là Searcher. Module Searcher sẽ có nhiệm vụ sử dụng tách query ra thành các term, search ra một tập document chứa các term đó, và present ra màn hình.

Tóm tắt lại chúng ta sẽ có các module sau:

• DocID : Lưu inverted index
• Content : Lưu id và dữ liệu thô từ input data
• Tokenizer : Bóc tách term
• Indexer : Sử dụng tokenizer để lưu thông tin
• Searcher : Tìm kiếm

Implement

Để implement bài toán này chúng ta sẽ sử dụng python. Chúng ta cũng cần một thư viện để lưu lại/sử dụng (dump) dữ liệu (inverted index) ra file. Python có một thư viện rất tốt để dump data structure ra file gọi là Pickle.

Sử dụng pickle, chúng ta sẽ lưu dữ liệu ra file và khi load chương trình lên sẽ sử load file vào data structure lên sau. Tách ra làm 2 bước như vậy giúp chúng ta tách biệt được 2 quá trình 1) Index và 2) Search, mà qua đó khi có thêm dữ liệu mới, index file sẽ được update thêm mà không ảnh hưởng đên Searcher.

Dưới đây chúng ta sẽ đi lần lượt vào implementation của từng module. Đầu tiên là DocID.

DocID

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

import pickle

class DocID:
  def __init__(self):
    self.docIDTable = dict()

  def get_doc_num(self):
    return len(self.docIDTable)

  def set(self, term, docID, termPos):
    value = self.docIDTable.get(term, [])
    value.append((docID, termPos))
    self.docIDTable[term] = value

  def get(self, term):
    return self.docIDTable.get(term, [])

  def dump(self, file):
    f = open(file, "w")
    pickle.dump(self.docIDTable, f)
    f.close()

  def load(self, file):
    f = open(file)
    self.docIDTable = pickle.load(f)
    f.close()

Ở DocID chúng ta có property docIDTable được lưu dưới dạng dictionary của python, mà trong đó key là term , và value sẽ là array chứa Ids của các document chứa term đó. docIDTable chính là biểu diễn bằng code của inverted index data structure.

Module DocID có các hàm dump và load để lưu dữ liệu ra file và load dữ liệu lên memory. Tiếp theo chúng ta sẽ đến với implemetation của module Content.

Content

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

import pickle

class Content:
  def __init__(self):
    self.contentTable = dict()

  def get_content_num(self):
    return len(self.contentTable)

  def set(self, content):
    self.contentTable[self.get_content_num()] = content
    current_index = self.get_content_num() - 1
    return current_index

  def get(self, id):
    return self.contentTable.get(id)

  ...

Module này chỉ nhằm nhiệm vụ lưu lại dữ liệu của document và Id của document đó. Việc này sẽ được thực hiện cũng qua dictionary của python, với key là Id của document, và value là content của document tương ứng.

Tiếp đến, module Tokenizer sẽ được implement như dưới đây

Tokenizer

Để cho đơn giản, tokenizer của chúng ta sẽ sử dụng ngram.

1
2
3
4
5
6
7
8
9
10

class Tokenizer:
  def __init__(self, engine):
    self.engine = engine

  def split(self, statement, ngram):
    result = []
    if(len(statement) >= ngram):
      for i in xrange(len(statement) - ngram + 1):
        result.append(statement[i:i+ngram])
    return result

Indexer

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

from docid import DocID
from content import Content
from tokenizer import Tokenizer


class Index:
  def __init__(self, ngram):
    self.tokenizer = Tokenizer("ma")
    self.docID = DocID()
    self.content = Content()
    self.ngram = ngram

  def tokenize(self, statement):
    return self.tokenizer.split(statement)

  def append_doc(self, token, id, pos):
    return self.docID.set(token, id, pos)

  def set_content(self, statement):
    return self.content.set(statement)

  def append(self, statement):
    tokenized_str = self.tokenize(statement)
    content_id = self.set_content(statement)

    token_index = 0

    for token in tokenized_str:
      self.append_doc(token, content_id, token_index)
      token_index += 1

  def dump(self, dir):
    f_content_name = "content.pickle"
    f_docid_name = "docid.pickle"
    self.content.dump(f_content_name)
    self.docID.dump(f_docid_name)

  def load(self, dir):
    f_content_name = "content.pickle"
    f_docid_name = "docid.pickle"

    self.content.load(f_content_name)
    self.docID.dump(f_docid_name)

def main(filepath, column):
  indexer = Index(NGRAM)
  f = codecs.open(filepath, "r", "utf-8")
  lines = f.readlines()

  for line in lines:
    print line
    elems = line.split("\t")
    indexer.append(''.join(elems[column-1]))

  f.close()
  indexer.dump("data/")
  return

if __name__ == "__main__":
  if len(sys.argv) < 3:
    print "usage: ./indexer.py INPUT_TSV_FILE_PATH TARGET_COLUMN_NUM"
    sys.exit(1)
  filepath = sys.argv[1]
  column = int(sys.argv[2])
  main(filepath, column)

Module này có nhiệm vụ là sử dụng Tokenizer để tách input document thành các term sử dụng ngram, tức là mỗi term sẽ có độ dài bằng độ dài ngram. Sau đó sẽ index term đó vào DocID, nếu term đó đã tồn tại thì id của document hiện tại sẽ được add vào docIDTable của docId thông qua hàm “set”.

Kết quả index sẽ được lưu vào file docid.pickle (inverted index data) và content.pickle (content data).

Searcher

Module này có nhiệm vụ load dữ liệu đã qua index từ 2 file docid.pickle và content.pickle vào memory, sau đó với mỗi query, Searcher sẽ phân tích query đó thành các term dựa vào tokenizer, tìm kiếm document chứa các term đó dựa vào dữ liệu từ docid, và present kết quả ra màn hình dựa vào dữ liệu lấy được từ content.pickle:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

from docid import DocID
from content import Content
from tokenizer import Tokenizer
from collections import Counter
import collections

class Searcher:
  def __init__(self, ngram, dir):
    self.docID = DocID()
    self.tokenizer = Tokenizer()
    self.content = Content()
    self.docID.load(dir + "docid.pickle")
    self.content.load(dir + "content.pickle")
    self.result = dict()

  def search(self, statement, numOfResult):
    tokenized_list = self.tokenizer.split_query(statement)
    return self._search(tokenized_list, numOfResult)

  def _search(self, tokenList, numOfResult):
    token_search_index = 0

    for token in tokenList:
      content_ids = self.docID.get(token)

      for content_id in content_ids:
        if not result[content_id]:
          self.result[content_id] = 0
        else:
          self.result[content_id] = result[content_id] + 1

  def print_result(self):
    sorted_result = sorted(self.result.items(), reverse=True)
    for item in sorted_result:
      print "{}\n".format(self.content.get(item))

Chúng ta có thể thấy Searcher là một module rất đơn giản sử dụng tokenizer để bóc tách query. Sau khi bóc tách query thành các term, với mỗi term chúng ta sẽ tìm các document chứa term đó dựa vào docID. Mỗi term chúng ta sẽ thu được một chuỗi Ids chứa id của document chứa chúng.

Để kết hợp các các chuỗi ids tìm được thành kết quả cuối cùng, chúng ta làm một mô hình ranking rất đơn giản, document nào chứa nhiều term hơn thì hiển thị trước. Logic này được thực hiện dựa vào tạo một dictionary chứa kết quả (self.result) , cứ mỗi khi tìm được document nào thì ta cộng kết quả thêm 1.

Kết quả cuối cùng sẽ được in ra màn hình thông qua hàm print_result. Như vậy chúng ta đã implement xong một search engine hết sức đơn giản.

Conclusion

Thông qua chuỗi bài viết, chúng ta đã hiểu được phần nào việc tạo ra một search engine. Để có một search engine thành công, như google hay yahoo, không những performance phải được hoàn thiện ở mức tối đa với khối lượng dữ liệu rất lớn, thì việc có một mô hình ranking thích hợp cũng vô cùng quan trọng. Hy vọng chuỗi bài viết đã đem đến cho các bạn cái nhìn cơ bản nhất về search engine.

Giới thiệu

Quy hoạch động là một trong những kĩ thuật lập trình cơ bản được sử dụng khá nhiều trong các cuộc thi lập trình. Ý tưởng về cơ bản rất đơn giản: để giải một bài toán, chúng ta đi giải các bài toán con, sau đó tổng hợp các lời giải đó lại thành lời giải của bài toán ban đầu. Trong một số bài toán, nếu không sử dụng quy hoạch động, rất nhiều bài toán con sẽ bị tính lặp đi lặp lại. Quy hoạch động sẽ tìm cách để giải mỗi bài toán con đúng 1 lần để giảm thiểu số lần tính toán. Một khi lời giải cho một bài toán con đã có, chúng ta lưu lại và lần tiếp theo cần lời giải đó, chúng ta chỉ cần tìm lại.

Quy hoạch động được sử dụng rất nhiều trong các thuật toán khác, ví dụ như: thuật toán Dijkstra tìm đường đi ngắn nhất, Knapsack, Nhân ma trận theo chuỗi (Chain matrix multiplication), thuật toán Floyd-Warshall tìm đường đi ngắn nhất giữa mọi cặp đỉnh trong đồ thị (đã có bài viết giới thiệu về thuật toán này).

Trong bài viết này, chúng ta sẽ cùng đi qua một số ví dụ sử dụng quy hoạch động trên TopCoder.

Ví dụ 1: ZigZag

A sequence of numbers is called a zig-zag sequence if the differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) may be either positive or negative. A sequence with fewer than two elements is trivially a zig-zag sequence.

For example, 1,7,4,9,2,5 is a zig-zag sequence because the differences (6,-3,5,-7,3) are alternately positive and negative. In contrast, 1,4,7,2,5 and 1,7,4,5,5 are not zig-zag sequences, the first because its first two differences are positive and the second because its last difference is zero.

Given a sequence of integers, sequence, return the length of the longest subsequence of sequence that is a zig-zag sequence. A subsequence is obtained by deleting some number of elements (possibly zero) from the original sequence, leaving the remaining elements in their original order.

{ 1, 7, 4, 9, 2, 5 }

Returns: 6

The entire sequence is a zig-zag sequence.

{ 1, 17, 5, 10, 13, 15, 10, 5, 16, 8 }

Returns: 7

There are several subsequences that achieve this length. One is 1,17,10,13,10,16,8.

{ 44 }

Returns: 1

{ 1, 2, 3, 4, 5, 6, 7, 8, 9 }

Returns: 2

{ 70, 55, 13, 2, 99, 2, 80, 80, 80, 80, 100, 19, 7, 5, 5, 5, 1000, 32, 32 }

Returns: 8

{ 374, 40, 854, 203, 203, 156, 362, 279, 812, 955, 600, 947, 978, 46, 100, 953, 670, 862, 568, 188, 67, 669, 810, 704, 52, 861, 49, 640, 370, 908, 477, 245, 413, 109, 659, 401, 483, 308, 609, 120, 249, 22, 176, 279, 23, 22, 617, 462, 459, 244 }

Returns: 36

Bài toán này là một dạng của bài toán tìm xâu dài nhất thoả mãn một điều kiện nào đó, ví dụ như tăng dần, giảm dần… Cách làm quy hoạch động là như sau: duyệt từ trái sang phải, tìm xâu dài nhất kết thúc tại phần tử đang xét. Xâu dài nhất này được tính dựa trên các bài toán con phía trước:

• Xem có thể thêm phần tử hiện tại vào các xâu dài nhất két thúc bằng các phần tử phía trước không.

• Chọn xâu dài nhất có thể trong các xâu thoả mãn.

Sau đây là đoạn code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

#include <iostream>
#include <cmath>
#include <vector>
using namespace std;

class ZigZag{
public:
  int longestZigZag(vector<int> sequence);
};

int ZigZag::longestZigZag(vector<int> sequence){
  int n = sequence.size();
  int f[n];
  bool isUp[n]; // check if in the longest sequence up to i-th member, we are going up or down
  for (int i = 0 ; i < n ; i++){
      f[i] = 1;
      for(int j = 0; j < i; j++){
          //special case
          if(j == 0 ){
              f[i] = 2;
              isUp[i] = sequence[i] > sequence[0];
          }
          if(isUp[j] == true && sequence[j] > sequence[i]){
              if(f[i] < f[j] + 1){
                  f[i] = f[j] + 1;
                  isUp[i] = false;
              }
          }
          if(isUp[j] == false && sequence[j] < sequence[i]){
              if(f[i] < f[j] + 1){
                  f[i] = f[j] + 1;
                  isUp[i] = true;
              }
          }
      }
  }

  return f[n-1];
}

Ví dụ 2: AvoidRoads

In the city, roads are arranged in a grid pattern. Each point on the grid represents a corner where two blocks meet. The points are connected by line segments which represent the various street blocks. Using the cartesian coordinate system, we can assign a pair of integers to each corner as shown below.

You are standing at the corner with coordinates 0,0. Your destination is at corner width,height. You will return the number of distinct paths that lead to your destination. Each path must use exactly width+height blocks. In addition, the city has declared certain street blocks untraversable. These blocks may not be a part of any path. You will be given a String[] bad describing which blocks are bad. If (quotes for clarity) “a b c d” is an element of bad, it means the block from corner a,b to corner c,d is untraversable. For example, let’s say width = 6 length = 6 bad = {“0 0 0 1”,“6 6 5 6”} The picture below shows the grid, with untraversable blocks darkened in black. A sample path has been highlighted in red.

Examples

6

6

{“0 0 0 1”,“6 6 5 6”}

Returns: 252

Example from above.

1

1

{}

Returns: 2

Four blocks aranged in a square. Only 2 paths allowed.

35

31

{}

Returns: 6406484391866534976

Big number.

2

2

{“0 0 1 0”, “1 2 2 2”, “1 1 2 1”}

Returns: 0

Vẫn trên tư tưởng quy hoạch động, dễ thấy ta cần duyệt từ đỉnh (0,0). Số lượng đường đi đến đỉnh (i,j) sẽ dựa trên số lượng đường đi đến đỉnh (i-1,j) và đỉnh (i, j-1). Chú ý nếu đường đi từ (i-1,j) hoặc (i, j-1) đến (i,j) bị chặn thì ta sẽ không tính đoạn đường đó nữa.

Sau đây là đoạn code (C++):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <cmath>
#include <algorithm>

using namespace std;

class AvoidRoads{
public:
  long numWays(int width, int height, vector<string> bad);
};

long AvoidRoads::numWays(int width, int height, vector<string> bad){
  bool badVertical[width+1][height+1];
  bool badHorizontal[width+1][height+1];

  for(int i = 0; i <= width; i++){
      for(int j = 0 ; j <= height; j++){
          badVertical[i][j] = false;
          badHorizontal[i][j] = false;
      }
  }

  for(int i = 0; i< bad.size(); i++){
      stringstream temp(bad[i]);
      int x, y, z,  t;
      temp >> x >> y >> z >> t;
      if(abs(z - x) ==1){
          badHorizontal[min(x,z)][y] = true;
          cout << "bad Horizontal at: " << min(x,z) << ", " << y << "\n";
      }
      else if(abs(t - y) == 1){
          badVertical[x][min(y,t)] = true;
          cout << "bad Vertical at: " << x << ", " << min(y,t) << "\n";
      }
  }

  long res [width+1][height+1];
  res[0][0] = 1;
  for(int i = 0; i<= width; i++ ){
      for(int j = 0; j <= height; j++){
          //don't override the base case
          if((i == 0) && (j == 0)){
              continue;
          }

          long temp = 0;
          if(i>0 && !badHorizontal[i-1][j] ) {
              temp += res[i-1][j];
          }
          if(j>0 && !badVertical[i][j-1]){
              temp += res[i][j-1];
          }
          cout << "temp = " << temp << "\n";
          res[i][j] = temp;
          cout << "Ways to (" << i << "," << j << ") is: " << res[i][j] << "\n";
      }
  }
  return res[width][height];
}

Kết luận

Hi vọng qua 2 ví dụ trên, bạn đã phần nào có được tư tưởng quy hoạch động. Về cơ bản, chúng ta chỉ cần đi đến được cách tính bài toán hiện tại dựa vào các bài toán con trước đó là 90% công việc đã xong. Hãy luyện tập thêm để chiến đấu tại TopCoder!

Tham khảo

1. TopCoder Graph Tutorial
2. ZigZag
3. AvoidRoad