演算法筆記 - 經典河內塔

最近在看CNN的文章的時候, 提到了Hierarchy的概念

目的是以divide-and-conquer的概念來將大問題切割為小問題

以image recognition / computer vision來說, "直覺上"每個pixels只會跟鄰近的pixels有關聯性(correlated to local pixels)

也就是說在Machine Learning的領域上又回歸到了"自然的"、"直覺式"的算法 XD

有點扯遠了, 讓我們先回到第一個關鍵字 "divide-and-conquer"

這個詞被翻譯做分治法, 也就是分而治之

如果你熟悉於科技業, 一定在很多問題/系統上都已經看過了分治法解決問題的能力.

如果你是一個科技新鮮人, 那麽這個經典的河內塔也是你在人生的遞迴之路的重要基石.

河內塔 (Tower of Hanoi) 的故事

 - 引述自 Wiki 百科 <河內塔>

傳說印度某間寺院有三根柱子，上串64個金盤。寺院裡的僧侶依照一個古老的預言，以一定的規則移動這些盤子；

規則: 有三根杆子A，B，C。A杆上有N個(N>1)穿孔圓盤，盤的尺寸由下到上依次變小。
要求按下列規則將所有圓盤移至C杆：

1. 每次只能移動一個圓盤；
2. 大盤不能疊在小盤上面。

預言說當這些盤子移動完畢，世界就會滅亡。這個傳說叫做梵天寺之塔問題（Tower of Brahma puzzle）。

若傳說屬實，僧侶們需要2⁶⁴ − 1步才能完成這個任務；若他們每秒可完成一個盤子的移動，就需要5845億年才能完成。

(整個宇宙現在也不過137億年。)

這個傳說有若干變體：寺院換成修道院、僧侶換成修士等等。

寺院的地點眾說紛紜，其中一說是位於越南的河內，所以被命名為「河內塔」。

移動河內塔

那麼, 要怎移動河內塔呢?

我們先來推一次, 當瓦片數為 3 的時候,  流程如下

移動次數＼塔	A	B	C
1	2 3		1
2	3	2	1
3	3	1 2
4		1 2	3
5	1	2	3
6	1		2 3
7			1 2 3

* 最少需要移動 2^3 - 1 = 7步

接著, 讓我們簡化問題變成瓦片數為 2 的狀況:

移動次數＼塔	A	B	C
1	2	1
2		1	2
3			1 2

看一下, 瓦片數為 2 的狀況跟 3 的狀況, 對於前 3 動的移動順序是不是非常相似

他們最大的差異, 就是將1號跟2號瓦片, 移動到C柱或者是B柱的差別

當N = 2的時候, 直接移動到C柱即可

當N = 3的時候, 你需要先將(1, 2)移動到B柱, 接著將(3)移到C柱, 最後將再將(1, 2)移到C柱

到這一步, 其實已經分治完成了 ヽ(∀ﾟ)人(ﾟ∀ﾟ)人( ﾟ∀)人(∀ﾟ)人(ﾟ∀ﾟ)人( ﾟ∀)ﾉ

河內塔的關鍵就在於, 要適時的把這些柱子當作暫存的buffer來使用

接著我們試著寫出虛擬碼:

moveDisk(N, from, to, buffer) {

    if (N == 0) {
         // 中止條件! 沒得動啦

        return;

    } else {
        // 把倒數第二片開始的盤子從A柱(from)移動到B柱(buffer)去

        move((N-1), from, buffer, to);
        // 把最底下的盤子N 從A柱(from)移動到C柱(to)去

        print("Move Disk %d from %d to %d", N, from, to);

        // 把倒數第二片開始的盤子從B柱(buffer)移動到C柱(to)去

        move((N-1), buffer, to, from);

    }

}

以上!

Process/Thread name in Android native layer

看起來在 libc/bionic 裡面有個 pthread_setname_np.cpp 可以去設置 process name,
但是不曉得為什麼沒有提供 getname 方法 (security?)

setname 的使用方法如下:

pthread_setname_np(pthread_self(), "xxx");

他的實作如下:

int pthread_setname_np(pthread_t t, const char* thread_name) {
  ErrnoRestorer errno_restorer;

  size_t thread_name_len = strlen(thread_name);
  if (thread_name_len >= MAX_TASK_COMM_LEN) {
    return ERANGE;
  }

  // Changing our own name is an easy special case.
  if (t == pthread_self()) {
    return prctl(PR_SET_NAME, thread_name) ? errno : 0;
  }

  // We have to change another thread's name.
  pthread_internal_t* thread = __pthread_internal_find(t);
  if (thread == NULL) {
    return ENOENT;
  }
  pid_t tid = thread->tid;

  char comm_name[sizeof(TASK_COMM_FMT) + 8];
  snprintf(comm_name, sizeof(comm_name), TASK_COMM_FMT, tid);
  int fd = open(comm_name, O_CLOEXEC | O_WRONLY);
  if (fd == -1) {
    return errno;
  }
  ssize_t n = TEMP_FAILURE_RETRY(write(fd, thread_name, thread_name_len));
  close(fd);

  if (n < 0) {
    return errno;
  } else if (n != static_cast<ssize_t>(thread_name_len)) {
    return EIO;
  }
  return 0;
}

我們可以如果是在當前的 thread name 進行更名的話,
就會直接透過 prctl(PR_SET_NAME, thread_name) 來完成

否則則會嘗試去開啟 /proc/self/task/%d/comm , 其中 %d 將會帶入目標 thread 的 tid,
並直接對他做 write 的動作.

這個 PR_SET_NAME 定義在 bionic/libc/kernel/uapi/linux/prctl.h
#define PR_SET_NAME 15
#define PR_GET_NAME 16
但沒有看到去呼叫 PR_GET_NAME 的方法

我們可以在 bionic/linker/debugger.cpp 找到一個較為接近的例子:

  char thread_name[MAX_TASK_NAME_LEN + 1]; // one more for termination
  if (prctl(PR_GET_NAME, reinterpret_cast<unsigned long>(thread_name), 0, 0, 0) != 0) {
    strcpy(thread_name, "<name unknown>");
  } else {
    // short names are null terminated by prctl, but the man page
    // implies that 16 byte names are not.
    thread_name[MAX_TASK_NAME_LEN] = 0;
  }

不過較奇妙的是他並沒有去 /proc/self/task 下面尋找對應的 tid
看起來是只要去 $cat /proc/<tid>/comm 就可以拿到 process name 了
(並且 /proc/<tid>/comm 這一路上的權限看起來都是有開啟的...)