(1) X 上的 ꒰ঌなんじゃこりゃてゃ໒꒱┃ お前の親友：「ワイヤレスイヤホン片方だけ落としたんだけど、落ち着いてBluetoothをONにして、来た道を辿っていったらまさかの接続！そこからその周りを散策して、接続がちょうど切れた点を3点探して、その3点を結ぶ三角形の外心あたりでワイヤレスイヤホンを発見‼️🤩🤩🤩見つけた時脳汁止まらんかった(実話) https://t.co/nysI2dBgB9」 / X (twitter.com)

看起來是東大理科生.

簡單的說就是利用不同的失去藍牙訊號位置, 找出圓心.

他取三個點, 剛好滿足理論上的情況, 也就是三角形的外心.

我在2024/04/22發生了類似的事情, 但沒有那麼神.

首先運氣很差的連續兩天在健身房流血.

第二天要離開時, 要拿安全帽, 去原本印象中放的櫃子找, 居然上鎖了(我放的時候沒上鎖). 這區櫃子的門有一個小透明塑膠, 可以看到裡面放什麼, 看了一下我的安全帽確實不在裡面. 於是我就把我平常有可能放的那區櫃子通通能開的就開, 確認我是不是記錯, 但還是沒找到.

於是報警, 等警察來才可以調監視器, 雖然不一定看得到. 等警察的時候, 發現手機跟安全帽上的藍牙耳機還在連線中(剛好那天忘記關), 應該還在同一層樓, 後來就去翻別區的櫃子, 就找到了, 那邊我從來不會放. 又遇到一個沒水準的人, 金梅送.

不過在不是太大的建築物內, 以現在的藍牙連線距離, 可能無法複製東大生的做法lol.

在資料會新增/刪除的情況下, 如果希望一直保持著整體的有序性, 那麼Sorted Containers (or Sorted Collections)是個選擇.

譬如想在一個python list中加入許多數字, 每次加入都要維持順序.

在加入的過程中可能會要知道現在的最大最小值, 或著第i大的值.

甚至其他需要知道中間某些數值的操作, 就不能全部加完再排序.

原本直接用built-in的作法可能是:

使用bisect module, insort_left()/insort_right()插入.

每次insort要移動位置在插入數字後的其他數字, 一次時間複雜度是O(n)

所以整體的時間複雜度會來到O(n²)

general一點, 如果想解決的問題, 在整個操作過程中可能會需要

1. 找最大最小值(or i-th value)
2. 插入/刪除
3. 查詢是否存在.
4. 維持有序性

希望將整體的時間複雜度降低, 就要將複雜度最高的降低.

通常是希望把O(n)的操作變成O(ln(n)), 但有時事情有取捨,

原本O(1)的操作可能會變得慢一點, 譬如也變成O(ln(n))

如果各種操作的機會是差不多的, 且n大到一個程度,

那這個trade off可能可以考慮.

一個比較常見的方法是使用平衡樹(紅黑樹, AVL之類的), 雖然查詢變慢了, 但插入刪除變快了.

python內應該是沒有built-in的平衡樹, 如果要解決像上面這樣的問題, 希望有差不多的時間複雜度, 可以試試Sorted Containers. 其實作方式應該不是平衡樹, 但有一些比較優秀的地方, 如記憶體使用, 因為不用儲存null的leaf pointers. 在官方文件第一頁有提到. 另外在下面還有提到

Implementation Details — Sorted Containers 2.4.0 documentation (grantjenks.com)

Traditional tree-based designs have better big-O notation but that ignores the realities of today’s software and hardware.

有興趣可以研究一下.

使用pip即可安裝, based on pure python, 官方文件有performace比較, 效率不錯, 也有覆蓋率很不錯的test. 雖然我還是碰到一點無傷大雅的bug.

$ pip install sortedcontainers

主要提供三種有序的containers, 用法文件裡面有範例, 還有各種估計的時間複雜度可以提供參考. 其中要注意 __contains__()/__getitem__()的時間複雜度, 可能與原本類似名稱的內建container不一樣.

簡單講一下幾個需要注意的點:

這些Sorted Conatiners都可以建立key function來決定排序方式, 但不能看到函數的詳細定義, 特別是使用lambda function時要注意. key function決定後無法修改.

SortedList:

1. 使用index取值的時間複雜度是O(ln(n))
2. discard()跟remove()的差別在前者在移除不存在的元素時不會raise error
3. 沒有append()/extend()/insert(), 因為加入新的元素都有自己應該在的位置, 應該要用add(). 一次加入多個可以用update(), 或著使用

sl += some_iterable

https://grantjenks.com/docs/sortedcontainers/sortedlist.html

SortedDict

1. 可以用index取值, 但要用peekitem(), O(ln(n))
2. 插入/刪除是O(ln(n))
3. 對key排序, 如果要對value排序, 請找Sorted Collections

Sorted Dict — Sorted Containers 2.4.0 documentation (grantjenks.com)

SortedSet

1. 支援set的相關操作.
2. __contains__()/count()是O(1)

Sorted Set — Sorted Containers 2.4.0 documentation (grantjenks.com)

意外的小發現有三個

1. Leetcode可以使用sortedcontainers. 這是一件有點奇怪的事, 照理說應該都要使用built-in才可以. 而且大多練習leetcode的人應該以面試為主要目的, 面試時能使用sortedcontainers的機會我想不高, 畢竟對方也不一定有用過.
2. 三種Sorted Conatiners都有個共通的小bug, 但對使用不太有影響. index可以為0.0, -1.0(其他float不行), 但原本的python list index必須是整數, 連0.0, -1.0都不行.
3. 另外不小心碰到一個無法重現的bug(on m1, 不確定有沒有關聯), 應該要不能加入無法比較的元素, 但我拿到error後還是加入了.

SortedList with integers add char with error, but char added. (Don’t know how to reproduce.) · Issue #193 · grantjenks/python-sortedcontainers (github.com)

github:

grantjenks/python-sortedcontainers: Python Sorted Container Types: Sorted List, Sorted Dict, and Sorted Set (github.com)

doc:

Python Sorted Containers — Sorted Containers 2.4.0 documentation (grantjenks.com)

更是這背後的行為讓我們覺得這是否一個平行世界, 多重宇宙, 失控多重宇宙.

在616宇宙是魔法, 在元宇宙是魔術.

code的世界也總是有些違反想法的結果, 即便排除設計錯誤的可能性, 也依然存在這現象.

原因依然是我對這世界不夠理解.

對一串數字, 如果數字大於等於門檻值, 我就丟到一邊加起來, 否則丟到另外一邊（流放組要不要加起來就隨意.）

直覺地想, 無論這一串數字有沒有排序過, 做這件事情需要花費的時間應該一樣.

// whatif.c
#include <stdio.h>

#include <stdlib.h>

#include <sys/time.h>

#define ARRAY_NUM 200000

double time_diff(struct timeval x , struct timeval y)

{

double x_ms, y_ms, diff;

x_ms = (double) x.tv_sec * 1000000 + (double) x.tv_usec;

y_ms = (double) y.tv_sec * 1000000 + (double) y.tv_usec;

diff = (double) y_ms - (double) x_ms;

return diff;

}

int compare(const void* a, const void* b)

{

int int_a = *((int*) a);

int int_b = *((int*) b);

if (int_a == int_b)

return 0;

else if (int_a < int_b)

return -1;

else

return 1;

}

int main()

{

srand(time(NULL));

int x[ARRAY_NUM];

int i, sum = 0;

struct timeval before , after;

for (i = 0; i < ARRAY_NUM; ++i)

{

x[i] = rand() % 256;

}

// qsort(x, ARRAY_NUM, sizeof(int), compare);

gettimeofday(&before , NULL);

for (i = 0; i < ARRAY_NUM; ++i)

{

if (x[i] >= 128)

{

sum += x[i];

}

}

gettimeofday(&after , NULL);

printf("Total time elapsed : %.0lf us", time_diff(before , after));

return 0;

}

以上檔案嘗試註解/取消註解qsort(), 配上編譯指令如

clang -o whatif whatif.c

會發現有排序過的求和會快上許多! Amazing!

*可以把編譯指令加上最佳化參數如 -O2試試.

用python寫一個類似的程式也會找到進入多重宇宙的分岔點.

多重宇宙的開端都是因為蜘蛛人想要重新開始安寧的生活, 所以有了

branch prediction…

我對這世界不夠理解.

簡言之

“What if you guess right, then you will be fast.”

這邊有還不錯的解說

java — Why is processing a sorted array faster than processing an unsorted array? — Stack Overflow

願原力與你同在.

在python如果需要使用圖論(graph theory)通常會使用networkx

如果要畫相關的圖, pyvis這套件或許可以提供不錯的效果.

譬如可以透過滾輪快速放大縮小.

# inside jupyter
import networkx as nx

from pyvis import network as net

nx_graph = nx.complete_graph(8)  # 隨便建一個圖
g = net.Network(notebook=True)
g.from_nx(nx_graph)
g.show('nx_graph.html')

上面這段會把用networkx建的圖存到nx_graph.html這個檔案內
並且在cell下顯示.

希望每次要顯示圖都可以一行完成, 所以寫了一個函數.

def vis_graph(nx_graph, file_name='nx_grpah.html'):
    g = net.Network(notebook=True)
    g.from_nx(nx_graph)
    g.show(file_name)
    return

執行

vis_graph(nx_graph)

會發現沒有出現圖, 但是圖片有存到nx_graph.html

查一下source code(或用type()看一下)

pyvis/network.py at master · WestHealth/pyvis

可以知道g.show()是一個 IPython.lib.display.IFrame

放到函數內時jupyter cell就無法顯示

有兩個workaround

# method 1
def vis_graph(nx_graph, file_name='nx_grpah.html'):
    # can import this at the beginning
    from IPython.display import display
    g = net.Network(notebook=True)
    g.from_nx(nx_graph)
    display(g.show(file_name))
    return

# method 2
def vis_graph(nx_graph, file_name='nx_grpah.html'):
    g = net.Network(notebook=True)
    g.from_nx(nx_graph)
    return g.show(file_name)

第一個是用IPython內的display函數去顯示IFrame, 同個cell中多次執行就會顯示多個.

第二個是將IFram當作return, 如果在一個cell中最後執行, cell接到就會顯示出來.

題目是google實際上遇到問題的簡化版

沒有標準答案, 想個方法讓總分盡量高就好.

每個題目(一輪應該只有一個題目)會有多個不同的input data.

總分就是每個input data的結果總和.

但是每個input data可以用不同的程式碼去跑.

所以可以針對各種不同的情況用不同的解法, 當然也可以由不同的人上傳.

2021資格賽是設計一個交通號誌系統.

2020資格賽是圖書館藏書排序問題.

github, codeforce, kaggle上都有一些討論這題目的資訊可以看.

沒有一定要用傳統課本上有提到的演算法. 當然也不需要自己造什麼NN. (要的話應該也可以)

我只有參加過這兩年的資格賽,

2021

看跟隊友的對話紀錄 不確定是5XX or 25XX 隊名都亂取 忘記是哪個…

https://codingcompetitions.withgoogle.com/hashcode/archive/2021

2020

好像是1856

https://codingcompetitions.withgoogle.com/hashcode/archive/2020

下面是hash code的官方連結. 有提供一個練習題目.

Hash Code - Google's Coding Competitions

之前的題目可以看這裡.

Hash Code - Google's Coding Competitions

資格賽比賽時間約三小時. 時間對台灣時區來說比較不利.

但會有extend round, 持續好幾天的樣子. 題目一樣, 有即時評分系統可以看看自己的成果. 以好玩來說算夠了.

程式在自己的電腦上跑. 所以基本上也沒有超時問題. 自己可以接受的時間就行了.

不知不覺已經兩年沒有寫文.

雖然本來就不是定期生產些什麼.

但有滿多筆記該做而沒有做, 或著解決的問題可以留下足跡, make world become +.

在駭客任務繼續之後, 把這些東西補上吧.

$ pip3 install ipython-autotime

在ipython/jupyter notebook內輸入

In[1]: %load_ext autotime

以後每執行一段程式, 就會自動顯示花費的時間.

但是下次進去就又沒有了, 每次都要重新輸入有點麻煩.

$ ipython3 profile create

訊息顯示產生兩個檔案(包含路徑), ipython_config.py, ipython_kernel_config.py.

編輯ipython_config.py, 找到

#c.InteractiveShellApp.extensions = []

改成

c.InteractiveShellApp.extensions = ['autotime']

這樣應該就可以.

這個演算法的英文名稱叫做Union Find / Disjoint Sets.

問題描述如下. a, b, c說的都是同一件事情.

a.一個有限集合U有n個元素, 其元素彼此間可能具有直接關聯性. 兩元素對同一元素有直接關聯性, 則算是具有間接關聯性. 而兩元素對同一元素有間接關聯性, 也算是有間接關聯性. 將U切割成數個非空子集u_i, 同子集內的任意兩元素有關聯性(直接或間接都可), 分屬不同子集間的元素不具有關聯性(直接或間接都沒有).

b.一個graph G有n個點, 點之間有關聯性就用一個邊連接起來(無向邊), 把G切成數個不連通(走不到)的子圖g_i.

c.社交小圈圈問題. 我認識校隊隊長, 校隊隊長認識校花, 校花認識大神, 這樣就構成一個小圈圈(但是我不認識校花跟大神沒有關係). 給定n個人, 找出這n個人可以分成幾個小圈圈. 小圈圈內任意兩人可以連連看到對方, 不同小圈圈內的人互相不認識.

初步的想法

每個group恰有一個leader, 當一個group只有一個member的時候, leader就是member自己. 兩個group有member具有關聯時就合併(兩個互斥集合取聯集), 新的leader在原本兩個leader中取一個.

用一個長度n的陣列group去紀錄每個member的leader是誰. 初始設定為每個member都分屬一個獨立的集合, leader就是自己. 兩group合併時, 修改其中之一的leader.

以下是一個簡短的範例. 合併時使用編號較小的leader當作新leader. 建議用手操作一次這個範例, 觀察每一次的變化.

n = 6  # 隨便給的數字
group = [i for i in range(n)]  # 每個元素i, 其所屬的group是group[i]
connects = [(0, 4), (3, 5), (1, 2), (2, 5), (5, 1)]  # 也是隨便給的數字

for c in connects:
    if group[c[0]] == group[c[1]]:  # already in the same group
        continue
    p = min(c)
    q = max(c)
    for i in range(len(group)):
        if group[i] == group[q]:
            group[i] = group[p]

# group = [0, 1, 1, 1, 0, 1]

為了要確定合併時要修改leader的member有誰, 跑了兩個for loop, time complexity O(n²). 這是由於使用陣列的限制造成的.

嘗試改進

把每個leader對應的全部member另外存起來, 這樣查詢一個leader下的member不用再遍尋陣列group. python可以利用dictionary, key為leader, value存所有的member, 使用的data type可以是集合(set)或連結串列(linked list), 各有優缺點, 原則上都比陣列(array, in python is called list)來的好. 單純以查詢跟合併所需的time complexity做比較, 簡列如下.

set: O(1), O(n)

linked list: O(n), O(1)

array: O(n), O(n)

合併時把被合併的group內member的leader修改為新leader. 然後把group合併.

更進一步, 由元素較多的group合併元素較少的, 需要操作的次數較少, 且可以避開worst cases.

在選擇set作為dictionary value的情況下, 實做了一個python3的union find class. 方法跟上面都一樣, 看註解應該可以理解.

theoneisneo/noteOfGtwaap

還有更快的方法(書中有寫, 我在遙遙無期的下一篇也會寫), 不過以上的實作就足夠解決大部分的問題了.

當然如果要實際解決一些圖論的問題, 我會推薦使用如networkX, cuGraph, igraph, graph-tool這類現成的lib.

前幾天被問說是不是在面試人的時候問這題的演算法, 我說:"沒有啊, 這什麼東西. XD"

於是隨手看了一下, 原則大概是要掌握一個性質

由此可知, 如果Fib(c)是質數, 那c也是質數, c ≥ 5, Fib(1) = 1, Fib(2) = 1.

Note:知道這個會快一點, 但對真的要研究這個問題, 可能還遠遠不夠.

關於此性質的證明如下

演算法大致上是

檢驗奇數c是否為質數, 如果是就檢驗Fib(c)是否為質數.

這之中影響效率的有(A)計算Fib(c) (B)質數檢驗

計算Fib(c)除了常見的DP以外, 可以用二次方遞迴, 如下, 用Fib一般式或著矩陣都可以推出.

質數檢驗要確定解, 基本上是暴力檢查, 不過機率式的檢驗演算法已經很有幫助, 譬如Miller-Robin. 以sympy.ntheory.primetest.isprime(n)來說, n < 2⁶⁴時, 檢驗的結果是必定正確的, 當n > 2⁶⁴時, 如果驗出是質數, 則有很小的機率可能不是, 所以此時再重新用暴力檢查確認, 即可省下很多時間.

very simple python3 code

from sympy.ntheory import isprime

def isPrime(p):
    if type(p) is not int or n < 0:
        return False
    elif p <= 2 ** 64:
        return isprime(p)
    else:
        # left as an exercise or just call some lib, return isprime() from sympy.ntheory is just a lazy doing.
        return isprime(p)

def fib(n):
    if n < 0:
        raise ValueError("Negative arguments not implemented")
    return _fib(n)[0]

def _fib(n):
    if n == 0:
        return (0, 1)
    else:
        a, b = _fib(n // 2)
        c = a * (b * 2 - a)
        d = a * a + b * b
        if n % 2 == 0:
            return (c, d)
        else:
            return (d, c + d)

def isNthFibPrime(n):
    if isPrime(n):

        fibN = fib(n)      
        if isPrime(fibN):
           return True, fibN
        else:
           return False, fibN
    else:
        return False, None

I used valgrind to analysis the fortran program, got

valgrind: mmap(*, *) failed in UME with error 12 (Cannot allocate memory)

And no any other messages.

Note that I am not sure the values of mmap(*, *) are important or not. I forgot those values.

I found post discussed this, said it is a bug of linux kernel, and have been fixed in v4.5, but my kernel is v4.20. Update kernel can not solve this for me.

Finally I found that the root cause is memory size too small (I use the smallest VM on GCP before), after changing to a larger one, all things are good.