2011年8月27日 星期六

PEP 8 -- Style Guide for Python Code (5)

Programming Recommendations
1. Code should be written in a way that does not disadvantage other implementations of Python (PyPy, Jython, IronPython, Pyrex, Psyco, and such).
  a. Do not rely on CPython's efficient implementation of in-place string concatenation for statements in the form a += b or a = a + b. Those statements run more slowly in Jython.
  b. In performance sensitive parts of the library, the ''.join() form should be used instead. This will ensure that concatenation occurs in linear time across various implementations.

2. Comparisons to singletons like None should always be done with 'is' or 'is not', never the equality operators.
  a. Beware of writing "if x" when you really mean "if x is not None" -- e.g. when testing whether a variable or argument that defaults to None was set to some other value. The other value might have a type (such as a container) that could be false in a boolean context!

3. When implementing ordering operations with rich comparisons, it is best to implement all six operations (__eq__, __ne__, __lt__, __le__, __gt__, __ge__) rather than relying on other code to only exercise a particular comparison.
  a. To minimize the effort involved, the functools.total_ordering() decorator provides a tool to generate missing comparison methods.
  b. PEP 207 indicates that reflexivity rules *are* assumed by Python. Thus, the interpreter may swap y > x with x < y, y >= x with x <= y, and may swap the arguments of x == y and x != y. The sort() and min() operations are guaranteed to use the < operator and the max() function uses the > operator. However, it is best to implement all six operations so that confusion doesn't arise in other contexts.

4. Use class-based exceptions.
  a. String exceptions in new code are forbidden, because this language feature is being removed in Python 2.6.
  b. Modules or packages should define their own domain-specific base exception class, which should be subclassed from the built-in Exception class. Always include a class docstring. E.g.:

  class MessageError(Exception):
      """Base class for errors in the email package."""

  c. Class naming conventions apply here, although you should add the suffix "Error" to your exception classes, if the exception is an error. Non-error exceptions need no special suffix.

5. When raising an exception, use "raise ValueError('message')" instead of the older form "raise ValueError, 'message'".
  a. The paren-using form is preferred because when the exception arguments are long or include string formatting, you don't need to use line continuation characters thanks to the containing parentheses. The older form will be removed in Python 3000.

6. When catching exceptions, mention specific exceptions whenever possible instead of using a bare 'except:' clause.

  try:
      import platform_specific_module
  except ImportError:
      platform_specific_module = None

  a. A bare 'except:' clause will catch SystemExit and KeyboardInterrupt exceptions, making it harder to interrupt a program with Control-C, and can disguise other problems. If you want to catch all exceptions that signal program errors, use 'except Exception:'.
  b. A good rule of thumb is to limit use of bare 'except' clauses to two cases:
    (1) If the exception handler will be printing out or logging the traceback; at least the user will be aware that an error has occurred.
    (2) If the code needs to do some cleanup work, but then lets the exception propagate upwards with 'raise'. 'try...finally' is a better way to handle this case.

7. For all try/except clauses, limit the 'try' clause to the absolute minimum amount of code necessary. Again, this avoids masking bugs.
  Yes:
       try:
           value = collection[key]
       except KeyError:
           return key_not_found(key)
       else:
           return handle_value(value)
  No:
       try:
           # Too broad!
           return handle_value(collection[key])
       except KeyError:
           # Will also catch KeyError raised by handle_value()
           return key_not_found(key)

8. Use string methods instead of the string module.
  a. String methods are always much faster and share the same API with unicode strings.
  b. Override this rule if backward compatibility with Pythons older than 2.0 is required.

9. Use ''.startswith() and ''.endswith() instead of string slicing to check for prefixes or suffixes.
  a. startswith() and endswith() are cleaner and less error prone.
  Yes: if foo.startswith('bar'):
  No: if foo[:3] == 'bar':

10. Object type comparisons should always use isinstance() instead of comparing types directly.

  Yes: if isinstance(obj, int):
  No:  if type(obj) is type(1):

  a. When checking if an object is a string, keep in mind that it might be a unicode string too! In Python 2.3, str and unicode have a common base class, basestring, so you can do:

  if isinstance(obj, basestring):

11. For sequences, (strings, lists, tuples), use the fact that empty sequences are false.

  Yes:
       if not seq:
       if seq:
  No:
       if len(seq):
       if not len(seq):

12. Don't write string literals that rely on significant trailing whitespace. Such trailing whitespace is visually indistinguishable and some editors (or more recently, reindent.py) will trim them.

13. Don't compare boolean values to True or False using ==

  Yes:
      if greeting:
  No:
      if greeting == True:
  Worse:
      if greeting is True:

2011年8月24日 星期三

PEP 8 -- Style Guide for Python Code (4)

Naming Conventions
1. Names to Avoid
  a. Never use the characters `l' (lowercase letter el), `O' (uppercase letter oh), or `I' (uppercase letter eye) as single character variable names.
  b. In some fonts, these characters are indistinguishable from the numerals one and zero. When tempted to use `l', use `L' instead.

2. Package and Module Names
  a. Python packages should also have short, all-lowercase names, although the use of underscores is discouraged.
  b. Since module names are mapped to file names, and some file systems are case insensitive and truncate long names, it is important that module names be chosen to be fairly short.

3. Class Names
  a. Class names use the CapWords convention. Classes for internal use have a leading underscore in addition.

4. Exception Names
  a. Because exceptions should be classes, the class naming convention applies here. However, you should use the suffix "Error" on your exception names (if the exception actually is an error).

5. Global Variable Names
  a. (Let's hope that these variables are meant for use inside one module only.) The conventions are about the same as those for functions.
  b. Modules that are designed for use via "from M import *" should use the __all__ mechanism to prevent exporting globals, or use the older convention of prefixing such globals with an underscore (which you might want to do to indicate these globals are "module non-public").

6. Function Names
  a. Function names should be lowercase, with words separated by underscores as necessary to improve readability.
  b. mixedCase is allowed only in contexts where that's already the prevailing style (e.g. threading.py), to retain backwards compatibility.

7. Function and method arguments
  a. Always use 'self' for the first argument to instance methods.
  b. Always use 'cls' for the first argument to class methods.
  c. If a function argument's name clashes with a reserved keyword, it is generally better to append a single trailing underscore rather than use an abbreviation or spelling corruption. Thus "print_" is better than "prnt". (Perhaps better is to avoid such clashes by using a synonym.)

8. Method Names and Instance Variables
  a. Use the function naming rules: lowercase with words separated by underscores as necessary to improve readability.
  b. Use one leading underscore only for non-public methods and instance variables.
  c. To avoid name clashes with subclasses, use two leading underscores to invoke Python's name mangling rules.
  d. Python mangles these names with the class name: if class Foo has an attribute named __a, it cannot be accessed by Foo.__a. (An insistent user could still gain access by calling Foo._Foo__a.) Generally, double leading underscores should be used only to avoid name conflicts with attributes in classes designed to be subclassed.

9. Constants
  a. Constants are usually defined on a module level and written in all capital letters with underscores separating words. Examples include MAX_OVERFLOW and TOTAL.

10. Designing for inheritance
  a. Public attributes should have no leading underscores.
  b. If your public attribute name collides with a reserved keyword, append a single trailing underscore to your attribute name. This is preferable to an abbreviation or corrupted spelling.
  c. For simple public data attributes, it is best to expose just the attribute name, without complicated accessor/mutator methods.
  d. If your class is intended to be subclassed, and you have attributes that you do not want subclasses to use, consider naming them with double leading underscores and no trailing underscores.

2011年8月23日 星期二

PEP 8 -- Style Guide for Python Code (3)

Comments
1. Block comments
  a. Block comments generally apply to some (or all) code that follows them, and are indented to the same level as that code. Each line of a block comment starts with a # and a single space (unless it is indented text inside the comment). Paragraphs inside a block comment are separated by a line containing a single #.
2. Inline comments
  a. Inline comments should be separated by at least two spaces from the statement. They should start with a # and a single space.

Documentation Strings
1. Write docstrings for all public modules, functions, classes, and methods. Docstrings are not necessary for non-public methods, but you should have a comment that describes what the method does. This comment should appear after the "def" line.
2. Note that most importantly, the """ that ends a multiline docstring should be on a line by itself, and preferably preceded by a blank line, e.g.:

"""Return a foobang

Optional plotz says to frobnicate the bizbaz first.

"""

3. For one liner docstrings, it's okay to keep the closing """ on the same line.

2011年8月22日 星期一

PEP 8 -- Style Guide for Python Code (2)

Whitespace in Expressions and Statements
1. Pet Peeves
  a. Avoid extraneous whitespace in the following situations:
    (1) Immediately inside parentheses, brackets or braces.
    Yes: spam(ham[1], {eggs: 2})
    No:  spam( ham[ 1 ], { eggs: 2 } )
    (2) Immediately before a comma, semicolon, or colon:
    Yes: if x == 4: print x, y; x, y = y, x
    No:  if x == 4 : print x , y ; x , y = y , x
    (3) Immediately before the open parenthesis that starts the argument list of a function call:
    Yes: spam(1)
    No:  spam (1)
    (4) Immediately before the open parenthesis that starts an indexing or slicing:
    Yes: dict['key'] = list[index]
    No:  dict ['key'] = list [index]
    (5) More than one space around an assignment (or other) operator to align it with another.
    Yes:
         x = 1
         y = 2
         long_variable = 3
    No:
         x             = 1
         y             = 2
         long_variable = 3
2. Other Recommendations
  a. Always surround these binary operators with a single space on either side: assignment (=), augmented assignment (+=, -= etc.), comparisons (==, <, >, !=, <>, <=, >=, in, not in, is, is not), Booleans (and, or, not).
  b. Use spaces around arithmetic operators:
  Yes:
       i = i + 1
       submitted += 1
       x = x * 2 - 1
       hypot2 = x * x + y * y
       c = (a + b) * (a - b)
  No:
       i=i+1
       submitted +=1
       x = x*2 - 1
       hypot2 = x*x + y*y
       c = (a+b) * (a-b)
  c. Don't use spaces around the '=' sign when used to indicate a keyword argument or a default parameter value.
  Yes:
       def complex(real, imag=0.0):
           return magic(r=real, i=imag)
  No:
       def complex(real, imag = 0.0):
           return magic(r = real, i = imag)
  d. Compound statements (multiple statements on the same line) are generally discouraged.
  Yes:
       if foo == 'blah':
           do_blah_thing()
       do_one()
       do_two()
       do_three()
  No:
       if foo == 'blah': do_blah_thing()
       do_one(); do_two(); do_three()
  e. While sometimes it's okay to put an if/for/while with a small body on the same line, never do this for multi-clause statements. Also avoid folding such long lines!
  Rather not:
    if foo == 'blah': do_blah_thing()
    for x in lst: total += x
    while t < 10: t = delay()
  Definitely not:
    if foo == 'blah': do_blah_thing()
    else: do_non_blah_thing()

    try: something()
    finally: cleanup()
    
    do_one(); do_two(); do_three(long, argument,
                                 list, like, this)

    if foo == 'blah': one(); two(); three()

2011年8月21日 星期日

PEP 8 -- Style Guide for Python Code (1)

Code layout
1. Indentation
  a. Use 4 spaces per indentation level.
  b. Continuation lines should align wrapped elements either vertically using Python's implicit line joining inside parentheses, brackets and braces, or using a hanging indent.
  # Aligned with opening delimiter
  foo = long_function_name(var_one, var_two,

                           var_three, var_four)
  # hanging indent
  # there should be no arguments on the first line and
  # further indentation should be used to clearly distinguish
  # itself as a continuation line

  def long_function_name(
          var_one, var_two, var_three,
          var_four):
      print(var_one)


2. Tabs or Spaces?
  a. Never mix tabs and spaces.
  b. Code indented with a mixture of tabs and spaces should be converted to using spaces exclusively.

3. Maximum Line Length
  a. Limit all lines to a maximum of 79 characters.
  b. For flowing long blocks of text (docstrings or comments), limiting the length to 72 characters is recommended.
  c. The preferred place to break around a binary operator is after the operator, not before it.

4. Blank lines
  a. Separate top-level function and class definitions with two blank lines.
  b. Method definitions inside a class are separated by a single blank line.

5. Encodings
  a. Code in the core Python distribution should always use the ASCII or Latin-1 encoding (a.k.a. ISO-8859-1). For Python 3.0 and beyond, UTF-8 is preferred over Latin-1, see PEP 3120.
  b. Latin-1 (or UTF-8) should only be used when a comment or docstring needs to mention an author name that requires Latin-1; otherwise, using \x, \u or \U escapes is the preferred way to include non-ASCII data in string literals.


Imports
1. Imports should usually be on separate lines.
  Yes: import os
       import sys
       from subprocess import Popen, PIPE
  No:  import sys, os


2. Imports are always put at the top of the file, just after any module comments and docstrings, and before module globals and constants.

3. Imports should be grouped in the following order:
  (1) standard library imports
  (2) related third party imports
  (3) local application/library specific imports

4. You should put a blank line between each group of imports.

5. Put any relevant __all__ specification after the imports.

6. Always use the absolute package path for all imports.

2011年1月28日 星期五

[Git] 01_認識 Git

  • Git 是 Distributed Version Control System (DVCS),每次 client 不只是從 repository 拿到最新版本的檔案而已,而是整個 repository 都整個備份下來 (包含從頭到尾的版本),不用擔心任何一台 server 掛掉的狀況,因為每個人都是 repository。
  • 大部分的 Version Control System (VCS) 都是儲存每一版本之間檔案的變化,如果要第 r 版的檔案,只要第 1 版的檔案,跟第 1 版到第 r 版的檔案的變化,就可以還原第 r 版的檔案長什麼樣,然而 Git 是紀錄整個檔案下來,而不是只儲存檔案的變化。
  • 因為整個 repository 都在你的電腦裡面,所以每次 commit 或絕大部分的 operation 都在自己的電腦裡面就完成了,不用靠網路連線連到遠端的 server 去完成 commit 或看 log 等之類的動作。
  • Git 在儲存檔案前會做 check sum (SHA-1 hash),事實上 Git 不是靠檔名來儲存檔案的,而是靠這些 hash value
  • 在 Git 裡,檔案會被歸類到三種狀態之一:
    • commited:檔案已經被安全的儲存到電腦中的 database 裡了
    • modified:你已經改變過檔案的內容了,但是還沒 commit 到你的 database 裡面
    • staged:標示這個修改過的檔案,準備把它 commit 到 database 裡

2011年1月25日 星期二

[Algo] Problem 9

Problem 9-1 Largest i numbers in sorted order
Given a set of n numbers, we wish to find the i largest in sorted order using a comparison-based algorithm. Find the algorithm that implements each of the following methods with the best asymptotic worst-case running time, and analyze the running times of the algorithms in terms of n and i.
a. Sort the numbers, and list the i largest.
b. Build a max-priority queue from the numbers, and call EXTRACT-MAX i times.
c. Use an order-statistic algorithm to find the ith largest number, partition around that number, and sort the i largest numbers.
solution:
a. Sort the numbers by heapsort $\Rightarrow \Theta(n\lg n)$
List the i largest $\Rightarrow \Theta(i)$
Total: $\Theta(n\lg n) + \Theta(i) = \Theta(n\lg n)$

b. Build a max-priority queue $\Rightarrow$ call MAX-HEAP-INSERT n times $\Rightarrow O(n\lg n)$
Call EXTRACT-MAX i times $\Rightarrow i\times O(\lg n) = O(i\lg n)$
Total: $O(n\lg n) + O(i\lg n) = O(n\lg n)$

c. Find the ith largest number  $\Rightarrow O(n)$
Partition around the number $\Rightarrow O(n)$
Sort the i largest numbers $\Rightarrow O(i\lg i)$
Total: $O(n + i\lg i)$


Problem 9-2 Weighted median
For n distinct elements $x_1, x_2, \ldots, x_n$ with positive weights $w_1, w_2, \ldots, w_n$ such that $\sum_{i=1}^n w_i = 1$, the weighted (lower) median is the element $x_k$ satisfying $$\sum_{x_i < x_k}w_i < \frac{1}{2}$$ and $$\sum_{x_i > x_k}w_i \leq \frac{1}{2}.$$
a. Argue that the median of $x_1, x_2, \ldots, x_n$ is the weighted median of the $x_i$ with weights $w_i = 1/n$ for $i = 1, 2, \ldots, n$.
b. Show how to compute the weighted median of n elements in $O(n\lg n)$ worst-case time using sorting.
c. Show how to compute the weighted median in $\Theta(n)$ worst-case time using a linear-time median algorithm such as SELECT from section 9.3.

The post-office location problem is defined as follows. We are given n points $p_1, p_2, \ldots, p_n$ with associated weights $w_1, w_2, \ldots, w_n$. We wish to find a point p (not necessarily one of the input points) that minimizes the sum $\sum_{i=1}^n w_id(p, p_i)$ where $d(a, b)$ is the distance between points a and b.

d. Argue that the weighted median is a best solution for the 1-dimensional post-office location problem, in which points are simply real numbers and the distance between points a and b is $d(a, b) = |a-b|$.
e. Find the best solution for the 2-dimensional post-office location problem, in which the points are $(x, y)$ coordinate pairs and the distance between points $a = (x_1, y_1)$ and $b = (x_2, y_2)$ is the Manhattan distance given by $d(a, b) = |x_1 - x_2| + |y_1 - y_2|$.

solution:
a. Let $y_1, y_2, \ldots, y_n$ be the sorted list of $x_1, x_2, \ldots, x_n$. The median is therefore $y_k$, where $k = \lfloor (n+1)/2 \rfloor$. In that case,
$$\sum_{y_i < y_k}\frac{1}{n} \leq \sum_{i=1}^{\lfloor (n+1)/2 \rfloor - 1}\frac{1}{n} = \frac{\lfloor (n+1)/2 \rfloor - 1}{n} < \frac{n-1}{2n} < \frac{1}{2},$$ and
$$\sum_{y_i > y_k}\frac{1}{n} \leq \sum_{i=\lfloor (n+1)/2 \rfloor + 1}^{n}\frac{1}{n} = \frac{n - \lfloor (n+1)/2 \rfloor}{n} \leq \frac{n - n/2}{n} = \frac{1}{2}.$$
Hence, $y_k$ is the weighted median as well.

b. We can sort $x_1, x_2, \ldots, x_n$ to get the sorted list $y_1, y_2, \ldots, y_n$. And find the weighted median by summing up the weights from $w_1$. Sorting whole list takes $O(n\lg n)$ time, and finding the weighted median according to the sorted list takes $O(n)$ time. So, total time is $O(n\lg n)$.

c.
@{
\proc{Weighted-Mediam}(X)
\li n = |X|
\li \If n = 1
\li \;\;\;\;\Return X[1]
\li \Elif |X| = 2
\li \;\;\;\;\Return\textup{max}(X[1], X[2])
\li \Else
\li \;\;\;\;x_k = \proc{Select}(X, 1, n, \lfloor(n+1)/2\rfloor)
\li \;\;\;\;L = \Sigma_{x_i < x_k} w_i
\li \;\;\;\;R = \Sigma_{x_i > x_k} w_i
\li \;\;\;\;\If L < 1/2 \;\textup{and}\; R \leq 1/2
\li \;\;\;\;\;\;\;\;\Return x_k
\li \;\;\;\;\Elif L \geq 1/2
\li \;\;\;\;\;\;\;\;w_k = w_k + R
\li \;\;\;\;\;\;\;\;X^{'} = \{x | x \in X \textup{and} x \leq x_k\}
\li \;\;\;\;\Else
\li \;\;\;\;\;\;\;\;w_k = w_k + L
\li \;\;\;\;\;\;\;\;X^{'} = \{x | x \in X \textup{and} x \geq x_k\}
\li \;\;\;\;\Return \proc{Weighted-Median}(X^{'})
}@