简明Python魔法 - 1

Python中类的实现

在Python的Web框架Django中,Python类的构造特性实现了它大部分的核心功能。

当Python解释器遇到类声明时,会创建一个新的namespace ,并执行其内的所有代码,并将变量注册到这个namespace中。

举例:

>>> class Foo(object):
...     print 'Loading...'
...     spam = 'eggs'
...     print 'Done!'
... 
Loading...
Done!
>>> f = Foo()
>>> f.spam
'eggs'

动态的实现一个类

使用type方法可以动态的代码中实现一个类,接受三个参数“类名”、“基类”、“属性”。

>>> Bar = type('Bar', (object,), {'spam': 'eggs'})
>>> Bar.spam
'eggs'

超类改变一切

“metaprogramming”是指一种在程序运行时创建或改变代码的编程手段。type是一个metaclass,一个创建其它类的metaclass。

我们可以替换掉原生的type,使用我们自己的版本,从而控制创建类的过程。

>>> class …
more ...

Codeforces 447D DZY Loves Modification

题意

给你一个n * m的矩阵,让你做K次操作,使得最后得到的值最大。

操作有两种:

一是在任意一行上操作,最终的结果值加上这一行数的和,然后这一行每一个数都要减去p。

二是在任意一列上操作,最终的结果值加上这一列数的和,然后这一列每一个数都要减去p。

数据范围:1 ≤ n, m ≤ 10^3; 1 ≤ k ≤ 10^6; 1 ≤ p ≤ 100

退化版的题目思路

如果我们只限定一种操作,此题就是简单题了。我们维护一个大根堆,堆中保存每一行(或列)之和。

每次操作只需要取出最大值,加到最终结果上。之后将这个值减去对应的p * n(或p * m),再加入堆中。

经过K次循环,就可以得到最后的答案了。

真正的题目思路

对于行和列同时操作,我们也可以套用这种方法。但是要解决对行操作后,对列上数字的值的影响 …

more ...

CPU cache引发的性能血案

在__为什么转置一个512x512的矩阵,会比513x513的矩阵慢很多?__一文中,作者引用了一个矩阵转置的例子,来讲解由于CPU cache的失效而带来的性能损失。

上面的文章对问题的解释与讨论都非常的透彻。我的这篇文章只是对上面文章的一篇读后感和实验报告。就酱。

CPU cache 之 组相联

组相联

组相联的实现和原理不必再赘述了。我想讨论的是,如何在编程中优化CPU的cache性能。

查看CPU信息

我的系统是Ubuntu 12.04,CPU是i5-3230M。(屌丝机 :D)

wizmann@Wichmann:~$ ls /sys/devices/system/cpu/cpu0/cache/index0/
coherency_line_size  physical_line_partition  size
level                shared_cpu_list          type
number_of_sets       shared_cpu_map           ways_of_associativity

使用cat命令查看文件内容,可以获得CPU L1 cache的一些信息。

Key Value
level …
more ...

玩玩算法题1:Sherlock and Queries

题目大意

给你三个数组:A[N], B[M], C[M]。让你按如下pseudo-code给出的规则计算,求出最终A[N]每一项的值。

for i = 1 to M do
    for j = 1 to N do
        if j % B[i] == 0 then
            A[j] = A[j] * C[i]
        endif
    end do
end do

数据范围

1≤ N,M ≤ 10^5

1 ≤ B[i …

more ...

Codeforces Round #253 Tutorial


443A - Anton and Letters

Simple and easy, solved by two lines of python code.

ls = filter(lambda y: y, map(lambda x: x.strip(), raw_input()[1:-1].split(",")))
print len(set(ls))

443B - Kolya and Tandem Repeat

Brute force. Just enumerate the beginning and the end of the substring, and …

more ...

A simple problem - World at War

Background

This problem is from the book "Algorithm 4th edition" (Exersise 4.1.10)

There are N cities and M undirected roads between those cities. People can travel to any city along the roads.

One day, a war breaks out. Our cities are under attack! As we can't defend all …

more ...