Kids Return: September 2010

Friday, September 24, 2010

[Linux]resize image

比如我有一个image叫old.png想要resize成320x240的文件,可以使用如下命令

convert -geometry  320x240 old.png new.png

注意new.png依然保持了原图片的横宽比例,所以未必能得到你想要的大小, 如果不想保持横宽比例

convert -resize  '320x240!' old.png new.png

如果你有9瓶酒,其中一瓶有毒但你不知道究竟是哪一瓶.幸运的是你有两只老鼠可以拿来测试--老鼠碰到毒酒立刻就被毒死了.给定这两只老鼠,如果测试两轮(一轮指你可以对部分或者全部老鼠喂一次酒),如何能够测试出哪瓶是毒酒? 进一步,如果给你5只老鼠,如何在两轮内找出243瓶酒中哪一瓶是毒酒.

Sol:
part1
给酒编号,编号为1 2 3的酒喂老鼠A, 编号为3 4 5的酒喂老鼠B.
case1 A alive, B alive -> poised in 6, 7, 8, 9.
case2 A dead, B alive -> poised in 1, 2
case3 A alive, B dead -> poised in 4, 5
case4 A dead, B dead -> poised is 3, done

case1的情况下, 使用A测试6,7, 使用B测试7,8就可以得到最后结果
case2和case3的情况下, 让活着的一只老鼠喝一瓶酒,也可以得到结果.

part2
让我们用N(k,1)指代给定k只老鼠,只能测试一轮的情况下,最多能找出多少瓶酒中的一瓶毒酒.不难发现N(k,1)=2^k (特别的N(0,1)=1 也就是说一只老鼠都不给,只能断定:只有1瓶的时候这瓶一定是毒酒)

N(k,2)=N(k,1)*C(0,k) + N(k-1,1)*C(1,k) + N(k-2,1)*C(2,k) + ... + N(0,1)*C(k,k)
= 3^k
=> N(5,2)=243

Thursday, September 23, 2010

[Python]几个常用数据结构的高效实现

Python中最广为熟知的container就是list和dict了. 但是对于特定的用途, 这二者未必是最高效的.比如判断容器中是否包括x(x in container),如果容器是list就需要O(n)的时间.而使用set的话这个就只需要O(1)的时间. 我的血泪教训是:　在list很长的时候, x in list这个操作是非常非常低效的.一个好的主意是在另一个set容器来保存membership的信息.

集合(Set)

set是Python的built-in类型,对于membership testing,　removing duplicates 的操作非常高校(O(1)时间).另外对集合操作也非常方便.如果对容器元素的顺序没有要求,set是非常好的选择对象

>>>s= set()
>>>s.add(1)
>>>s.add(2)
>>>s.remove(1)  #throw exception if not in set
>>>s.discard(1) #remove if present
>>>print set([1,2,3]) | set([3,4,5]) #union
set([1, 2, 3, 4, 5])
>>>print set([1,2,3]) & set([3,4,5]) #intersection
set([1])
>>>print set([1,2,3]) - set([3,4,5]) #difference
set([1, 2])
>>>print set([1,2,3]) ^ set([3,4,5]) #symetric difference
set([1, 2, 4, 5])

栈(Stack)

栈的特点是先进后出(FILO).built-in的list用来实现栈非常合适.对于append和pop的实现非常高效.

FIFO队列(FIFO Queue)

队列的特点是先进先出(FIFO). list用来实现队列不够有效.collections.deque可以弥补这一缺点(fast appends and pops from both ends)

>>>from collections import deque
>>>queue = deque()
>>>queue.append(1)
>>>queue.append(2)
>>>queue.appendleft(3)
>>>print queue
deque([3, 1, 2])
>>>queue.pop()
2
>>>queue.popleft()
3

利用deque,我们可以实现一个时间上高效的FIFO queue:

class FIFOQueue():
    def __init__(self):
        self.queue = deque()
        self.counter = itertools.count(1)    # unique sequence count
        self.task_finder = {}                # mapping of tasks to entries

    def append(self, task):
        if debug:
            print "FIFOQueue.append "+repr(task)

        if task in self:
            return
        count = next(self.counter)

        entry = [count, task]
        self.task_finder[task] = entry
        self.queue.append(entry)
        if debug:
            print "FIFOQueue.append "+repr(task)+" done"

    def top(self):
        if debug:
            print "FIFOQueue.top "
        while self.queue:
            count, task  = self.queue[0]
            if count:
                if debug:
                    print "FIFOQueue.pop "+repr(task)+" done"
                return task
            else:
                self.queue.popleft()
        if debug:
            print "FIFOQueue.top none"
        return None

    def pop(self):
        if debug:
            print "FIFOQueue.pop "
        while not self.top():
            continue
        if self.queue:
            entry  = self.queue.popleft()
            count, task = entry
            assert(count != None)
            assert(self.task_finder[task] == entry)
            del self.task_finder[task]
            if debug:
                print "FIFOQueue.pop "+repr(task)+" done"
            return task
        if debug:
            print "FIFOQueue.pop none"
        return None

    def remove(self, task):
        if debug:
            print "FIFQueue.remove "+repr(task)
        if task not in self:
            return
        entry = self.task_finder[task]
        assert(entry[0] != None)
        entry[0] = None
        del self.task_finder[task]
        if debug:
            print "FIFOQueue.remove "+repr(task)+" done"

    def __len__(self):
        return len(self.task_finder)

    def __contains__(self, task):
        return self.task_finder.has_key(task)

    def __repr__(self):
        return repr(self.queue)

这个实现的好处在于可以常数时间删除一个元素以及在常数时间内判定一个元素是否属于这个queue

优先队列(Priority Queue)

使用堆(heap)实现的优先队列(priority queue)可以在O(1)时间内得到队列中最小元素,O(logn)时间内插入或者删除一个元素.我通常在simulator中会使用priority queue来管理所有事件.

Python提供了heapq来实现.值得注意的是heapq并不是一个容器,而是操作在list上的一系列的heap算法(包括heappush,heappop,heapify)等.http://docs.python.org/library/heapq.html给出了用这一些算法实现堆排序(heapsort)以及优先队列的. 不过在那个优先队列的例子里有一点小bug. 这里是我给出的代码

import itertools
from heapq import heappush, heappop
class PriorityQueue():
    def __init__(self):
        self.pq = []                         # the priority queue list
        self.counter = itertools.count(1)    # unique sequence count
        self.task_finder = {}                # mapping of tasks to entries
        self.size = 0
 
    def add_task(self, priority, task, count=None):
        if count is None:
            count = next(self.counter)
        entry = [priority, count, task]
        self.task_finder[task] = entry
        heappush(self.pq, entry)
        self.size  += 1

    def pop_task(self):
        while self.pq:
            entry = heappop(self.pq)
            priority, count, task = entry
            if self.task_finder[task] == entry:
                del self.task_finder[task]
            if count is not None:
                self.size -= 1
                return (priority, task)
        return None


    def del_task(self, task):
        entry = self.task_finder[task]
        if entry[1] != None:
            self.size -= 1
        entry[1] = None

    def reprioritize(self, priority, task):
        entry = self.task_finder[task]
        self.add_task(priority, task, entry[1])
        if entry[1] != None:
            self.size -= 1
        entry[1] = None

    def __len__(self):
        return self.size

Intel CPU Lineup, roadmap

从Intel的主页来看Processor产品线的划分

按照处理器的品牌

Core(酷睿)主要是针对中端到高端的处理器.
- 早期(2006年)的32位CPU使用NetBurst架构,分为Core Solo(单核)和Core Duo(双核)
- 升级到64位CPU以后, 使用了Core架构,从低端到高端分为Core 2 Solo, Core 2 Duo, Core 2 Quad和Core 2 Extreme
- 升级到Nehalem微架构以后, 从低端到高端可以具体划分为Core i3, Core i5, Core i7. i3,i5,i7在不同的时间使用不同的微架构. 这3个系列的区别可见下表
Pentium
Celeron
Atom
Xeon(至强), 主要针对服务器以及工作站

按照处理器的微架构

Sandy Bridge
Nehalem

Intel Microarchitecture 所有Intel Microarchitecture列表这是从wiki上偷来的图,展示从Netburst和P6到Nehalem的变迁

Intel CPU的家族史: Intel CPU 家族一覽 - 桌上電腦(上篇) Intel CPU 家族一覽 - 桌上電腦(中篇) Intel CPU 家族一覽 - 桌上電腦(下篇)

Monday, September 20, 2010

[Python]glob

glob用于寻找符合pattern的文件名/目录名, 相当于shell下的ls, 很好用

>>import glob
>>glob.glob(”/path/to/me/*.txt”)
['./1.txt', './2.txt']

Monday, September 13, 2010

[Linux]查看系统信息相关命令

Linux版本信息

$uname -a
Linux gs7600 2.6.32-24-generic #42-Ubuntu SMP Fri Aug 20 14:21:58 UTC 2010 x86_64 GNU/Linux

CPU信息

$cat /proc/cpuinfo

Cache大小

cat /sys/devices/system/cpu/cpu0/cache/index*/size

系统内存使用信息

系统当前内存使用状况

$cat /proc/meminfo

或者

$free -m

如果要看具体某个进程的内存使用情况,/proc/pid/底下有一些　比如statm, maps, smaps, status.

mem_usage.py是另一个脚本可以查看具体进城的内存使用. 比如要查看pid为4418的进程

$mem_usage.py 4418
Mapped memory:
               Shared            Private
           Clean    Dirty    Clean    Dirty
    r-xp    8364        0    15484        0  -- Code
    rw-p       0        0        0     1704  -- Data
    r--p     704        0      648      516  -- Read-only data
    ---p       0        0        0        0
    rw-s       0      304        0        0
    r--s     800        0       40        0
   total    9868      304    16172     2220
Anonymous memory:
               Shared            Private
           Clean    Dirty    Clean    Dirty
    rwxp       0        0        0     1340  -- Writable code (stack)
    r-xp       0        0        0        0
    rw-p       0        0        0    81048  -- Data (malloc, mmap)
    ---p       0        0        0        0
   total       0        0        0    82388
   ----------------------------------------
   total    9868      304    16172    84608

更多详细的可以参见http://elinux.org/Runtime_Memory_Measurement

进程的信息

最基本的命令就是广为人知的top.
htop是更fancy的一个版本, 可以看到每个线程使用的内存和CPU

当前mount的设备

$cat /proc/mounts

或者等同的

$mount

I/O的统计信息

$ iostat
Linux 2.6.38-8-server (fawnserver)  04/15/2011  _x86_64_ (12 CPU)

avg-cpu:  %user   %nice %system %iowait  %steal   %idle
           4.47    0.00    2.07    0.16    0.00   93.30

Device:            tps   Blk_read/s   Blk_wrtn/s   Blk_read   Blk_wrtn
sda               6.24        51.31      1011.76     676334   13337192
sdb               0.00         0.03         0.00        408          0

$ iotop
Total DISK READ: 0.00 B/s | Total DISK WRITE: 0.00 B/s
  TID  PRIO  USER     DISK READ  DISK WRITE  SWAPIN     IO>    COMMAND                                                                       
    1 be/4 root        0.00 B/s    0.00 B/s  0.00 %  0.00 % init
    2 be/4 root        0.00 B/s    0.00 B/s  0.00 %  0.00 % [kthreadd]
    3 be/4 root        0.00 B/s    0.00 B/s  0.00 %  0.00 % [ksoftirqd/0]
    4 be/4 root        0.00 B/s    0.00 B/s  0.00 %  0.00 % [kworker/0:0]
...

网络流量的统计信息

每块网卡的收发packet数目:

$cat /proc/net/dev
Inter-|   Receive                                                |  Transmit
 face |bytes    packets errs drop fifo frame compressed multicast|bytes    packets errs drop fifo colls carrier compressed
    lo:896689377 11170911    0    0    0     0          0         0 896689377 11170911    0    0    0     0       0          0
  eth0:708410727 3925021    0    0    0     0          0      5468 84085137  732531    0    0    0     0       0          0

bwm-ng:基于/proc/net/dev信息,动态显示各个网卡的traffic

iftop:动态显示各台主机之间traffic

nethogs: 如果要查看每个process使用的网络情况,可以使用
http://www.ubuntugeek.com/nethogs-net-top-tool-grouping-bandwidth-per-process.html

能耗

如果是基于Intel的CPU, 可以用powertop查看power consumption

内核消息

dmesg将内核消息输出至标准输出

$dmesg

Ref:

http://www.ubuntugeek.com/category/monitoring
http://www.cyberciti.biz/tips/how-do-i-find-out-linux-cpu-utilization.html

Thursday, September 09, 2010

[Linux/Mac]删除所有.svn文件夹

用于删除一个目录下(以及其子目录下)所有的.svn目录

$ rm -rf `find . -type d -name .svn`