Memoization 在具有函数式编程特性的语言中用于缓存函数运算后的结果值,在java中可以使用动态代理实现这一特性，但对于java中的递归的运算,其不能缓存递归的过程值,而python,lisp等函数式特性的动态语言则能对每一次运算进行缓存.

Memoization的简单介绍如下:
我们在第一次计算一个值后就记录一个值.然后在后续问题中使用这个值.
we record a value the first time it’s computed,then look it up the subsequent times we need it.

这就是动态编程这种通用技术的核心
And this is what lies at the heart of this very general technique called dynamic programming.

实际上 它也是很多保存结果的计算技巧的核心
And in fact,it lies at the heart of a lot of useful computational techniques where we save results.

java具体的类可以这样实现:

import java.lang.reflect.InvocationHandler;
import java.lang.reflect.InvocationTargetException;
import java.lang.reflect.Method;
import java.lang.reflect.Proxy;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Memoizer implements InvocationHandler {
public static Object memoize(Object object) {
return Proxy.newProxyInstance(object.getClass().getClassLoader(), object.getClass().getInterfaces(), new Memoizer(
object));
}

private Object object;
private Map caches = new HashMap();

private Memoizer(Object object) {
this.object = object;
}

public Object invoke(Object proxy, Method method, Object[] args) throws Throwable {

if (method.getReturnType().equals(Void.TYPE)) {
// Don’t cache void methods
return invoke(method, args);
} else {
Map cache = getCache(method);
List key = Arrays.asList(args);
Object value = cache.get(key);

System.out.println(“get cache value ===”+value);
if (value == null && !cache.containsKey(key)) {
value = invoke(method, args);
System.out.println(“put cache value ===”+key +”–”+value);
cache.put(key, value);
}
return value;
}
}

private Object invoke(Method method, Object[] args) throws Throwable {
try {
return method.invoke(object, args);
} catch (InvocationTargetException e) {
throw e.getTargetException();
}
}

private synchronized Map getCache(Method m) {
Map cache = (Map) caches.get(m);
if (cache == null) {
cache = Collections.synchronizedMap(new HashMap());
caches.put(m, cache);
}
return cache;
}
}

然后可以构造一个接口:

public interface Car {
public int fibonacci(int n);
}

一个实现类:

public class CarImpl implements Car {
public int fibonacci(int n) {
if (n == 0 || n == 1)
return 1;
return fibonacci(n - 1) + fibonacci(n - 2);
}
}

在调用时候:

Car foo = (Car) Memoizer.memoize(new CarImpl());
int n = foo.fibonacci(5);//直接运算并对结果进行缓存
int rr = foo.fibonacci(6);//直接运算并对结果进行缓存，不能够获取fibonacci(5)的结果值

但是若:

int n = foo.fibonacci(5);//直接运算并对结果进行缓存
int rr = foo.fibonacci(5);//直接获取缓存值

但在函数式特性的语言中(javascript):

function memoize(fundamental, cache){
cache = cache || {};
var shell = function(arg){
if (!cache.hasOwnProperty(arg)){
cache[arg] = fundamental(arg);
}
return cache[arg];
};
return shell;
}

function factorial(n){
if (n==0 || n==1){ return 1;}
return factorial(n-1)+factorial(n-2);
}

//memoize the factorial function
var memfactorial = memoize(factorial, { 0: 1, 1: 1 });

//call the new function
var fact6 = memfactorial(6);

var fact5 = memfactorial(5);//直接获取前面已经计算过的结果
console.info(fact6);
console.info(fact5);

wiki中对Memoization的介绍:

In computing, memoization is an optimization technique used primarily to speed up computer programs by having function calls avoid repeating the calculation of results for previously processed inputs. Memoization has also been used in other contexts (and for purposes other than speed gains), such as in simple mutually recursive descent parsing^[1] in a general top-down parsing algorithm^[2][3] that accommodates ambiguity and left recursion in polynomial time and space. Although related to caching, memoization refers to a specific case of this optimization, distinguishing it from forms of caching such as buffering or page replacement. In the context of some logic programming languages, memoization is also known as tabling;^[4] see also lookup table.

关于java Memoization实现的文章:

Memoization in Java Using Dynamic Proxy Classes

导数的概念:
设y=f(x)在x0的邻域U内有定义,x0,x0+△x∈U,△x:该变量,增量.△y = f(x0+△x)-f(x0),△y/△x = [f(x0+△x)-f(x0)]/△x;
如果lim_(△x->0) △y/△x 存在,则称此极限为f(x)在x0处的导数.记为:f’(x0)或y’|_(x=x0)或dy/dx|_(x=x0)

1.给定f(x),x0,则f’(x0)随之而确定,f’(x0)是一个数.
2.求导过程中△x->0是变量
3.若f(x)在(a,b)内每一点都可导,则称f(x)在(a,b)区间可导.
f’(x0) = lim_(△x->0) △y/△x;

例如:f(x) = x³ ,求x=2时的导数.

f ‘ (x) = △y/△x;

△y = f(x+△x) - f(x) = (x+△x)³-x³ = 3x²△x + 3x△x² + △x³ ;

所以f ‘ (x) = 3*x² ;(因为△x趋向于0);

f ‘ (2) =12;

导数的一些性质:

几何性质:曲线y = f(x)在(x0,f(x0))的切线存在,且此切线不垂直于x轴.
(曲线折点切线不存在,点切线垂直于x轴,tg 值无限大,所以不可导)

wiki导数的介绍: 导数

牛顿迭代法的公式为 :

如果f ‘ (x_n-1)!=0;那么 x_n = x_n-1 - f(x_n-1)/f ‘ (x_n-1);

推导过程为:

假设有函数f(x),使得f(x) = 0;

求此时x的值,在函数上取一点x0,其下一个点值f(x1)比f(x0)更接近与0,这个时候假设x0的值f(x0)趋近f(x)的值,
则可以假设此点的切线斜率为k:

则F(x1)-F(x0) = k(x1-x0).而斜率为f(x0) 的导数f ‘ (x0),而F(x1)=0;

所以:x1= x0 - f(x0)/f ‘ (x0);

示例:求任意一个正数的平方根.

牛顿迭代法则可以视为:求函数f(x) = x² - N = 0 的解.

java代码如下:

public static double sqrt(double n, double guess) {

if (n > 0 && guess > 0) {

double temp = (guess + n / guess) / 2;

if (temp == guess) {

return temp;

} else {

System.out.println(“the newton computation –” + temp);

return sqrt(n, temp);

}

}

return 0;

}

同样也可以使用二分法来实现求解,代码如下:

public static double bisectionSqrt(double n, double min, double max) {

if (n > 0) {

double mid = (min + max) / 2;

double temp = mid * mid;

if (Math.abs(n - temp) <= 0.000000001) {

return mid;

} else if (temp > n) {

max = mid - 1;

System.out.println(“the bisection computation –” + mid);

return bisectionSqrt(n, min, max);

} else if (temp < n) {

min = mid + 1;

System.out.println(“the bisection computation –” + mid);

return bisectionSqrt(n, min, max);

}

}

return 0;

}

牛顿法在解决问题的效率上远远大于二分法:

public static void main(String args[]) {

System.out.println(sqrt(3, 2));

System.out.println(bisectionSqrt(3, 0, 3));

}

计算结果为:

the newton computation –1.75

the newton computation –1.7321428571428572

the newton computation –1.7320508100147274

the newton computation –1.7320508075688772

1.7320508075688772

the bisection computation –1.5

the bisection computation –2.75

the bisection computation –2.125

the bisection computation –1.8125

the bisection computation –1.65625

the bisection computation –1.734375

the bisection computation –1.6953125

the bisection computation –1.71484375

the bisection computation –1.724609375

the bisection computation –1.7294921875

the bisection computation –1.73193359375

the bisection computation –1.733154296875

the bisection computation –1.7325439453125

the bisection computation –1.73223876953125

the bisection computation –1.732086181640625

the bisection computation –1.7320098876953125

the bisection computation –1.7320480346679688

the bisection computation –1.7320671081542969

the bisection computation –1.7320575714111328

the bisection computation –1.7320528030395508

the bisection computation –1.7320504188537598

the bisection computation –1.7320516109466553

the bisection computation –1.7320510149002075

the bisection computation –1.7320507168769836

the bisection computation –1.7320508658885956

the bisection computation –1.7320507913827896

the bisection computation –1.7320508286356926

the bisection computation –1.732050810009241

the bisection computation –1.7320508006960154

the bisection computation –1.7320508053526282

1.7320508076809347

1.Goal of the course;what is computation;introduction to data types,operators,and variables
what is knowledge?
I can divide knowledge into at least two categories.
陈述性知识和程序性知识
are declarative and imperative knowledge.
任何可以合法使用值的地方都可以使用变量
So,any place it’s legal to use the value.

2.Operators and operands statements;branching,conditionals,and iteration
分支程序就是一个能基于一些测试来改变指令顺序的程序
a branching program is something that can change the order of instructions based on some test

3.Common code patterns:iterative programs
在写每个循环程序的时候确保他们总是能终结,第二件要做的事情就是要确保程序返回了正确的答案
you’d like to be able to assrue yourself that they will always terminate,and then the second thing you’d like to do,is to assure yourself that it does give you back a reasonable answer.
4.Decomposition and abstraction through functions;introcuction to recursion
函数的关键是它要提供分解和抽象
the key of the function is that it’s going to provide both of these.
将代码分解为模块
it’s going to let us break up into modules.
忽略细节
suppress detail.
一种创建原语的思考方式,我们将引用这些原语,这就是继承
it is to create new primitives.and i’m going to put those in quotes,it’s a generalization.
函数的目的就是寻找计算的共同模式
The idea of a function is,that i’m going to capture a common pattern of computation.

这些本地绑定并不影响全局绑定
These local bingdings do not affect any global bindings.

递归的概念就是我将把一个问题进行分解成一个更简单的同类问题以解决我可以解决的小步骤
The idea of recursion is that I’m going to take a problem and break it down into a simpler version of the same problem plus some steps

Fibonacci
Pairs(0) = 1;
Pairs(1) = 1;
Pairs(n) = Pairs(n-1) + Pairs(n-2);

5.Floating point numbers,successive refinement,finding roots
当我们表达一些数字的时候尾数位于1和2之间,严格的小于2
when we represent something,the mantissa is between one and two.Strictly less than two.
而指数在-1022到+1023之间
The exponent,is in the range,-1022 to +1023
因此我们表达的数字可以从正负10到正负308th
So this lets us represent numbers up to about 10 to the 308th,plus or minus to the 308th,plus or minus.
现代计算机语言是64位的
the words today in a modern computer are 64 bits
我们设立1位以存储符号这个数字是整数还是负数然后11字节存储指数剩下的52个字节存放尾数(小数)
we get one bit for the sign is it a positive or negative number 11 for the exponent,and that leaves 52 for the mantissa

有些10进制的数如1/10 ,在转变为二进制的时候会无限循环下去

打印十进制数字的近似二进制数
So on most computers,if you were to print the decimal value of the binary approximation

repr()函数将数字以字符串表达.
对于浮点数 计算机截至第17位数
for floats,it rounds it to seventeen digits

warry about == on floats
每一次猜想都比前一次的更接近答案的方法,这就是逐次逼近法
that each guess is better than the previous guess
This is what’s called successive approximation
起始猜想,然后迭代
which would be the initial guess,you then iterate

Bisection method二分法
处理过程是对数级的
because I am getting logarithmically progressed

6.Bisection methods,Newton/Raphson,introduction to lists

我们实际上是在解方程式f:猜想数的平方减去x
we are looking a equation f of guess equals the guess squared minus x.

我们正需求方程式f=0的解.
and we trying to solving the equation that f of guess equals 0.Looking for the root of this equation.

sqrt(x);
F(guess) = guess^2 -x;

猜想切线(导数)
You take a guess and you find the tangent of that guess.

下一个猜想是切线与x的交点.
My next guess is going to be where the tangent crosses the x axis.

这里用到了导数的概念,
This is where derivatives come in.

我们都知道切点处切线的斜率跟函数在切点处的一阶导数是相同的,也就是dy/dx
What we know is that the slope of the tangent is given by the first derivative of the function f at the point of the guess.Which dy over dx.

guess(i+1) = guess(i) -F(guess(i))/2*guess(i);

可以将第i+1次猜想等于上一次猜想也就是第i次的减去第i次的猜测的结果值除以第i次猜想的本身值
we’ll know that we can choose guess i plus 1 to be equal to the old guess guess i,minus whatever the value is of the new guess–of the old rather the old guess– divided by twice the old guess.

从猜想数3开始求16平方根
F(3) = 9 -16 = -7;
guess(i+1) = 3 -(-7/6) = 4.1666

7.Lists and mutability,dictionaries,pseudocode,introduction to efficiency

order of grows
-choice of algorithm
-map problem into class of algorithms

8.Complexity; log,linear,quadratic,exponential algorithms

增长率,当问题的规模变大时,随之时间和空间的增长
Rate of growth as the size of the problem grows.
If it was,how much bigger does this get
大O符号,代表着当输入增加时也就是问题规模变大时对应的解决方法增长上限
Big Oh notation - is basically going to be an upper limit to the growth of a function as the input grow–as the input gets large.

a的b次方
ab = (a*a)(b/2) b even;
= a(a**(b-1)) b odd;
ef exp3(a,b):
if b==1:
return a;
if(b%2)2 == b:
return exp3(aa , b/2);
else: return aexp3(a,b-1);
b even t(b) = 6 + (b/2);
b odd t(b) = 6 + (b-1) = 12 + t((b-1)/2)

t(b) = 12 + (b/2);
=12+12+t(b/4)
=12k+t(b/2^k)

k=log2 b;
In the b even case, again i’m going to let t of b be the number of steps I want to go through.
if b is eqaul to 1,and then I’ve got to do the remainder(求余数),the multiplication,and the test,i’m up to four.

And then in the even case I’ve got to do a square(求平方) and the divide.
So i’ve got six steps
对数级,线性的,平方级,指数级算法
log,Linear ,quadratic,exponential algorithm

9.Binary search,bubble and selection sorts

但如果我们用的是保存列表的列表呢?如果列表存储的不同的东西 比如存储的是整数 字符串 浮点数 列表 列表的列表 列表的列表的列表 或者其他各种东西呢?
if i know that i have things stored in constant size.But what if i have a list of lists?What if i have a homogeneous list,a list of integers and strings and floats and lists and lists of lists and lists of lists of lists
标准的处理方法是使用链表
So in this case,one of the standard ways to use linked list
开始我们指向列表的开始
Start again,we’ll point to the beginning of the list.
在第一点,我们存下一个元素的地址偏移量,然后 用之后连续的几个单元表示第一个元素 如果你喜欢也可以说是第0个元素.在这里 我可能需要五个内存单元在下一个位置中 存放需要多大的内存偏移量跳转到下一个元素然后无论你想存放什么都可以放在接下来的单元中 可能只是些空格
在下一点可能我得存放一个很长的列表了

in the first spot,I am going to store something that says,here’s how far you have to jump to get to the next element.And then,I am going to use the next sequence of things to represent the first element,or the zero-th element,if you like.In this case I might need five.And then in the next spot,I am going to say how far you have to jump to get to the next element.All right,followed by whatever i need to represent it,which might only be a blank one.And in the next spot,maybe I’ve got a really long list

here is the problem.How do i get to the nth er,the k’th element in the list,in this case?
Well i have to go to the zero-th element,and say OK,gee,to get to the next element,I’ve got to jump this here.And to get to the next element,I’ve got to jump to here,and to get to the next element,I’ve got to jump to here,until i get there.
primarily Lisp.
盒状指南针每个元素实际上由两部分组成这里我们颠倒了顺序 这里有指针指向内存包含实际值的地址 可能实际值也是一系列指针 这里还有指向实际指向下一个元素的指针
Python store list, it is called a box pointer diagram,what we really have for each element is two things.And i’ve actually just reversed the order here.we have a pointer to the location in memory that contains the actual value,which itself might be a bunch of pointers,and we have a pointer to the actual a pointer the value and we have a pointer

一次一个的比较遍历这些元素直到找到了它,这个复杂度是n
I am just going to take an unsorted list and search it,i cound do it in linear time,right?One at a time.Walk down the elements until i find it.That wound be order n.
另一种方法,先排序再搜索,需要花nlog n时间排序,然后花log n时间搜索
On the other hand,sort it first,and search.take n logn time to sort it,then i can search it in log n time.

amortize the cost.
Linear sort + search
kn nlog n + klog n

bubbule sort
我遍历一次列表 每次取两个值 确认最大的元素在后面一个
I’m walking along the list once,taking two things,and saying, make sure the biggest one is next.

所以无论最大的元素在列表的什么位置 跑完了一遍 它总是在最下面 然后我回来再做一次,下一个最大元素又能跑到倒数第二的位置.
So wherever the largest element started out in the list,by the time i get through it,it’s at the end.And then i go back and i start again,and i do the same thing.The next largest element has to end up in the second last spot.

divide and conquer algorithm
分而治之

10. Divide and conquer methods,merge sort,exceptions

merge sort

所以我在树的每个层次都要做O(n)的操作,因为在每一层 我都是把问题分解成两半,以n开始 然后是n/2 n/4 n/8 所以我log n遍的n次操作
have order n operations at each level in the tree.And then we have Log n level,Beacause at each stage i cute problem in half.So i start off with n then it’s n over two n over four n over eight.So i have n operations log n times, n log n

hashing
Trade space for time 用空间换时间

11. Testing and Debugging

validation
progress to uncover problem and increase confidence.
我们需要一种不会我们这种无保证的自信的方法
So we need to have a method not designed to give us unwarranted confidence.

是两件事情的组合 测试和推理
It’s typically a combination of two things.Testing and reasoning.
测试就是 我们输入一些信息并且运行我们的程序 然后查看答案
Testing we run our program on some set of inputs.And check the answers,and say yeah

debugging
这其实是一个查明为什么程序不运行或者不按期待运行的过程
And that’s basically the process of ascertaining why the program is not working.

Defensive programming.防卫性程序设计

And that’s basically writing your programs in such a way that it will facilitate both validation and dubugging.

实验必须有做什么的能力才能被称为一个有效的科学实验呢?
what must this experiment have the potential to do,to be a valid scientific experiment?
实验必须有反驳我们假设的可能
It must have the potential to refute the hypothesis.

12. More about debugging,knapsack problem,introduction to dynamic programming

first,keep in mind that the bug is probably not where you think it is.

simple things you can care:

自变量顺序错误
Reversed order of arguments.

忘记初始化
Initialization.

对象与值相等
Object versus value equality.

别名
Aliasing deep vs shallow capy.

Keep record of what you tried.

Think about reconsidering your assumptions.

Bin packing

sequence alignment

Knapsack problem 背包问题

Continuous problem 连续问题
4/bs Au dust
3/bs Ag dust
10/bs Raisins

function is cost value of gold times how many pounds of gold.Plus the cost of silver times however many pounds of silver.Plus cost of raisins times the number of pounds of raisins.
maximize the function Cg PG + Cs PS + Cr * PR

the constraint is PG + PS + PR <=8
Greedy algorithm
at every step you do what maximizes your value at that step.So there’s no planning ahead.You just do what is ever best.

Locally optinal not always lead to global optimums.

zero-one knapsack problem 0/1 背包问题
exhaustive enumeration 穷举法

E(n ,i = 1) W i X i <= C

Dynamic programming

有重叠子问题且被称为最理想子结构的情况
there are overlapping sub-problems and what’s called optimal substructrue.

redundant computation 累赘计算

13.Dynamic programming: overlapping subproblems,optimal substructure

Overlapping subproblems 重叠子问题
Memoization
我们在第一次计算一个值后就记录一个值.然后在后续问题中使用这个值.
we record a value the first time it’s computed,then look it up the subsequent times we need it.

这就是动态编程这种通用技术的核心
And this is what lies at the heart of this very general technique called dynamic programming.

实际上 它也是很多保存结果的计算技巧的核心
And in fact,it lies at the heart of a lot of useful computational techniques where we save results.

Decision Tree 决策树
Back track

14.Analysis of knapsack problem,introduction to object-oriented programming

Size of solution
运行时间与装进背包的物品数目有关
how long it takes to run is related to how many items i end up being able to fit into the knapsack.
要记住的物品数量是和我能在背包中装多少东西有关
So the number of items i have to remember is related to how many items i can fit in the Knapsack.

这里有的是伪多项式算法
so we’d much rather define big O in terms of the inputs.

通常我们查看计算复杂度O的时候 我们会把它定义为实现输入的代码的大小
computational complexity,big O,what we’ll define the in terms of,is the size of the coding of the input.
size of coding of input

Pseudo polynomial algorithm 伪多项式

polynomial in the numeric value of input

1.动态编程中,我们是在用空间换时间
In dynamic programming, one of the things that’s going on is we’re trading time for space.

2. 不要被指数型问题吓到
Two,don’t be intimidated by exponential problems.

3. 动态编程有广泛的应用,每当你在处理一个看上去有自然而然的递归算法的时候

Dynamic programming is broadly useful.Whenever you’re looking at a problem that seems to have a natural recursive solution,think about whether you can attact it with dynamic programming.

4. 减少问题 problem reduction

Module (modularity)
我想要说的是一种类型的模块当然这是因为我们关注的是程序的可组合性
what i want to be talking about is modules of one sort,and of course that’s because what we’re interested in is modularity.

模块是相识函数的集合
Now i think of a module as a collection of related functions.

我们将要通过圆点标记法来使用函数( . )
and we’re going to refer to the functions using dot notation.

一种特殊的模块,模块中包括了类或者它们本身就是类
a particular kind of module,and those are the modules that include classes or that are classes.

在这个问题上我们将要强调要在面向对象编程的环境中使用类
In this subject we’re going to emphasize using classes in the context of what’s called object-oriented programming.

data abstractions
Abstract data type

对象就是数据和函数的集合
An object is a collection of data and functions.
这里关键思想就是将函数和操作数据的函数绑在一起成为一个东西
The key idea here is to bind together the data and the functions that operate on that data as a single thing.

user defind types
数据与函数的结合是面向对象编程的核心
This combining of data and functions on that data is a very essence of object-oriented programming.

we also call it encapsulation 封装

消息传递 传递隐喻的消息
we talk about it in terms of message pass, a message passing metaphor.

one object can pass a message to another object and the receiving object responds by executing one of its methods on the object.

l.sort();
这个对象传递一个消息sort 这个消息让我们去找sort方案,然后应用到对象I
pass the object I the message sort,and that message says find the method sort,and apply it to the object I.

notion of an instance.
类是有相同特质对象的集合
A class is a collection of objects with characteristics in common.

and extend the language.

15.Abstract data types,classes and methods

Class ,a template for creating instances of an object.
类是创建对象实例的模板

浅意义上的相等和深意义上的相等
shallow equality and deep equality.

测试浅意义上的相等
The first thing is testing shallow equality.
它本质是说,对于给定的两个东西它们是不是指向同一个引用
is essentially saying,given 2 things,do they point to exactly the same referent?
看看这两个是否指向内存中的同一位置.
is saying,do these things point to exactly the same spot in memory.

建立不同的版本的这些东西的一个模板
that’s going to let us build versions of these things.

这里有一个奇怪的额外的名为self的变量
There’s this weird extra variable in there called self.

当我创建了一个实例我应该能够获得那些特性化这个实例的东西
When i create a instance,i have to be able to get access to the things that characterize that instance.
这里特性化这个实例的东西是内在的详细说明要做什么的参数
what characterizes an instance here,it’s the internal parameters that specify what is going on.

init –when we call it, create an instance
–use “self” to refer to that instance

init方法创建了一个指向这个实例的指针
Init create a pointer to the instance.

把self作为指向这个实例的指针传了进去
And then it needs to have access to that,so it calls it passing in self as the pointer to the instance.

init这个方法可以去访问内存中的这一块了 然后在这块内存里面
it says it has access to that piece in memory,and now inside of that piece of memory

self will always point to the particular instance.
same other programming languages do not provide that pointer.

Methods - can access values of the specific instance.

Data hiding
一个人仅仅可以通过定义好的方法来访问实例变量

• one can only access instance values through defined methods.

python doesnot do this

str - printed representation,it converts things into a string type.代表打印,将东西转为字符串格式.

cmp - doing comparisons.

Operate overloading

Instance (

• methods
• fields
  )
  attributes

与实例相关联的是方法和域,它们统称为实例的属性
associated with an instance,we have both methods and fields.these are both called attributes of the instance.

16.Encapsulation,inheritance,shadowing

class
是一种将数据聚集起来的数据,这是模块/抽象的概念,在这里都把它们当作了原语
just trying to cluster data together.And this is a notion of modularity slash abstraction,where i’m treating them as primitives.

类将会创建实例,也就是该结构的特例
Class is used to make instances,meaning particular versions,of that structure

当我们调用person类定义的时候,它就创建了一个实例
when we called the class definition,person,it create an instance,there it is.

把它想成是指向内存中一点的指针,然后我们所做的是初始化成员函数
Thinkd of it as a pointer to a spot in memory,and then what we do is,then we call,or find that init method.

初始化(init)成员函数
And the first argument self,points to the instance.

17.Computational models:random walk simulation

探索一些随机性
Dealing with & exploiting randomness

随机指标 它们包含了一些随机性
Stochastic they incorporate randomness.

弄清数据的概念
Making sense of data

当我们在 再说一次 在对世界进行建模 我们发现里面有大量的数据
As we look at,again,modeling the world,what we discover,there’s a lot of data out there

评价答案的质量
Evalvating quality of answers

从简单的地方入手
Start Simple

也就是从一些对真实问题的简单估算开始
So start with some simple approximation to the real problem.

我会去假设 就像我们之前做的一样 我们有一个笛卡尔坐标系,玩家是站在一片像坐标纸一样的场地上
And I’m going to assume,as we’ve seen before,that we have Cartesian coordinates and that the player is standing on a field that has been cut to resemble a piece of graph paper.

只能选择四个方向中的一个:北 南 东或西
only go in one of four directions: north, south, east, or west.

然后对着一个方向迈出一步.不失去一般性
student is here and takes a step in one direction or another.without loss of generality

有四分之三的几率学生离出发点更远了
three times out of four you get further away.

模拟无规则运动
Simulate random walk

模拟 也就是我们去尝试着建立一个假扮成真实世界的模型然后模拟一些东西
Simulation where we try build the model that pretends it’s the real world and simulates what goes on,and a random walk.

来尝试着给你们做一个实例分析
Trying to give you a case study

开始去想象合适的抽象数据是什么
Thinking about what might be the appropriate data abstractions.

位置
Location

Compass point

Field

Drunk

罗经点的数据抽象来代表这个学生会朝北 南 东 西 四个方向走
compass point to capture the notion that the student is going north,south,east,or west.

把位置和方向的概念分离开了
separate the notion of direction

因此可以把它当作是一个完全的笛卡尔平面而这个人所处的位置就是平面上的一个点
So think of that as the whole Cartesian plain,as opposed to a point in the plane,which is what the location is.
因为全部问题是关于这个喝醉的人现在在哪儿的
since after all the whole problem talks about where the drunk is.

pseudo random

18.Presenting simulation results,Pylab,plotting

执行一个模拟实验的内循环
1) we start with an inner loop that simulates one trail.

然后我会把这个内循环”包”在执行恰当数量的实验的循环中
2)And then i’ll quoto,enclose,unquote the inner loop in another loop that conducts an appropriate number of trials.

计算实验的统计数据并将它们表示出来
3)Calculate and present some relevant statistics about the trials.

19.Biased random walks,distributions

有偏的随机漫步

Polymorphism 多态性

尝试创建一个代表性的场景
Generate a sample of representative scenarios.

因为穷举所有可能的洲是不大可能的
Because an exhaustive enumeration of all possible states would be impossible.

你可以穷举空间,然后看看它会得到什么结果
you can exhaustively enumerate the space and then see what’s going on.

Experimental device

I’m running an experiment designed to give me some information about the real world.

他们都是描述性的而非预测性的
they are typically descriptive not presciptive.

they describe a situation,they don’t tell you what the answer is.

模拟并不是一个最优化过程
a simulation is not an optimization procedure.When we looked at optimization,that was prescriptive.We ran an optimization algorithm,and it gives us the best possible solution.

20.Monte Carlo simulations,estimating pi

将模拟模型进行分类的不同途径
classify simulation models.
是随机还是确定性的问题
it’s stochastic or deterministic

静态还是动态
static vs dynamic time

第三个分歧就是离散和连续
A third dichotomy is discrete vs continuous.

21.Validating simulation results,curve fitting,linear regression
验证模拟结果,曲线拟合,线性回归

How many samples?
How accurate?
Biased sample

Data
Models that explain data
Consequences that follow from the models

Whenever we try and fit something,We need some sort of an objective function.

Least squares fit

进行最优化的方式,实际上还有更有效率的办法
It turns out that for this particular optimization,there’s something more efficient.

对这种问题有一个闭型解决方案
there is a closed form way of attacting this

线性回归
Linear regression

因变量y和自变量的关系是这些参数的线性函数
the relationship of the dependent variable y to the independent variables is assumed to be a linar function of the parameters.

R2 - coefficient of determination

R2 = 1 - EE/Dr

就是它通过模型中的变量去尝试获取因变量的比例
It’s attempting to capture the proportion of the response variation explained by the variables in the model.

所以你可以看到一部分值的改变是因为变量值的改变
So you’ll have some amount of variation that is explained by changing the values of the variables

我有一些预测数据 如果你愿意
So e e is going to be the errors in the estimation.

r2 = 0.9

基本上这些变量90%的改变都能靠这个模型来解释
approximately 90 percent of the variation in the variables can be explained by the model.

潜在变量
lurking variable

2d的变形:

-webkit-transform: matrix3d(1, 0, 0, 1);

这里的`(1, 0, 0, 1)是两个向量a(1,0) b(0,1),向量a是x轴方向上的,向量b是y轴方向上的.向量值的变化使得图形在方向和大小上有所改变.
`

3d的变形:

-webkit-transform: matrix3d(1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1);

这里的16个值描述了3个向量：

x轴方向 a(x1,x2,x3) y轴方向 b(y1,y2,y3) z轴方向 c(z1,z2,z3).

T行则重新定义了 x,y,z轴方向的对象(object)位置，即其在3d空间中的坐标.

W列则决定各个轴的透视效果(perspective-projection),它是我们沿着相关轴的视角(viewpoint).具体与齐次坐标(Homogeneous Coordinates)有关.

x

x

x

Wx

y

y

y

Wy

z

z

z

Wz

Tx

Ty

Tz

W



原文地址:http://www.eleqtriq.com/2010/05/css-3d-matrix-transformations/

Abstract 摘要

社会化网络构建了一个与现实社会对应的人际网络生态圈,但是基于web本身的缺陷,其给我们生活带来越来越多的问题.如信息泛滥,线上线下时间的平 衡,共同目标人群的聚合,社交对教育的影响等等.而语义网则是在传统web上加入关联数据等特性使得人工智能的网络成为可能,那么其可能在某些方面为社会 化网络的优化和发展起到积极作用.

Introduction 简介

本文主要由两大部分组成,一大部分是关于社会化网络的种种缺陷和问题,另一部分是关于如何利用语义网的概念来改善和弥补这些不足,而让其更加与现实社会关系密切并更方便地为人们服务.主要章节有:

1.社会化网络生态模型及缺陷

2.社会化网络中的心理学

3.社会化网络中的教育问题

4.为什么关联数据

5.人工智能的web能做什么

6.语义的社会化网络:智能的生态模型

社会化网络生态模型及缺陷

目前的社会化网络模型分为两种:强制双向连接模型和单双向任意连接模型,强制双向连接模型信息传递方式为双向互传,并且信息范围只存在于组内(或者说圈内).单双向任意连接模型则允许信息进行单向或双向传递,并且允许接收点进行信息传递,即传播扩散.

以上两种网络模型属于现实社会网络模型的部分实现,或者说其映射了现实社会网络的一部分,前者基于朋友或者好友的分享与互动这个个人社会活动,后者基于个人即时分享并传播这个生活中的例子(比如说演讲).

就单个个体所在网络来说,单个个体处于一个个体数量为n的集合里面,并且通过信息传递建立连接,信息单向传递的称为单向连接,双向传递称为双向连 接,单向连接数最大为:n(n-1)/2.而双向的最大连接数为:n(n-1).同时n趋向无穷大时,无论单双向连接Lim(n->∞) f(n) = n*n;

而最小传播连接数指在所有点都建立连接所需的最少连接,它有两种连接方式,一种是环连接,还有一种为发散状连接.其单向最小连接为n-1,而双向则为2(n-1).

因此,在一组存在完整连接的n个点中(不存在孤点),如果每一个点发出一条信息,在不同连接状态,其值与连接数f(n)相同.也就是说,在存在关联的社会化网络中,如果一个人际圈中有n个用户,每个用户共享一条信息,那么产生的有效信息数在n到n*n之间.

当一个个小型集合通过1到n个交叉个体产生关联,就形成了完善的社会化网络生态圈,并且假设信息通过这1到n个交叉个体进行发散,每组平均人数为m,传播次数为n,若m>=3,n>=1体系成立,单条信息进行发散,总传递接收次数约为 f(m,n)=m+m²+ … +mⁿ; 若信息传播模式为双向则接收次数约为 f(m,n)=2m+2m²+ … +2*mⁿ;

并且由此可以得出,当连接为双向时：

传播起始点，接收重复信息(m-1)次,传播重复信息0次.

中间点接收重复信息(m+1)次,传播重复信息(m-1)次.

边界点(末端)接收重复信息0次,传播重复信息0次.

总传播重复次数约为: f(n) = m² + m³ + … +mⁿ;(n>=2),

在一组有连接的点中,一条信息被传递,传播次数介于m+ m²+ …+mⁿ 与m+ 2m²+ …+ 2mⁿ之间(m>=3,n>=1)

现在的社会化网络模型只是完成了信息的分享与传播,其对使用者之间的关系的定义是不确切的，对不同年龄和角色的使用者的帮助是有限的，对共同目标或 兴趣的用户聚合是不完善的,它是现实社会网络的子集，所以存在许许多多的缺陷,并且对信息本身的考虑也非常少,以至于使用者本身一直处于被动接受状态,对 信息传播带来的问题无法应对.所以目前的网络最迫切的是将用户最需要的信息第一时间送达,并且为用户屏蔽无效信息.并且一个理想的状态是,网络本身开始习 惯用户的喜好和特点,并进行按需呈现信息.

在Javascript高级程序设计中有讲到使用动态原型(dynamic prototyping)来构建对象,其有讲到原型的赋值在判断语句里面不可行,但是其却没有讲根本原因

function Polygon(iSides) {
this.sides = iSides;
if (typeof Polygon._initialized == “undefined”) {
Polygon.prototype.getArea = function () {
return 0;
};
Polygon._initialized = true;
}
}
function Triangle(iBase, iHeight) {
Polygon.call(this, 3);
this.base = iBase;
this.height = iHeight;
if (typeof Triangle._initialized == “undefined”) {
Triangle.prototype = new Polygon();
Triangle.prototype.getArea = function () {
return 0.5 this.base this.height;
};
Triangle._initialized = true;
}
}

其有讲到原因:

The previous code illustrates both Polygon and Triangle defined using dynamic prototyping. The mistake is in the highlighted line, where Triangle.prototype is set. Logically, this is the correct location;
but functionally, it doesn’t work. Technically, by the time that code is run, the object is already instantiated and tied to the original prototype object. Although changes to that prototype object are reflected properly with very late binding, replacing the prototype object has no effect on that object. Only future object instances reflect the change, making the first instance incorrect.

这表明prototype对象是在代码执行之前进行实例化的,有文章说是在解析期进行实例化的,但是个人比较奇怪的是为什么在调用两次才真正让原型赋值成功:

var temp1 = new Triangle(2,3);
var temp2 = new Triangle(4,5);
alert(temp2.getArea());

In javascript, the inheritance method is so different with java,and some note here is to summary it.

Methods of inheritance
As usual with ECMAScript, you have more than one way to implement inheritance. This is because inheritance in JavaScript isn’t explicit; it’s emulated. This means that the interpreter doesn’t handle all the inheritance details. It is up to you, as the developer, to handle inheritance in a way that is most appropriate for your situation.

Object masquerading

function ClassA(sColor) {
this.color = sColor;
this.sayColor = function () {
alert(this.color);
};
}

function ClassB(sColor) {
this.newMethod = ClassA;
this.newMethod(sColor);
delete this.newMethod;
}

function ClassB(sColor, sName) {
this.newMethod = ClassA;
this.newMethod(sColor);
delete this.newMethod;
this.name = sName;
this.sayName = function () {
alert(this.name);
};
}

the this keyword references the currently created object in a constructor; in a method,however, this points to the owning object. The theory is that treating ClassA as a regular function instead of as a constructor establishes a type of inheritance.

but in java,the inheritance is extend the ancestors’ all method.it looks like:

public class A{

…

}

public class B extends A{

…

}

and then we can use call() to replace the inheritance:

function ClassB(sColor, sName) {
ClassA.call(this, sColor);
this.name = sName;
this.sayName = function () {
alert(this.name);
};
}

also apply() can use to reach this effect:

function ClassB(sColor, sName) {
ClassA.apply(this, new Array(sColor));
this.name = sName;
this.sayName = function () {
alert(this.name);
};
}

But i have a question,why javascript use call and apply to simulate object inheritance.And also why not make a extends pattern and it will looks like:

function ClassB extends ClassA(sColor, sName) {
this.name = sName;
this.sayName = function () {
alert(this.name);
};
}

9.7 ‘display’,’position’和’float’间的相互关系 Relationships between ‘display’, ‘position’, and ‘float’

影响盒子的生成和布局的三个属性——‘display’,’position’和’float’——间的相互关系如下:

1. 如果’display’值为’none’,那么’position’和’float’无效,元素不生成盒子.
2. 否则,如果’postion’值为’absolute’或者’fixed’,盒子绝对地定位’float’计算的值为’none’,并且 display根据下面的表格进行设定.盒子的位置由’top’, ‘right’, ‘bottom’和’left’属性和包含块决定.
3. 否则,如果’float’的值不是’none’,该盒子是浮动的,且’display’值根据下面的表格进行设定.
4. 否则,如果元素是根元素,’display’值根据下面的表格进行设定,除了其在CSS2.1里面没有定义是否’list-item’的指定值成为’block’或者’list-item’计算值.
5. 否则,应用指定的其它’display’属性.
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   

   指定值 Specified value	计算值 Computed value
   inline-table	table
   inline, table-row-group, table-column, table-column-group, table-header-group, table-footer-group, table-row, table-cell, table-caption, inline-block	block
   others	same as specified

9.8 常规流向，浮动和绝对定位的对比 Comparison of normal flow, floats, and absolute positioning

为了演示常规流向，相对定位，浮动和绝对定位间的区别，我们提供一系列的例子，它们都基于如下的HTML片段:

<!DOCTYPE HTML PUBLIC “-//W3C//DTD HTML 4.0//EN”>
<HTML>
<HEAD>
<TITLE>Comparison of positioning schemes</TITLE>
</HEAD>
<BODY>
<P>Beginning of body contents.
<SPAN id=”outer”> Start of outer contents.
<SPAN id=”inner”> Inner contents.</SPAN>
End of outer contents.</SPAN>
End of body contents.
</P>
</BODY>
</HTML>

在文档中，我们假定有如下规则:

body { display: block; font-size:12px; line-height: 200%;
width: 400px; height: 400px; }
p { display: block;}
span { display: inline; }

9.8.1 常规流向 Normal flow

考虑如下的outer和inner的CSS声明，它们并不改变常规流盒子:

#outer { color: red; }

#inner { color: blue; }

P元素包含所有的行内内容：匿名行内文本以及两个SPAN元素。因此所有的内容将在一个行内格式化内容中得到排列，包含在一个由P元素生成的包含块中，看起来如下图:

[D]

9.8.2 相对定位 Relative positioning

要看到相对定位的效果,我们规定:

#outer { position: relative; top: -12px; color: red; }

#inner { position: relative; top: 12px; color: blue; }

文本正常排列直到outer元素.outer的文本在第一行结尾排列到它的正常流向的位置和尺寸.然后包含文字行内盒(分三行排列)移动了’-12px’单位(向上).

inner的内容,作为outer的子元素,正常地应该紧接”of outer contents”排列(在第1.5行).不过,inner的内容自身相对outer内容偏移’12px’(向下),而回到它原来的位置第二行.

注意跟随在outer之后的内容并不受outer相对定位的影响.

[D]

还要注意,如果outer的偏移是’-24px’,那么outer的文本和主体文本会重合.

9.8.3 浮动一个盒 Floating a box

现在考虑浮动inner元素的效果,我们通过如下规则将它的文本向右浮动:

#outer { color: red; }

#inner { float: right; width: 130px; color: blue; }

文本正常排列直到inner盒,它从流向中脱离并浮动到右边距(它的’width’是显式指定的).浮动左边的行盒被缩短,文档的其余文本流入里面.

[D]

要显示’clear’属性的效果，我们在例子中加入一个同胞元素:

<!DOCTYPE HTML PUBLIC “-//W3C//DTD HTML 4.0//EN”>
<HTML>
<HEAD>
<TITLE>Comparison of positioning schemes II</TITLE>
</HEAD>
<BODY>
<P>Beginning of body contents.
<SPAN id=outer> Start of outer contents.
<SPAN id=inner> Inner contents.</SPAN>
<SPAN id=sibling> Sibling contents.</SPAN>
End of outer contents.</SPAN>
End of body contents.
</P>
</BODY>
</HTML>

和如下规则：

#inner { float: right; width: 130px; color: blue; }

#sibling { color: red; }

这就使inner盒和以前一样向右浮动，而文档的其余文本流入空出的地方：

[D]

但是,如果同胞元素的’clear’属性设置为’right’(即,生成的同胞盒不接受在右边有浮动盒相邻的位置),则同胞的内容在浮动之下开始排列:

#inner { float: right; width: 130px; color: blue; }

#sibling { clear: right; color: red; }

[D]

9.8.4 绝对定位 Absolute positioning

最后，我们考虑绝对定位的效果。考虑如下的outer和inner的CSS声明：

#outer {
position: absolute;
top: 200px; left: 200px;
width: 200px;
color: red;
}

#inner { color: blue; }

这就使outer盒的顶部的定位基于它的包含块。定位盒的包含块由最靠近的定位的父辈创建(或者，如果不存在这样的父辈，则采用初始包含块，就像在本例中)。outer盒的顶部在包含块顶部 ‘200px’之下，左边在包含块左边’200px’。outer盒的子盒的排列相对于outer盒正常排列。

[D]

下面的例子展示了一个相对定位盒子中的一个绝对定位的子盒。尽管outer父盒并没有实际偏移，设置它的’position’属性为’relative’ 意味着这个盒可以作为定位派生内容的包含块。由于outer盒是一个行内盒并跨越几行分布，第一个行内盒的顶和左边(在图形中用粗点线标出)作为 ‘top’和’left’偏移的参考.

#outer {
position: relative;
color: red;
}

#inner {
position: absolute;
top: 200px; left: -100px;
height: 130px; width: 130px;
color: blue;
}

结果可能看起来是这样的:

[D]

如果我们不定位outer盒：

#outer { color: red }

#inner {
position: absolute;
top: 200px; left: -100px;
height: 130px; width: 130px;
color: blue;
}

inner盒的包含块成为初始包含块(在我们的例子中).下面的例子展示了这种情况下.inner盒最终的位置.

[D]

相对和绝对定位可以用来实现变更栏，下例是这一实现的演示。考虑如下文档:

<P style=”position: relative; margin-right: 10px; left: 10px;”>
I used two red hyphens to serve as a change bar. They
will “float” to the left of the line containing THIS
<SPAN style=”position: absolute; top: auto; left: -1em; color: red;”>–</SPAN>
word.</P>

可能呈现为:

[D]

首先，该段落(包含块在图形中也显示出来)正常排列.然后它从包含块的左边偏移’10px’(从而为该偏移保留了’10px’的右边距).两个作为变更栏的连字号从常规流向中脱离，并定位在当前行(由于’top: auto’).相对它的包含块(由最终位置的P创建)的左边移动’-1em’.结果是变更栏看上去”浮动”在当前行的左边.

9.9 分层的呈现 Layered presentation

9.9.1 指定堆叠层次:’z-index’属性 Specifying the stack level: the ‘z-index’ property

‘z-index’
值： auto | <integer> | inherit
初始值： auto
适用于： 定位元素
可否继承： 否
百分比： N/A
媒介： 图形

对于一个定位盒，’z-index’属性指定了：

当前堆叠内容中盒的堆叠层次。
该盒子是否生成局部堆叠内容。
取值的含义如下：

<integer>
该整数是生成的盒在当前堆叠内容中的堆叠层次。该盒也生成了一个局部堆叠内容，在其中它的堆叠层次是’0’。
auto
生成的盒在当前堆叠内容中的堆叠层次和它的父盒相同。该盒不生成新的局部堆叠内容。

在该章节中,表达式”in front of”意思是更接近用户因为用户面对屏幕.

在CSS 2.1中,每个盒子在3个维度(dimensions)有个定位.除了水平和垂直的位置,盒子沿着”z-轴”展现并且被格式化成一个在其他的上面.当盒子在视觉上重叠了Z-轴定位特别地重要.这个章节谈论盒子怎样沿着z-轴定位.

渲染的树绘到canvas上的顺序描述是依照堆叠上下文.堆叠上下文能包含更深层的堆叠上下文.一个堆叠上下文从它的父级堆叠上下文的观点来看是原子的;在其它堆叠上下文的盒子可能不干涉它的任何盒子.

每个盒子属于一个堆叠上下文.每个定位的盒子在给出的堆叠上下文有一个整数的堆叠级别,堆叠级别是它在相同堆叠上下文里面z-轴相对于其它堆叠级别的位 置.有较大堆叠级别的盒子总是会被格式化在较低堆叠级别盒子的前面.盒子可以有负的堆叠级别.盒子在同样的堆叠上下文中有同样的堆叠级别根据文档树顺序由 后到前堆放.

根元素形成根堆叠上下文.其它由任意定位的元素生成(包含相对定位元素)的堆叠上下文有一个可计算的’z-index’值不同于’auto’.堆叠上下文不一定与包含块相关.在未来CSS的等级,其它属性可以引入堆叠上下文,例如‘opacity’[CSS3COLOR].

在每个堆叠上下文中,下面的层在从后到前的顺序中绘出:

1. background和元素的borders形成堆叠上下文.
2. 子堆叠上下文有负的堆叠级别(大多是负的在前面).
3. 流内,非行内级别,非定位的后代.
4. 非定位的浮动.
5. 流内,行内级别,非定位后代,包含inline tables和inline 块.
6. 堆叠级别为0的子堆叠上下文和堆叠级别为0的定位后代.
7. 子堆叠上下文有正的堆叠级别(最小的正数优先)
   在每个堆叠上下文,定位元素的堆叠级数为0(第6层),非定位浮动(第4层),内联块(5层),还有inline table(5层),被绘制好像那些元素本身生成新的堆叠上下文,除了它们定位的后代和任意将是子堆叠上下文参与当前的堆叠上下文.

该绘制顺序递归地应用到每个堆叠上下文.该堆叠上下文绘制顺序的描述构成附录E详细规范定义的概述.

在下面的例子中，各个盒（以它们的”id”属性命名）的堆叠层次是:
“text2”=0，”image”=1，”text3”=2，”text1”=3。”text2”的堆叠层次从它的根盒子继承而来。其它的由’z-index’属性指定。

<!DOCTYPE HTML PUBLIC “-//W3C//DTD HTML 4.0//EN”>
<HTML>
<HEAD>
<TITLE>Z-order positioning</TITLE>
<STYLE type=”text/css”>
.pile {
position: absolute;
left: 2in;
top: 2in;
width: 3in;
height: 3in;
}
</STYLE>
</HEAD>
<BODY>
<P>
<IMG id=”image”
src=”butterfly.gif” alt=”A butterfly image”
style=”z-index: 1”>

<DIV id=”text1”
style=”z-index: 3”>
This text will overlay the butterfly image.
</DIV>

<DIV id=”text2”>
This text will be beneath everything.
</DIV>

<DIV id=”text3”
style=”z-index: 2”>
This text will underlay text1, but overlay the butterfly image
</DIV>
</BODY>
</HTML>

本例演示了透明的概念。一个盒子的缺省行为是允许在它后面的盒子透过它内容中透明的区域而可见。本例中，每个盒子透明地覆盖它下面的盒子。这一行为可以通过使用某个现成的背景属性而被重写。

9.10 文本方向：’direction’及’unicode-bidi’属性

遵照用户端不支持双向文本可以忽略’direction’和’unicode-bidi’属性在该章节描述.该例外包括用户端简单地从右至左渲染字符.因为一个系统上的字体包含它们但是不支持从右到左文本方向的概念.

在某些脚本中，文字是从右到左书写的。某些文档中，特别是以阿拉伯或希伯来文写成的文档中，以及一些混合语言的内容中，单一(视觉上显示的)块中文字的排列也有不同的方向。这一现象称为双向排列或简称为“双向”。

Unicode标准([UNICODE],[UAX9]) 定义了一个复杂的算法来确定文字正确的方向。该算法包含了基于字符属性的隐式部分，以及对于嵌入和重写的显式控制。CSS2依赖这一算法来获得正确的双向 渲染。’direction’及’unicode-bidi’属性允许作者规定文档语言的元素和属性如何与该算法相匹配.

用户端支持双向文本必须应用Unicode双向算法到每个行内级别盒的序列且该序列不被强制(bidi class B) 中断或者块边界打断.这个序列在双向算法中形成”paragraph”(段落)单元.该段落嵌入级别通过包含块的‘direction’属性的值进行设置而不是通过Unicode算法在步骤P2和P3中给出的启发式heuristic来设置.

由于文字的方向性取决于文档语言的结构和语意，在大多数情况下，这些属性应该只由文档类型描述（DTD）的设计者或特殊文档的作者使用。如果一个缺 省样式表指定了这些属性，作者和用户不应该指定重写它们的规则。一个常见的例外可能是，如果一个用户端在用户的要求下将犹太语（通常以希伯来字母写成）音 译为拉 丁字母时，用户端重写了双向表现。

HTML 4.0规范（[HTML40]，8.2节）定义了HTML元素的双向排列行为。一致的HTML用户端可能在作者和用户的样式表里忽略 ‘direction’和’unicode-bidi’属性。在[HTML40]中指定的那些可能产生双向行为的规则出现在示例样式表中。HTML 4.0规范也包含了有关双向排列事项的更多的信息。

‘direction’
值： ltr | rtl | inherit
初始值： ltr
适用于： 所有元素，但参见描述
可否继承： 可
百分比： N/A
媒介： 图形

该属性指定了块的基本书写方向，以及Unicode双向算法中嵌入和超越的方向（参见’unicode-bidi’）。另外，它还规定了表格列布局的方向，水平溢出的方向，以及块设置了’text-align: justify’时，最后一个不完全的行的位置。

该属性取值的含义如下：

ltr
左到右的方向。
rtl
右到左的方向。
要使’direction’属性对行内元素有影响，’unicode-bidi’属性的值必须是’embed’或’override’。

注意.‘direction’属性指定给表格列元素时，并不被列内的单元格继承，这是因为列不存在于文档树中。因此，对于[HTML4]，11.3.2.1节中描述的”dir”属性的继承规则，CSS不可能很容易地保持.

‘unicode-bidi’
值： normal | embed | bidi-override | inherit
初始值： normal
适用于： 所有元素，但参见描述
可否继承： no
百分比： N/A
媒介： 图形

该属性取值的含义如下：

normal
基于双向算法，元素不打开一个额外的嵌入层次。对于行内元素，在元素的边界中隐含了重排列的工作。
embed
如果元素是行内的，基于双向算法，该值打开一个额外的嵌入层次。该嵌入层次的方向由’direction’属性给出。在元素内，重排列隐式地完成。这相当 于在元素的开头加入一个LRE（U+202A；对于’direction: ltr’）或RLE（U+202B；对于’direction: rtl’），在元素的结尾加入一个PDF（U+202C）。
bidi-override
如果元素是行内的，或者是只包含行内元素的块类元素，该值创建一个超越。这意味着在元素内，重排列严格按照’direction’属性的顺序；双向算法的 隐式部分被忽略。这相当于在元素的开头加入一个LRO（U+202D；对于’direction: ltr’）或RLO（U+202E；对于’direction: rtl’），在元素的结尾加入一个PDF（U+202C）。
每一个块类元素的字符的最终的顺序就如同：双向控制代码如上所述加入，标记被剥离，结果的字符顺序传递给用于普通文字的Unicode双向算法实现，该实 现产生和样式文本一样的分行。在这一处理中，非文字实体如图形被认为是中性字符，除非它们的’unicode-bidi’属性不是设置为 ‘normal’。在这一情况下，它们被认为是为该元素指定的’direction’中的重要字符。

请注意，为了能够在一个单一方向（要么全部左到右，要么全部右到左）中排列行内盒，必须创建更多的行内盒(包括匿名行内盒)，而且某些行内盒在排列之前，可能必须分割或重排。

由于Unicode算法限制嵌入的层次为15层，将’unicode-bidi’设置为非’normal’的使用，必须小心，除非确定是合适的。特别地， 使用’inherit’值时要特别小心。不过，对于那些一般来说显示为块的元素，更应该设置’unicode-bidi: embed’，这样在显示改变到行内时，可以将元素保持在一起（见下例）。

下面的例子显示了包含双向文字的一个XML文档。它演示了一个重要的设计原则：DTD设计者应该在语言语言（元素和属性）和任何相关联的样式表中考虑双向 因素。样式表的设计应该是双向规则和其它样式表规则分离。双向规则不应该被其它样式表规则超越，从而文档语言或DTD的双向行为得以保留。

例子：

本例中，小写字母表示左到右的字符而大写字母表示右到左的字符：

<HEBREW>
<PAR>HEBREW1 HEBREW2 english3 HEBREW4 HEBREW5</PAR>
<PAR>HEBREW6 <EMPH>HEBREW7</EMPH> HEBREW8</PAR>
</HEBREW>
<ENGLISH>
<PAR>english9 english10 english11 HEBREW12 HEBREW13</PAR>
<PAR>english14 english15 english16</PAR>
<PAR>english17 <HE-QUO>HEBREW18 english19 HEBREW20</HE-QUO></PAR>
</ENGLISH>

由于这是一个XML，样式表负责设置书写方向。样式表如下：

/ Rules for bidi /
HEBREW, HE-QUO {direction: rtl; unicode-bidi: embed}
ENGLISH {direction: ltr; unicode-bidi: embed}

/ Rules for presentation /
HEBREW, ENGLISH, PAR {display: block}
EMPH {font-weight: bold}

HEBREW元素是一个块，基本方向是右到左，ENGLISH元素是一个块，基本方向是左到右。PAR元素是块，基本方向从父元素继承。因此，前两个 PAR从右顶部开始阅读，最后的三个从左顶布开始阅读。请注意元素名选择HEBREW和ENGLISH只是为了明显表示而已；一般情况下，元素名应该反映 结构而不反映语言。

EMPH元素是行内元素，而且它的’unicode-bidi’设置为’normal’（初始值），它对文字的排列没有影响。另一方面，HE-QUO元素创建一个嵌入。

如果行宽足够的长，这些文字的格式化效果可能是：

5WERBEH 4WERBEH english3 2WERBEH 1WERBEH

8WERBEH 7WERBEH 6WERBEH

english9 english10 english11 13WERBEH 12WERBEH

english14 english15 english16

english17 20WERBEH english19 18WERBEH

注意，HE-QUO嵌入使HEBREW18出现在english19之右。

如果需要分行，可能效果是：

2WERBEH 1WERBEH
-EH 4WERBEH english3
5WERB

-EH 7WERBEH 6WERBEH
8WERB

english9 english10 en-
glish11 12WERBEH
13WERBEH

english14 english15
english16

english17 18WERBEH
20WERBEH english19

由于HEBREW18必须在english19前阅读，它在english19所在行的上面。仅仅是在前一格式化例子中分割长行不会有用。还要注意 english19的第一个音节可能可以放在上一行中。但是，为了避免在一行的中间出现一个连字符，在右到左的内容中，左到右单词的连字通常被禁止。反之 亦然。

工厂范式 Factory paradigm

function showColor() {
alert(this.color);
}
function createCar(sColor, iDoors, iMpg) {
var oTempCar = new Object;
oTempCar.color = sColor;
oTempCar.doors = iDoors;
oTempCar.mpg = iMpg;
oTempCar.showColor = showColor;
return oTempCar;
}
var oCar1 = createCar(“red”, 4, 23);
var oCar2 = createCar(“blue”, 3, 25);
oCar1.showColor(); //outputs “red”
oCar2.showColor(); //outputs “blue”

缺点:工厂方法只能创建一种对象,且对象属性固定.

构造器范式 Constructor paradigm

function Car(sColor, iDoors, iMpg) {
this.color = sColor;
this.doors = iDoors;
this.mpg = iMpg;
this.showColor = function () {
alert(this.color)
};
}
var oCar1 = new Car(“red”, 4, 23);
var oCar2 = new Car(“blue”, 3, 25);

When a constructor is called with the new operator, an object is created before the first line of the constructor is executed; that object is accessible (at that point) only by using this. It is then possible to assign properties directly to this that are returned as the function value by default (no need to explicitly use the return operator).

这句讲了为啥使用new关键字能使得对象属性可用.并且和java的类构造器很像:

public class Car{
public Car(String sColor, String iDoors, String iMpg) {
this.color = sColor;
this.doors = iDoors;
this.mpg = iMpg;
}
}

原型范式 Prototype paradigm

function Car() {
}
Car.prototype.color = “red”;
Car.prototype.doors = 4;
Car.prototype.mpg = 23;
Car.prototype.showColor = function () {
alert(this.color);
};
var oCar1 = new Car();
var oCar2 = new Car();

这里是javascript最烂的地方,为了使创建的对象实例能够像java一样可以使用对象的属性,其使用了prototype而不是像java一样使用get和set方法.并且java中的prototype模式用于克隆对象.

混合构造器原型范式 Hybrid constructor/prototype paradigm

function Car(sColor, iDoors, iMpg) {
this.color = sColor;
this.doors = iDoors;
this.mpg = iMpg;
this.drivers = new Array(“Mike”, “Sue”);
}
Car.prototype.showColor = function () {
alert(this.color);
};
var oCar1 = new Car(“red”, 4, 23);
var oCar2 = new Car(“blue”, 3, 25);
oCar1.drivers.push(“Matt”);
alert(oCar1.drivers); //outputs “Mike,Sue,Matt”
alert(oCar2.drivers); //outputs “Mike,Sue”

同样非常烂的一个设计,为了让属性赋值和方法声明分开.说明如下:
All the nonfunction properties are defined in the constructor, meaning that once again it is possible to assign default values by passing arguments into the constructor. Only one instance of the showColor() function is being created, so there is no wasted memory.

动态原型范式 Dynamic prototype method

function Car(sColor, iDoors, iMpg) {
this.color = sColor;
this.doors = iDoors;
this.mpg = iMpg;
this.drivers = new Array(“Mike”, “Sue”);
if (typeof Car._initialized == “undefined”) {
Car.prototype.showColor = function () {
alert(this.color);
};
Car._initialized = true;
}
}

为了使showColor方法只初始化一次.

混合工厂模式 Hybrid factory paradigm

function Car() {
var oTempCar = new Object;
oTempCar.color = “red”;
oTempCar.doors = 4;
oTempCar.mpg = 23;
oTempCar.showColor = function () {
alert(this.color)
};
return oTempCar;
}

var car = new Car();

这里研究的是社会化网络中的一些关系，并归纳了数学模型，具体分为单组信息传播模型和多组信息传播模型.

1.Single group information spread model 单组信息传播模型

这里的研究对象是一组点,并且其存在两种身份,传播者和接收者,在点与点之间存在两种连接关系,单向连接和双向连接.

问题:求解用户数为n的情况下的最大连接数f(n).

由,
f(1) = 0;
f(2) = 1;
f(3) = 3;
f(4) = 6;
f(5) = 10;
可以得出:
f(n) = f(n-1) + (n-1);
及:f(n) = f(n-2) + (n-2) + (n-1);
f(n) = f(n-3) + (n-3) + (n-2) + (n-1);
f(n) = f(1) +1+…+ (n-3) + (n-2) + (n-1);
f(n) = n(n-1)/2;

用同样的推倒方式可得出,最小传播连接数:
f(n) = n-1;

图示如下:

[caption id=”” align=”alignnone” width=”537”] 社会化个体关系图[/caption]

需要补充的是，这里的连接数指的是两点之间建立的通信连接,单向连接数最大为:n(n-1)/2.而双向的最大连接数为:n(n-1).同时n趋向无穷大时,无论单双向连接

lim(n->∞) f(n) = n*n;

而最小传播连接数指在所有点都建立连接所需的最少连接,它有两种连接方式,一种是环连接,还有一种为发散状连接.其单向最小连接为n-1,而双向则为2(n-1).

并且由以上的关系，可以得到一些推论:

在一组存在完整连接的n个点中(不存在孤点),如果每一个点共享一条信息,在不同连接状态,其值与连接数f(n)相同.也就是说,在存在关联的社会化网络中,如果一个人际圈中有n个用户,每个用户共享一条信息,那么产生的共享信息数值在n到n*n之间.

2.Multigroup information spread model 多组信息传播模型

在多组信息传播模型中,不同的组,通过一个或者多个点建立连接,然后信息通过建立的层级进行扩散,并且扩散因为连接方式的不同产生不同的信息重叠.

若发散传播组(树状结构如下图),假设每组平均人数为m,传播次数为n,若m>=3,n>=1体系成立,单条信息进行发散,总传递接收次数为 f(m,n)=(m-1)+ (m-1)²+ …+ (m-1)ⁿ;约为 f(m,n)=m+m²+ … +mⁿ;若信息传播模式为双向则 f(m,n)=2(m-1)+ 2(m-1)²+ …+ (m-1)ⁿ;,约为f(m,n)=2m+2m²+ … +2*mⁿ;

推导过程如下:

当信息传递模式为单向时,假设组内点数m为固定值3

则在第1次传播时,传递次数为2,即3-1,

在第2次传播时,传递次数为4,即(3-1)²,

在第3次传播时,传递次数为8,即(3-1)³,

所以总传递次数f(m,n)=(m-1)+ (m-1)²+ …+ (m-1)ⁿ;(m>=3,n>=1)

当信息传递模式为双向时,假设组内点数m为固定值3

则在第1次传播时,传递次数为2,即3-1,

在第2次传播时,传递次数为6,即(3-1)²+(3-1),

在第3次传播时,传递次数为12,即(3-1)³+(3-1)²,

所以总传递次数f(m,n)=2(m-1)+ 2(m-1)²+ …+ (m-1)ⁿ;(m>=3,n>=1)

注:最后一项没有2倍.

若组人数不定,每次传播会在下一级有若干次则传播接收次数为 f(m,n) = (m₀-1) + [(m₁₁-1) + (m₁₂-1)+ .. + (m_1n-1)]+ .. + [(m_N1-1) + (m_N2-1) + .. + (m_Nn-1)];

示意图如下:

[caption id=”” align=”alignnone” width=”417”] Multigroup information spread model 多组信息传播模型[/caption]

若每组中各个点之间信息传送关系都为双向,即边界点会成为组之间的连接点，假设每组平均人数为m,传播次数为n,若m>=3,n>=1体系成立,单条信息进行发散,传递接收次数为 f(m,n)=(m-1)+ 2(m-1)²+ …+ 2(m-1)ⁿ;

假设组内点数m为固定值3,则，

则在第1次传播时,传递次数为2,即3-1,

在第2次传播时,传递次数为6,即2*(3-1)²,

在第3次传播时,传递次数为12,即2*(3-1)³,

在第n次传播时,传递次数为12,即2*(3-1)ⁿ,

所以总传递次数 f(m,n)=(m-1)+ 2(m-1)²+ …+ 2(m-1)ⁿ;(m>=3,n>=1)

注:第一项没有2倍.

[caption id=”” align=”alignnone” width=”415”] Multigroup information spread model 多组信息传播模型[/caption]

并由此可以得出一些推论:

传播起始点，接收重复信息(m-1)次,传播重复信息0次.

中间点接收重复信息(m+1)次,传播重复信息(m-1)次.

边界点(末端)接收重复信息0次,传播重复信息0次.

总传播重复次数为: f(n) = (m-1)^2 + (m-1)^3 + … +(m-1)^n;(n>=2)

在一组有连接的点中,一条信息被传递,传播次数介于(m-1)+ (m-1)²+ …+ (m-1)ⁿ 与(m-1)+ 2(m-1)²+ …+ 2(m-1)ⁿ之间(m>=3,n>=1)