Hakale

奇迹和更新

刚开始搭建博客的时候,是很激动的,也想着以后能够经常更新,也希望这个博客能够帮我思考。

然而每次回头看的时候,都会觉得过去在发博客的时候怎么会那么无知,这样一个小问题都能激动到写一篇来庆祝下。每过一段时间,都会这样。以至于想删了之前写过的一些神叨。

更重要的一点是,我觉得自己的博客并没有干货,没有产出。一些支离破碎的胡言乱语堆在了这里,更像是自言自语。而我离能够写出干货的那一天,还有点距离。

Read More

C++对象转移

在想为何string的输入流清空了string对象,查找函数定义时发现了>>运算符的重载方式.而其中的move()函数似乎没有见过.

1
2
3
4
5
6
7
8
9
template<class _Elem,
class _Traits,
class _Alloc> inline
basic_istream<_Elem, _Traits>& operator>>(
basic_istream<_Elem, _Traits>& _Istr,
basic_string<_Elem, _Traits, _Alloc>& _Str)
{ // extract a string
return (_STD move(_Istr) >> _Str);
}

搬了一本C++标准库,找了一些关于move的说明.

简单来说,move出现是因为

有时候生成一个临时对象并用于赋值之后销毁,或者拷贝一个对象之后将不再使用这个对象,而拷贝层数又比较深的时候,或者例如string容量追加的时候,申请新空间并将旧值一一复制过去是比较花时间的,这时候直接搬用内存空间会更快。而move最差的情况下与copy的复杂度相同,其他情况下会更快。这个在ACCU2011_MoveSemantics中有分析。

std::move函数的作用是返回一个对象的右值引用。对象将不再被拷贝而是被moved。而对象自身需要有移动构造函数移动赋值运算符

首先是右值引用的问题,右值引用就是必须绑定到右值的引用,只能绑定到一个将要销毁的对象上.

右值恒久;左值短暂

左值有持久的状态。右值要么是字面值常量,要么是在表达式求值中创建的临时对象

右值引用只能绑定到临时对象,所以

  • 所引用的对象将要被销毁
  • 该对象没有其他用户

意味着,使用右值引用的代码可以自由地接管所引用的对象的资源。

不能将一个右值引用直接绑定到一个变量上。但是可以显式将一个左值转为对应的右值引用类型

所以move函数要登场了。

通过调用std::move()可以获取在左值上的右值引用。调用std::move(rr)也就意味着承诺除了对rr赋值和销毁外,不再使用rr

在类中,将有移动构造函数和移动赋值运算符,这样才能进行move操作。在C++ Primer中有一个移动构造函数的例子

1
2
3
4
5
StrVec::StrVec(StrVec &&s) noexcept
: elements(s.elements), first_free(s.first_free)
{
s.elements = s.first_free = nullptr;
}

移动构造函数不分配新内存,析构函数对first_free调用deallocate,而不是直接释放指向的内存。在移动复制函数中,还需要注意自赋值的可能性,因为在释放自身资源后移动自身元素将会出现错误。

C++的很多地方采用了特殊对象处理内存的分配和归还,这样的对象称为allocator。表现出一种特殊的内存模型,被当作一种用来把“内存需求“转换为”内存低级调用“的抽象层。

Nicolai M. Josuttis C++标准库

在标准库中关于Move的有些说明如下

  • Move Iterator(搬移迭代器)

    这种迭代器始于C++11,用来将任何“对底层元素(underlying element)的访问”转为一个move操作。也就是说,他们允许从一个容器搬动元素到另一个容器,不论是在构造函数内或是在运用算法时。

  • STL迭代器-迭代器适配器-Move迭代器

    一般而言,只有当“算法将元素从某个来源区间迁移到某个目标区间时”,这种情况下在算法中使用move迭代器才有意义。此外,必须确保每个元素只被处理一次,否则,搬迁一次以上的行为未定义。

随后找到了一关于Move语义的PPT.

Moving most important when:

  • Object has data in separate memory (e.g., on heap).
  • Copying is deep.

Moving copies only object memory.

  • Copying copies object memory + separate memory

Moving never slower than copying, and often faster.

Rvalue references identify objects that may be moved from

而标准库中的容器均提供了move构造函数。对于比较复杂的类型,也应该提供这样一个构造函数。

参考
  1. ACCU2011_MoveSemantics
  2. 《C++ Primer》
  3. 《C++ 标准库》

C++中String的一些用法

C++整型转字符串

Failed

今天做了操作系统的银行家算法实现。本来也是一很简单的实现。加上处理任意长度的向量,改为矩阵操作,也不是很难。然而在处理状态信息输出的时候,字符串转换卡了半个多小时。在没有网的情况下不能面向Google编程,很影响编程速度.

第一次大概是这样的写法

1
2
int num = 3;
std::string strResult = std::string("A", num + "B");

当然这种写法比较蠢,当然运行的时候有错误


photos:

- http://7xlkdd.com1.z0.glb.clouddn.com/stringerror.png

大概也提示了是字符串操作的问题。但是在一堆代码里面找哪一行错了.倒是加了不少断点才找到

第二次改成这个样子

1
2
3
4
std::stringstream ss;
ss << *i;
ss >> res;//追加i到res尾部
ss.clear();

很可惜这样也是错的。res会被清空的.

1
2
3
4
string s = "123";
stringstream ss("456");
ss >> s;
cout << s;

结果为456.的确跟想的不太一样,对于数值型的变量来说,这很直观

既然这样不能,res会被清空,那就拉个垫背的。

1
2
3
4
5
std::stringstream ss;
ss << *i;
ss >> tempStr;
res += tempStr;//追加i到res尾部
ss.clear();

在标准库String Class关于I/O函数的说法中

1
istream& operator>> (istream&& strm, string& str)
  • strm中读取下一个string的所有字符,放入str

说明str的确是会被清空的,写入新值.

这里&&是右值引用.右值指不具名的临时对象,只能出现在赋值操作的右侧。

正确的做法

正确的方式应该是使用std命名空间里的std::to_string函数.

1
std::to_string(321.6);

String可以执行的操作

  • 元素访问

    • 除了下标操作符[]以外,还有成员函数at(),前者不会检查索引是否有效,后者会检查.如果at()指定索引无效,则会抛出out_of_range异常,而下标操作符的行为则不明确.
    • 对空字符串front()会返回'\0',back()行为未定义.
    • append()相当于+=,而push_back()用于追加单个字符.
  • npos的意义

    1
    static const size_t npos = -1;

    npos比较有意思,是size_t类型的,然而size_t则是Unsigned integral type 类型.有符号数-1被转换为无符号整型时,直接根据二进制值转换(CSAPP有说),所以npos也就成了最大的数.查找函数失败会返回npos.

    为了图省事而用`int`声明下标变量的方式比较危险.
    在声明下标类型时,必须使用`string::size_type`
  • 数值转换

    C++11开始,标准库提供了转换函数,只适用于stringwstring,而不适用于u16stringu32string.

    | String函数 | 效果 |
    | :-: | :-: |
    | stoi(str, idxRet =nullptr, base = 10) | str转int |
    | stol(str, idxRet =nullptr, base = 10) | str转long |
    | stoul(str, idxRet =nullptr, base = 10) | str转unsigned long |
    | stoll(str, idxRet =nullptr, base = 10) | str转long long |
    | stoull(str, idxRet =nullptr, base = 10) | str转unsigned long long |
    | stof(str, idxRet =nullptr) | str转float |
    | stod(str, idxRet =nullptr) | str转double |
    | stold(str, idxRet =nullptr) | str转double |
    | to_string(val) | val转为string |
    | to_wstring(val) | val转为wstring |

IPython

之前写程序在出错之后都是二话不说加断点跟踪调试,第一反应并不是检查逻辑上的问题。一头懵地跟踪几个来回,找到错误的地方再改。在问题比较低级的时候,倒是能很快在一堆不太想看的代码里找到问题,不过很多时候倒是还得回头理一遍逻辑。又称玄学Debug

在IPython中实验代码的时候,直接贴一段看能不能跑就行了。出错也会打印详细的调用堆栈。而C++中编译检查不出来的问题,在运行时的错误倒是不知道错在哪里了,只是知道访问越界了,引用错误了。相比之下我觉得用Python快速构建是不错的办法。

不过这次的错误倒不是有关这点,而是在不能面向Google编程,手头又没参考书的时候,闭眼瞎写。

机器学习实战-朴素贝叶斯分类器

在看贝叶斯分类器的时候,西瓜书全书没有一行代码.公式一直推来推去,而贝叶斯网则更看得心塞.

就转向机器学习实战,看了一个简单的分类器例子.(虽然第一遍也没看懂

贝叶斯定理在高数课上都上过,对于这个公式来说,理解起来是挺简单的.拿公式做分类的时候,就花了点功夫.

$ P(B|A) = \frac{P(A|B)P(B)}{P(A)}$

比较直观的例子就是用贝叶斯公式实现垃圾邮件识别,当时在数学之美上看到这个例子,s

$ P(c_i|\vec w) = \frac{P(\vec w|c_i)P(c_i)}{P(\vec w)}$

kNN实现手写数字识别

在机器学习实战中,使用了kNN实现了一个简易的手写识别系统.

在这之前,我都一直觉得,实现手写识别是相当复杂的.(事实上也是这样.

kNN的想法就是找原有数据与新数据距离最近的k个点,将k个点中出现最多的分类作为新数据的分类.

而距离的计算有多种方式,欧氏距离,曼哈顿距离,海明距离…这里使用的是欧氏距离.

这里因为数据和测试 样例都是处理好的,而且只是识别了数字,相对来说简单了很多.

下面就是第二章一直在使用的分类器,inX为测试数据,dataSet为数据集,labels为标签集,k即为选出最近的k个数据.主要用到的是numpy中的矩阵运算,求出inXdataSet的欧氏距离.

1
2
3
4
5
6
7
8
9
10
11
12
13
def classify0(inX, dataSet, labels, k):
dataSetSize = dataSet.shape[0]
diffMat = tile(inX, (dataSetSize, 1)) - dataSet
sqDiffMat = diffMat ** 2
sqDistances = sqDiffMat.sum(axis=1)
distances = sqDistances ** 0.5
sortedDistIndecies = distances.argsort()
classCount = {}
for i in range(k):
voteLabel = labels[sortedDistIndecies[i]]
classCount[voteLabel] = classCount.get(voteLabel, 0) + 1
sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)
return sortedClassCount[0][0]

其中一个例子是这样的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
00000000000000111100000000000000
00000000000001111111100000000000
00000000000001111111100000000000
00000000000000111111111100000000
00000000000000111111111110000000
00000000000000111111110000000000
00000000000000111111110000000000
00000000000000111111110000000000
00000000000000111111110000000000
00000000000000111111110000000000
00000000000001111111100000000000
00000000000011111111100000000000
00000000000011111111100000000000
00000000000111111111100000000000
00000000000111111111100000000000
00000000111111111111100000000000
00000001111111111111100000000000
00000011111111111111100000000000
00000001111111111111100000000000
00000000000000111111100000000000
00000000000000111111100000000000
00000000000000111111100000000000
00000000000000111111100000000000
00000000000000111111100000000000
00000000000000111111100000000000
00000000000001111111100000000000
00000000000001111111100000000000
00000000000001111111110000000000
00000000000000111111111111000000
00000000000001111111111111000000
00000000000000011111111111000000
00000000000000001111111110000000

测试代码长这样的,读入文本数值转换为向量形式,对每个测试向量进行距离计算.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
def img2vector(filename):
returnVector = zeros((1, 1024))
with open(filename) as f:
for i in range(32):
lineStr = f.readline()
for j in range(32):
returnVector[0, 32 * i + j] = int(lineStr[j])
return returnVector
def handwritingClassTest():
hwLabels = []
trainingFileList = os.listdir('trainingDigits')
m = len(trainingFileList)
trainingMat = zeros((m, 1024))
for i in range(m):
fileNameStr = trainingFileList[i]
fileStr = fileNameStr.split('.')[0]
classNumStr = int(fileStr.split('_')[0])
hwLabels.append(classNumStr)
trainingMat[i, :] = img2vector('trainingDigits/' + fileNameStr)
testFileList = os.listdir('testDigits')
errorCount = 0.0
mTest = len(testFileList)
for i in range(mTest):
fileNameStr = testFileList[i]
fileStr = fileNameStr.split('.')[0]
classNumStr = int(fileStr.split('_')[0])
vectorUnderTest = img2vector('testDigits/' + fileNameStr)
classifierResult = classify0(vectorUnderTest, trainingMat, hwLabels, 2)
print('the classifier come back with:%d, the real answer is: %d'%(classifierResult, classNumStr))
if classifierResult != classNumStr:
errorCount += 1.0
print('the total number of errors is: ', errorCount)
print('the total error tate is: ', errorCount/ float(mTest))

尝试改变k的值,得到了不同的结果

k 错误率
1 1.3%
2 1.3%
3 1.2%
5 1.7%
10 2.1%

可以看出来,K值的选取对分类结果的正确性会产生影响,但并不是越大越好或者越小越好.

K值过大,分类会很模糊,K值很小,对噪声会很敏感.

Read More

someTroubleInMLinAct

  • reload函数是在imp模块中的
1
AttributeError: 'dict' object has no attribute 'iteritems'

Python3中移除了iteritems方法.在Python2中items方法返回字典拷贝,iteritems方法返回迭代器.在Python3中items返回字典迭代器.

A 2-dimensional array has two corresponding axes: the first running vertically downwards across rows (axis 0), and the second running horizontally across columns (axis 1).

axis 0 指对列进行操作,axis 1 指对行进行操作.