Giới thiệu

Hàng ngày chúng ta gặp phải rất nhiều bài toán thống kê khác nhau. Bài toán thống kê số liệu cũng có thể xuất hiện dưới nhiều dạng khác nhau như: bằng việc kiểm apache acccess log thống kê xem có tổng số truy cập vào 1 API trong 1 phút, hay 1 API cụ thể được truy cập từ những địa điểm nào và cụ thể là bao nhiều lần. Xử lý số liệu là một bài toán khó, và việc bóc tách dữ liệu nhiều khi cũng không hể đơn giản. Tuy vậy, bằng việc sử dụng thành thạo các công cụ command line của linux, nhiều khi ta có thể giải quyết những bài toán trên một cách nhanh chóng chỉ bằng 1, 2 dòng lệnh. Bài viết này sẽ đưa ra 1 bài toán cụ thể và cách sử dụng các unix command line tool để giải quyết các bài toán đó.

Khái lược các tool dùng trong bài

• Grep: Cho phép tìm một chuỗi bất kỳ trong một file. Chuỗi có thể được mô tả bằng regular expression.
• uniq: công cụ giúp loại bỏ
• sort: sắp xếp các record trong 1 file
• wc: đếm từ và dòng trong 1 file
• awk: công cụ để in các cột dữ liệu, cũng như xử lý dữ liệu trên từng cột

Bài toán

Để dễ hình dung cũng như dễ kiểm tra tính đúng đắn, ta giả sử 1 bài toán tưởng tượng như sau:

Có log file:

    IP1 2 20:00:01 Get /A 
    IP2 2 20:00:02 Get /B
    IP2 3 20:00:03 Get /C
    IP4 2 20:02:01 Get /A 
    IP5 2 20:03:01 Get /B
    IP2 3 20:03:02 Get /A
    IP3 2 20:03:04 Get /B 
    IP2 2 20:04:01 Get /B
    IP1 3 20:05:12 Get /C
    IP6 2 20:05:31 Get /C 
    IP5 2 20:06:02 Get /B
    IP4 3 20:07:03 Get /A

Bài toán: Hãy đếm xem trong 1 phút có bao nhiêu requests và thử đếm xem có bao nhiêu request đến A, B.

Phương pháp giải quyết

Theo đề bài, ta có 2 bài toán * Thống kê requests theo từng phút. * Thống kê requests đến A, B.

Ta sẽ lần lượt giải từng bài toán 1.

Thống kê requests đến A, B

Bài toán này thực chất khá dễ và ta có thể giải quyết bằng grep và wc. Để ý rằng mỗi dòng là 1 requests đến A, B hoặc C vì vậy bài toán có thể chuyển về là: đếm số dòng có ký tự A và ký tự B. Để lọc ký tự ta có thể dùng grep, để đếm số dòng ta có thể dùng wc. Như vậy bài toán có thể được giải quyết bằng cách pipe kết quả grep sang wc.

Lời giải:

grep A data.dat | wc -l
4
grep B data.dat | wc -l
5

Như vậy có 4 requests đến A và 5 requests đến B trong log file. Bằng 1 câu lệnh, ta có thể đưa ngay ra được kết quả. Dễ như ăn kẹo!

Đếm số request trong 1 phút.

Bài toán này khó hơn 1 chút do ta chỉ có trong log các request theo từng giây, trong khi ta cần thống kê theo phút. Liệu có cách nào biến bài toán về bài toán đếm số dòng như ở trên không? Nếu như ta có thể nhóm các dòng dữ liệu theo phút, bài toán có thể được giải quyết tương tự như bài toán trên.

Trước tiên, làm thế nào để nhóm dòng theo phút? Muốn nhóm dòng theo phút ta phải tách được phần phút ra. Để ý giờ:phút là trường thứ 3 trong file. Do vậy nếu tách được cột thứ 3 và lấy 5 ký tự đầu tiên, ta có thể lấy phút của từng request. Tách cột là việc của awk!

awk '{print substr($3, 1, 5)}' data.dat
20:00
20:00
20:00
20:02
20:03
20:03
20:03
20:04
20:05
20:05
20:06
20:07

Ồ, ta đã tiến được 1 bước! Bước tiếp theo, nếu như ta có thể nhóm các phần tử giống nhau và đếm các phần tử đó, ta sẽ có kết quả mong muốn. Nhóm các giá trị giống nhau là nhiệm vụ của uniq!

awk '{print substr($3, 1, 5)}' data.dat | uniq -c
3 20:00
2 20:02
3 20:03
1 20:04
2 20:05
1 20:06
1 20:07

Tuyệt! Như vậy bằng 1 dòng lệnh, ta đã nhóm được các API trong cùng 1 phút, cũng như số lượng API trong thời điểm đấy. Nếu số lượng request nhiều, số dòng kết quả lớn và ta chỉ muốn biết thời điểm có truy cập lớn nhất, ta có thể sắp xếp theo số lượng truy cập. Sắp xếp các dòng theo giá trị cột là công việc của sort! Bằng câu lệnh sort ta có kết quả như dưới đây:

awk '{print substr($3, 1, 5)}' data.dat | uniq -c | sort -nk1 -r
3 20:03
3 20:00
2 20:05
1 20:07
1 20:06
1 20:04
1 20:02

Bài toán đầu tiên cũng đã được giải quyết chỉ với 1 dòng lệnh!

Kết luận

Bài viết đã giới thiệu qua các công cụ commandline của unix cũng như cách áp dụng công cụ đó vào bài toán cụ thể. Hy vọng qua bài viết bạn đã thấy được phần nào tầm quan trọng cũng như sức mạng của các chương trình tiện ích như awk, wc, grep, uniq, sort. Và để hiểu rõ công cụ thì không cách nào khác là áp dụng thật sáng tạo chúng vào công việc hàng ngày, do vậy bạn hãy thử áp dụng các công cụ trên vào bài toán sau nhé:

Với log file trên, đếm xem có bao nhiêu nguồn truy cập, và nguồn truy cập nào có số lượng truy cập lớn nhất ;)

The song, and the home page

Đầu tiên có thể độc giả sẽ tự hỏi ý nghĩa của tiêu đề bài viết là gì ? Vậy trước hết mời bạn ghé qua home page và enjoy the song

99-bottles-of-beer cũng từng là đề bài của code golf và phpgolf. Mission của chúng ta là code 1 đoạn PHP snippet print lyric của bài hát mà dung lượng đoạn code là nhỏ nhất. Logic thật đơn giản phải không :D

1
2
3
4
5
6
7
8
9
10
11
12
13

99 bottles of beer on the wall, 99 bottles of beer.
Take one down and pass it around, 98 bottles of beer on the wall.

98 bottles of beer on the wall, 98 bottles of beer.
Take one down and pass it around, 97 bottles of beer on the wall.

97 bottles of beer on the wall, 97 bottles of beer.
Take one down and pass it around, 96 bottles of beer on the wall.

...

1 bottle of beer on the wall, 1 bottle of beer.
Go to the store and buy some more, 99 bottles of beer on the wall.

Với mục tiêu dùng ít code nhất có thể, tôi sẽ không dùng cấu trúc rẽ nhánh if-else, thay vào đó là ternary operator của PHP ( có nghĩa là bạn có thể viết “(condition)?true-action:false-action” thay vì “if (condition) {true-action} else {false-action}” )

Đoạn code đầu tiên tôi nghĩ ra trong đầu như sau:

1
2
3
4
5
6
7
8
9

<?php
  $a="beer on the wall";
  for($i=99;$i>=1;$i--){
    $x=($i==1)?"bottle":"bottles";
    $b="<p>$i $x of $a, $i $x of beer.<br>";
    $b.=($i==1)?"Go to the store and buy some more, 99 bottles of $a.":"Take one down and pass it around, ".($i-1)." $x of $a.</p>";
  print $b;
}
?>

Optimize

Bạn thử ls -l sẽ thấy đoạn code trên có dung lượng 288 bytes!

Để rút ngắn đoạn code trên, đầu tiên tôi nhớ lại những kiến thức cơ bản về PHP: dấu space hoàn toàn không cần thiết, và ký tự “?>” ở cuối cũng có thể bỏ đi PHP long tag ở đầu có thể thay = PHP short tag

1
2
3
4
5
6
7
8

<?
$a="beer on the wall";
for($i=99;$i>=1;$i--){
$x=($i==1)?"bottle":"bottles";
$b="<p>$i $x of $a, $i $x of beer.<br>";
$b.=($i==1)?"Go to the store and buy some more, 99 bottles of $a.":"Take one down and pass it around, ".($i-1)." $x of $a.</p>";
print $b;
}

263 bytes!

Làm thế nào để rút ngắn hơn nữa ? Nếu để ý vào những chi tiết nhỏ hơn, bạn sẽ thấy:

• trong điều kiện vòng lặp, thay “\(i>=1" bằng "\)i>0”
• “(\(i==1)?" là quá dài. Ta có thể bỏ đi 2 dấu ngoặc "\)i==1?”
• print có thể thay bằng echo. ( Thực tế trong PHP bạn còn có thể thay rtrim -> chop, explode -> split, implode -> join, preg_split -> split (trong 1 vài trường hợp) và preg_replace -> preg_filter trong hầu hết các TH )
• “\(x=(\)i==1)?”bottle“:”bottles“;” có thể được viết lại : “\(x='bottle';\)i==1?:$x.=‘s’;”
• Mỗi lần sử dụng biến $a ta đều có “of” ở đăng trước. Vậy có thể đơn giản cho word “of” vào trong biến a
• “99 bottles of \(a" có thể rewrite tiếp lại thành "99{\)x}s of $a”
• Chúng ta có thể xoá “\(i–" trong vòng lặp for, vì thế thêm – vào trước "\)i==1” ở dòng gần cuối thành “\(i–==1" và vì thế bỏ luôn đoạn (\)i-1) ở sau đó

Như vậy solution tiếp theo của chúng ta sẽ là

1
2
3
4
5
6
7
8

<?
$a=" of beer on the wall";
for($i=99;$i>=1;){
$x='bottle';$i==1?:$x.='s';
$b="<p>$i $x$a, $i $x of beer.<br>";
$b.=$i--==1?"Go to the store and buy some more, 99 {$x}s$a.":"Take one down and pass it around, ".$i." $x$a.</p>";
echo $b;
}

241 bytes!

The trick

Bạn có nghĩ đã hết cách để rút gọn đoạn code ?

Bạn có quên điều gì không ? Bỏ đi tất cả các ký tự line-feed (line break), cho code thành 1 dòng, chúng ra sẽ có kết quả tốt hơn.

1
2
3

<?$a=" of beer on the wall";for($i=99;$i>0;){$x='bottle';$i^1?$x.='s':0;$b="<p>$i $x$a, $i $x of beer.<br>";$b.=$
i--==1?"Go to the store and buy some more, 99 {$x}s$a.":"Take one down and pass it around, ".$i." $x$a.</p>";echo
 $b;}

233 bytes!

Bạn có tin có 1 đoạn code sẽ cho kết quả tương tự với … 30 bytes ???

!!

1

<?include('http://bit.ly/xxxx'); ?>

PHP là 1 ngôn ngữ web! Với allow_url_fopen và allow_url_include turn on có thể dễ dàng load 1 link kết quả có sẵn đi kèm 1 dịch vụ như bitly !

Stay hungry, stay foolish :D

Tham khảo

1. phpgolf tips and tricks
2. Question on StackOverFlow

Giới thiệu

Trong thư viện Collection của Java, có một lớp đặc biệt: WeakHashMap. Về hoạt động nói chung nó rất giống với HashMap, đều có chức năng quản lý key, value như thêm, bớt, truy xuất value theo key… Vậy khác biệt của WeakHashMap so với HashMap là gì? Đó chính là khả năng phối hợp của WeakHashMap với garbage collector nhằm loại bỏ khả năng leak memory có thể xảy ra với HashMap. Trong bài viết này, chúng ta sẽ tìm hiểu WeakHashMap là gì, cách hoạt động của nó như thế nào, và cách nó xóa bỏ những entry không dùng đến ra sao.

Mở đầu

Thử tưởng tượng một tình huống như thế này: bạn muốn sử dụng một class nào đó, nhưng không thể extend được nó (ví dụ trường hợp đơn giản nhất là class đó được chỉ định là final). Vậy bạn làm gì khi muốn thêm property cho object thuộc class đó?

Ví dụ, bạn muốn sử dụng một class Product mà không thể extend được. Bây giờ muốn thêm serialNumber cho product đó, ứng cử viên hàng đầu là HashMap, bạn có thể tạo một cặp key là Product object, value là serialNumber:

1
2
3
4
5
6

import java.util.HashMap;
...
Map<Product, String> productMap = new HashMap<Product,String>();
...
productMap.put(product, serialNo);
...

Đoạn code trên có vẻ đã hoàn thành mục tiêu thêm thuộc tính cho Product object, nhưng có vấn đề gì ở đây không? Cách giải quyết này gặp phải vấn đề liên quan đến việc giải phóng bộ nhớ. Vì HashMap sử dụng strong reference để trỏ đến Product object, nên khi trong chương trình không còn reference nào đến Product object nữa, garbage collector nhận thấy vẫn còn strong reference ở trong HashMap, nên nó không giải phóng object này nữa. Lâu dần, sẽ xuất hiện hiện tượng Leak Memory: ta không thể giải phóng được cặp key, value nằm trong HashMap, khi mà HashMap còn được sử dụng (để hiểu rõ hơn, bạn có thể xem ví dụ demo ở cuối bài).

Nhân đây, xin giải thích thêm về Strong reference. Đây là Java reference bình thường mà ta thường sử dụng. Như ví dụ sau:

1

String serialNo = new String();

sẽ tạo một object String và lưu một strong reference đến nó vào biến serialNo. Ta cần phải để ý mới quan hệ giữa strong reference và garbage collector như sau: Nếu một object được trỏ đến qua một số strong references, object đó sẽ không được garbage collector để ý đến.

WeakHashMap

Trái ngược lại với strong reference là weak reference. *Weak reference** sẽ không thể cản trở garbage collector giải phóng object khỏi memory. Khai báo như sau:

1

WeakReference<Product> weakProduct = new WeakReference<Product>(product);

Sau đó, ta có thể truy cập đến Product object thông qua việc gọi method weakProduct.get(). Tuy nhiên, ta cần phải chú ý khi gọi method này. Vì weak reference không đủ khả năng chặn quá trình garbage collection, nên đến một cycle nào đó, garbage collector sẽ giải phóng Product object (khi không còn strong reference nào đến nó) , và bạn sẽ thấy weakProduct.get() đột nhiên trả về null.

Quay trở lại với ví dụ Product ở trên, ta giải quyết vấn đề đã nêu bằng cách sử dụng WeakHashMap class. WeakHashMap hoạt động y hệt như HashMap, chỉ khác là key được refer đến bằng weak reference. Lúc này, khi một object chỉ reachable bởi WeakReference, garbage collector sẽ giải phóng object, đồng thời sẽ đặt weak reference trỏ đến object kia vào một queue. WeakHashMap sẽ định kì kiểm tra queue này xem có weak reference nào mới đến không. Nếu thấy một weak reference trong queue, nghĩa là key đã không được ai sử dụng nữa và nó đã bị garbage collector “tịch thu”. Lúc đó, WeakHashMap sẽ bỏ entry liên quan đi. No more memory leak ! :)

Demo

Lý thuyết là vậy. Để dễ hiểu hơn, quan sát đoạn demo WeakHashMap sau:

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

package corejava.collection;

import java.util.Map;
import java.util.WeakHashMap;

public class WeakHashMapTest {

  public static void main(String[] args) {
      
      //add one element to the map...
      Map<Data, String> map  = new WeakHashMap<Data, String>();
      Data someDataObject = new Data("test");
      map.put(someDataObject, someDataObject.value);
      System.out.println("map contains someDataObject ? " + map.containsKey(someDataObject));
      
      //now make someDataObject eligible for garbage collection...
      someDataObject = null;
      
      for (int i = 0; i < 1000000; i++){
          if(map.size()!=0)
          {
              System.out.println("At iteration " + i + " the map still holds the reference on someDataObject");
          }
          else
          {
              System.out.println("someDataObject has finally been garbage collected at iteration " + i + ", so the map is now empty");
              break;
          }
          
      }
  }

  static class Data{
      String value;
      Data(String value){
          this.value = value;
      }
  }
}

Chạy đoạn code trên: kết quả như sau:

1
2
3
4
5
6

map contains someDataObject ? true
At iteration 0 the map still holds the reference on someDataObject
At iteration 1 the map still holds the reference on someDataObject
...
At iteration 29574 the map still holds the reference on someDataObject
someDataObject has finally been garbage collected at iteration 29575, hence the map is now empty

thay WeakHashMap bằng HashMap, kết quả sẽ như thế nào?

1
2
3
4
5
6
7

map contains someDataObject ? true
At iteration 0 the map still holds the reference on someDataObject
At iteration 1 the map still holds the reference on someDataObject
...
At iteration 999997 the map still holds the reference on someDataObject
At iteration 999998 the map still holds the reference on someDataObject
At iteration 999999 the map still holds the reference on someDataObject

Bạn đã thấy điểm khác biệt? Sau một khoảng thời gian, WeakHashMap sẽ bỏ đi entry tương ứng với weak reference. Còn HashMap, vì là strong reference, trong map sẽ luôn chứa cặp phần tử (someDataObject, value) mặc dù bên ngoài someDataObject đã set là null.

Kết luận

Bài viết này đã trình bày tác dụng của một lớp trong Collection của Java: WeakHashSet. Đồng thời, bài viết cũng giới thiệu weak reference và strong reference và mối quan hệ của chúng với Java garbage collector.

Tham khảo

1. Core Java Volume I–Fundamentals
2. http://docs.oracle.com/javase/6/docs/api/java/util/WeakHashMap.html