My note

计算笛卡尔积

Posted on 2016-12-20 In Algorithm

笛卡尔积又名直积，是所有可能的有序对组成的集合，其中有序对的第一个对象是X的成员，第二个对象是Y的成员。可以表示如下：

\[X\times Y={<x,y>|x\in X\land y\in Y}\]

例如，[[a,b],[1,2,3]]的笛卡尔积为[[a,1],[a,2],[a,3],[b,1],[b,2],[b,3]]

在实际应用中，笛卡尔积常用于在电商中生成商品的sku信息，将所有的属性组合起来。

当空间数量固定时，可以直接使用嵌套的循环来完成，例如上面的二元笛卡尔积：

let a = ['a','b']
let b = ['1','2','3']
let result = []
for(let i=0;i<a.length;i++){
    for(let j=0;j<b.length;j++){
        result.push([a[i],b[j]])
    }
}

output>>>

[ [ 'a', '1' ],
  [ 'a', '2' ],
  [ 'a', '3' ],
  [ 'b', '1' ],
  [ 'b', '2' ],
  [ 'b', '3' ] ]

推广到n元笛卡尔积：

\[ X_{1}\times X_{2}\times ...\times X_{n}={(x_{1},...,x_{n})|x_{1}\in X_{1}\land ...\land x_{n}in X_{n}}\]

for(let i=0;i<a.length;i++){
    for(let j=0;j<b.length;j++){
        for(){
            ...(n次循环)
        }
    }
}

当n不为固定数值的时候，不能以这种嵌套循环的方式表示。因此考虑使用嵌套

import copy
def combination(array):
    """
    :type array: List[][]
    :rtype: List[str]
    """
    result = []
    if len(array) is 0: return result
    def cartsianProduct(index,rs):
        if index is len(array):
            result.append(rs)
        else:
            for item in array[index]:
                next_rs = copy.copy(rs)
                next_rs.append(item)
                cartsianProduct(index+1,next_rs)
    cartsianProduct(0,[])
    return result
    
combination([['a','b'],['1','2','3']])

output>>>

1	[['a', '1'], ['a', '2'], ['a', '3'], ['b', '1'], ['b', '2'], ['b', '3']]

对于python来说，除了使用遍历之外也可以使用py自带的迭代器itertools:

import itertools
rs = []
for x in itertools.product(['a','b'],[1,2,3]):
    rs.append(x)

output>>>

1	[('a', 1), ('a', 2), ('a', 3), ('b', 1), ('b', 2), ('b', 3)]

Support Vector Regression

Posted on 2016-12-11 In Machine Learning

Intro quote from

“A Tutorial on Support Vector Regression”, Alex J. Smola, Bernhard Schölkopf - Statistics and Computing archive Volume 14 Issue 3, August 2004, p. 199-222

A support vector machine constructs a hyper-plane or set of hyper-planes in a high or infinite dimensional space, which can be used for classification, regression or other tasks. Intuitively, a good separation is achieved by the hyper-plane that has the largest distance to the nearest training data points of any class (so-called functional margin), since in general the larger the margin the lower the generalization error of the classifier.

Mathematical formulation

Given training vectors \(x_{i}\in \mathbb{R}^{p}\), i=1,..., n, and a vector \(y\in {1,-1}^{n}\),SVC solves the following primal problem:

\[\min \limits_{w,b,\zeta }\frac{1}{2}w^{T}w+C\sum_{i=1}^{n}\zeta _{i}\\ subject \to y_{i}(w^{T}\phi (x_{i}+b))\geq 1-\zeta _{i},\\ \zeta _{i}\geq 0,i=1,...,n\]

Its dual is

\[\min \limits_{a} \frac{1}{2}a^{T}Qa-e^{T}a\\ subject \to y^{T}a=0\\ 0\leq a_{i}\leq C,i=1,...,n\]

where 'e' is the vector of all ones,'C' > 0 is the upper bound,'Q' is an n by n positive semidefinite matrix,\(Q_{ij}\equiv y_{i}y_{j}K(x_{i},x_{j})\),where \(K(x_{i},x_{j})=\phi (x_{i})^{T}\phi (x_{j})\) is the kernel. Here training vectors are implicitly mapped into a higher (maybe infinite) dimensional space by the function \(\phi\).

The decision function is:

\(sgn(\sum_{i=1}^{n}y_{i}a_{i}K(x_{i},x)+\rho )\)

These parameters can be accessed through the members dual_coef_ which holds the difference , support_vectors_ which holds the support vectors, and intercept_ which holds the independent term

Key to ‘JavaScript Puzzlers'(3)

Posted on 2016-11-30 In Algorithm

4.What is the result of this expression? (or multiple ones)

var END = Math.pow(2, 53);
var START = END - 100;
var count = 0;
for (var i = START; i <= END; i++) {
    count++;
}
console.log(count);

A 0

B 100

C 101

D other

Correct answer is D.2⁵³ is the largest number in javascript,so that i never become lager than START.This code will cause infinite loop.

5.What is the result of this expression? (or multiple ones)

1
2
3

var ary = [0,1,2];
ary[10] = 10;
ary.filter(function(x) { return x === undefined;});

A [undefined x 7]

B [0,1,2,10]

C []

D [undefined]

C is correct answer.The ary looks like [0,1,2,undefined x 7,10] , but in fact array.prototype.filter() ignore undefined element.So it returned [] > See more information about array.prototype.filter()

6.What is the result of this expression? (or multiple ones)

var two   = 0.2
var one   = 0.1
var eight = 0.8
var six   = 0.6
[two - one == one, eight - six == two]

A [true,true]

B [false,false]

C [true,false]

D other

Is C.

Javascript hasn't ability of precise calculation,so that float number will be calculated in a imprecise mode.

> 0.8-0.6 = 0.20000000000000007

Specially, 0.2-0.1 = 0.1

7.What is the result of this expression? (or multiple ones)

function showCase2(value) {
    switch(value) {
    case 'A':
        console.log('Case A');
        break;
    case 'B':
        console.log('Case B');
        break;
    case undefined:
        console.log('undefined');
        break;
    default:
        console.log('Do not know!');
    }
}
showCase2(String('A'));

A Case A

B Case B

C Do not know!

D undefined

swith() method uses '===' to judge condition,new String(A) construct a new string object,

new String('a') == 'a' but new String('a') !== 'a'.

So this question's answer is C

let a = new String("b")

typeof a === 'object'

8.What is the result of this expression? (or multiple ones)

function showCase2(value) {
    switch(value) {
    case 'A':
        console.log('Case A');
        break;
    case 'B':
        console.log('Case B');
        break;
    case undefined:
        console.log('undefined');
        break;
    default:
        console.log('Do not know!');
    }
}
showCase2(String('A'));

A Case A

B Case B

C Do not know!

D undefined

Correct is A.

String('A') === 'A'

let a = String('b')

typeof a === 'string'

Key to 'JavaScript Puzzlers'(2)

Posted on 2016-11-28 In Front End

Continue.

3.What is the result of this expression? (or multiple ones)

1	[ [3,2,1].reduce(Math.pow), [].reduce(Math.pow) ]

A an error

B [9,0]

C [9,NaN]

D [9,undefined]

See more information about Array.prototype.reduce()> The reduce() method applies a function against an accumulator and each value of the array (from left-to-right) to reduce it to a single value.

reduce() accept 2 arguments:reduce(callback,initialValue),this callback function will get 4 arguments:

callback(accumulator,currentValue,currentIndex,array) > accumulator > > The accumulated value previously returned in the last invocation of the callback, or initialValue, if supplied. (See below.) > > currentValue > > The current element being processed in the array. > > currentIndex > > The index of the current element being processed in the array. Starts at index 0, if an initialValue is provided, and at index 1 otherwise. > > array > > The array reduce was called upon.

For example,use

1
2
3

[1,2,3,4,5].reduce(function(a,b){
    return a+b
})

It returned 15.

First callback function got (1,2) returned 3,then the 2nd callback function got (3,3) returned 6.The 3rd callback got (6,4) returned 10,the 4st callback got (10,5) returned 15,the finally result.

Math.pow() will calculate power value.It accept 2 arguments,like Math.pow(base,exponent)

It's equal to base^exponent

In this problem,[1,2,3].reduce(Math.pow) means that:

step1: Math.pow got (1,2) returned 1

step2: Math.pow got (1,3) returned 1

Finally it got 1.

But the 2nd array's item is []

reduce() method need an intial value at least,so it will throw an error:

TypeError: Reduce of empty array with no initial value

So this problem's correct answer is A

4.What is the result of this expression? (or multiple ones)

1 2	var val = 'smtg'; console.log('Value is ' + (val === 'smtg') ? 'Something' : 'Nothing');

A Value is Something

B Value is Nothing

C NaN

D Other

This is a trick question.The correct is D

The operator '+' will calculate first because it has higher precedence.

That expression equal to

1	console.log('Value is true'? 'Something':'Nothing');

An string expression like 'true' in condition,So it will print 'Something'

5.What is the result of this expression? (or multiple ones)

var name = 'World!';
(function () {
    if (typeof name === 'undefined') {
        var name = 'Jack';
        console.log('Goodbye ' + name);
    } else {
        console.log('Hello ' + name);
    }
})();

A Goodbye Jack

B Hello Jack

C Hello undefined

D Hello World

This a question about "Hoisting".The 'var' will hoisting in the function scope.

So the code will be this:

var name = 'World!';
(function () {
    var name
    if (typeof name === 'undefined') {
        name = 'Jack';
        console.log('Goodbye ' + name);
    } else {
        console.log('Hello ' + name);
    }
})();

For if (typeof name === 'undefined'),it will find name from scope chain,so this 'name' is declared in anonymous function: var name

'var name' means that name is undefined,so condition of 'if' is true,then name is declared 'Jack'.

Hence,printed 'Goodbye Jack'

See more information about Hoisting

Do rest tomorrow

Key to 'JavaScript Puzzlers'(1)

Posted on 2016-11-27 In Front End

Make a tool:convert algebraic expression to functional expression(2)

Posted on 2016-11-09 In Algorithm

I got the data structure of stack and binary tree in last article,and finally I got a stack what can describe algebraic expression clearly.Now I can create a expression tree with this stack.

Create the expression tree

This expression tree is a binary tree because each function has 2 arguments commonly.So there are 3 things to describe an algebraic:operator,1st operand(orginal) and 2nd operand.I set binary tree node's left child is the 1st operand,right child is the 2nd operand and its value is the operator.

For example,1+2 is writen

1
2
3

  +
 / \
1   2

Before create the expression tree,I have to deal with the stack I got before.Because that stack is a reverse array to describe the algebraic expression.

Reverse stack

1 2	stack = Stack() while origin.length() is not 0: stack.push(origin.pop())

Um..that's all.

And create an empty stack to store the operands temporarily while pop this stack.

Create expression tree and assign elements

while stack.length() is not 0:
    if stack.getTop() in operators:
        node = BiTree(stack.pop())
        node.right = temp.pop()
        node.left = temp.pop()
    else:
        node = BiTree(stack.pop())
    temp.push(node)
return temp.pop()

By this way,I get the correct expression tree.

For example,I input "A+b-x*(12.13+51^y)1.4121" before,now I get a binary tree:

  +
 / \
A   -
   / \
  b   *
     / \
    +   ^
       / \
      +  1.4121
     / \
   51   y

Traverse the binary tree and create functional expression

This is an iterative process.I convert each child node into a functional expression,such as

1
2
3

  +
 / \
1   2

will change to add(1,2)

And put this functional expression as its parent node's child,and loop again and again,until only one node left.

operators_name = {'+':'add','-':'mius','*':'muilt','/':'divide','^':'power'}
#create_function_expression
def cfe(Tree):
    if Tree.value in operators_name:
        Tree.value = operators_name[Tree.value] +'('+ cfe(Tree.left) +','+ cfe(Tree.right) +')'
    return Tree.value

Test it,input "A+b-x*(12.13+51^y)1.4121" and this script ouput add(A,mius(b,muilt(x,power(add(12.13,power(51,y)),1.4121))))

All script have been uploaded to Github:

https://github.com/lsvih/algebraic-expression-to-function

Make a tool:convert algebraic expression to functional expression(1)

Posted on 2016-11-07 In Algorithm

Introduction

My colleague,Tu is writing a programme for calculation of money in bank.Those algebraic expression are complicated.And he write program with Java.So when he is writing functional expression in Java,he is confusion because there are too much functions and brackets.

To save him in brackets' sea,I plan to make an tool to convert algebraic expression to functional expression.

I will use Python to do that.

First,I consider commonly operators are functions have 2 arguments,so I can construct binary tree to store algebraic expression.

Second,it is likely that many brackets in expression.So I consider using stack to deal those brackets.

Review:

Data structure of stack

class Stack:
    def __init__(self):
        self.items = []

    def is_empty(self):
        return len(self.items)==0

    def push(self,item):
        self.items.append(item)

    def pop(self):
        if not self.is_empty():
            return self.items.pop()

    def getTop(self):
        if not self.is_empty():
            return self.items[len(self.items)-1]

    def length(self):
        return len(self.items)

    def clear(self):
        self.__init__()

Data structrue of binary tree

class BiTree:
    def __init__(self, value=None, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

    def clear(self):
        self.__init__()

    def is_empty(self):
        return self.value is None

    def depth(self,node):
        if node.value is None or node is None:
            return 0
        else:
            l_length = self.depth(node.left)
            r_length = self.depth(node.right)
            if l_length&gt;=r_length:
                return l_length+1
            else:
                return r_length+1

    def value(self):
        return self.value

    def per_order_traverse(self, node):
        if node is None or node.value is None:
            return
        print node.value
        self.per_order_traverse(node.left)
        self.per_order_traverse(node.right)

    def in_order_traverse(self, node):
        if node is None or node.value is None:
            return
        self.in_order_traverse(node.left)
        print node.value
        self.in_order_traverse(node.right)

    def post_order_traverse(self, node):
        if node is None or node.value is None:
            return
        self.post_order_traverse(node.left)
        self.post_order_traverse(node.right)
        print node.value

(It is not good to put those additional function in data structrue.lol)

Covert algebraic expression to binary tree

This binary tree describes the whole computational procedure so it always called expression tree.

To get more information about expression tree,visite CS1112 in The George Washington University：

https://www.seas.gwu.edu/~mtdiab/Courses/CS1112/lectures/module10/module10Supp.html

(1)Break expression

Un,when I got an algebraic expression like "x+(y-31)^1.4+10*N",I will break it into an list at first.

Like this:

Exp = "A+b-x*(12.13+51^y)^1.4121"
operators = {'(':0,')':0,'+':1,'-':1,'*':2,'/':2,'^':3}
for op in operators:
    Exp = Exp.replace(op,'|'+op+'|')
Exp = Exp.split('|')

out print ['A', '+', 'b', '-', 'x', '*', '', '(', '12.13', '+', '51', '^', 'y', ')', '', '^', '1.4121']

there some unexpected elem "" in this list,filter it!

1	Exp = [item for item in Exp if not item is ""]

Finally I got ['A', '+', 'b', '-', 'x', '*', '(', '12.13', '+', '51', '^', 'y', ')', '^', '1.4121']

Ps:I find that it is difficult to consider the situation when expression has negative item....

TODO:consider the negative item!

(2)Consider those brackets

Brackets will change the step of calculate,so I have to cope them before constructing expression tree.

I set an empty stack,when I meet "(" in expression,I will push this bracket and elems behind it into stack.When i meet ")" in expression,I will pop stack's elems until the next "(" is out from stack.

By this way,I will get an correct order list of calculation whitout bracket.

def clear_brackets(exp):
    temp = Stack()
    result = Stack()
    for elem in exp:
        if elem not in operators:
            result.push(elem)
        else:
            if temp.length() is 0 or elem is '(':
                temp.push(elem)
            else:
                if elem is ')':
                    while temp.getTop() is not '(':
                        result.push(temp.pop())
                    temp.pop()
                elif operators[elem] < operators[temp.getTop()]:
                    while temp.length() is not 0:
                        if temp.getTop() is '(':
                            break
                        result.push(temp.pop())
                    temp.push(elem)
                else:
                    temp.push(elem)
    while temp.length() is not 0:
        result.push(temp.pop())
    return result

Ps:Must import stack class before:

1 2	from data import Stack from data import BiTree

test it!

input:

1
2
3

a = clear_brackets(Exp)
while a.length() is not 0:
    print a.pop()

output:

+
-
*
^
1.4121
+
^
y
51
12.13
x
b
A

Try to reduce it:

+
-
*
^
1.4121
+
^
y
51
12.13
x
b
A
===========
+
-
*
^
1.4121
+
51^y
12.13
x
b
A
==========
+
-
*
^
1.4121
12.13+51^y
x
b
A
==========
+
-
*
(12.13+51^y)^1.4121
x
b
A
==========
+
-
x*(12.13+51^y)^1.4121
b
A
==========
+
b-x*(12.13+51^y)^1.4121
A
==========
A+b-x*(12.13+51^y)^1.4121

Perfect!I got the original expression,it says this function is work normally.

summary

Now,the original expression is converted to a ordered stack.I will convert this stack to expression tree later.

几个常用的 bash 命令

Posted on 2016-10-25 In Essay

鉴于经常忘记这几个常用命令，故此记录下来。。

1.查看当前正在运行的进程:ps -aux

2.在当前正在运行的进程中查找指定的进程: ps -aux|grep npm (查找名字为npm的进程)

"|"符号为管道符号，会将前面命令的执行结果传给后面的命令。

grep为文本搜索命令，可以跟文本或正则进行查找

3.查看指定端口的进程: isof -i:80(跟着的是端口号)

4.查找到进程之后可以使用 kill 10000 (kill PID)来终止指定的进程

5.静默启动程序: nohup npm run dev &

这样可以使程序在后台运行，不会影响操作而且也不会被挂断，即使ssh连接掉了也没有影响

6.查看静默启动程序的日志: tail -f nohup.out

使用vmware(vmware fusion)突破themida对于虚拟机的限制

Posted on 2016-10-24 In Essay

themida是比较有名的一款壳，可以在一定程度上保护软件不被破解或非法使用。例如一些游戏使用themida壳来防止用户使用虚拟机来进行多开。

但是，我希望在mac上使用windows的软件，使用了vmware fusion 8虚拟机，结果软件在运行时会弹出“Sorry, this application cannot run under a Virtual Machine”的提示并终止程序运行。为了正常使用程序，需要进行以下操作：

1.在关闭虚拟机的情况下编辑虚拟机的.vmx文件（此文件在虚拟机保存目录中），在文件中加上

monitor_control.restrict_backdoor = "TRUE"

disable_acceleration = "TRUE"

这两行。

2.themida通过判断系统硬件中是否存在"Vmware"类似名字的硬件来判断是否在虚拟机中运行，因此需要对硬件的名称进行修改。最简单的方式是使用驱动管理软件（例如驱动人生等），将驱动进行备份。备份后的驱动会以.zip文件的形式保存在设定的目录中，将其中的安装信息文件(后缀名为.inf)复制出来，进行如下修改：

在文件的最后部分会有一个[String]设置块，把里面的xxx.Disk，xxx.Msg，xxx.SvcDesc等项目的值改成不包含Vmware字样的文字。

3.在虚拟机设置中关闭所有不需要的项目，例如蓝牙等

4.在虚拟机的系统中将Vmware Tools完全卸载

通过这些操作，就能使themida认为运行环境不是虚拟机，从而不会终止运行了。

Problem-solving ideas of Nim game(classical problem)

Posted on 2016-10-17 In Algorithm

Nim game's rule:

You are playing the following Nim Game with your friend: There is a heap of stones on the table, each time one of you take turns to remove 1 to 3 stones. The one who removes the last stone will be the winner. You will take the first turn to remove the stones.

Both of you are very clever and have optimal strategies for the game. Write a function to determine whether you can win the game given the number of stones in the heap.

For example, if there are 4 stones in the heap, then you will never win the game: no matter 1, 2, or 3 stones you remove, the last stone will always be removed by your friend.

idea of Nim game

There are some situations in this game.

Let's think about what will happend while stones is few:

If there are 4 stones in the heap,you will lose the game in every matters.

If there are less than 3 stones,you will win the game in one step.

So,when there are more than 4 stones,you should remove some stones and let your friend getting 4 stones.In this situation,we can simplify this problem to that how to leaving 4 stones.And you will find it is the same as initially problem.

Now, what you should do is leaving multiple of 4 stones in every matters.So,if the number of stones is not the muiltiple of 4,you will win this game.

Finally,we can use a formula to express this problem:

stone_num%4!==0

you will win.