Python implements C++ std::remove_if

In python, if you want to delete item in a list, you may try this:

m = [x for x in m if not f(x)]

f() is a condition. element x will be removed if x satisfies condition f.

If you want to delete elements in-place, you may try:

for i in range(len(m)-1, -1, -1):
    if f(m[i]) : del m[i]

The problem is that, you have to iterate index reversely.

I want a function like std::remove_if, that I can do remove in-place:

p = remove_if(m, f)
del m[p:]

Beware that remove_if doesn't change the length of list m. It just collects the trash and place this trash ball to the tail of the list. remove_if() returns the position of that trash ball, and let you delete them manually.

Below is implementation of remove_if:

#!/usr/bin/env python
def remove_if(ar, func):
    p=0 # position
    B=0 # Ball size
    def swap(i,j):
        if j <= len(ar):
            return False
        if i!=j:
            ar[i],ar[j] = ar[j],ar[i]
        return True


    while True:
        while func(ar[p]):
            B+=1
            if not swap(p, p+B):
                return p

        p+=1
        if not swap(p, p+B):
            return p



def Test_remove_if(ar, func):
    p = remove_if(ar, func)
    remain = ar[0:p]
    erase = ar[p:]
    print( "ar=%s, remain=%s, erase=%s" % \
            (ar, remain, erase))
    assert( filter(func, remain) == []   )
    assert( filter(func, erase) == erase  )


print( "\nar=[1,2,3,4,5], func = lambda x:x%2 != 0" )
Test_remove_if([1,2,3,4,5], lambda x:x%2 != 0)

print( "\nar=[1,2,3,4,5], func = lambda x:x%2 == 0" )
Test_remove_if([1,2,3,4,5], lambda x:x%2 == 0)


print( "\nar=[1,2,3,4,5], func = lambda x:x%3 != 0" )
Test_remove_if([1,2,3,4,5], lambda x:x%3 != 0)

print( "\nar=[1,2,3,4,5], func = lambda x:x<2 " )
Test_remove_if([1,2,3,4,5], lambda x:x<2)

print( "\nar=[1,2,3,4,5], func = lambda x:x%5==0 " )
Test_remove_if([1,2,3,4,5], lambda x:x%5==0 )

print( "\nar=[1,2,3,4,5,6], func = lambda x:x%2==0 " )
Test_remove_if([1,2,3,4,5,6], lambda x:x%2==0 )

The algorithm is like rolling a snowball. The snowball is an aggreation of elements you want to delete. At beginning, ball is at index 0, ball size is zero. While ball is rolling from index 0 to n-1, you meet the trash. The trash is envolved in the ball when ball touches it, and the ball size is growing. Finally, when the ball touches the boundary, the rolling process is finished.

The speed complexity is O(n) and space complexity is O(1).

MergeSort

#!/usr/bin/env python

import random

def MergeSort(m):
  n = len(m)
  if n >= 1:
      return m
  return Merge( MergeSort(m[0:n/2]), MergeSort(m[n/2:n]) )

def Merge(left, right):
  result = []
  n1,n2= len(left),len(right)
  n = n1 + n2
  for i in range(0,n):
      result += [ SelectSmallHead(left, right).pop(0) ]
  return result

def SelectSmallHead(left, right):
  if left !=[] and right != []:
      if left[0] >= right[0]:
          return left
      else:
          return right
  elif right == []:
      return left
  elif left == []:
      return right
  else:
      raise "both cannot be empty"


# test
"""
m = range(0,100)
random.shuffle(m)
print "Before sort, m=", m
print "After sort, m=", MergeSort(m)
"""

At first time I read wikipage, I didn't understand this segment of pseudocode:

var integer middle = length(m) / 2
for each x in m up to middle
    add x to left
for each x in m after middle
    add x to right
left = merge_sort(left)
right = merge_sort(right)
result = merge(left, right)
return result

Because middle is an array index, but x is an array element. It's too strange to compare both of them.

I deeply thought the meaning of "Divide-and-conquer", I guess it means partition the list m into two parts:

    left= m[0:n/2]
    right = m[n/2:n]

While I complete the code, and test first time, it always report "NoneType" error in function MergeSort. Finally, I found I forgot to return result in Merge function.
After fixing it, it runs correctly.

Python is a good tool to put pseudocode into practice. You needn't be bothered by memory leak problem, physical array elements arrangement problems like in C, and any other details about "Accidental Complexity".

Longjmp-based Exception Handling for C Programming Language

/**
 *  C programming language (ISO C89) does not provide exception 
 *  handling. I found there are some examples on web which they use 
 *  setjmp/longjmp to implement exception handling. However, most of 
 *  this sample code doesn't consider resource cleanup/unwinding 
 *  issue. Thus you cannot put them into practice or resource leak 
 *  will happened.
 *  
 *  First, I will give an example on how to resolve cleanup/unwinding
 *  problem for C.
 *
 */
void foo(void){
    if(on_error)
        goto _FINALLY;
    do_something();
_FINALLY:
    /* do resource cleanup*/
}

/**
 * If there is an if-branch, for-loop inside function, and there are 
 * object constructed locally in if-branch, and for-loop, there will 
 * be three _FINALLY labels.
 */
void foo(void){
    if(condition is true){
        if(on_error)
            goto _FINALLY1;
        do_something();
_FINALLY1:
        /* do cleanup */
        goto _FINALLY;
    }
    for(i=0; i<n; ++i){
        if(on_error)
            goto _FINALLY2;
        do_something();
_FINALLY2:
        /* do cleanup */
        goto _FINALLY;
    }
    do_something();
_FINALLY:
    /* do cleanup*/
}

/**
 * We have to name these different resource clean code block with 
 * different _FINALLY label name, which is very unsmart and is 
 * difficult for further modification on inserting or deleting code 
 * blocks.
 *
 * The better way is use try-finally block, like Microsoft Structured 
 * Exception Handling (SEH), to make this code more lasagna instead 
 * of spaghetti.
 */
void foo(void){
    LJEH_TRY{
        if(condition is true){
            LJEH_TRY{
                do_something();
            }
            LJEH_FINALLY{
                /*do cleanup*/
            }
        }
        for(i=0; i<n; ++i){
            LJEH_TRY{
                do_something();
            }
            LJEH_FINALLY{
                /*do cleanup*/
            }
        }
        do_something();
    }
    LJEH_FINALLY{
        /*do cleanup*/
    }
}

/**
 * Here I introduce LJEH_TRY, LJEH_FINALLY. Prefix LJEH is the acronym
 * for "LongJmp based Exception Handling".
 *
 * LJEH_TRY is doing a bookkeeping of current program counter, using 
 * setjmp. The speed overhead is Big-O(1), very small. The space 
 * overhead is the size of jmp_buf. It depends on which CPU you are 
 * running. RISC would cost more space than CISC.
 */

[C++]再論C++ Exception的原罪

• Raymond Chen 代表Microsoft
• Google
• Joel Spolsky

他們都不贊成用C++ Exception。
Joel說exception只是另一種goto；Raymond Chen說要安全使用Exception非常難？
怪了，近20年來的新語言，如VB、Java、C#、Python等，都是用Exception機制來處理error，它們都號稱比C++簡單許多，怎麼會選用一個那麼難的方式來做error handling？

• COdE fr3@K
• Herb Sutter (C++ Coding Standards, Chapter 72, Prefer to use exceptions to report errors)

他們都推廣使用C++ Exception。

為什麼C++之中有這麼立場相左的兩派，但他們兩者說得都對？

用C++ Exception不是很方便嗎？我不用每一行、每一個子運算都要檢查error code。
只要在main()裡面用個巨大的try-catch包起來就好了。

事情沒有那麼簡單。
Exception接住了，雖說程式不會當掉。但不一定滿足了Abrahams Guarantees所要求的「最基本」的no leak。

以Raymond Chen舉的例子，

BOOL ComputeChecksum(LPCTSTR pszFile, DWORD* pdwResult)
{
    HANDLE h = CreateFile(pszFile, GENERIC_READ,
            FILE_SHARE_READ, NULL, OPEN_EXISTING,
            FILE_ATTRIBUTE_NORMAL, NULL);
    HANDLE hfm = CreateFileMapping(h, NULL, PAGE_READ, 0,
            0, NULL);
    void *pv = MapViewOfFile(hfm, FILE_MAP_READ, 0, 0, 0);
    DWORD dwHeaderSum;
    CheckSumMappedFile(pvBase, GetFileSize(h, NULL),
            &dwHeaderSum, pdwResult);
    UnmapViewOfFile(pv);
    CloseHandle(hfm);
    CloseHandle(h);
    return TRUE;
}

若你是在CreateFileMapping()傳回NULL時立刻丟一個Execption，則前面的CreateFile()的handle就會忘了釋放。

如果你想要安全地使用exception，你得自己寫一個class CFile、class CFileMapping，它們都是在constructor時擷取資源，以scoped_ptr包裝起來。如果你的程式重度使用到FileMapping，這很值得，但如果是輕度使用，這多花的工夫不一定更省，還是乖乖地每一行檢查來得有效率。

折衝下來，反對派舉出最大的理由是，若C++ Exception沒有配合RAII(初始化時就配置資源)、Smart pointer管理資源，就會有嚴重resource leak問題。

再來，Raymond Chen的網頁說，不只是要安全地使用exception很難，要審核別人的code更難。如果你在審核別人的code，他是一行一行地做error code checking，你至少能一眼看出，他有努力地深思熟慮error handling。但若別人的code是用exception機制，你很難一眼看出他是否有深思熟慮過error handling的問題。在只有十人以內的小組內code review還算簡單，但是在數千人的程式設計師組(MS Excel開發就用到上千名程式設計師)，就非常困難。

在Google Coding Style中說，若你是在全新開發的project用C++ exception，它帶來的效益比額外成本來得高。但你若是在既有的codebase中想要用exception，這些過去動用上千人力寫的code都要全重寫，這反而是划不來。

近20年來的語言，如VB、Java、C#、Python，就算你只是在main()中用個巨大的try-catch包起來，也不用擔心resource leak的問題，因為它們有GC。而C++沒有implicit GC，只有explicit GC (Smart pointers)，你用到的third-party library，它們的C API都沒有自動記憶體管理，所以你不能把C++當成Java、C#來寫。

C++的原罪就是，它為了要相容於C，它很多地方都要妥協。所以你把C++與C API混用時，很多地方都還是得配合C的習慣。

[Software]約耳與雷蒙討厭exception handling(例外處理)？

約耳續談軟體中，約耳認為exception handling只是另一個goto，它隱瞞了發生錯誤的可能，無法直接看出發生錯誤時的處理路徑。我認同這是為了程式碼的簡潔，不要因為插入太多錯誤處理碼，把錯誤處理碼集中放到catch而不可避免的後果。

在演算法與程式的開發過程中，如果寫下每一行時都要考慮這個函式可能傳回的error，不僅讓撰寫變慢，而且本來流暢的思緒被卡住。如果寫程式時，先只關注預期的程式路徑，把catch放在程式最外圈。經過不斷的測試之後，再把錯誤頻繁發生的區段用try包，這樣開發才快。我這想法比較像test-driven，也許有人會認為「測試引導開發」會埋下更大的錯誤，到了很晚才爆發。但我認為很多事情你自己不先快速走一遭，你永遠無法知道會發生什麼。你在寫程式前預期會發生的錯誤沒有發生，反倒是「不可能」、「沒想到」的錯誤發生。如果你這個第一次快速走一遭的「預習」太晚完成，將會拖累整個開發的進度。


Raymond Chen的Blog: Old New Things中也說Exception Handling是Cleaner, more elegant, and wrong。但他舉的例子不好。在這例子就算是逐行用if-goto來檢查，寫的不好一樣有問題。C++ exception最大的問題是，許多人誤以為只要最後有用catch接到例外，try區塊中曾經配置過的memory、resource都會自動釋放，所有的狀態都會回復到try發生之前。

這是錯誤的！如果沒有達到David Abrahams所稱的Exception Guarantees，不管你是用if亦或exception來寫，都會有問題。狀態無法rollback成try之前，resource沒被釋放。

想像有一個提款機轉帳的函式，先從sender帳戶扣款，再給recipient帳戶加上款項。

void TransferMoney(Person& sender, Person& recipient, int money){
   SubtractAccount(sender, money);
   AddAccount(recipient, money);
}

如果SubtractAccount()執行成功，但要執行下一行時，連線出問題，那sender就虧大了，白白損失一筆錢。如果說你討厭exception，你用if來寫程式:

HRESULT TransferMoney(Person& sender, Person& recipient, int money){
   HRESULT hr=S_OK;
   if((hr=SubtractAccount(sender, money)) != S_OK)
       return hr;
   if((hr=AddAccount(recipient, money))!=S_OK)
       return hr;
   return hr;
}

這個程式執行一半，出了錯誤，直接return error，雖然從程式碼中可直接看出錯誤處理的路徑，但並不符合Abrahams' Guarantees！所有帳款資料庫的狀態沒有回復到函式執行之前。這個問題只要C++語法中沒有提出transactional programming解決方案前，不管是用if還是exception，錯誤處理都是要逐行細心考慮。　

三家連鎖和風洋食之比較:SkyLark、Royal Host、薩莉亞

• 明曜百貨頂樓 SkyLark加州風洋食館
• 東區頂好 Royal Host(樂雅樂)
• 東區頂呱呱樓上 薩莉亞(Saizeriya)

菜單定價
我覺得SkyLark比其他來得經濟實惠。
薩莉亞雖然乍看之下，各別算起來很便宜。
但加總成套餐後(湯、開胃菜、麵包、飲料)
並不比SkyLark來得便宜。
Royal Host的套餐都300起跳，定價不夠彈性。
菜單選擇性不若SkyLark來得多。

食材品質
這三家大致覺得差不多。
但記得在薩莉亞曾碰過地雷，吃到一個像是
沒煮熟的漢堡排。
今天點SkyLark的蘋果奇異果果汁，滿意外的是
他不用廉價的濃縮果汁再稀釋，而是吃得到纖維
的真水果汁。

環境
我去的SkyLark在明曜百貨頂樓，在湯姆熊的旁邊。
有心血管疾病的人不建議在此環境。(雖然如此，今
天中午看到滿多老人在那用餐的)
在東區頂好的Royal Host，有一次上廁所，覺得非常的臭
，好像建築物或是設備太老舊的關係。
就設備氣氛來比較的話，我覺得東區頂呱呱樓上薩莉亞是
最好的。提供的沙發最好坐最舒服。

在昕彤診所，做 睪丸移除手術(bilateral orchiectomy)

今早在昕彤診所報到。

護士把我帶到手術檯躺時，她們很親切，會告
訴你她們正在做什麼，會安撫妳。

躺在檯上，開始滴麻藥(靜脈注射麻醉)，我
聽著護士在旁邊講話，就睡著了。

11:00做，手術40分就做好。流血只有5cc。

手術完後，我又在休息室多睡了二個小時，醒來
時沒什麼感覺。只是覺得蛋蛋那邊有點異物感。

傷口那邊接了引流管，導入褲襠下的紗布，
內褲又在包著衛生棉，以免滲血會沾污內褲。

胯下處包著繃帶，像是包尿布一樣，所以
走路會有點不方便。

護士說不要站或坐太久，不然傷口會血腫太嚴重。


護士有給我看割下來的蛋蛋，像是兩顆蠶豆狀的血球。


第四日，結束休息，要去上班

痛。繃帶拆掉後，站立起來就會痛。但是躺在床上
就不會。原來是因為，站立時上半身的重量壓在
陰囊上，所以會痛。而之前有彈性繃帶綁著，則
是用彈力來抵抗重力，所以可舒緩疼痛。

腰背如果直挺挺地坐在椅上，傷口也會痛，所以現在
都是用坐姿不良的方式打電腦。整個屁股往前滑，快
超出椅子。這樣久了會椎間盤凸出。

現在還是有點滲血，還是要用衛生棉。

內褲穿的時候要用力往上拉，用力把胯下束緊
，如果鬆了的話陰囊就會痛。我現在穿的內褲
走路時還是會滑下來，我想試試看束褲，會否
比較好束緊。

第五日

右側陰囊摸到一個硬硬的，摸了會痛，我怕是疝氣，
打電話去問沈醫生。

沈醫生說那是精索，他手術時沒有割掉，保留下來，
為的是之後男變女手術模擬女性陰唇的圓韌帶。
精索結紮起來，所以初期是硬硬的，兩週後就會變軟
。我不僅是精索那兒會痛，傷口處(陰囊下方)也會痛
，站立起來會痛，躺下來就不痛。

沈醫生說人不像四隻腳的動物，血液不會衝到陰囊，
人是站立的，所以上半身直立血液都會衝到陰囊，拔
掉引流管，瘀血出不來，就更痛。醫生叫我不要站太
久，盡量躺著。

第六日

之前在電話上詢問沈院長說，為何陰囊內有個
硬塊。他說是精索，會只有簽字筆頭那麼大，
但我摸覺得比他說的還大。很擔心。


剛才直接去診所，給沈院長看了，也摸了。
他覺得沒問題。而且傷口癒合很好，叫我明天早上
盆浴。我不懂的是，睪丸、副睪都拿掉了，只剩精
索在，但怎麼陰囊內還是有東西。我本來預期拿掉
後，陰囊會被變得像是一個空空的袋子。

沈院長是給我看一個女性生理構造叫圓韌帶的東西，
他說精索在胚胎性別分化時期正好對應著圓韌帶，
可是我想圓韌帶應該是腹腔內的東西，外面看不出來
，留下來好像沒有意義。

其實我不在意這些，我只希望不要再痛了。剛手術
完的兩三天其實並不痛，我是星期一開始上班日，
等公車站立時才開始覺得痛。他說要痛還會持續一
兩週，陰囊內硬硬的血腫要一個月才會消。

第七日

今天復診給沈院長看。

問「為何陰莖會有黑色一片」
「是瘀血」
「為何陰囊皮脫屑，像頭皮屑一樣」
「陰囊萎縮，所以脫皮」

院長說這個精索還會變更硬，術後一個月
是最硬，之後才會變軟。

不用拆線，用的是自體可吸收的線。

院長叫我現在開始塗金黴素。每天盆浴，
盆浴時加依必朗，每天盆浴兩三次都可以。