Thuật toán Floyd cài đặt khá đơn giản, dựa trên ý tưởng: Nếu có đường đi từ i tới k và từ k tới j nhỏ hơn đường đi hiện tại từ i tới j thì ta sẽ cập nhật đường đi từ i tới j thành đường đi từ i tới k cộng với từ k tới j. Ta gọi k là đỉnh trung gian của i và j. Như vậy sau khi thực hiện thuật toán, sẽ có một số cạnh “ảo” được sinh ra, tức là các cạnh không nối trực tiếp giữa hai đỉnh.

for k:=1 to n do for i:=1 to n do for j:=1 to n do path[i,j] := min (path[i,j] , path[i,k] + path[k,j] ); Như vậy mặc dù có độ phức tạp lên tới O(n^3) nhưng ta chỉ cần thực hiện 1 lần là có thể tìm đường đi ngắn nhất giữa hai đỉnh bất kì.

Tham khảo thêm tại:

http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm

Trong bài toán này tôi sử dụng ma trận kề với giá trị data[i,j] = -1 để biểu diễn không có đường đi giữa hai đỉnh i và j. Sau đó tạo thêm một mảng 2 chiều FloydData để lưu kết quả sau quá trình thực hiện thuật toán Floyd.

public void Floyd() {

if (Data == null)  
    return;  
int n = Data.GetLength(0);
FloydData = new MatrixCell[n, n];
for (int i = 0; i < n; i++)  
    for (int j = 0; j < n; j++)  
        FloydData[i, j] = new FloydCell(Data[i, j]);
for (int i = 0; i < n; i++)  
{  
    for (int j = 0; j < n; j++)  
    {  
        if (FloydData[j, i].Value > 0)  
        {  
            for (int k = 0; k < n; k++)  
            {  
                if (FloydData[i, k].Value > 0)  
                {  
                    if (FloydData[j, k].Value < 0 || FloydData[j, i].Value + FloydData[i, k].Value < FloydData[j, k].Value)  
                    {  
                        FloydData[j, k].Value = FloydData[j, i].Value + FloydData[i, k].Value;
                        FloydData[j, k].Previous = i;  
                    }  
                }  
            }  
        }  
    }  
}  

struct FloydCell {

public int Previous;  
public int Value;
public FloydCell(int value)  
    : this(-1, value)  
{ }  
public FloydCell(int previous, int value)  
{  
    this.Previous = previous;  
    this.Value = value;  
}  

Lấy đường đi ngắn nhất giữa hai đỉnh

List<Point> _path = new List<Point>(); // […] void GetPath(int x,int y) {

if(_matrix.FloydData[x,y].Value== -1)  
    return;  
int i=_matrix.FloydData[x,y].Previous;  
if(i== -1)  
{  
    _path.Add(new Point(x+1,y+1));  
    return;  
}  
else  
{  
    GetPath(x,i);  
    _path.Add(new Point(_preNodeIndex+1,i+1));  
    _preNodeIndex=i;  
    GetPath(i,y);  
}  

Khi nhắc đến các thuật toán duyệt đồ thị, có thể bạn đã biết (và đã từng implement) Depth-First Search, Breadth-First Search, hoặc Dijkstra. Xin nhắc lại về ý nghĩa của từng thuật toán, đứng ở khía cạnh bài toán tìm đường đi ngắn nhất. DFS dùng để giải các bài toán mà chúng ta muốn tìm được lời giải (không nhất thiết phải là quãng đường ngắn nhất), hoặc ta muốn thăm tất cả các đỉnh của đồ thị. BFS cũng để duyệt các đỉnh của đồ thị, nhưng có một tính chất quan trọng là: nếu tất cả các cạnh không có trọng số, lần đầu tiên một đỉnh được thăm, ta có ngay đường đi ngắn nhất đến đỉnh đó. Bây giờ đến thuật toán Disjkstra, đây là thuật toán nổi tiếng dùng để tìm đường đi ngắn nhất từ một đỉnh cho trước đến các đỉnh còn lại, trong một đồ thị có các cạnh có trọng số không âm. Như vậy, Dijkstra đã tiến hơn một bước so với BFS.

Đó là sơ qua về ba thuật toán mà có thể mọi người đều đã biết. Trong bài viết này, tôi xin giới thiệu một thuật toán ít biết đến hơn để duyệt đồ thị, đó là Floyd-Warshall.

Thuật toán Floyd-Warshall là gì?

Nếu như Dijkstra giải quyết bài toán tìm đường đi ngắn nhất từ một đỉnh cho trước đến mọi đỉnh khác trong đồ thị, thì Floyd-Warshall sẽ tìm đường đi ngắn nhất giữa mọi đỉnh sau một lần chạy thuật toán. Một tính chất nữa là Floyd-Warshall có thể chạy trên đồ thị có các cạnh có trọng số có thể âm, tức là không bị giới hạn như Dijkstra. Tuy nhiên, lưu ý là trong đồ thị không được có vòng (cycle) nào có tổng các cạnh là âm, nếu có vòng như vậy ta không thể tìm được đường đi ngắn nhất (mỗi lần đi qua vòng này độ dài quãng đường lại giảm, nên ta có thể đi vô hạn lần)

Thuật toán Floyd-Warshall so sánh tất cả các đường đi có thể giữa từng cặp đỉnh. Nó là một dạng của quy hoạch động (Dynamic Programming). Đặt hàm adj(i,j,k) là đường đi ngắn nhất từ i đến j, chỉ dùng các đỉnh trong tập {1,2,…,k}. Giả sử ta muốn tính adj{i,j,k+1}. Với mỗi cặp đỉnh i và j, đường đi ngắn nhất có thể là: (1) đường đi chỉ sử dụng các đỉnh trong tập {1,…k} hoặc (2) đường đi từ i đến k+1 rồi từ k+1 đến j, cũng chỉ sử dụng các đỉnh trong tập {1,…k}. Do vậy:

Trường hợp cơ bản: adj(i,j,0) = w(i,j)

Đệ quy: adj(i,j,k+1) = min{adj(i,j,k), adj(i,k+1, k) + adj(k+1, j, k)}

Đây là đoạn pseudocode của Floyd-Warshall (có một chút thay đổi, nhưng ý tưởng là như nhau)

pseudo.c

1 2 3 4

for(k=1 to n)
  for(i=1 to n)
      for(j=1 to n)
          adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]);

Dễ thấy độ phức tạp thuật toán là O(n^3) với n là số đỉnh của đồ thị.

Thuật toán Floyd-Warshall dùng cho tìm tính chất kết nối

Tư tưởng của thuật toán Floyd-Warshall trong việc tìm đường đi ngắn nhất có thể áp dụng vào các bài toán dạng tìm tính chất kết nối giữa các đỉnh. Tôi xin lấy một ví dụ, đó là bài TopCoder SRM 184, Div 2, 1000-point problem

Đề bài như sau (xin chịu khó đọc hiểu đề bài)

You are arranging a weird game for a team building exercise. In this game there are certain locations that people can stand at, and from each location there are paths that lead to other locations, but there are not necessarily paths that lead directly back. You have everything set up, but you need to know two important numbers. There might be some locations from which every other location can be reached. There might also be locations that can be reached from every other location. You need to know how many of each of these there are.

Create a class TeamBuilder with a method specialLocations that takes a String[] paths that describes the way the locations have been connected, and returns a int[] with exactly two elements, the first one is the number of locations that can reach all other locations, and the second one is the number of locations that are reachable by all other locations. Each element of paths will be a String containing as many characters as there are elements in paths. The i-th element of paths (beginning with the 0-th element) will contain a ‘1’ (all quotes are for clarity only) in position j if there is a path that leads directly from i to j, and a ‘0’ if there is not a path that leads directly from i to j.

Examples

{“010”,“000”,“110”} Returns: { 1, 1 } Locations 0 and 2 can both reach location 1, and location 2 can reach both of the other locations, so we return {1,1}. {“0010”,“1000”,“1100”,“1000”} Returns: { 1, 3 } Only location 3 is able to reach all of the other locations, but it must take more than one path to reach locations 1 and 2. Locations 0, 1, and 2 are reachable by all other locations. The method returns {1,3}. {“01000”,“00100”,“00010”,“00001”,“10000”} Returns: { 5, 5 } Each location can reach one other, and the last one can reach the first, so all of them can reach all of the others. {“0110000”,“1000100”,“0000001”,“0010000”,“0110000”,“1000010”,“0001000”} Returns: { 1, 3 }

Solution Về cơ bản, bài này cần tìm số lượng các đỉnh mà từ đó có thể đi đến tất cả các đỉnh khác, và số lượng các đỉnh mà các đỉnh khác đều có thể đi tới. Một ví dụ rất tốt để áp dụng thuật toán Floyd-Warshall tìm tính chất kết nối giữa 2 đỉnh bất kì.

Trong bài này, chúng ta chỉ cần phải kiểm tra xem có đường đi từ đỉnh i đến đỉnh j trong đồ thị hay không. Chúng ta sẽ áp dụng thuật toán Floyd-Warshall trên, nhưng có thay đổi một chút trong dòng xử lý bên trong vòng lặp. Về cơ bản, chúng ta vẫn sử dụng ý tưởng là update thông tin giữa 2 đỉnh i và j, mỗi khi ta có thêm thông tin giữa đỉnh i và đỉnh k, đỉnh k và đỉnh j, với k là một đỉnh khác i và j. Nhưng ta không cập nhật thông tin về * đường đi ngắn nhất* nữa, mà ta cập nhật thông tin về có hay không đường đi từ i đến j. Với mỗi cặp đỉnh i và j chưa có kết nối, ta sẽ kiểm tra xem nếu có đường đi từ i đến k và từ k đến j, thì ta cập nhật là có đường đi từ i đến j.

Sau đây là đoạn code C++ minh hoạ:

TeamBuilder.cpp

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 66 67 68

vector<int> TeamBuilder::specialLocations(vector<string> paths){

  int N = paths.size();
  vector<vector<int> > adj;
  
  for(int i = 0; i < N; i ++){
      string s = paths[i];
      vector<int> row;
      for(int j = 0; j < N; j++){
          row.push_back(s[j] -'0');
      }
      adj.push_back(row);
  }

  //Floyd-Warshall
  for(int k = 0; k < N; k++){
      for (int i = 0; i < N; i++){
          for(int j = 0; j < N; j++){
              //i,j,k must be different
              if(i==j || j == k || k==i)
                  continue;

              //only update those no-paths
              if(adj[i][j] == 0){
                  if(adj[i][k] !=0 && adj[k][j] != 0){
                      adj[i][j] = 1;
                  }
              }
          }
      }

  }

  //find number of locations that can reach all other locations
  int firstNum = 0;
  for(int i = 0 ; i < N; i++){
      bool canReachAll = true;
      for(int j = 0; j<N; j++){
          if(j==i) continue;

          if(adj[i][j] == 0){
              canReachAll = false;
              break;
          }
      }
      if(canReachAll)
          firstNum ++;
  }

  //find number of locations that are reachable from other locations
  int secondNum = 0;
  for(int j = 0 ; j < N; j++){
      bool canBeReachedFromAll = true;
      for(int i = 0; i<N; i++){
          if(j!=i && adj[i][j] == 0){
              canBeReachedFromAll = false;
              break;
          }
      }
      if(canBeReachedFromAll)
          secondNum ++;
  }

  vector<int> res;
  res.push_back(firstNum);
  res.push_back(secondNum);
  return res;
}

Tham khảo:

1. Floyd-Warshall Algorithm
2. TopCoder Graph Tutorial

Full Text Search Từ Khái Niệm đến Thực Tiễn (Phần 4)

Introduction

Trong phần 3, các bạn đã được tìm hiểu về việc sử dụng Boolean Logic để tìm ra các Document chứa các term trong query cần tìm kiếm. Vậy sau khi tìm được các Document thích hợp rồi thì chỉ việc trả lại cho người dùng, hay đưa lên màn hình? Bài toán sẽ rất đơn giản khi chỉ có 5, 10 kết quả, nhưng khi kết quả lên đến hàng trăm nghìn, thì mọi việc sẽ không đơn giản là trả lại kết quả nữa. Lúc đó sẽ có vấn đề mới cần giải quyết, đó là đưa kết quả nào lên trước, hay chính là bài toán về Ranking

Việc Ranking trong Full Text Search thông thường sẽ được thực hiện thông qua việc tính điểm các Document được tìm thấy, rồi Rank dựa vào điểm số tính được. Việc tính điểm thế nào sẽ được thực hiện thông qua các công thức, hay thuật toán, mà mình gọi chung là Ranking Model

Ranking Model

Trong bài viết về Ranking news, mình đã nói về việc giải quyết một bài toán gần tương tự. Tuy nhiên bài toán lần này cần giải quyết khác một chút, đó là việc Ranking sẽ phải thực hiện dựa trên mối quan hệ giữa “query terms” và “document”.

Ranking Model được chia làm 3 loại chính: Static, Dynamic, Machine Learning. Dưới đây mình sẽ giới thiệu lần lượt về mỗi loại này.

Static

Static ở đây có nghĩa là, Ranking Model thuộc loại này sẽ không phụ thuộc vào mối quan hệ ngữ nghĩa giữa “query term” và “document”. Tại sao không phụ thuộc vào “query term” mà vẫn ranking được? Việc này được giải thích dựa theo quan điểm khoa học là

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 66 67 68

0.

Chúng ta sẽ đi vào cụ thể một Ranking Model rất nổi tiếng trong loại này, đó chính là PageRank. PageRank là thuật toán đời đầu của Google, sử dụng chủ yếu cho web page, khi mà chúng có thể “link” được đến nhau. Idea của PageRank là “Page nào càng được nhiều link tới, và được link tới bởi các page càng quan trọng, thì score càng cao”. Để tính toán được PageRank, thì chúng ta chỉ cần sử dụng WebCrawler để crawl được mối quan hệ “link” giữa tất cả các trang web, và tạo được một Directed Graph của chúng.

Chính vì cách tính theo kiểu, tạo được Graph xong là có score, nên mô hình dạng này được gọi là “Static”.

Ngoài PageRank ra còn có một số thuật toán khác gần tương tự như HITS đã từng được sử dụng trong Yahoo! trong thời gian đầu.

Dynamic

Ranking Model thuộc dạng Dynamic dựa chủ yếu vào Mối quan hệ giữa “query term” và “document”. Có rất nhiều thuật toán thuộc dạng này, có thuật toán dựa vào tần suất xuất hiện của “query term” trong document, có thuật toán lại dựa vào các đặc tính ngữ nghĩa (semantic) của query term , có thuật toán lại sử dụng những quan sát mang tính con người như thứ tự xuất hiện các từ trong “query term” và thứ tự xuất hiện trong “document”.

Một trong những thuật toán được sử dụng nhiều nhất là TF-IDF (Term Frequency Inverse Document Frequency). Thuật toán này dựa vào Idea là “query term” xuất hiện càng nhiều trong document, document sẽ có điểm càng cao.

Thuật toán này được biểu diễn dưới công thức sau \[TF-IDF(t, d, D) = TF(t, d) * IDF (t, D)\] Ở đây t là query term, d là document cần được score, và D là tập hợp “tất cả” các documents. Trong đó thì: \[TF(t, d) = frequency(t, d)\] \[IDF(t, D) = log{N \over \|\{d \in D : t \in d\}\|}\]

Một cách đơn giản thì:

• TF : tần suất xuất hiện của term t trong document d
• IDF : chỉ số này biểu hiện cho tần suất xuất hiện của term t trong toàn bộ các documents. t xuất hiện càng nhiều, chỉ số càng thấp (vì xuất hiện quá nhiều đồng nghĩa với độ quan trọng rất thấp)

Công thức của TF-IDF đã phối hợp một cách rất hợp lý giữa tần suất của term và ý nghĩa/độ quan trọng của term đó.

Trong thực tế thì người ta hay sử dụng thuật toán Okapi BM25 hay gọi tắt là BM25, là một mở rộng của TF-IDF, nhưng thêm một vài weight factor hợp lý.

Machine Learning

Ngoài việc sử dụng các mối quan hệ đơn giản giừa query term và document, hay giứa document với nhau, thì gần đây việc sử dụng học máy (Machine Learning) trong Ranking cũng đang trở nên rất phổ biến. Để nói về Machine Learning thì không gian bài viết này có lẽ là không đủ, mình sẽ nói về ý tưởng của Model này.

Idea của việc sử dụng Machine Learning trong ranking là chúng ta sẽ sử dụng một mô hình xác suất để tính toán. Cụ thể hơn là chúng ta sẽ sử dụng supervised learning, nghĩa là chúng ta sẽ có input là một tập dữ liệu X để training, một model M ban đầu, một hàm error để so sánh kết quả output X’ có được từ việc áp dụng model M vào query term, và một hàm boost để từ kêt quả của hàm error chúng ta có thể tính lại được model M. Việc này được lặp đi lặp lại mỗi lần có query, hoặc lặp lại một cách định kỳ (1 ngày 1 lần, 1 tháng 1 lần..) để model M luôn luôn được cải thiện.

Thuật toán gần đây được sử dụng khá nhiều trong Ranking model chính là Gradient Boosting Decision Tree mà các bạn có thể tham khảo ở đây

Conclusion

Bài viết đã giới thiệu về 3 mô hình chính dùng để Ranking kết quả tìm kiếm trong Full Text Search. Trong thực tế thì các công ty lớn nhưn Google, Yahoo, MS sẽ không có một mô hình cố định nào cả, mà sẽ dựa trên các kết quả có từ người dùng để liên tục cải thiện. Không có một mô hinh nào là “đúng” hay “không đúng” cả, mà để đánh giá Ranking Model chúng ta sẽ phải dựa trên thông kê người dùng (như click rate, view time…). Việc hiểu rõ Ranking Model sẽ giúp chúng ta build được một search engine tốt cho service của mình, đông thời cũng giúp ích rất nhiều cho việc SEO (Search Engine Optimization).

Tài liệu tham khảo: - Yahoo! Learning to Rank Challenge Overview

include,

import, @import (Clang Modules)

Mở đầu

Happy New Year! Chúc mọi người năm mới vui vẻ, hạnh phúc.

Như các bạn cũng biết gần đây XCode5 cùng iOS7 đã được giới thiệu. Đi cùng XCode5 là feature mới “modules” của Clang, một giải pháp nhằm giải quyết một số vấn đề như tăng tốc độ compile source code của ứng dụng. Hôm nay mình sẽ giới thiệu qua về tính năng modules này. Hiện tại thì modules đã có thể sử dụng trong C và Objective-C trên môi trường iOS7 hoặc MacOSX 10.9. Các đoạn code dưới đây tuy mình viết bằng Objective-C nhưng cũng gần như tương tự với C. Để hiểu về modules thì trước tiên mình sẽ giải thích lần lượt về

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 66 67 68

1,

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 66 67 68

2, và pre-compiled headers (PCH), sau đó là về modules.

include

Khi chúng ta include 1 file header thì tại giai đoạn preprocessing của quá trình compile, compiler sẽ copy nội dung của file header này và paste vào dòng

include. Và tất nhiên quá trình copy/paste này là đệ quy cho đến khi copy xong tất cả file header mà nó include và các file header khác được include tại các file nó include. (hơi xoắn)

Ví dụ với chương trình helloworld quen thuộc như dưới đây:

helloworld.m

1 2 3 4 5 6 7 8

# include <Foundation/Foundation.h>

int main(int argc, const char *argv[])
{
     NSLog(@“Hello world”);

     return 0;
}

Chúng ta có thể chạy preprocessor để xem file sinh ra sau giai đoạn này bằng lệnh

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 66 67 68

3.

Nhìn vào kết quả output chúng ta có thể thấy tới hơn 92000 dòng là của Foundation.h (và của các file header mà Foundation.h include), chỉ 8 dòng cuối là code của chúng ta.

Với việc sử dụng

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 66 67 68

1 tồn tại vấn đề gọi là recursive include. Ví dụ :

FirstFile.h

1 2 3

# include "SecondFile.h"

/* Some code */

SecondFile.h

1 2 3

# include "FirstFile.h"

/* Some other code */

Khi đấy preprocessor sẽ duyệt file FirstFile.h và copy nội dung của SecondFile.h vào FirstFile.h. Khi duyệt file SecondFile.h lại copy/paste nội dung của file FirstFile.h. Vấn đề này được gọi là recursive include.

import

Trong Objective-C để tránh vấn đề recursive include như trên thì chúng ta thường dùng

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 66 67 68

2. Khi dùng

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 66 67 68

2 thì trước khi include 1 file header, preprocessor sẽ kiểm tra xem file đấy đã được include chưa, nếu đã include rồi thì sẽ không include nữa. Tương tự trong C chúng ta cũng tránh recursive include bằng việc kiểm tra file header đã được include chưa như sau:

for(k=1 to n)
  for(i=1 to n)
      for(j=1 to n)
          adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]);

0

for(k=1 to n)
  for(i=1 to n)
      for(j=1 to n)
          adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]);

1

@import

Tuy nhiên việc sử dụng

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 66 67 68

2 cũng như

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 66 67 68

1 khiến cho preprocessor đối mặt với 1 số vấn đề khác như Fragility và Performance. Để hiểu về vấn đề Header Fragility chúng ta xem qua một ví dụ đơn giản sau:

MyFile.h

for(k=1 to n)
  for(i=1 to n)
      for(j=1 to n)
          adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]);

2

for(k=1 to n)
  for(i=1 to n)
      for(j=1 to n)
          adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]);

3

Khi đó sau quá trình preprocessing thì file header của chúng ta sẽ như sau:

1 2 3 4 5 6 7 8

for(k=1 to n)
  for(i=1 to n)
      for(j=1 to n)
          adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]);

5

Tất cả những đoạn NSURL của Foundation.h đều bị preprocessor thay thế bằng “my url” do 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 63 64 65 66 67 68

9 bên trên. Từ đó ta thấy với việc dùng

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 66 67 68

1 hay

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 66 67 68

2 thông thường thì các header của các file khác, hay của thư viện mà chúng ta dùng đều có thể bị ảnh hưởng như việc dùng

vector<int> TeamBuilder::specialLocations(vector<string> paths){

  int N = paths.size();
  vector<vector<int> > adj;
  
  for(int i = 0; i < N; i ++){
      string s = paths[i];
      vector<int> row;
      for(int j = 0; j < N; j++){
          row.push_back(s[j] -'0');
      }
      adj.push_back(row);
  }

  //Floyd-Warshall
  for(int k = 0; k < N; k++){
      for (int i = 0; i < N; i++){
          for(int j = 0; j < N; j++){
              //i,j,k must be different
              if(i==j || j == k || k==i)
                  continue;

              //only update those no-paths
              if(adj[i][j] == 0){
                  if(adj[i][k] !=0 && adj[k][j] != 0){
                      adj[i][j] = 1;
                  }
              }
          }
      }

  }

  //find number of locations that can reach all other locations
  int firstNum = 0;
  for(int i = 0 ; i < N; i++){
      bool canReachAll = true;
      for(int j = 0; j<N; j++){
          if(j==i) continue;

          if(adj[i][j] == 0){
              canReachAll = false;
              break;
          }
      }
      if(canReachAll)
          firstNum ++;
  }

  //find number of locations that are reachable from other locations
  int secondNum = 0;
  for(int j = 0 ; j < N; j++){
      bool canBeReachedFromAll = true;
      for(int i = 0; i<N; i++){
          if(j!=i && adj[i][j] == 0){
              canBeReachedFromAll = false;
              break;
          }
      }
      if(canBeReachedFromAll)
          secondNum ++;
  }

  vector<int> res;
  res.push_back(firstNum);
  res.push_back(secondNum);
  return res;
}

2 ở trên.

Về vấn đề performance thì như ở trên ta đã thấy

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 66 67 68

1 và

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 66 67 68

2 sẽ copy/paste toàn bộ file header mà nó include (đệ quy). Như ở ví dụ đầu tiên chúng ta chỉ include mình Foundation.h nhưng sau khi preprocessing thì có tới hơn 92000 dòng là của Foundation.h (và các file header mà Foundation.h include), chỉ 8 dòng cuối là code của chúng ta. Thế nên thời gian compile sẽ trở nên nhiều hơn rất nhiều.

Để giải quyết 1 phần vấn đề performance chúng ta có thể dùng precompiled headers (.pch). Nếu các bạn chú ý thì tất cả iOS project khi được XCode tạo ra đều có file PROJECTNAME-Prefix.pch như sau:

PROJECTNAME-Prefix.pch

for(k=1 to n)
  for(i=1 to n)
      for(j=1 to n)
          adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]);

6

for(k=1 to n)
  for(i=1 to n)
      for(j=1 to n)
          adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]);

7

Trong file .pch này chúng ta sẽ include những header mà có khả năng được include tại nhiều nơi trong source code của ứng dụng như Foundation.h, UIKit.h… Khi source code của ứng dụng được compile thì file .pch này sẽ được compile đầu tiên, đồng nghĩa với việc tất cả file header được include trong file .pch này sẽ được compile trước và được include vào tất cả source code.

Bằng viêc caching những file header đã được biên dịch này thì những file này chỉ cần compile 1 lần, những lần sau chỉ cần sử dụng lại nên thời gian compile sẽ được rút gọn.

Thế nhưng các developer thường không hay quản lý file .pch này, và không phải file header nào cũng được dùng tại nhiều nơi trong source code nên hiệu quả của .pch chưa được cao.

Modules

Vào tháng 11 năm 2012, Doug Gregor (một kỹ sư của Apple) đã giới thiệu tính năng modules nhằm giải quyết vấn đề trên của proprocessor thay cho .pch. Vậy module là gì? Module chính là một package mô tả một library, framework.

Ví dụ chạy 2 lệnh dưới đây ta sẽ có thể xem được các module trong SDK của iOS7.

for(k=1 to n)
  for(i=1 to n)
      for(j=1 to n)
          adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]);

8

for(k=1 to n)
  for(i=1 to n)
      for(j=1 to n)
          adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]);

9

Với mỗi framework ta thấy có 1 file module.map để mô tả framework đấy.

Và để sử dụng framework chúng ta có thể thay

vector<int> TeamBuilder::specialLocations(vector<string> paths){

  int N = paths.size();
  vector<vector<int> > adj;
  
  for(int i = 0; i < N; i ++){
      string s = paths[i];
      vector<int> row;
      for(int j = 0; j < N; j++){
          row.push_back(s[j] -'0');
      }
      adj.push_back(row);
  }

  //Floyd-Warshall
  for(int k = 0; k < N; k++){
      for (int i = 0; i < N; i++){
          for(int j = 0; j < N; j++){
              //i,j,k must be different
              if(i==j || j == k || k==i)
                  continue;

              //only update those no-paths
              if(adj[i][j] == 0){
                  if(adj[i][k] !=0 && adj[k][j] != 0){
                      adj[i][j] = 1;
                  }
              }
          }
      }

  }

  //find number of locations that can reach all other locations
  int firstNum = 0;
  for(int i = 0 ; i < N; i++){
      bool canReachAll = true;
      for(int j = 0; j<N; j++){
          if(j==i) continue;

          if(adj[i][j] == 0){
              canReachAll = false;
              break;
          }
      }
      if(canReachAll)
          firstNum ++;
  }

  //find number of locations that are reachable from other locations
  int secondNum = 0;
  for(int j = 0 ; j < N; j++){
      bool canBeReachedFromAll = true;
      for(int i = 0; i<N; i++){
          if(j!=i && adj[i][j] == 0){
              canBeReachedFromAll = false;
              break;
          }
      }
      if(canBeReachedFromAll)
          secondNum ++;
  }

  vector<int> res;
  res.push_back(firstNum);
  res.push_back(secondNum);
  return res;
}

5 bằng

vector<int> TeamBuilder::specialLocations(vector<string> paths){

  int N = paths.size();
  vector<vector<int> > adj;
  
  for(int i = 0; i < N; i ++){
      string s = paths[i];
      vector<int> row;
      for(int j = 0; j < N; j++){
          row.push_back(s[j] -'0');
      }
      adj.push_back(row);
  }

  //Floyd-Warshall
  for(int k = 0; k < N; k++){
      for (int i = 0; i < N; i++){
          for(int j = 0; j < N; j++){
              //i,j,k must be different
              if(i==j || j == k || k==i)
                  continue;

              //only update those no-paths
              if(adj[i][j] == 0){
                  if(adj[i][k] !=0 && adj[k][j] != 0){
                      adj[i][j] = 1;
                  }
              }
          }
      }

  }

  //find number of locations that can reach all other locations
  int firstNum = 0;
  for(int i = 0 ; i < N; i++){
      bool canReachAll = true;
      for(int j = 0; j<N; j++){
          if(j==i) continue;

          if(adj[i][j] == 0){
              canReachAll = false;
              break;
          }
      }
      if(canReachAll)
          firstNum ++;
  }

  //find number of locations that are reachable from other locations
  int secondNum = 0;
  for(int j = 0 ; j < N; j++){
      bool canBeReachedFromAll = true;
      for(int i = 0; i<N; i++){
          if(j!=i && adj[i][j] == 0){
              canBeReachedFromAll = false;
              break;
          }
      }
      if(canBeReachedFromAll)
          secondNum ++;
  }

  vector<int> res;
  res.push_back(firstNum);
  res.push_back(secondNum);
  return res;
}

6 Ví dụ khi sử dụng framework Foundation ta sẽ dùng

vector<int> TeamBuilder::specialLocations(vector<string> paths){

  int N = paths.size();
  vector<vector<int> > adj;
  
  for(int i = 0; i < N; i ++){
      string s = paths[i];
      vector<int> row;
      for(int j = 0; j < N; j++){
          row.push_back(s[j] -'0');
      }
      adj.push_back(row);
  }

  //Floyd-Warshall
  for(int k = 0; k < N; k++){
      for (int i = 0; i < N; i++){
          for(int j = 0; j < N; j++){
              //i,j,k must be different
              if(i==j || j == k || k==i)
                  continue;

              //only update those no-paths
              if(adj[i][j] == 0){
                  if(adj[i][k] !=0 && adj[k][j] != 0){
                      adj[i][j] = 1;
                  }
              }
          }
      }

  }

  //find number of locations that can reach all other locations
  int firstNum = 0;
  for(int i = 0 ; i < N; i++){
      bool canReachAll = true;
      for(int j = 0; j<N; j++){
          if(j==i) continue;

          if(adj[i][j] == 0){
              canReachAll = false;
              break;
          }
      }
      if(canReachAll)
          firstNum ++;
  }

  //find number of locations that are reachable from other locations
  int secondNum = 0;
  for(int j = 0 ; j < N; j++){
      bool canBeReachedFromAll = true;
      for(int i = 0; i<N; i++){
          if(j!=i && adj[i][j] == 0){
              canBeReachedFromAll = false;
              break;
          }
      }
      if(canBeReachedFromAll)
          secondNum ++;
  }

  vector<int> res;
  res.push_back(firstNum);
  res.push_back(secondNum);
  return res;
}

7 Vậy khi trong một file header gặp đoạn import module thì compiler đã xử lý gì và tại sao lại giải quyết được vấn đề Fragility và Performance của preprocessor?

Ví dụ khi trong một file header, preprocessor gặp

vector<int> TeamBuilder::specialLocations(vector<string> paths){

  int N = paths.size();
  vector<vector<int> > adj;
  
  for(int i = 0; i < N; i ++){
      string s = paths[i];
      vector<int> row;
      for(int j = 0; j < N; j++){
          row.push_back(s[j] -'0');
      }
      adj.push_back(row);
  }

  //Floyd-Warshall
  for(int k = 0; k < N; k++){
      for (int i = 0; i < N; i++){
          for(int j = 0; j < N; j++){
              //i,j,k must be different
              if(i==j || j == k || k==i)
                  continue;

              //only update those no-paths
              if(adj[i][j] == 0){
                  if(adj[i][k] !=0 && adj[k][j] != 0){
                      adj[i][j] = 1;
                  }
              }
          }
      }

  }

  //find number of locations that can reach all other locations
  int firstNum = 0;
  for(int i = 0 ; i < N; i++){
      bool canReachAll = true;
      for(int j = 0; j<N; j++){
          if(j==i) continue;

          if(adj[i][j] == 0){
              canReachAll = false;
              break;
          }
      }
      if(canReachAll)
          firstNum ++;
  }

  //find number of locations that are reachable from other locations
  int secondNum = 0;
  for(int j = 0 ; j < N; j++){
      bool canBeReachedFromAll = true;
      for(int i = 0; i<N; i++){
          if(j!=i && adj[i][j] == 0){
              canBeReachedFromAll = false;
              break;
          }
      }
      if(canBeReachedFromAll)
          secondNum ++;
  }

  vector<int> res;
  res.push_back(firstNum);
  res.push_back(secondNum);
  return res;
}

8 thì sẽ xử lý các bước như sau:

• Tìm file module.map của framework có tên là Foundation
• Dựa vào mô tả về framework trong file module.map này compiler sẽ parse các file headers và sinh ra file module (lưu dưới dạng AST - biểu diễn dưới dạng tree trước khi chuyển sang mã máy)
• Load file module này tại đoạn khai báo import
• Cache file module này để sử dụng lại cho những lần sau

Thứ nhất thay vì copy nội dung các file header được include rồi mới compile, mà import trưc tiếp file module đã được lưu dưới dạng AST nên các header của framework ko bị ảnh hưởng bởi các đoạn code trước khi import (như

define) -> tránh được vấn đề Fragility.

Thứ hai là nhờ việc cache những file module này mà compiler không phải biên dịch lần 2 nên sẽ rút gọn thời gian biên dịch.

Ngoài ra một điều thú vị nữa mà tính năng module mang lại cho lập trình viên đó là chúng ta không phải tự tay link các framework mà chúng ta import. Ví dụ như trước đây nếu trong file tmp.m có

vector<int> TeamBuilder::specialLocations(vector<string> paths){

  int N = paths.size();
  vector<vector<int> > adj;
  
  for(int i = 0; i < N; i ++){
      string s = paths[i];
      vector<int> row;
      for(int j = 0; j < N; j++){
          row.push_back(s[j] -'0');
      }
      adj.push_back(row);
  }

  //Floyd-Warshall
  for(int k = 0; k < N; k++){
      for (int i = 0; i < N; i++){
          for(int j = 0; j < N; j++){
              //i,j,k must be different
              if(i==j || j == k || k==i)
                  continue;

              //only update those no-paths
              if(adj[i][j] == 0){
                  if(adj[i][k] !=0 && adj[k][j] != 0){
                      adj[i][j] = 1;
                  }
              }
          }
      }

  }

  //find number of locations that can reach all other locations
  int firstNum = 0;
  for(int i = 0 ; i < N; i++){
      bool canReachAll = true;
      for(int j = 0; j<N; j++){
          if(j==i) continue;

          if(adj[i][j] == 0){
              canReachAll = false;
              break;
          }
      }
      if(canReachAll)
          firstNum ++;
  }

  //find number of locations that are reachable from other locations
  int secondNum = 0;
  for(int j = 0 ; j < N; j++){
      bool canBeReachedFromAll = true;
      for(int i = 0; i<N; i++){
          if(j!=i && adj[i][j] == 0){
              canBeReachedFromAll = false;
              break;
          }
      }
      if(canBeReachedFromAll)
          secondNum ++;
  }

  vector<int> res;
  res.push_back(firstNum);
  res.push_back(secondNum);
  return res;
}

9 thì khi biên dịch chúng ta phải tự link tới Foundation bằng lệnh :

1 2 3 4 5 6 7 8

0

Thế nhưng khi sử dụng

1 2 3 4 5 6 7 8

1 thì chúng ta không cần phải tự link tới framework nữa mà chỉ cần:

1 2 3 4 5 6 7 8

2

Với XCode chúng ta sẽ không phải add thêm các framework mà mình muốn dùng trong

1 2 3 4 5 6 7 8

3 như hình dưới đây.

Đối với những project được tạo từ XCode5 thì tính năng module tự động được enable. Nhưng những project được tạo trước đây các bạn phải tự enable trong phần

1 2 3 4 5 6 7 8

4 (tức là set flag -fmodules).

Kết luận

Bài viết này mình đã giới thiệu qua tính năng module của Clang trong được giới thiệu từ XCode5. Và đồng thời cũng giải thích qua về

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 66 67 68

1,

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 66 67 68

2, pch. Mặc dù tính năng module vẫn đang trong quá trình hoàn thiện nhưng hiện tại chúng ta đã có thể sử dụng với XCode5.