一个监督的赫布学习(Hebb Learning)的例子

赫布学习(Hebb  Learning)基于赫布规则(Hebb Rule):

When an axon of cell A is near enough to excite a cell B and repeatedly or persistently takes part in firing it, some growth process or metabolic change takes place in one or both cells such that A’s efficiency, as one of cells firing B, is increase.

赫布规则大致说的是如果神经细胞刺激不断加强,两者联系加强。

首先看看一个简单的神经网络的结构(以识别为例):

networkneural

左边P(R×1的向量) 是输入,表示待识别物体的R 个特征。W是权重矩阵,通过计算特征和权重矩阵的乘法,用于形成S 个结果,S是判别函数。最终形成a (S×1向量)的结果。下面以位矩阵的数字识别为例:

问题:有6×5大小的像素矩阵用于表示数字0,1,2,如下图所示pattern012

每个数字矩阵用一个一维的特征向量表示,比如0 对应的特征向量为p1:

p1 = [-1 1 1 1 -1 1,-1 -1 -1 1 1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1]^T

其中-1代表这个像素不上色,1反之,t1-t3分表代表结果是0,1,2。那我们的问题是如果识别带有误差,或者只有部分像素的例子。如下面图中应该识别为多少呢?

0inbroknbroken2

 

 

 

 

分析:使用如下的神经网络,

networkpractical

权重矩阵W通过下面等式计算:

W = p1·p1^T + p2·p2^T + p3·p3^T

在我们这个例子里,权重函数如下

weightmatrix

S判别函数我们使用hardlims,当输入大于0则结果为1,当小于0 则结果为-1. 针对一个特定识别过程(如下图):

recog0

下面是实现这个过程的Python 代码,使用到numpy 库。

#_*_coding:utf-8_*_
import os
import sys
import numpy as np
mat0 = np.matrix([-1,1,1,1,-1,\
1,-1,-1,-1,1,\
1,-1,-1,-1,1,\
1,-1,-1,-1,1,\
1,-1,-1,-1,1,\
-1,1,1,1,-1])
mat1 = np.matrix([-1,1,1,-1,-1,\
-1,-1,1,-1,-1,\
-1,-1,1,-1,-1,\
-1,-1,1,-1,-1,\
-1,-1,1,-1,-1,\
-1,-1,1,-1,-1])
mat2 = np.matrix([1,1,1,-1,-1,\
-1,-1,-1,1,-1,\
-1,-1,-1,1,-1,\
-1,1,1,-1,-1,\
-1,1,-1,-1,-1,\
-1,1,1,1,1])
mat0t = mat0.getT()
mat0p = mat0t.dot(mat0)
mat1t = mat1.getT()
mat1p = mat1t.dot(mat1)
mat2t = mat2.getT()
mat2p = mat2t.dot(mat2)
print "===============matrix 0===================="
print(mat0p)
print "===============matrix 1===================="
print(mat1p)
print "===============matrix 2===================="
print(mat2p)
matw = mat0p+mat1p+mat2p
print "===============matrix sum===================="
print matw
testa0 = np.matrix([-1,1,1,1,-1,\
1,-1,-1,-1,1,\
1,-1,-1,-1,1,\
-1,-1,-1,-1,-1,\
-1,-1,-1,-1,-1,\
-1,-1,-1,-1,-1])
mata0 = matw.dot(testa0.getT())
print "=========== raw mata0 =============="
print mata0
for ii in xrange(mata0.size):
if mata0[ii] > 0:
mata0[ii] = 1
else:
mata0[ii] = -1
print "============= After testa0 ================="
print mata0

备注:这是Neural Network Design 的一个例子,作者用python 代码实现了下。

Python 和字符编码

Python 2.* 的程序员肯定遇到过这样那样的字符编码问题:

  • 为什么从网站上爬取的html 在本地显示的就不正常?
  • 为什么会显示 UnicodeEncodeError: ‘ascii’ codec can’t encode character 这样的错误
  • python 中encode(),decode() 方法如何使用?

这样的字符编码问题总会让新手、老手都头痛,有时候即使解决了问题也不能完全知道原理。然后似乎这样的问题似乎在Python 3 中却又解决了?Python 3 又是如何解决字符编码问题?。写在python 2.* 即将要退出历史舞台时候,不知道以后python 程序员还会不会遇到这样的问题。但即使python 不会再有编码问题的困扰,更低级的语言可能还是会遇到,字符编码的原理也不会变化。


一、从编码的历史谈起

将任何一门课程(专业)都要从这个课程所研究的历史讲起。这是因为了解了历史问题,才能够明白课程需要解决的真正问题是什么?知道了这些年解决历史问题的方法,才能够反映出最新解决方法的先进性,也明白了为什么我们(课程)要这么做。

字符是信息的一种体现,字符编码也是信息编码的一个子集。如果考虑到古代的绳结记事、甲骨文和壁画也是信息的一种编码,我们这里所讲的字符编码指的是:自然语言字符(文字)在现代计算机上的映射方法。字符编码的来源是人类自然语言(文字),编码结果是存储在现代计算机上的二进制串。之所以是映射,因为每一个自然语言字符所对应的二进制串是唯一的。

large

1.1 ASCII 码表

现代计算机起源于英语为母语的美国,所以最初美国工程师在字符编码中首先考虑的是自己母语的使用方便,即26个英文字母(大小写),0-9数字和常用字符的编码。在1963年颁布了ASCII (American Standard Code for Information Interchange)字符编码表,如下所示:

ASCII 表

ASCII table

ASCII 表包含字符个数128(2^7)个,因此任何一个字符都可以在一个字节内存储下来,不会出现超过一个字节的字符。计算机解码时按字节解码即可,非常方便。ASCII 表不仅定义了像空格(space)、字母等可见字符,还定义了一些不可见字符。使用下面的代码可以输出0-127 的ASCII 码表。

for ii in xrange(0,128) print chr(ii)+'\t'

ASCII码表很好的解决了英语为母语的计算机使用者的信息存储问题,但人类的科技进步的成果也必须全人类共享啊。但如果仅靠一个字节来保存全世界所有语言的字符肯定是不合适的。如果法国人要将自己语言中的 é, è, ê or ë 输入到计算机怎么办呢?更不用说中韩日语以庞大数量汉字为基础了。

1.2 GB2312 中文字符编码

为兼容本地语言,各个国家开始制定了自己语言的编码方法。但为了向下兼容英语,各种编码方法都是在ASCII码上进行了扩展。我国常使用的GB2312 是最常见的中文编码方法,GB2312 于1980 年颁布,所以其标准号是GB2312-1980。GB2312 按两个字节编码一个中文字符,共收集了6763 个汉字和682 个非汉字图形。GB2312 不仅收录了中文,还收录了拉丁字母、希腊字母、日文片假名、平假名字母等。

GB2312 将两个高、低字节(第一个字节为高字节,第二个为低字节)分别称为区字节和位字节,一个区包含94个字,共计94个区。GB2312 规定区字节仅 0xA1-0xF7 (01-87加上0xA0)存储汉字,位字节 0xA1-0xFE 存储汉字。GB2312之所以从A0 开始编码可以避免与ASCII的冲突,比如打开一个GB2312 编码的文件,如果字节值小于128,则这是ASCII字符;如果字节值大于128,则这个字节属于一个汉字。
下面的方法给出了中国字符“您好!”和GB2312 编码后结果:

>>> ("你好").decode('gb2312').encode('gb2312')
'\xc4\xe3\xba\xc3'
>>>

这里需要解释下decode() 和encode() 函数了。首先需要明白Python 中有两种字符串类型,一种是str 字符串,一种是unicode 字符串。比如 ‘你好’ ,’news’,’나는 당신을 사랑합니다’ 是str 字符串,而 u’你好’ 则是unicode 字符串。

decode() 是将str 字符串转化为unicode 字符串

encode() 是将unicode 字符串转化为str 字符串

以GB2312 为代表的区域性字符编码方法还是存在着通用性的问题。

  1. 因为不同国家指定了不同的字符编码方法,相同的0/1 字符串在不同的字符编码方法中很可能对应不同的字符。那么打开一个文件,首先得知道它的编码方法才行。
  2. 为全世界语言字符进行统一的字符编码(或者制定一套各地域字符编码方法的转换规则),两个字节肯定是不够的,那么需要更多字节来存储字符么?

1.3 unicode

unicode 可以看做一个终极的字符编码方法,它给出了地球上常用字符的二进制映射,而且所有的二进制字符串唯一地表示一个字符。当然unicode 也向下兼容ASCII,下面给出了一些字符所对应的二进制、十六进制值。

字符   十六进制    二进制
I      49        01001001
J      4A        01001010
日     65e5      01101001 11100101
ᅱ      FFD6      11111111 11010110
♀      2640      00100110 01000000
♬      266C      00100110 01101100

unicode包含了人类常用的语言字符、标识等字符编码,目标是统一全球字符编码,它也似乎正在向这终极目标迈进。但也可以看出unicode 只给出了字符和二进制串的对应关系,并没有给出存储形式。而不同字符所占用的存储空间可能不同,比如ASCII 在unicode 中只占用了一个字节即可,而常用汉字在unicode 中需要占用两个字节,还有一些罗马字符可能需要三个或以上字节。如果直接存储的话可能导致无法分割字符串,也无法正确解码出字符,比如计算机读到了“65e5”,这是中文的日字还是两个字符(’65’ 和 ‘e5’在unicode 中对对应的字符)呢?

关于unicode 问题:如果计算机读到一个字节,如何判断这个字节是新的字符的开始,还是一个未读完字符的继续呢?

这个问题在ASCII 码表和GB2312 中是不存在的,因为所有字符都是固定长度。那么unicode 可不可以也使用最大的长度字符的字节数来表示呢?当然可以,比如最大unicode 用四个字节可以保存,那么所有的字符都占用四个字节,但问题就是需要的存储空间变得很大。比如unicode 对应字符的存储如下(这么多0 是不是浪费了很多存储空间呢?):

I    00000049
J    0000004A
日   000065e5
ᅱ    0000FFD6
♀    00002640
♬    0000266C

一个可以想到的办法就是在一个8 bits 的字节中,第一位用来保存是否是字符的开始(1表示这是一个新字符,0表示这个字符的unicode 还没有结束),后面七位用来保存unicode 的值。这是一种变长编码方法,即每个字符的编码后所占空间是不同的(下面称作首位编码)。

字符   十六进制     二进制               首位编码
I       49       01001001              11001001
J       4A       01001010              11001010
日      65e5     01101001 11100101     10000001 01010011 01100101
ᅱ       FFD6     11111111 11010110     10000011 01111111 01010110
♀       2640     00100110 01000000     11001100 01000000
♬       266C     00100110 01101100     10010011 00011011

每次解码时,将字符每个字节除去第一位(红色标示)的其他位拼接得到的值作为其unicode 值。但这种方法我能想到的存在问题就是效率低,处理器每次只能一个字节一个字节的处理,读取到第一个字节时并不能知道这个字符占多少个字节,而且没有办法知道中间数据是否发生损坏。而我们常见的UTF-8 却可以很好解决这个问题。

1.4 UTF-8

该UTF-8 出场了,简单地说,UTF-8 是unicode 在计算机中的一种实现方式。和我们上节提到的首位编码类似,也是一种变长编码,每个字符占1-4 个字节。UTF-8 将字节分为数值位和标识位,数值位真正保存字符编码数值标识位表示这个字节是属于哪个字符的、或者该字符占多少个字节。UTF-8 编码方法的:

单字节,首位为标识位0;多字节字符首字节标志位1··10开头,字符占多少字节则有多少1,其他字节标识位10开头;

  • 单字节字符: 0xxxxxxx (以0 开头标志位,数值位用x 表示)
  • 双字节字符: 110xxxxx 10xxxxxx
  • 三字节字符: 1110xxxx 10xxxxxx 10xxxxxx
  • 四字节字符: 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx

解码时,如果字节首位是0,那么这个字节是个字符;如果字节以i 个1开头,那么这个是一个i 位字符。那么unicode 又是如何填入到UTF-8 的空缺(x)中呢?首先来看看每个多字节UTF-8 编码对应unicode 值的范围:

UTF-8二进制                           unicode二进制
0xxxxxxx                              00-7F
110xxxxx 10xxxxxx                     0080-07FF
1110xxxx 10xxxxxx 10xxxxxx            0800-FFFF
11110xxx 10xxxxxx 10xxxxxx 10xxxxxx   00010000-10FFF

unicode 变为UTF-8 编码非常简单,unicode 二进制按照从低到高,填充UTF-8的数值位,除去那些不真正表示数值的标识位(字节开头的0,10,110,1110和11110),顺序也是由低到高。以汉字“你”为例,看看unicode 如何转换成UTF-8 编码。

>>> (u"你").encode('utf-8')
'\xe4\xbd\xa0'
>>> (u"你")
u'\u4f60'

“你”字unicode 编码为 ‘4f60’ (二进制 ‘01001111 01100000’)。从“你”的unicode 值范围可以看到需要三个字节,接着从低位字节向高位字节填充得到“你”的UTF-8 编码(高位没有填充完则用0补充)。

字符    unicode十六进制   unicode二进制        UTF-8二进制                  UTF-8十六进制
 你        4f60        01001111 01100000   11100100 10111101 10100000    e4bd60

可以看到将UTF-8 用于标记位(红色)的位去掉,合并可以得到原始的unicode 码。

二、文件和终端编码格式

所有的文本文件在计算机中存储的都是一串有限长度的二进制串,只有使用合理的编码方式才能正确地显示文件,但文件本身又是如何告诉编辑器它是如何编码的呢?

2.1 py 文件的字符编码

实际上如果文件本身不申明,编辑器是不知道一个文件所采用的编码方法的。所以编辑器有一个默认的打开方式,比如记事本(notepad)和notepad++ 都默认用ASCII 打开文件。作为Python 初学者可能会遇到下面的一个问题:

故障1:新建一个test.py 文件,用记事本默认打开,输入下面内容:

import os
print "你" 

保存后在终端运行”python test.py” 发现提示错误:

>>python test.py
File "test.py", line 2
SyntaxError: Non-ASCII character '\xc4' in file test.py on line 3, but no encoding 
declared; see http://python.org/dev/peps/pep-0263/ for details

发现提示存在非ASCII 码字符,这是因为在记事本中中文默认使用GB2312编码,”你”的GB2312 编码是”\xc4\xe3″,于是在执行test.py 文件时,出现了无法识别的字符’\xc4’。如果将文件修改为’UTF-8′ 编码时,则可以看到因为”\xc4\xe3″是不合法的字符串,所以显示为它的二进制内容。

utf8save

写过Python 程序的都知道,为了避免py 文件内的编码问题,需要在文件首做一个申明:

#_*_encoding:utf-8_*_

这样,编辑器在开个你这个文件的时候就会默认按照UTF-8 格式打开。当然,UTF-8 也可以换做其他格式。

2.2 python 与文件的字符编码

除了py 文件本身要保存为UTF-8 格式,以避免出现py 文件出现的非ASCII 字符无法被正确的识别。当py 访问其他文件,将数据写入文件时也需要注意字符编码。

故障2:Python2 默认编码是ASCII 码

>>> example = u'你好'
>>> str(example)
Traceback (most recent call last):
File "<pyshell#1>", line 1, in <module>
str(example)
UnicodeEncodeError: 'ascii' codec can't encode characters in position 0-1: 
ordinal not in range(128)
>>> example = u'你好'
>>> open('temp.txt','w').write(example)
Traceback (most recent call last):
File "<pyshell#3>", line 1, in <module>
open('temp.txt','w').write(example)
UnicodeEncodeError: 'ascii' codec can't encode characters in position 0-1: 
ordinal not in range(128)

当用u’字符串’ 的形式申明这个字符串变量时,也就指明了该字符串是使用unicode 字符编码。当如果要将unicode 字符串转换为str 字符串(python2 认为unicode 字符串和str 字符串是不同的)或者写入文件时,python 将默认使用ASCII 码保存数据,而ASCII 码无法识别大于128 的字符,于是报了上面的错误。

类似这样的错误还有:

>>> unicode('abcdef' + chr(255))
Traceback (most recent call last):
...
UnicodeDecodeError: 'ascii' codec can't decode byte 0xff in position 6: 
ordinal not in range(128)

2.3 终端编码

上linux 操作系统课程的时候,我们被教导到:一切都是文件,终端作为一种设备也是文件,当需要输出内容到终端时,实际上也是按照终端对应的字符编码显示相应的内容。

故障3:如果你在windows 终端cmd.exe 运行下面代码(需要安装requests 包)。

import os,sys
import requests
ss = requests.Session()
res = ss.get("http://www.hust.edu.cn/")
con = res.content
print con

这段代码是获取http://www.hust.edu.cn/ 页面的内容,并在终端显示,(如下图)这里出现了乱码。

cmd

但如果你进一步将con 中内容写入到文件或者在linux 下运行这段代码,可能则没有乱码的问题。问题出在哪里呢?原因是因为页面内容是UTF-8 编码(可以在页面源码<meta charset=”utf-8“>中看到 ),而windows 命令提示符cmd 中却使用的是mbcs 字符编码。可以通过下面的命令查看该终端的字符编码

print sys.getfilesystemencoding()

熟悉Linux 的应该知道,终端也是要设置语言格式的,否则在此终端上显示的文件,文件名以及输出到终端的内容会存在乱码。可以通过下面命令设置linux 终端字符编码为UTF-8:

export LC_ALL=en_US.UTF-8
export LANG=en_US.UTF-8
export LANGUAGE=en_US.UTF-8

2.4 str 和unicode

计算机保存的数据,以及从文件中读取的数据都可以理解为str 字符串,str 字符串是需要字符编码才能够被计算机所理解,而unicode 字符串采用统一的字符编码方法。为节省空间等原因计算机并不会直接存储unicode 类型。但在Python2 处理字符数据时,建议全部转化为unicode。

但如果不知道str 字符串编码类型,按照Python2 默认的ASCII 码转换出现大于128 的字节的错误怎么办(UnicodeEncodeError: 'ascii' codec can't encode characters)?

有两种方法:一是用特定的数值(magic number)替代错误的字节;二是干脆忽略错误字节


>>> unicode('\x80abc', errors='replace')
u'\ufffdabc'
>>> unicode('\x80abc', errors='ignore')
u'abc'

同样地,encode() 和decode() 也可以这样使用。

str 字符串和unicode 字符串进行比较,或者合并两个字符串时,首先将它们转换为unicode 格式,再计算它们的值。比如合并str 字符串’你’ 和unicode 字符串u’你’,因为’你’ 按照默认的ASCII 码发现无法解码’你’,于是报错了~~~

>>> '你'+u'你'
Traceback (most recent call last):
 File "<pyshell#0>", line 1, in <module>
 '你'+u'你'
UnicodeDecodeError: 'ascii' codec can't decode byte 0xc4 in position 0: 
ordinal not in range(128)

看下面的例子比较str 和unicode 字符串,python2 按照默认的ASCII 码解码为unicode 过程中发现无法识别的字节,然后就返回不相等(False),并抛出一个异常。

>>> if '你' == u'你':
...    print True
>>> 
>>> '你' == u'你'
__main__:1: UnicodeWarning: Unicode equal comparison failed to convert both argu
ments to Unicode - interpreting them as being unequal
False

正确比较方法应该是:

>>>'你'.decode('gb2312') == u'你':
True
>>> 

如果你在百度或者Google 上搜索解决str 字符串在转码为unicode 时不知道字符编码类型的“问题”时,大部分时候你会看到大家提出在py 文件上加上两句:

reload(sys)
sys.setdefaultencoding('utf-8')

这样py 文件中str 字符串默认以UTF-8 编码。但一位有经验的Python 程序员会告诉你尽量不要这样做,因为这样在对于不是UTF-8 编码的字符时,还是会出现乱码,下节再谈这点。

2.5 _*_encoding:utf-8_*_ 和 reload(sys) sys.setdefaultencoding(‘utf-8’)

有了上面一节的基础,我们大概知道了

#_*_encoding:utf-8_*_

放在py 源代码之前申明,表示py 源文件是UTF-8 编码(即文件中所有的字符都是UTF-8 编码)。这样的好处是如果py 源文件中存在非ASCII 码的字符(你写代码时所输入的UTF-8 字符),python 程序也能够正常的识别为你所输入的字符,而不是按默认为ASCII 码(这样在运行时会抛出无法识别为ASCII 码的错误)。

这种申明文件编码类型是我们推荐的,而下面

reload(sys)
sys.setdefaultencoding('utf-8')

这两句话申明py 文件中所有str 都是UTF-8 编码的,而这种强制定义所有str 字符串为UTF-8 编码是我们不推荐的。比如会遇到下面的问题,在一个测试文件test.py 中有内容:

#_*_encoding:utf-8_*_
import os
import sys
reload(sys)
sys.setdefaultencoding('utf-8')

sym1 =u'♀'+'你'
sym2 = '你'.decode('utf-8').encode('gb2312')
ff = open('temp.txt','w')
ff.write(sym1)
ff.write(sym2)
ff.close()

然后用notepad++打开temp.txt 文件,看到了什么内容呢?

setdefault

不难看出,’♀’ 和’ 你’ 显示都没有问题,但后一个’你’ 就因为使用的是GB2312 编码,写入文件后,前两个字符都是UTF-8 编码,后一个字符GB2312 编码,用UTF-8 格式打开时,最后一个编码肯定就显示不正常了。

当然,上面只是一个例子,很多时候你不会在程序中写出这么buggy 的代码,但是很多时候用python 处理一些非UTF-8 编码的文件或者数据时,就会因为你强制申明str 为UTF-8 编码导致很多问题,比如读取非UTF-8 编码的Oracle 的数据库,修改、添加非UTF-8 编码的文件时,就会产生很多字符编码混乱。因此也有人建议python2 程序员在处理str 时能够显示地使用特定合适的字符编码,而不是默认地使用UTF-8。

Python3 只有unicode 字符串,而没有str 字符串,上面所遇到的字符编码的坑不再有了。

所以—— Bravo~ 学Python3 去吧,骚年!

 

参考文章:

  1. 何世友的日志——立即停止使用setdefaultencoding(‘utf-8’),以及为什么
  2. unicode 编码
  3. Python2 unicode howto

MongoDB 性能测试(一)

数据写入(插入)测试:数据源为文本文件,一行一条记录(record),长度约为125B,使用单线程Pymongo 的 insert_one() 方法写入,所有记录写入到相同collection(类似于数据库中的表)。


环境一(主要特征:老机器单机两块独立硬盘、新版本):

  • CPU:Intel Core Quad Q8300 (2.5GHz) with 2MB cache
  • 内存:DDR2 2×2 GB
  • 硬盘:HDD1,HDD2;
  • OS:Ubuntu 14.04
  • MongoDB:V3.2.7

从本机HDD2 读取写入装在HDD1上的MongoDB 中,

速度约为1000 records 每秒,约等于 0.1MB/sCPU 占用率100%。瓶颈在CPU(解析数据)。


环境二(主要特征:服务器CPU单机两块独立硬盘SSD老版本):

  • CPU:Intel Xeon E3-1231(3.4GHz) with 8MB cache
  • 内存:DDR3 2×8 GB
  • 硬盘:SSD1 (128GB),HDD2;
  • OS:Ubuntu 14.04
  • Mongodb:V2.4.9

从本机HDD2 读取写入装在SSD1 上的MongoDB中,

速度约为6000-8000 records 每秒,约等于1MB/s,CPU占用率100%(python 80%,MongoDB 20%)。两点说明如下:

  1. 改环境测试时间较长,到记录8710万条记录,插入速度没有下降。
  2. 五个线程(一个生产者读取记录,四个消费者写入记录)速度下降为5500 records 每秒(0.6MB/s),印证了collection 全局锁。

环境三(主要特征:网络双机器老版本):

  • 服务器配置为环境二服务器
  • 客户端CPU:Intel i7-4790K 4GHz
  • 客户端内存:DDR3 2×8 GB
  • 客户端硬盘:HDD
  • 客户端OS:Ubuntu 14.04
  • MongoDB:V3.2.7

从客户端HDD 中读取数据写入到服务器SSD 中的MongoDB 中,

速度为1500-2000 records 每秒,客户端CPU占用率20%,瓶颈可能在网络协议。

同样是用一个线程读取数据,多线程写入数据时,速度有所提升(因为网络得到更好使用)。但当线程数增加到8个以上时,速度变化不大,速度稳定在6100 records 每秒(0.63MB/s)。此时,服务器MongoDB 是瓶颈,MongoDB服务器CPU 使用率37%左右。


环境四(环境二和环境三换批量插入

硬件环境与环境二、环境三相同,为支持批量插入数据(bulk),使用新版本(V2.6 以上)。批量每次插入10000条数据(1.3MB)

环境三单线程可以达到15000 records 每秒(TCP/IP网络还是对长报文比较友好,短报文只能用多线程来堆了,后经测试,四线程也只能达到18000 records 每秒)

环境二单线程可以达到30000 records 每秒(4MB/s)

插入速度较慢,SSD 换成HDD 变化不大,可能查询有差别。

insert

 

 

 

 

计算二维空间某点的最近k 个点

计算多维空间——主要是二维空间——中最近点问题是GIS、游戏、计算机图形学中常遇到的问题。最近点问题包含但不局限于下面问题:

  1. 一维空间中距离点A 最近的一个点
  2. 一维空间中距离点A 最近的K 个点
  3. 一维空间中距离点A 小于D 的所有点
  4. 二维空间中距离点A 最近的一个点
  5. 二维空间中距离点A 最近的K 个点
  6. 二维空间中距离点A 小于D 的所有点

下面以问题 5. 二维空间中距离点A 最近的K 个点 为例,谈谈我的思路:

绘图1

 首先将二维距离变为一维距离,得到距离该点(红点)在一个坐标系上最近的1→i 个点,所对应的点的集合为Sx。下图是当i=3 时,距离最近的点:

绘图2

同理,得到y轴上最近的1→i 个点,点的集合为Sy。

绘图3

i 的大小从1 逐渐递增,每次计算集合Sx和集合Sy 的交集(Sx∩Sy),如果交集中的点w 是x、y坐标距离红点之和(△x+△y)第k 小的那个点,且满足约束条件:

△x+△y < max(Sx∪Sy)

那么停止i 的递增,在Sx和集合Sy 的交集(Sx∩Sy)中距离红点之和(△x+△y)中最小的k 个点即是平面上距离红点之和(△x+△y)最小的k 个点。当然约束条件可以进一步优化为:

△x+△y ≤ max(min(Sx)+max(Sy),min(Sy)+max(Sx))

因为二维平面距离之和(△x+△y)与距离(\sqrt{\bigtriangleup x^2+\bigtriangleup y^2})满足:

△x+△y ≥  \sqrt{\bigtriangleup x^2+\bigtriangleup y^2}

 那么距离红点最近的k 个点距离上限小于△x+△y。

最终,只需要在一个较小的集合Sx∪Sy 中遍历找到距离红点最近的k 个点就可以咯~~~

计算某一点到连接两点的直线距离(矢量方法)

方法一:计算两点形成直线的斜率,斜率的负倒数是某点到该直线的斜率,通过计算垂足到该点距离得到某点到两点形成的直线距离。

方法二:矢量方法,好处是对于任意斜率都可以计算。

问题:已知点A (ax, ay),求到连接点B(bx, by)  和C(cx, cy) 的直线距离。

假设:建立坐标系,向量\vec{a}\vec{b} \vec{c}  分别对应三点的向量,如下图:

绘图1

图中C到直线AB 的垂线是紫色那根(假设垂足为D,图中未标注)。分别求得A 到B 的向量和C 到B的向量:

\vec{AB} = \vec{b}-\vec{a}    \vec{CB} = \vec{b}-\vec{c}

通过计算\vec{AB} \times \vec{CB} 可以推导出红色线段长度为$\mid\vec{CB}\mid \cos\theta $,因为

\vec{AB} \times \vec{CB}  = \mid\vec{AB}\mid \cdot \mid\vec{CB}\mid $ \cos\theta $

再通过勾股定理得到垂线距离:

$\mid CD\mid = \sqrt{\mid\vec{CB}\mid ^2 - (\frac{\vec{AB} \times \vec{CB})^2}{\mid\vec{AB}\mid}}$

$ = \sqrt{(cy-by)^2+(cx-bx)^2-\frac{((bx-ax)(bx-cx)+(by-ay)(by-cy))^2}{(ay-by)^2+(ax-bx)^2}}$

 

Android 开发笔记(SDK)

Android 为开发者提供的SDK(Software Development Kit,软件开发包)提供了一系列API,通过调用这些API 即可写出各具形态的app 了,所以我们应该对SDK 有一定的了解。

SDK 中Java 类以树层次结构打包,最上层的是android package,它主要包含了app 的资源类和对安卓系统的权限。如:Manifest  |  Manifest.permission  |  R  |  R.anim  |  R.array  |  R.attr  |  R.color  |  R.dimen  |  R.drawable  |  R.id  |  R.layout  |  R.string  |  R.style  |  R.xml 等。

android.app 中包含了android已封装好的一些高级类,如: Activity  |  Service  |  Fragment

Activity 类表示人机交互的一个界面。

Service 类表示一个后台长时间运行的组件,无UI,比如处理网络通信,音乐播放,或者是与一个content provider 交互。

Fragment 类在平板等大屏显示时表示activity 行为的一部分,并且关联相应的UI(可以看做是一部分UI,类似于activity)。

adroid.app 中还包含了其他类和接口:Dialog  |  ActionBar  |  Notification 等。

 

提供基础的操作系统级别的服务:services, message passing,IPC(Inter-Process Communication)。

BatteryManager 电池状态信息。

Bundle  一个字符各种可打包类型映射

 

包含了可以访问android 提供content providers 的类。

 

包含app 外观设计的一些资源类:  R  |  R.anim  |  R.attr  |  R.bool  |  R.color  |  R.dimen  |  R.drawable  |  R.id  |  R.integer  |  R.layout  |  R.string  |  R.style  |  R.styleable 等。

 

提供了app 布局的一些小部件,如Bar 等。  AppBarLayout  |  NavigationView  等。

 

关于文字的类。有关接口和类: Editable  |  GetChars  |  Annotation  |  AutoText  |  Html  |  Layout

 

人如其名,包含一些小工具类,如时间、base64编码、字符串和数字处理方法等。

 

安卓app 上常用的一些UI 组件类。接口:Menu  |  ContextMenu  |  MenuItem  类:Display  |  Gravity  |  LayoutInflater (在对应的View 对象中实例化某个XML布局) |  MenuInflater  |  View(UI最基本的组件)

 

包含屏幕上使用的UI 组件,你也可以自己设计一些组件(实现View 的子类)。类:  Button  |  CheckBox  |  CheckedTextView  |  EditText  |  GridView  |  ImageButton  |  ImageView  |  LinearLayout  |  ListView  |  MediaController  |  ProgressBar  |  RadioButton  |  RadioGroup  |  RelativeLayout  |  Scroller  |  TableLayout  |  Toast  等。

 

包含了在设备上访问和写入数据的类,主要包括:1.内容分享 (android.content  中的 ContentProvider 、 ContentResolver 、Intent 和 IntentFilter);2. 包管理(访问一个安卓包.apk的信息) 3. 资源管理(获取应用app 相关的资源数据,如strings,drawables,media等)。

 

包含用于处理从content provider 返回来的数据。如果需要管理一个私有的数据库,请使用 android.database.sqlite 类。

 

管理Sqlite 的类。接口和类:SQLiteCursorDriver  |  SQLiteClosable  |   SQLiteCursor  |  SQLiteDatabase  |  SQLiteQuery  |  SQLiteStatement  等。

 

提供可以在屏幕上直接画图的低级工具,如画布、滤镜、点和矩形。

 

提供管理可视化元素(图、灰度等)的类,这些类经常被widgets 作为背景图片或者指示器。

 

管理音频和视频的类。AsyncPlayer  |  AudioManager  |  MediaPlayer  |  Ringtone

 

java.net.* 之上的网络访问类。

 

使用OpenGL 画图。