btsync 体验

更新

惊闻 btsync 已经改名字,现在叫 Resilio ,官网地址也改为: https://www.resilio.com/

可以从 这里 获取不同平台客户端。

Linux 安装 Package 可以参考 https://help.getsync.com/hc/en-us/articles/206178924 这里

创建文件 /etc/apt/sources.list.d/resilio-sync.list, 添加如下内容:

deb http://linux-packages.resilio.com/resilio-sync/deb resilio-sync non-free

添加公钥:

wget -qO - https://linux-packages.resilio.com/resilio-sync/key.asc | sudo apt-key add -

安装:

sudo apt-get update
sudo apt-get install resilio-sync

配置文件存储地址 https://help.getsync.com/hc/en-us/articles/206664690

Linux 下配置文件地址: /var/lib/resilio-sync

啊,安装好了之后,添加这个 key,当个示例啦 BB63I5PBPBFDELAPXI6NTF47IPNZQAAJZ ,一周一本好书。

如果想要手动开启或者关闭 Resilio Sync 可以使用如下命令:

sudo service resilio-sync stop
sudo service resilio-sync start

原文

全称 BitTorrent Sync , 我习惯了叫他 btsync 了。想要了解他的前世今生直接去看维基百科就好了。一句话概括,他就是一个同步工具,类Dropbox,但是利用 P2P等等 bt 种子的技术。当然私人使用当成网盘工具也好,当成分享工具也好,看个人使用了。不过黑客提醒,虽然是去中心化的,但是安全性依然存在问题,最好不要传输私人信息。

官网地址: https://www.getsync.com/

全平台

现在使用任何一个工具或者服务,我首要考虑的问题离不开跨平台了,最好是Windows , Linux, Mac 下全部都有,不然在平台间来回切换不同的服务和工具时间成本,学习成本太高了。也正是因为这个原因我放弃了 Google Drive 而转用 Dropbox,作为主力同步工具。当然 btsync 在全平台都有客户端,甚至连一些 NAS,路由器设备都有。

安装

安装非常简单,去官网下载,下一步下一步,OK。当然 Linux 下,如果不想使用 下一步下一步安装法,也可以使用命令从 PPA 里拖。

PPA

sudo add-apt-repository ppa:tuxpoldo/btsync
sudo apt-get update

For normal desktop use, you only need to install btsync-user:

sudo apt-get install btsync-user

Alternatively, if you’re setting up your BTSync server, install btsync:

sudo apt-get install btsync

btsync client

在官网根据自己的机器选择合适的 client 下载并解压。并运行:

./btsync

即可。

默认的Web GUI地址是 : http://127.0.0.1:8888

更加详细的安装指南可以参考这篇

VPS上架设

类似 Linux 下安装,官网下载并解压 btsync 文件。

tar -zxvf BitTorrent-Sync_x64.tar.gz

然后执行:

./btsync --dump-sample-config > btsync.conf

创建配置文件,然后修改 btsync.conf 配置文件中的:

"listen" : "0.0.0.0:8888" 

还有 loginpassword , 端口默认是8888,可修改成其他没有冲突的。loginpassword 是登陆用户名和密码。其他配置看注释修改即可。参考官网 config 文章.

然后保存配置文件,启动:

./btsync --config btsync.conf

在浏览器中就能够在 http://ip:port/ 访问 Web GUI。

然后在本地获取同步 key ,和 VPS 上同步即可。

技巧

移动同步后的文件夹

如果你已经同步了一个文件夹,比如在 ~/books,现在想要将该同步的目录移动到 ~/btsync/books 目录下。 就像Dropbox 同步已经存在的文件夹一样,如果单纯的再重新下载一边太麻烦了。所以幸好 btsync 和 dropbox 都有这样的性质,同步的内容都有文件记录,将文件重新加入索引,等索引完之后就可以继续和其他的文件同步了。

  1. 拷贝该文件夹的”共享秘钥”
  2. 从 btsync 中移除该文件夹
  3. 在本地硬盘移动文件夹到新的位置
  4. 重新在 btsync 用之前的”共享秘钥“,添加该文件夹

VPS 上启用 https

默认 btsync 的 web gui 是没有启用加密的,如果想要使用 https://ip:port/gui 来访问,则需要使用 config 配置,并在config 配置中设置 force_https, ssl_certificate,ssl_private_key ,然后重启 btsync 。

如果觉得这样让 btsync 直接获取证书不安全,这里 还有另外一种配置,利用 nginx 的代理。

分享密钥的网站

reference


2016-04-18 btsync , 产品体验

小行星视图App review

最近迷上了360度全景,搞了得图800,和理光 theta m15的全景相机玩。然后就对周边的全景处理App都体验了一下。最早接触到 Sphere Photo 也要归功于 Google 的原生 Camera, 然而因为不知道的原因,在 Android kitkat 之后的版本中这个小行星视图就消失不见了。而我还是依然很怀念这样的视图。下面就是一些 Play Store 中存在的制作小行星视图的App。

Android Apps

Tiny Planet FX Pro

完整却不够完美 市场上唯一一款收费的小行星app,但是给我的感觉却是做的不够精致和完美,今天竟然处理出不完整的人脸。处理图像甚至比不上另一款免费的app。

Little Planet

除了开始的广告一切还好 开始的广告可能是让很多人打低分的原因,但是这款app,确实达到了我的需求,并且实现的很好。开发者可以尝试提供pro版本来去除广告或者内购去广告。

Tiny Planet - Globe Photo

广告多功能简单 太多影响操作的广告,横幅广告侵占了操作预览区域。功能比不上其他app。

Spherify

功能简单广告影响使用 功能几乎没有,处理时间太长。广告占据太多篇幅。

最后推荐 Little Planet , 虽然在App开始出现了全屏广告,但是效果及功能和收费的 Tiny Planet FX Pro 相差不大。

temple

android

cosoc

How to make sphere photo using photoshop

大多数时候我没有时间用 Google Camera 照完整个全景,这个时候如果可以后期合成当然是最好的,于是就有了这样一篇文章 ,只要有一张全景照片,利用 Photoshop 同样可以实现 Sphere Photo。 同样也可以参考这篇文章

最后推荐一个社区 https://plus.google.com/u/0/communities/115970110085205516914 ,社群的简介里面有很多教程,并且分享的 Post,质量都很高。


2016-04-16 Android , SpherePhoto , Android app

推荐网站之邮件签名:htmlsig

推荐好用的网站系列之生成邮件签名 htmlsig 。想要一个漂亮的邮件签名,又不想自己写 html,最好的方法就是找一个模板然后自己填写内容。这个网站就是这样的。

官网地址:https://htmlsig.com/

样式1 htmlsig 1

样式2 htmlsig 2

样式3 htmlsig 3

样式4 htmlsig 4

当然我本人最喜欢样式2.

如果稍微懂一点 html 知识,将模板下载下来然后自己手动修改倒也是不错的选择。

生成自己的模板之后,Gmail 和 Inbox 都可以使用复制粘贴的方式将签名添加进去。


2016-03-23 website , 推荐网站

C++ 解析JSON

因项目需求,需要使用 C++ 解析 JSON。

RapidJSON

第一种方法,使用 RapidJSON 可以方便的用来生成或者解析 JSON。

项目地址:https://github.com/miloyip/rapidjson

RapidJSON 是只有头文件的 C++ 库。使用时只需要把 include/rapidjson 复制到项目目录中即可。

类似如下的JSON,其中包括Object,包括Array,掌握解析该JSON,基本 RapidJSON 解析可掌握:

{
  "ret": "101",
  "error": [
    {
      "errortype": "A0001",
      "errorstroke": {
        "0": "0.2",
        "1": "0.3"
      }
    },
    {
      "errortype": "A0021",
      "errorstroke": {
        "0": "0.2",
        "1": "0.3"
      }
    }
  ]
}

代码如下:

#include <iostream>
#include <vector>
#include <string>

#include "rapidjson/document.h"
#include "rapidjson/writer.h"
#include "rapidjson/stringbuffer.h"

using namespace rapidjson;
using namespace std;

int main() {

    string ret =
            "{\"ret\":\"101\",\"error\":[{\"errortype\":\"A0001\",\"errorstroke\":{\"0\":\"0.2\",\"1\":\"0.3\"}},{\"errortype\":\"A0021\",\"errorstroke\":{\"0\":\"0.2\",\"1\":\"0.3\"}}]}";
    rapidjson::Document doc;
    doc.Parse<kParseDefaultFlags>(ret.c_str());
    if (doc.HasMember("ret")) {
        string retjson = doc["ret"].GetString();
        for (unsigned i = 0; i < retjson.length(); ++i) {
            cout << retjson.at(i) << " ";
        }
    }
    cout << endl;
    if (doc.HasMember("error")) {
        const Value & errorjson = doc["error"];
        for (SizeType i = 0; i < errorjson.Size(); ++i) {
            // 或者这里可以换用一种遍历使用 Value::ConstValueIterator
            // http://rapidjson.org/md_doc_tutorial.html#QueryArray
            if (errorjson[i].HasMember("errortype")) {
                string errortype = errorjson[i]["errortype"].GetString();
                cout << "errortype: " << errortype << endl;
            }
            if (errorjson[i].HasMember("errorstroke")) {
                const Value & errorstroke = errorjson[i]["errorstroke"];
                cout << "errorstroke" << endl;
                for (Value::ConstMemberIterator iter = errorstroke.MemberBegin();iter != errorstroke.MemberEnd(); ++iter) {
                    cout << iter->name.GetString() << ": " << iter->value.GetString() << endl;
                }
            }
        }
    }

    return 0;
}

关于 RapidJSON 的更多内容可以参考官网。

boost property_tree

使用 boost 库中的 property_tree 解析如下:

/*
 first config your project to include /usr/local/include
 second link lib /usr/local/lib
 */

#include <iostream>
#include <boost/property_tree/ptree.hpp>
#include <boost/property_tree/json_parser.hpp>
#include <boost/foreach.hpp>
#include <string>

using namespace boost::property_tree;

int main(int argc, const char * argv[]) {

    std::string str_json = "{\"ret\":\"101\",\"error\":[{\"errortype\":\"A0001\",\"errorstroke\":{\"0\":\"0.2\",\"1\":\"0.3\"}},{\"errortype\":\"A0021\",\"errorstroke\":{\"0\":\"0.2\",\"1\":\"0.3\"}}]}";

    ptree pt;                       //define property_tree object
    std::stringstream ss(str_json);
    try {
        read_json(ss, pt);          //parse json
    } catch (ptree_error & e) {
        return 1;
    }

    std::cout << pt.get<std::string>("ret") << std::endl;
    ptree errortype = pt.get_child("error");            // get_child to get errors

    // first way
    for (boost::property_tree::ptree::iterator it = errortype.begin(); it != errortype.end(); ++it) {
        std::cout << it->first;
        std::cout << it->second.get<std::string>("errortype") << std::endl;
        ptree errorstroke = it->second.get_child("errorstroke");
        for (ptree::iterator iter = errorstroke.begin(); iter != errorstroke.end(); ++iter) {
            std::string key = iter->first;
            std::cout << iter->first << std::endl;
            std::cout << iter->second.data() << std::endl;
        }
    }

    // second way: using boost foreach feature
//    BOOST_FOREACH(ptree::value_type &v, errortype){
//        ptree& childparse = v.second;
//        std::cout << childparse.get<std::string>("errortype") << std::endl;
//        ptree errorstroke = childparse.get_child("errorstroke");
//        BOOST_FOREACH(ptree::value_type& w, errorstroke){
//            std::cout << w.first << std::endl;
//            std::cout << w.second.data() << std::endl;
//        }
//    }

    /*
     101
     A0001
     0
     0.2
     1
     0.3
     A0021
     0
     0.2
     1
     0.3
     */

    return 0;
}

2016-03-17 C++ , JSON , 经验总结 , rapidjson , boost

中国科技馆一日游

早上去的时候一大群熊孩子在外面排队吓得我差点想要放弃,其实后来才发现到的时候没有开馆,排了一会儿队就进去了,还是很快的。其实这个地方还只适合亲子去游玩,如果真的高中都毕业了,真的看到没有意思了,涉及到的一些物理,化学小道具都是课本上曾经存在过的实验。如果有机会未来带小孩来玩一玩还是挺不错的。

进门就能看到这只巨大的恐龙化石。

恐龙化石

去的时候直接从顶层往下逛的,馆中走道还有不少奥运的雕塑。

奥运雕塑1

奥运雕塑2

在上几层物理展馆中还是有不少有趣的玩意儿的,没拍多少照片,让我驻足的有如下的傅科摆,曾经屋里课本上学单摆的时候有看到过。当然傅科摆也间接地证明了地球的自转。物理那块区域的电生磁,磁生电,光等等区都是挺有趣的。

傅科摆

古代计时工具—-日晷。

日晷1

日晷2

最后走的时候在一层见到了很多中国古代天文,地理,木工等等的仪器和小工具,给我印象深刻的就是这个鲁班锁,用6块切割好的木块能够拼接成如图的形状。

鲁班锁


2016-03-12 经验总结 , beijing , travel , 游记

Goodbye Picasa

Google Photos 官网:http://googlephotos.blogspot.com/

Picasa Resources : https://sites.google.com/site/picasaresources/Home/Picasa-FAQ

这个网站整理了 Google Picasa Help Forum 中的很多问题,也解决了困惑我很久的问题,比如 新 Google Photos 中相册的排序问题,比如 Google Photos 中分享出去照片自定义大小的问题,比如 Picasa Web Album 关闭之后的问题。

总之有关从 Picasa 平稳迁移到 Google Photos 的很多问题基本都能找到解决方案。

还有一个 Top Contributor 自己的网站 : http://picasageeks.com/ 也是很棒,总结了各种经验。

虽然 Google 关闭 Picasa 来看,对长期使用 Picasa 的老用户来说是件悲痛的事情,就像当时 Google 关闭 Google Reader 一样。但是多少年过去了,可能新用户根本不知道曾经有一个 Google Reader 存在过。从公司的角度看 关闭 Picasa 一心 Google Photos 当然也无口厚非,集中一心把一款产品打造好。只是从 Picasa 到 Google Photos 走得太快,以至于 Picasa Web Album 很多很实际的功能 Google Photos 一个都没有。而 Google Photos 一直在宣传的功能 Picasa 却很早就就拥有。这里本不想多说却还是依然写了这么多。

转到 Google Photos 本身这个产品,如果是新用户并且是移动设备使用时长较多的话,它本身是一款非常棒的产品: 1. 全备份(日期排序) 2. 简单修图工具 3. 相册以及好用的分享工具。 单就这三点已经完全满足一个相册应该具备的功能了。而反过来真是因为在移动设备上的简单,以及没有对老用户的照顾,Google Photos 中的时间线,相册管理远远不及 Picasa。但是细想原本这两款产品针对的用户就是不一样的。

  • Picasa 这一款产品是一款云端相册,用来提供给用户分享照片,因此重在 Web ,以及相册管理

  • Google Photos 私人相册,云端相册,重在移动,重在备份,虽然也有分享功能却很弱。上面 Picasa Geeks 网站上有篇文章写得好,列举了 Google Photos 没有的功能。在 Web 上,缺乏排序功能,分享设置只有 Private 和 Public 两个选项,而 Picasa Web Album 有 Public,Limited(Anyone with link), Limited(Listed People), Private 四个选项,而这4个选项和 Google Drive 文件分享类似。希望 Google Photos 之后会把这些功能都添加上吧。

总之事情已经这样,结局无法改变,现在提前去适应一下 Google Photos 也好,不至于到时候慌乱。我关注的事情如下:

图片分享及直链

在之前的文章中我都是使用的 Picasa Web Album 分享出来的图片链接,Picasa 提供的免费无限图床真是赞到家,不仅没有流量限制,还能自定义大小。

比如下面两张照片,通过修改 s144-Ic42 参数就能够变换图片的大小,当然具体参数可以从这里 查到。最常用的可能就是改 s0 获得原图了吧。

https://lh3.googleusercontent.com/-1vVMbu8s7d8/VlVQy4J3bDI/AAAAAAAA2vo/Npd_MTH-yLc/s144-Ic42/150724-pluto-hires.jpg

https://lh3.googleusercontent.com/-1vVMbu8s7d8/VlVQy4J3bDI/AAAAAAAA2vo/Npd_MTH-yLc/s800-Ic42/150724-pluto-hires.jpg

在 Picasa 关闭之后获取直链成为一个问题,我在 StackOverflow 上面的提问也没有任何实质性的解决。不过在后来的使用过程中发现,将照片分享到 Google+ ,这时 Google 会产生一个直接的图片 URL,点击看图片,并右击复制图片链接,就可以获取和 Picasa 分享类似的链接。

相册及分享

这要从很久很久以前说起,我原先的照片管理一直依照相册来管理,比如今天可能拍了很多照片,我会以 日期-活动 ,例如 160311-Event 来命令相册然后通过合适的分享途径分享出去,如果我想使用某张照片到博客中,获取直链并添加到博客配图即可。可是在 Google+ Photos 时代,Google 就彻底搞乱了我的相册管理方法。Picasa 中被莫名其妙的添加了很多的相册。自此之后相册管理体系彻底崩溃,没有了清晰的相册管理,现在我已经不管相册了,按照 Google Photos 给我的时间流排布照片,适当的时候将图片添加到相册中。其他时候基本上放任 Google Photos 自己备份。

在 Google Photos App 中即使我想分享一个相册我首选的也是讲照片内容传到 Google+ ,并不会优先使用 Google Photos 的分享功能,所以至今为止,我的 Share 相册中也只有当时测试使用过的一个相册。

测试帖如上

关于容量

可能让我唯一开心一点的就是 Picasa 到 Google+ Photos 到 Google Photos 的容量变成了无限大。其实听到这个消息的时候,我的相册容量已经到到了10G,当时正愁怎么办呢。随之后面的改变就已经很吸引人了,从 Google+ 时代的 2048*2048 像素以下不算空间,到现在 Google Photos 的16MP 下不算空间,几乎已经是无限容量的节奏了,我手机最高像素也没这么大。。

最后的吐槽,真的不想管这个了,改来改去太累了。


2016-03-11 Google , Picasa , Google Photos , Blogger , 经验总结 , 产品体验

排序算法

排序算法复习,插入排序,选择排序,冒泡排序,希尔排序,归并排序,堆排序,快排。

关于排序算法的 stable 稳定性, 排序保存原始数据顺序则稳定,否则不稳定。

关于原址排序,算法需要额外的空间计算或者保存数据, in-place sorting ,归并排序为非原址排序 not-in-place sorting。

关于时间复杂度,归并排序,堆排序,快排有相对较快的速度 O(n*lg(n))

插入排序

每次取一个元素插入正确的位置,适合少量元素。对于未排序的数据,从已排序的序列中从后向前扫描,找到相应的位置插入,实现上通常使用 in-place 排序,只需要使用额外 O(1) 空间,但是因为插入正确的位置之后,需要反复移动已经排序的序列,为新元素提供插入空间,因而比较费时。

一般来说,插入排序都采用in-place在数组上实现。具体算法描述如下:

  1. 从第一个元素开始,该元素可以认为已经被排序
  2. 取出下一个元素,在已经排序的元素序列中从后向前扫描
  3. 如果该元素(已排序)大于新元素,将该元素移到下一位置
  4. 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置
  5. 将新元素插入到该位置后
  6. 重复步骤2~5

Algorithm

for i = 2:n,
    for (k = i; k > 1 and a[k] < a[k-1]; k--)
        swap a[k,k-1]
    → invariant: a[1..i] is sorted
end

Java 版本:

static void insert_sort(int[] array) {
    for(int i = 1; i < array.length; ++i) {
        int cur = array[i];
        for(int j = i - 1; j >= 0 && array[j] > cur; j--) {
            array[j + 1] = array[j];
            array[j] = cur;
        }
    }
}

Properties

  • Stable
  • O(1) extra space
  • O(n^2^) comparisons and swaps
  • Adaptive: O(n) time when nearly sorted
  • Very low overhead

Example

list = [4,6,2,5,1,3,0,4,8,1,5,3,6]

# 升序
# 从第二个元素开始,每次循环将前i个元素排序
for i in range(1,len(list)):
    value = list[i]
    j = i-1
    # 将第i个元素的位置腾出
    while j >= 0 and list[j]>value:
        list[j+1] = list[j]
        j=j-1
    # 在排完序的 list[0...i] 中将值插入合适位置
    list[j+1]=value

# 降序
list = [4,6,2,5,1,3,0,4,8,1,5,3,6]

for i in range(len(list)-1, -1, -1):
    value = list[i]
    j=i+1
    while j<len(list) and value < list[j]:
        list[j-1] = list[j]
        j=j+1
    list[j-1]=value

print(list)

选择排序

每次选取数组中最小(或者最大)的元素,并将其与未排序数组中首元素交换,依次进行。

选择排序拥有最小的交换次数,适合交换元素开销比较大的情况。选择排序其他情况都比较低效。

Algorithm

for i = 1:n,
    k = i
    for j = i+1:n, if a[j] < a[k], k = j
    → invariant: a[k] smallest of a[i..n]
    swap a[i,k]
    → invariant: a[1..i] in final position
end

Properties

  • Not stable
  • O(1) extra space
  • Θ(n^2^) comparisons
  • Θ(n) swaps
  • Not adaptive

Example

list = [4,6,2,5,1,3,0,4,8,1,5,3,6]

for i in range(0,len(list)):
    k = i
    for k in range(i+1, len(list)):
    # 没有完全按照定义写,不过这样交换的开销更大。
        if list[k] < list[i]:
            list[i], list[k] = list[k], list[i]

print(list)

Java 版:

static void selection_sort(int[] array) {
	if(array.length <= 1) return;
	for(int i = 0; i < array.length; i++) {
		int smallest = i;
		for(int j = i + 1; j < array.length; j++) {
			if (array[j] < array[smallest]) {
				smallest = j;					
			}
		}
		int temp = array[i];
		array[i] = array[smallest];
		array[smallest] = temp;
	}
}

冒泡排序

反复交换相邻未按次序排列的元素,一次循环之后最大的元素到数组最后。

Algorithm

for i = 1:n,
    swapped = false
    for j = n:i+1, 
        if a[j] < a[j-1], 
            swap a[j,j-1]
            swapped = true
    → invariant: a[1..i] in final position
    break if not swapped
end

Properties

  • Stable
  • O(1) extra space
  • O(n^2^) comparisons and swaps
  • Adaptive: O(n) when nearly sorted

Example

def bubble_sort_1(list):
    for i in range(0, len(list)):
        for j in range(1, len(list)-i):
            if list[j-1] > list[j]:
                list[j-1], list[j] = list[j], list[j-1]

def bubble_sort_2(list):
    for i in range(0, len(list)):
        swap = False
        for j in range(len(list)-1, i, -1):
            if list[j-1] > list[j]:
                list[j-1], list[j] = list[j], list[j-1]
                swap = True
        if swap is False:
            break

相较于第一种直接冒泡,设定标志优化冒泡。

Java 版

static void bubble_sort(int[] arr) {
	int i, j, temp, len = arr.length;
	for (i = 0; i < len - 1; i++)
		for (j = 0; j < len - 1 - i; j++)
			if (arr[j] > arr[j + 1]) {
				temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
}

希尔排序

分组插入排序,将数组拆分成若干子序列,由增量决定,分别进行直接插入排序,然后缩减增量,减少子序列,最后对全体元素进行插入排序。插入排序在基本有序的情况下效率最高。

Algorithm

h = 1
while h < n, h = 3*h + 1
while h > 0,
    h = h / 3
    for k = 1:h, insertion sort a[k:h:n]
    → invariant: each h-sub-array is sorted
end

Properties

  • Not stable
  • O(1) extra space
  • O(n^3/2^) time as shown (see below)
  • Adaptive: O(n·lg(n)) time when nearly sorted

Example

list = [4,6,2,5,1,3,0,4,8,1,5,3,6]

def insertion_sort(k,h,n):
    """
    :param k: group count
    :param h: step length
    :param n: total
    :return:
    """
    for i in range(k+h, n, h):
        value = list[i]
        j = i-h
        while j >= 0 and list[j]>value:
            list[j+h] = list[j]
            j=j-h
        list[j+h]=value


h = 1       # step length
while h < len(list):
    h = 3*h +1

while h > 0:
    h = int(h / 3)
    for k in range(0, h):           # devide into k groups
        insertion_sort(k, h, len(list))

print(list)

归并排序

典型的分治算法,将数组分成两个子数组,在子数组中继续拆分,当小组只有一个数据时可认为有序,之后合并,所以重点就到了合并有序数组。

Algorithm

# split in half
m = n / 2

# recursive sorts
sort a[1..m]
sort a[m+1..n]

# merge sorted sub-arrays using temp array
b = copy of a[1..m]
i = 1, j = m+1, k = 1
while i <= m and j <= n,
    a[k++] = (a[j] < b[i]) ? a[j++] : b[i++]
    → invariant: a[1..k] in final position
while i <= m,
    a[k++] = b[i++]
    → invariant: a[1..k] in final position

Properties

  • Stable
  • Θ(n) extra space for arrays (as shown)
  • Θ(lg(n)) extra space for linked lists
  • Θ(n·lg(n)) time
  • Not adaptive
  • Does not require random access to data

Example

From wiki

from collections import deque

def merge_sort(lst):
    if len(lst) <= 1:
        return lst

    def merge(left, right):
        merged,left,right = deque(),deque(left),deque(right)
        while left and right:
            merged.append(left.popleft() if left[0] <= right[0] else right.popleft())  # deque popleft is also O(1)
        merged.extend(right if right else left)
        return list(merged)

    middle = int(len(lst) // 2)
    left = merge_sort(lst[:middle])
    right = merge_sort(lst[middle:])
    return merge(left, right)

堆排序

利用最大堆的性质,堆性质,子结点的值小于父节点的值。每次将根节点最大值取出,剩下元素进行最大堆调整,依次进行。

Algorithm

# heapify
for i = n/2:1, sink(a,i,n)
→ invariant: a[1,n] in heap order

# sortdown
for i = 1:n,
    swap a[1,n-i+1]
    sink(a,1,n-i)
    → invariant: a[n-i+1,n] in final position
end

# sink from i in a[1..n]
function sink(a,i,n):
    # {lc,rc,mc} = {left,right,max} child index
    lc = 2*i
    if lc > n, return # no children
    rc = lc + 1
    mc = (rc > n) ? lc : (a[lc] > a[rc]) ? lc : rc
    if a[i] >= a[mc], return # heap ordered
    swap a[i,mc]
    sink(a,mc,n)

Properties

  • Not stable
  • O(1) extra space (see discussion)
  • O(n·lg(n)) time
  • Not really adaptive

Example

def max_heapify(lst, i):
    """
    下标为i的根节点调整为最大堆
    :param lst:
    :param i:
    :return:
    """
    l = 2 * i + 1
    r = 2 * (i + 1)
    if l < len(lst) and lst[l] > lst[i]:
        largest = l
    else:
        largest = i
    if r < len(lst) and lst[r] > lst[largest]:
        largest = r
    if largest != i:
        lst[i], lst[largest] = lst[largest], lst[i]
        max_heapify(lst, largest)


def build_max_heap(lst):
	"""
    建立最大堆
    """
    for i in range((len(lst)-1)/2, 0, -1):
        max_heapify(lst, i)


def heap_sort(lst):
    build_max_heap(lst)
    ret = []
    for i in range(len(lst)-1, -1, -1):
        ret.append(lst[0])
        lst.remove(lst[0])
        max_heapify(lst, 0)
    return ret

L = [16, 4, 10, 14, 7, 9, 3, 2, 8, 1]
R = heap_sort(L)
print(R)

快排

从数列中挑出元素,将比挑出元素小的摆放到前面,大的放到后面,分区操作。然后递归地将小于挑出值的子数列和大于的子数列排序。

Algorithm

# choose pivot
swap a[1,rand(1,n)]

# 2-way partition
k = 1
for i = 2:n, if a[i] < a[1], swap a[++k,i]
swap a[1,k]
→ invariant: a[1..k-1] < a[k] <= a[k+1..n]

# recursive sorts
sort a[1..k-1]
sort a[k+1,n]

Properties

  • Not stable
  • O(lg(n)) extra space (see discussion)
  • O(n^2^) time, but typically O(n·lg(n)) time
  • Not adaptive

Example

list_demo = [2,8,7,1,3,5,6,4]

def partition(lst, p, r):
    """
    划分
    :param lst: 待排序数组
    :param p: 起始下标,子数组第一个元素
    :param r: 终止下标,子数组最后一个元素 r < len(lst)
    :return: 划分结果下标
    """
    if r >= len(lst) or p < 0:
        return
    x = lst[r]
    i = p - 1
    for j in range(p, r):
        if lst[j] <= x:
            i += 1
            lst[i], lst[j] = lst[j], lst[i]
    lst[i+1], lst[r] = lst[r], lst[i+1]
    return i + 1


def quick_sort(lst, p, r):
    if p < r:
        q = partition(lst, p, r)
        quick_sort(lst, p, q-1)
        quick_sort(lst, q+1, r)

quick_sort(list_demo, 0, len(list_demo)-1)
print(list_demo)

分配排序

箱排序

箱排序也称桶排序(Bucket Sort),其基本思想是:设置若干个箱子,依次扫描待排序的记录R[0],R[1],…,R[n-1],把关键字等于k的记录全都装入到第k个箱子里(分配),然后按序号依次将各非空的箱子首尾连接起来(收集)。对于有限取值范围的数组来说非常有效,时间复杂度可以可达 O(n). 例如给人年龄排序,人的年龄只能在0~100多之间,不可能有人超过200,适用桶排序。

  • 箱排序中,箱子的个数取决于关键字的取值范围。 若R[0..n-1]中关键字的取值范围是0到m-1的整数,则必须设置m个箱子。因此箱排序要求关键字的类型是有限类型,否则可能要无限个箱子。

  • 箱子的类型应设计成链表为宜 一般情况下每个箱子中存放多少个关键字相同的记录是无法预料的,故箱子的类型应设计成链表为宜。

  • 为保证排序是稳定的,分配过程中装箱及收集过程中的连接必须按先进先出原则进行。

桶排序的平均时间复杂度是线性的,O(n), 但是最坏的情况可能是 O(n^2)

基数排序

基数排序是非比较排序算法,算法的时间复杂度是O(n). 相比于快速排序的O(nlgn),从表面上看具有不小的优势.但事实上可能有些出入,因为基数排序的n可能具有比较大的系数K.因此在具体的应用中,应首先对这个排序函数的效率进行评估.

基数排序的主要思路是,将所有待比较数值(注意,必须是正整数)统一为同样的数位长度,数位较短的数前面补零. 然后, 从最低位开始, 依次进行一次稳定排序.这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列.

这个算法的难度在于分离数位,将分离出的数位代表原元素的代表, 用作计数排序.但是分离数位不能脱离原来的数字,计数排序的结果,还是要移动原元素.

注意计数排序的元素数值与位置的联系,引申到基数排序的从元素得到中间值然后与位置的联系.

枚举排序

通常也被叫做秩排序(Rank Sort) ,算法基本思想是:对每一个要排序的元素,统计小于它的所有元素的个数,从而得到该元素在整个序列中的位置,时间复杂度为O(n^2)

reference


2016-03-09 C++ , Sort , Algorithm , python

中国美术馆一日游

本来打算去的自然博物馆,可无奈去官网看的时候已经没有预订票,于是就去了中国美术馆。北京来了快6年而似乎该去的博物馆都尚未能去,想接下来的时间里能不能用自己的脚都走遍,用自己的眼睛都看遍。借用网友的一句话,“不能也不敢说自己懂艺术,只是单纯的喜欢,喜欢美,喜欢不同的表达,喜欢安静的可以欣赏思想与灵感的地方”。上一次画画还要追溯到初中,近十年时间没有接触任何艺术,也没有接受任何艺术形式的熏陶。在最初进入的时候确实是一头雾水,幸而我们这一次去的时候正好是中华民族大团结全国美术作品展,至少还有一个主题让我们可以想象。虽然进门看到如此主旋律的主题有点失望,然而从一个展厅进到另一个展厅,除了进门见到的习大大有点恶心之外,渐渐就开始敬佩起这些画家。

喜欢画画的人可以经常上美术馆的官网看看,不定期的会举办一些展览。

下面是三幅震撼到我的画:

朝鲜族

这原本是一副很大的画,这里的两位只是画的一小部分,记得画的左边还有一位在回眸,右边也还有两位。

一家人

远看真的像是一副照片,细节部分也是栩栩如生,近看脸部的文理,光影的处理着实让我震惊了。

口爱的小狗

被萌到的小狗,哈士奇?不认识。

其他令我印象深刻的画作:

塔吉克新娘 官网

美术馆馆藏作品链接

很遗憾,写这篇文章的时候中途忘记保存了,漏掉了一些内容,现在凭感觉补了一些,却再也找不到当时的感觉,虽然只仅仅相隔一天。由此可见随时保存的重要性了。


2016-03-05 经验总结 , beijing , travel , 游记

几道 C++ 问题

Question 6

Method overriding is key to the concept of Polymorphism. 覆盖是多态的核心 True

多态可以概括成“一个接口,多个方法”,运行时决定调用函数。C++ 多态利用虚函数实现,虚函数允许子类重新定义方法,子类重新定义方法的做法称为“覆盖”,或者重写。(直接覆盖成员函数和覆盖虚函数,只有重写了虚函数的才能算作是体现了C++ 多态性)

封装可以使得代码模块化,继承可以扩展已存在的代码,而多态的目的则是为了接口重用。也就是说,不论传递过来的究竟是那个类的对象,函数都能够通过同一个接口调用到适应各自对象的实现方法。

最常见的用法就是声明基类的指针,利用该指针指向任意一个子类对象,调用相应的虚函数,可以根据指向的子类的不同而实现不同的方法。如果没有使用虚函数的话,即没有利用C++多态性,则利用基类指针调用相应的函数的时候,将总被限制在基类函数本身,而无法调用到子类中被重写过的函数。因为没有多态性,函数调用的地址将是一定的,而固定的地址将始终调用到同一个函数,这就无法实现一个接口,多种方法的目的了。

#include <iostream>  
using namespace std;  

class A  
{  
public:  
    void foo()  
    {  
        printf("1\n");  
    }  
    virtual void fun()  
    {  
        printf("2\n");  
    }  
};  
class B : public A  
{  
public:  
    void foo()  
    {  
        printf("3\n");  
    }  
    void fun()  
    {  
        printf("4\n");  
    }  
};  
int main(void)  
{  
    A a;  
    B b;  
    A *p = &a;  
    p->foo();  
    p->fun();  
    p = &b;  
    p->foo();  
    p->fun();  
    return 0;  
}  

输出
1 2
1 4

基类指针指向基类对象,调用基类函数;基类指针指向子类对象, p->foo() 指针是个基类指针,指向是一个固定偏移量的函数,因此此时指向的就只能是基类的foo()函数的代码了,因此输出的结果还是1。而p->fun() 指针是基类指针,指向的fun是一个虚函数,由于每个虚函数都有一个虚函数列表,此时p调用fun()并不是直接调用函数,而是通过虚函数列表找到相应的函数的地址,因此根据指向的对象不同,函数地址也将不同,这里将找到对应的子类的fun()函数的地址,因此输出的结果也会是子类的结果4。

上面例子,还有一种问法

B *ptr = (B *)&a;  ptr->foo();  ptr->fun();

输出
3 2

从原理上来解释,由于B是子类指针,虽然被赋予了基类对象地址,但是ptr->foo()在调用的时候,由于地址偏移量固定,偏移量是子类对象的偏移量,于是即使在指向了一个基类对象的情况下,还是调用到了子类的函数,虽然可能从始到终都没有子类对象的实例化出现。而ptr->fun()的调用,可能还是因为C++多态性的原因,由于指向的是一个基类对象,通过虚函数列表的引用,找到了基类中fun()函数的地址,因此调用了基类的函数。由此可见多态性的强大,可以适应各种变化,不论指针是基类的还是子类的,都能找到正确的实现方法。

“隐藏”是指派生类的函数屏蔽了与其同名的基类函数,规则如下: (1)如果派生类的函数与基类的函数同名,但是参数不同。此时,不论有无virtual 关键字,基类的函数将被隐藏(注意别与重载混淆)。 (2)如果派生类的函数与基类的函数同名,并且参数也相同,但是基类函数没有virtual 关键字。此时,基类的函数被隐藏(注意别与覆盖混淆)。

纯虚函数,virtual ReturnType Function()= 0;

C++支持两种多态性:编译时多态性,运行时多态性。

  • 编译时多态性:通过重载函数实现
  • 运行时多态性:通过虚函数实现。

虚函数是在基类中被声明为virtual,并在派生类中重新定义的成员函数,可实现成员函数的动态覆盖(Override) 包含纯虚函数的类称为抽象类。由于抽象类包含了没有定义的纯虚函数,所以不能定义抽象类的对象。

Q16

Which objected oriented design concept is key to the factory design pattern?

Inheritance

Q23

Which of the following describe the C++ programming language?

Compiled Declarative

Q25

The friend keyword is used to grant access to private class members. True

  1. 友元函数:普通函数对一个访问某个类中的私有或保护成员。
  2. 友元类:类A中的成员函数访问类B中的私有或保护成员。

友元函数

friend <类型><友元函数名>(<参数表>);  

友元函数只是一个普通函数,并不是该类的类成员函数,它可以在任何地方调用,友元函数中通过对象名来访问该类的私有或保护成员

#include <iostream>
using namespace std;

class Base{
public:
    Base(int _data):data(_data){};

    friend int getData(Base& _base);
private:
    int data;
};

int getData(Base& _base){
    return _base.data;
}

int main() {
    Base b(2);
    std::cout << getData(b) << endl;
    return 0;
}

友元类

friend class <友元类名>;

友元类的声明在该类的声明中,而实现在该类外。

#include <iostream>
using namespace std;

class Base{
public:
    Base(int _data):data(_data){};

    friend class FClass;
private:
    int data;
};

class FClass{
public:
    int getData(Base _base){
        return _base.data;		// call friend class private data
    }
};

int main() {
    Base b(2);
    FClass c;
    cout << c.getData(b) << endl;
    return 0;
}

Q38

Choose word or words to describe UML language.

  • Picture
  • Relational
  • Interpreted
  • Abstract
  • None of the answers are correct.

只有 Picture 正确

The Unified Modeling Language (UML) is a general-purpose, developmental, modeling language in the field of software engineering, that is intended to provide a standard way to visualize the design of a system.

为啥没有 Relation 有点神奇~ UML 图能够看出类与类的关系的啊

Q40

Generalization is used by UML to describe Inheritance and the deriving of one class from another.

Generaliztion 是从属关系,可以表示继承,或者派生

http://www.uml-diagrams.org/generalization.html

Q44

#include <iostream>

void f0(int& sum){
    sum = 3+2*7;
}

int main() {
    int *p, sum = 0;
    (*p)++;
    sum = sum * 3;
    f0(sum);
    std::cout << sum << ",";
    return 0;
}

(*p)++ 一行有问题

具体问题内容请看这里


2016-03-03

Nexus 6 刷机及电信 3G/4G 破解

adb and fastboot

从 Android 开发官网下载 Android SDK,从事过 Android 开发的应该知道 adb 和 fastboot 工具,在完整 SDK 中这两个工具在 platform-tools 文件夹下。如果想要方便的使用这两个工具,可以将文件路径加入到系统环境变量中,这样以后就可以在任何目录使用 adb 和 fastboot 命令。

flash factory image

救砖,或者在 recovery 下没有备份又无法开机的情况下只能刷回原厂镜像救砖机。因此折腾需谨慎,刷机前请一定使用 recovery 备份系统及数据。可以从 Google 官网下载镜像。

下载镜像

https://developers.google.com/android/nexus/images#shamu

解压之后应该会有如下文件

bootloader-shamu-moto-apq8084-71.15.img  2016/01/06  07:19        10,636,288
flash-all.bat                            2016/01/06  07:19               985
flash-all.sh                             2016/01/06  07:19               856
flash-base.sh                            2016/01/06  07:19               814
image-shamu-mmb29q.zip                   2016/01/06  07:19     1,009,825,337
radio-shamu-d4.01-9625-05.32+fsg-9625-02.109.img      2016/01/06  07:19       118,272,512

解锁bootloader

解锁 bootloader 会抹去手机一切内容,需谨慎,总之只需要一句命令

 fastboot oem unlock

然后利用音量键及电源键来确认解锁 bootloader, 之后运行

 fastboot reboot

重启手机。

刷镜像

  1. 关机并进入 fastboot 也就是 bootloader模式,在关机状态下,同时按住“电源键”+“音量下”
  2. 数据线连接手机与电脑,在驱动安装正确之后
  3. 执行 flash-all.bat (Windows 下) 或者 flash-all.sh (MAC或者 Linux 下)
  4. 等待执行完毕,手机恢复成出厂镜像

root

root 工具及教程来自 @Chainfire ,在此由衷的感谢他。

  • 下载ZIP工具
  • 解压文件,并将手机进入 bootloader/fastboot 模式
  • 连接数据线,并运行 root-windows.bat (Windows 下)或者 chmod +x root-linux.sh 并运行 root-linux.sh (Linux下) Mac下同Linux

Recovery

第三方的 Recovery 有以下的功能:

  • Wipe your phone’s data (Factory reset) and cache
  • Make, restore and manage backups of your phone’s operating system and software
  • Mount, unmount and format your phone’s internal as well as external storage partitions
  • Install a custom ROM or application from a zip file to your phone
  • Wipe Dalvik cache and battery statistics
  • Make logs for error reporting and debugging

刷入 recovery

  • 官网 下载 Nexus 6 TWRP 的 recovery 文件
  • 进入 bootloader/fastboot 模式
  • 执行以下命令

    fastboot flash recovery recovery.img

    recovery.img 即下载的 Recovery 镜像。

  • 利用音量键选择 recovery ,点击电源键选择,可以进入 “Recovery Mode”.

安装完 recovery 之后就能够快速的备份系统,恢复出厂设置,恢复备份数据,刷入新ROM,刷入ZIP

kernel

一张图解释什么是 kernel

android kernel

Nexus 6 第三方的 kernel 有很多选择 比如 franco.kernel,这里推荐 ElementalX,有如下功能

  • Easy installation and setup with Aroma installer
  • overclock/underclock CPU
  • user voltage control
  • Advance color control
  • MultiROM support
  • optional USB fastcharge
  • optional sweep2wake and doubletap2wake
  • optional sweep2sleep
  • sound control
  • init.d support
  • NTFS r/w and exFAT support
  • option to disable fsync
  • adjustable vibration
  • does not force encryption

安装 ElementalX kernel

  • ElementalX 官网下载,并保存到手机
  • 进入 Recovery Mode
  • 刷入 ZIP ,选择下载的文件,安装

Nexus 6 破解电信3G/4G

6.0.1 (MMB29Q) 有效

下载文件,教程中需要用的软件及文件 https://yunpan.cn/cxCaHyqkKPwg9 提取码 db02

  • DFS
  • QPST

还有这里

  • moto x qc diag interface - 64bit.zip
  • carrier_policy.xml

具体步骤参考nexus6破解电信教程

简单来说破解4G步骤:

  • 用QPTS工具里面的EFS Explorer, 添加/policyman/carrier_policy.xml,nexus6 默认没有这个文件
  • 进入BP TOOLS模式,安装好后,必须确认好你的设备管理器 端口(COM和LPT)中BP驱动的端口号
  • 从开始菜单中,打开QPST configuration
  • 先点Ports标签,然后点Add New Prot 输入你的设备端口号
  • 点StartClient菜单中的EFS Explorer选项
  • 连接上手机后,在EFS 根目录创建policyman目录
  • 把carrier_policy.xml(见附件)拖进policyman目录中
  • 完成后重启手机

破解完成后请在手机拨号面板那输入 *#*#4636#*#* 看下首选网络是不是LTE/GSM/CDMA auto(prl)

参考


2016-03-01 Android , Nexus 6

Google+

最近文章

  • celery best practice 不要使用数据库作为 AMQP Broker 随着worker 的不断增多可能给数据库IO和连接造成很大压力。 Docker 上很多 相关的镜像。
  • Git 使用过程中遇到的小技巧 Git 使用过程中遇到的小技巧,平时没有 commit, merge, branch 用的那么勤快,但是需要时也需要查看一下,因此记录一下,以免忘记。
  • URL 短域名 逛博客看到别人在讨论短URL的设计实现,然后偶然间发现了 GitHub 曾经推出1过的短域名服务 Git.io https://github.com/blog/985-git-io-github-url-shortener ↩
  • 目录 /usr/local vs /opt 的区别 今天看 JDK 的路径突然发现我在两台机子上,一台装在了 /usr/local/ 目录下,而我自己的 Mint 装在了 /opt/ 目录下。感觉对 Linux 目录结构还需要增加了解,就Google了一下。
  • SQLAlchemy session 使用问题 在更改 SQLAlchemy Session 从每次请求都创建到共享同一个 Session 之后遇到了如下问题: