Single Number Problem

Introduction

There are a lot of interview problem based on the 1D-array, which is the one of the easiest "data structure".

But the problem about that simple data structure might not be that simple. Here is the summary of the problem about 1D-array.

Of course, most of them come from …

more ...

简明Python魔法 - 2

再说描述符 - Descriptor

最简单的描述符

覆写类的__get____setter__函数就可以实现一个简单的描述符。对某个类型实例的读写进行额外的控制。

>>> import datetime
>>> class CurrentDate(object):
...     def __get__(self, instance, owner):
...         return datetime.date.today()
...     def __set__(self, instance, value):
...         raise NotImplementedError("Can't change the current date.")
...
>>> class Example(object):
...     date = CurrentDate()
...
>>> e = Example()
>>> e.date
datetime.date(2008, 11, 24 …
more ...

简明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 ...

How to implement a queue with stack(s)?

This problem is from the book Algorithms, 4th Edition.

Queue with three stacks. Implement a queue with three stacks so that each queue operation takes a constant (worst-case) number of stack operations.

Warning : high degree of difficulty.

When I search the Internet to find a solution, I find varieties of …

more ...

逗比带你读论文之Barrier

知识共享许可协议

逗比带你读论文之BarrierWizmann 创作

采用 知识共享 署名-非商业性使用-相同方式共享 4.0 国际 许可协议进行许可。

原文地址

Barrier February 17th, 2007

前言:我艹!好多核!

虽然80核心的浮点数运算巨兽离我们还有些遥远,但是多核处理器已经走进了我们的生活。

其实多核处理器已经不是新鲜名词了,在Power Macintosh 9500中,就使用了多核处理器。

现在让我们深入了理解一下多核心处理器吧。

线程技术

一些名词定义

线程

线程只是 抢占调度的(pre-emptively scheduled) 共享地址空间的 执行上下文。

多线程

用来简化控制流和绕开阻塞的系统调用的方法,并非用来实现程序的并行化

并发多线程

在物理上并发的线程,用来利用多核处理器来优化系统性能

为什么“并发多线程”是个神坑

人人都在说”并发多线程“是个神坑,但这种老生常谈并不是因为自然原因 …

more ...