0和1

安装WIN10一个月以来，校园有线网经常间歇性断网，通常是20分钟不到就断了，需要重启或者把有线连接关闭再打开才可以。在微博上问过微软客服也无果，后来Google到某国外的解决办法，现记录如下。 说到底WIN10断网的问题还是和驱动有关，先看一下我的有线网卡Broadcom NetLink (TM) Gigabit Ethernet，驱动信息是这样的： 还是13年的驱动，版本号是15.6.0.14，于是第一想到的是更新驱动。点击驱动右键选更新->自动搜索更新的驱动程序软件->提示“已安装适合设备的最佳驱动程序软件”，但这明明不是最新的驱动啊！ 于是在Broadcom的官网上找到了最新驱动win_b57_x64-17.2.0.2，版本号是17.2.0.2，更新日期2015-10-27，原来这才是最新的驱动。 （2018.1.25更新：上面的地址已失效，最新地址请点击此处，并选择DOWNLOADS→Software→NetLink®/NetXtreme® I Desktop/Mobile/Server (x64)，也可以从本站下载。） 在安装最新驱动之前，我们需要关闭WIN10的自动更新驱动功能，因为WIN10会认为它的15.6.0.14版本是最新的，在windows update时把实际最新的17.2.0.2版本替换掉。具体做法是在Cortana中搜索“更改设备安装设置”并打开，选择否，从不安装来自Windows更新的驱动程序软件，如下。 然后重启进入安全模式，再次在设备管理器中右键点击网卡驱动，选择更新->浏览计算机以查找驱动程序软件->从计算机的设备驱动程序列表中选取->点击从磁盘安装按钮->浏览找到你之前在网上下载的最新驱动（*.inf格式）->选中->依次确定。刷新之后再次查看驱动信息如下： 可以看到驱动已经更新到最新的版本了。再次重启进入正常模式，目前用了两天了也没有再断过网。 其他WIN10驱动问题应该也可以用类似的方法解决。 （话说我的WIN10偶尔会死机，就是用着用着突然鼠标和键盘完全动不了了，只能强制重启，有谁知道这是怎么回事吗？）

进入研究生生涯完成的第一个新生培训作业是“2.5亿个浮点数的外部排序算法”，前后折腾了将近一个月，结果是在i7处理器上，限制512MB内存，排序用时250秒左右。 这个作业的常规思路大部分人都能想到，按块读取文件->atof转换为double->内部快速排序或基数排序->dtoa转换为char*->按块写入文件。这里面中间的三个过程都很耗时，特别是atof和dtoa，因为精度只要求保留9位小数，所以可以自己实现atof和dtoa来加速，也可以使用多线程加速。 整个作业都是基于对IEEE754浮点数的深刻理解展开的，所以下面详细讲解浮点数的一些知识。 IEEE754双精度浮点数 目前大多数CPU内浮点数的表示都遵循IEEE754标准，IEEE754双精度浮点数（double）表示如下图所示。 IEEE754 double在内存中的形式[1] sign bit：符号位，1位，用来表示正负号，0表示非负；1表示负 exponent：指数位，11位，用来表示次方数，是一个无符号数 fraction：尾数位，52位，用来表示精确度，也是一个无符号数，有些资料也叫做mantissa或significand 这种表示形式有两点需要注意。 第一，既然exponent是无符号的，那么怎样表示负指数呢？ IEEE754规定，二进制串中算得的e需要减去一个偏移量bias，对于double，bias=1023，即e’=e-bias。因为\(e\in[0,2^{11}-1]\)，所以最终\(e’\in[-2^{10}+1,2^{10}]\)。但是如果把e本身看作有符号数e”，则\(e”\in[-2^{10},2^{10}-1]\)，既然e”和e’相差微小，为什么不直接把e看成有符号数，而非要把它看成无符号数，再减去一个偏移量bias呢？ 这是因为如果把e看成无符号数再减偏移量，浮点数大小比较速度更快。引用维基百科的一段话： By arranging the fields so that the sign bit is in the most significant bit position, the biased exponent in the middle, then the mantissa in the least significant bits, the resulting value will be ordered properly, whether it’s interpreted as a floating point or integer value. This allows high speed comparisons of floating point numbers using fixed point hardware. ...

去年暑假在北大计算所实习的时候，任务之一就是批量下载百度图片。当时没学python，用c#实现了一个简易版本的批量下载器，如下图。 C#版本百度图片批量下载器（抓的是百度的wap站点，现在好像不能用了） 当时“时间紧，任务重“，既没仔细研究百度图片API，也没处理好界面线程阻塞的问题。这个问题其实很有意思，趁着暑假在家，实现了一个比较完美的python版本，先上效果图。 python3版本百度图片批量下载器 新版使用了python-3.4.3.amd64.msi + PyQt5-5.5-gpl-Py3.4-Qt5.5.0-x64.exe + eric6-6.0.8.zip + cx_Freeze-4.3.4-cp34-none-win_amd64.whl，完整项目在我的GitHub上。大致有如下几点工作： 研究百度图片API，获取原始图片URL列表 使用python3进行多线程下载 利用pyqt5实现界面 利用cx_Freeze4打包整个程序 下面记录每个步骤的要点，供后人参考。 百度图片API 正常使用百度图片搜索的时候，URL是这样的： http://image.baidu.com/search/index?ct=201326592&z=0&tn=baiduimage&ipn=r&word=%E6%AD%A6%E6%B1%89%E5%A4%A7%E5%AD%A6&pn=0&istype=2&ie=utf-8&oe=utf-8&cl=2&lm=-1&st=-1&fr=&fmq=1439374041843_R&ic=0&se=&sme=&width=0&height=0&face=0 里面有很多参数，有些我们并不需要，精简之后大概是这样的： http://image.baidu.com/i?tn=baiduimage&ie=utf-8&word=%E7%BE%8E%E5%A5%B3&pn=&rn=&z= word为搜索关键词；pn为page number当前是第几页，实际含义是image id，表示第几张图片，从0开始；rn为每一页的图片数量，最大为60；z表示图片尺寸，z=9特大尺寸，z=3大尺寸，z=2中等尺寸，z=1小尺寸，z=0所有尺寸。 但是这个URL是给”人“看的，下一页的图片是动态加载的，其html代码的图片URL数量固定。一番查询之后发现，将tn=baiduimage换成tn=resultjson_com能获取到所有图片URL的json，json当然是给”猴“看的，这样就能轻松获取到所有图片的URL。 慢着，仔细看看json中的objURL，是一串连”猴“都看不懂的字符串，原来百度把图片真实URL加密了，好在加密方法是简单的字符映射，参考这篇博客成功解密。 更新：tn=resultjson_com的objURL是加密了，但是tn=resultjson的objURL并没有加密，所以采用tn=resultjson最佳。 通过控制pn和rn就能获取指定数量的图片URL，但是我发现rn最大只能为60，并且不同的pn可能会有相同的图片url（比如pn=0和pn=1都有ippr_z2C$qAzdH3FAzdH3Fooo_z&e3Bd8vs7k_z&e3Bv54_z&e3BvgAzdH3F7rs5w1utsjAzdH3Fda8nAzdH3Fa080AzdH3Fda8na080aldm9bb8m_z&e3B3r2这个objURL），所以使用python的集合（set）去重。 更新：pn实际上指图片的id，pn=0、rn=60能获取到从0~59这60个URL列表，pn=1、rn=60能获取到从1~60这60个URL列表，所以pn=0和pn=1的列表中当然有59个是重复的。正确的做法是pn=0、rn=60获取0~59这60个URL列表，然后pn=60、rn=60获取60~119这60个列表，以此类推，这样获取到的URL就不会有重复的了。 获取图片URL列表的简要代码如下： 1 2 3 4 5 6 7 8 9 10 11 def ParseJSON(self, pn, rn, st): url = 'http://image.baidu.com/i?tn=resultjson_com&ie=utf-8&word=%s&pn=%d&rn=%d&z=%d'%(self.word, pn, rn, self.size) #print(url) request = urllib.request.Request(url = url, headers = my_header) html = urllib.request.urlopen(request).read() hjson = json.loads(html.decode('gbk')) for i in range(0, len(hjson['data'])-1):#最后一个数据为空 img_url = self.DecodeURL(hjson['data'][i]['objURL']) if img_url not in st: st.add(img_url)#去重 self.progressBar_updated_signal.emit()#更新进度条 DecodeURL是解密函数。很奇怪，json最后一个数据是空的。 ...

在上一题POJ Problem 1837: Balance中，我们曾讲到，如果只有两个挂钩，问题会好办得多，就拿题目给的样例数据来说： Sample Input 2 4 -2 3 3 4 5 8 Sample Output 2 如上图所示，给定重量为3,4,5,8的砝码，放在一个左右臂长分别为2和3的天平上，要使天平平衡，问有多少种方法。 这个问题可以稍加转换，假设放在左边的重量为x，右边为y，则有如下方程组成立： $$ \begin{cases} x+y=3+4+5+8=20\\ 2x=3y \end{cases} $$马上解出x=12,y=8。这样就相当于把原问题转换为：已知序列3,4,5,8，问从中取若干个数使和为12（或8）的方案数有多少个？ 因为取出数字和为8，则剩余和为12，所以和为8和12的方案数是相等的。 因为这里只有4个数字，一眼就能看出有(3,4,5)，(4,8)能使和为12，即只有两种方案。如果给的数字较多较大，该怎样写代码求出呢？可以使用动态规划求解。 设dp[i][j]表示从前i个数中选若干个数使得和为j的方案数，则我们可以得到这样的状态转换方程： $$ \begin{cases} dp[i][j]=1\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\text{if}i=0\&\&j=0\\ dp[i][j]=dp[i-1][j]\qquad\qquad\qquad\qquad\qquad\qquad\text{if}w[i]>j\\ dp[i][j]=dp[i-1][j]+dp[i-1][j-w[i]]\qquad\quad\text{if}w[i]<=j \end{cases} $$ 当i=0&&j=0时，dp[i][j]=1表示从0个数中取若干个数使得和为0，当然只有1种方案，那就是什么都不取 当w[i]>j时，第i个数用不上，因为你单个数字都超过j了，怎么使和为j呢，所以直接dp[i][j]=dp[i-1][j] 当w[i]<=j时，第i个数可以用了，这个时候分两种情况，用或者不用第i个数，如果不用，则和w[i]>j时一样dp[i][j]=dp[i-1][j]，如果用的话，则要从前i-1个数中取若干个数使和为j-w[i]，也就是dp[i-1][j-w[i]]，这样总的方案数就是用和不用第i个数的方案数之和，即dp[i][j]=dp[i-1][j]+dp[i-1][j-w[i]] 下面是针对这个例子我手算的一个图： 以上面的内容设计一个OJ题如下： 描述： 给定一个正整数数字序列，从中取出若干个数字，使得这些数字之和为某一个特定的值，求所有取法的方案数。 输入： 输入包含多个测试用例，每个测试用例的第一行有两个数N,S，N表示这个数字序列共有多少个数字；S表示取出的数字之和为S。后面一行包含N个正整数。 N,S为0程序结束 输出： 每个测试用例输出一行，表示从N个数中取若干个数使得和为S的方案总数。 样例输入： 4 8 3 4 5 8 4 12 3 4 5 8 10 10 10 9 8 7 6 5 4 3 2 1 0 0 样例输出： 2 2 10 知道了状态转换方程，我们可以很快的写出以上OJ的代码： ...

一、第一次使用Github的步骤： 在这个页面中填写Repo名称 不要勾选Initialize this repository with a README 点击Create repository 在本地使用Git命令行工具进入到和第1步填写Repo相同名称的文件夹中（此文件夹中已包含你要push到Github上的内容），执行以下几个命令： 1 2 3 4 5 6 git init touch README.md #optional git add . git commit -m 'your comment' git remote add origin https://github.com/UserName/RepoName git push origin master 如果你在第2步中勾选了Initialize this repository with a README，那么在第4步中省略touch README.md并且在git add .之前，执行第5行代码，然后git pull origin master将远端（remote）的内容pull到本地 关于Git命令中的fetch和pull的区别，请看这篇博文 关于Git bash和Github的连接，请看这篇博文 二、Git命令中fetch和pull的区别（转载） Git中从远程的分支获取最新的版本到本地有这样2个命令： ...