比特股源码阅读笔记(四)

前面的笔记本提到,maybe_produce_block函数是witeness 插件尝试生成新块的函数。该函数会先执行一些必要的检查,如本地机器中是否保存有该轮见证人的私钥,时间是否正确。该函数依赖于前面提到的chain::database 类型的全局db对象提供的接口。主要接口有以下几个:
1、get_slot_time
2、get_slot_at_time
3、head_block_time
4、get_secheduled_witness
5、witness_participation_rate
6、generate_block
以上接口的功能,顾名思义就可以了,后期有机会在详细分析下,这里先专注于当前函数的逻辑。

按照bitshares的规则,每3秒就要产生一个块,见证人轮流产生新块,如果一个见证人由于意外而不能按时产生区块则需要跳过此见证人,并由排在他后面的一个见证人来产生区块。

schedule_production_loop 每秒都唤醒一次,并最后进入到maybe_produce_block中,而在maybe_produce_block中,只有当下个区块的正常产生时间与当前时间之间的差值在500ms以内,才会调用generate_block产生区块。

llabs((scheduled_time - now).count()) > fc::milliseconds( 500 ).count()

从这个函数中不能发现,如果一个见证人由于意外不能产生新的区块时,程序会如何处理。chain::database中的get_scheduled_witness 函数

witness_id_type database::get_scheduled_witness( uint32_t slot_num )const
{
    const dynamic_global_property_object& dpo = get_dynamic_global_properties();
    const witness_schedule_object& wso = witness_schedule_id_type()(*this);
   uint64_t current_aslot = dpo.current_aslot + slot_num;
   return wso.current_shuffled_witnesses[ current_aslot % wso.current_shuffled_witnesses.size() ];
}

只是简单地返回见证人数组中与slot_num对应的元素,而并没有考虑到元素所代表的见证人是否正常工作。
slot的含义是将要产生的第几个区块,比如 slot=1就代表下一个区块,slot==2就代表下下个区块。

程序到底如何应对见证人不能正常出块的情况呢?在

database::update_witness_schedule()

中我们看到似乎有相关的代码在打乱wso.current_shuffled_witnesses这人数组的顺序。那么我们的猜测到底正不正确呢?由于我们目前关注的控制流,还没有流到这个函数中,先暂时搁置这个问题。

[leetcode] Add Two Numbers 总结

今天是周末比较空闲,无聊的时候,打开leetcode,随便找到了这个题目,本以为自己能一次就通过,可后来没有。其中的曲折如下:
1、没有仔细审题,输入的单链表是从最低位开始的,我以为是从最高位开始的,所以先自己写了就地反转单链表的方法,想先反转输入的两个链表,然后相加,最后再反转。
2、自己太小瞧就地反转单链表的难度了,总以为自己能一次就写出来,可是经过实践,凭自己直觉写出来的代码,要不死循环,要不会发生指针丢失,最后得到一个空的链表,还会造成内存泄漏。虽然后来经过几次修改,总算得到了正确的代码,可是也花费接近一个小时的时间。
3、在好不容易改好就地反转单链表过后,发现自己审错题了,根本用不到反转单链表。不过这个好改,改完后提交还是不行。
4、检测发现出错的地方在处理进位时,没有考虑到最后一位加法有进位的情况,我只考虑到输入的两个数字位数相等的情况下,最后一位可能会有进位。在输入的两个数字位数不相等的情况下,在最后一位,仍然可能会有进位。修改方法是将处理最后一位进位的代码移动到函数的最后。

总结如下:
1、自己的编程基础还是不过关,对像就地反转链表这样的基本算法的代码记不牢固,以后对这种基础代码我觉得自己应该全部自己从头写一遍以达到真正理解代码的目的,然后记下相应的代码。
2、小心驶得万年船,看起来再简单的事情,也需要仔细认真地读完相应的要求,千万不能想当然。
3、最后提交的代码仍然不是最精简的代码,可以去掉就地反转链表的代码,可是一想到自己写得这么辛苦,确实舍不得删除,就保留下来了。 继续阅读[leetcode] Add Two Numbers 总结

jupyter notebook 安装与试用

jupyter notebook 是基于浏览器的代码文档笔记工具。早就听人不断安利使用它了,这个周末特意试用了一下,感觉还不错,至少我很喜欢。
一、安装。
我使用的是win10 64位系统,先安装python 3.6 x64,然后使用pip包管理工具来安装,由于伟大的墙,需要先设置国内的pip镜像来加速,推荐使用中科大的镜像。
创建并编辑%homepath%/pip/pip.ini,使其内容如下:

[global]
index-url = https://mirrors.ustc.edu.cn/pypi/web/simple
format = columns

直接使用windows自带的powershell 或者cmd来运行命令

pip install jupyter

最后会有编码错误,造成安装失败。
解决办法是使用git for windows自带的bash 来运行上述命令,就没有错误了。 继续阅读jupyter notebook 安装与试用

重温排序算法

这两天趁空闲时间比较多,好好复习了下基本的排序算法。排序算法分为两大类,一类是基于比较的排序方法,最好的时间复杂度是O(nLogn),另外一类以计数排序为代表,不需要进行比较,但是一般会占用更多的空间。其实排序算法,那怕是最简单的冒泡排序,如果很久没写过了,也很难一次性写对,更不要说其他的了。经过这次复习,我发现我最快写出来的是归并排序,基本一次写好,运行通过。其次是基数排序或者桶排序、计数排序、冒泡排序,一次修改后通过,堆排序和快速排序需要多次修改尝试。


import random
class solution:
    def bob_sort(self,r):
        for l in range(len(r)-1,1,-1):
            for i in range(l):
                if r[i]>r[i+1]:
                    r[i],r[i+1]=r[i+1],r[i]
        return r
   #快速排序
    def quick_sort(self,ls):
        if len(ls) <2:
            return ls
        l=0
        r=len(ls)-1
        k=ls[0]
        while(l<r): while ls[r]>=k and l<r:
                r=r-1
            ls[l]=ls[r]
            while ls[l]<k and l<r:
                l=l+1
            ls[r]=ls[l]
        ls[l]=k
        if l==0 and r==l:
            l=1
            r=1
        a=self.quick_sort(ls[:l])
        b=self.quick_sort(ls[r:])
        return a+b
   #归并排序
    def merge_sort(self,ls):
        if len(ls)<2:
            return ls
        a=self.merge_sort(ls[:len(ls)//2])
        b=self.merge_sort(ls[len(ls)//2:])
        i=0
        j=0
        r=[]
        while i<len(a) and j <len(b):
            if a[i]<b[j]:
                r.append(a[i])
                i=i+1
            else:
                r.append(b[j])
                j=j+1
        while i<len(a):
            r.append(a[i])
            i=i+1
        while j<len(b):
            r.append(b[j])
            j=j+1
        return r
    #堆排序
    def heap_sort(self,ls):
        if len(ls)<2:
            return ls
        def adjust_heap(i,j,ls):
            while i<j:
                parent=ls[i]
                #print("parent:", parent)
                k=i
                if i*2+2<j: right=ls[i*2+2] #print("right:",right) if right>=parent:
                        ls[i],ls[i*2+2]=ls[i*2+2],ls[i]
                        k=i*2+2
                if i*2+1<j: left=ls[i*2+1] #print("left:", left) if left>=ls[i]:
                        ls[i],ls[i*2+1]=ls[i*2+1],ls[i]
                        k=i*2+1
                if k==i:
                    break
                i=k
        for i in range(len(ls)//2-1,-1,-1):
            adjust_heap(i,len(ls),ls)
            #print(ls)
        for i in range(len(ls)-1,0,-1):
            #print(ls)
            ls[0],ls[i]=ls[i],ls[0]
            adjust_heap(0,i,ls)
        return ls
    #计数排序
    def count_sort(self,ls):
        if len(ls)<2: return ls m=max(ls) n=min(ls) c=m-n+1 d=[0 for i in range(c)] for i in ls: d[i-n]=d[i-n]+1 index=0 for i,j in enumerate(d): while j>0:
                ls[index]=n+i
                index=index+1
                j=j-1
        return ls
    #基数排序
    def radix_sort(self,ls):
        if len(ls)<2: return ls def get_base(base,i,x): while i>0:
                x=x//base
                i=i-1
            return x%base
        def merge_buckets(ls):
            return [i for l in ls for i in l ]
        base=16
        m=max(ls)
        import math
        n=int(math.log(m,base))
        for j in range(n):
            buckets=[[] for i in range(base)]
            for i in ls:
                buckets[get_base(base,j,i)].append(i)
            ls=merge_buckets(buckets)
        return ls
            





sol= solution()
print(sol.bob_sort([1,3,2,6,4,7,8,3,23,565,109]))
print(sol.quick_sort([1,3,2,6,4,7,8,3,23,565,109]))
print(sol.merge_sort([1,3,2,6,4,7,8,3,23,565,109]))
print(sol.heap_sort([1,3,2,6,4,7,8,3,23,565,109]))
print(sol.count_sort([1,3,2,6,4,7,8,3,23,565,109]))
print(sol.radix_sort([1,3,2,6,4,7,8,3,23,565,109]))

bitshares 比特股源码阅读笔记(三)

比特股重节点,也称重钱包,英文名称witness-node,无疑是比特股网络的核心。比特股内盘区块链中的区块生成,就是由见证人运行的witness_node生产的。
witness_node编译为一个单独的可执行文件,其main函数在programs\witness_node 目录下,在main函数当中,我们并不能看到太多有用的信息。因为bitshares-core 项目提供了一个应用框架(application)类,和一些插件接口(plugin)来访问bitshares区块网络和区块链数据库。witness_node实际就是一个启用了witness plugin的application的实例。
application 类位于命名空间graphene::app下,其重要的成员和方法有:
一个指向区块链数据库实例的智能共享指针
一个指向p2p网络节点的智能共享指针
插件的注册,启用,初始化,关闭等功能的接口
客户端访问api的权限设置方法
一个表示本地节点是否同步完毕的信号和方法
appliation 采用了桥接设计模式,以上接口和方法的真实实现其实都在graphene::app::detail::application_impl类当中。重钱包的websocket server 的智能指针就存放于application_impl类当中。

witness_node 的区块产生循环位于libraries\plugins\witness\witness.cpp文件中。witness区块生成循环启动时的堆栈调用过程:main()->node.startup()->application.startup_plugins()->witness_plugin.plugin_startup()-> schedule_production_loop()

schedule_production_loop()中使用到多线程,通过bitshares-fc 提供的基于promise/future的异步通信机制来与新线程通信。bitshares-fc后台是使用boost的多线程实现,只不过自己加了层封装。 schedule_production_loop()异步调用witness_plugin::block_production_loop()生成区块。witness_plugin::block_production_loop()生成区块后,又调用schedule_production_loop(),这样就构成了一个循环。循环周期在一秒左右。
block_production_loop()调用maybe_produce_block()检测是否可以并生成区块。

maybe_produce_block 先检查区块是否已经完成同步,然后检测是否已经到生成新区块的时间,如果是,则再检查当前轮先的见证人私钥是否在本地节点中,检测本地节点正常区块生成率是否高于33%,检测当前时间是否已经比预计的时间晚了500ms,最后生成新的区块并异步广播。

auto block = db.generate_block(
      scheduled_time,
      scheduled_witness,
      private_key_itr->second,
      _production_skip_flags
      );
capture("n", block.block_num())("t", block.timestamp)("c", now);
fc::async( [this,block](){ p2p_node().broadcast(net::block_message(block)); } );

C++ tcp stream的简单实现

C++的I/O流是很强大的. 一方面在于易于使用, 类型安全. 另一方面在于容易扩展.
先考虑一下最后客户代码的写法, 我希望是这样

huxw::Socket so = huxw::TCPv4_Connect("echo", "166.111.172.6");
        huxw::tcpstream ts(so);
        std::string tmpstr;
        while( std::cin >> tmpstr )
        {
                ts << tmpstr << std::endl;
                ts >> tmpstr;
                std::cout << "We got " << tmpstr << std::endl;
        }
        return 0;

以上就是一个echo client.

我们知道stream操作streambuf, streambuf才真正和设备(或者是更底层的buffer)打交道.
而stream操作streambuf是通过一系列标准接口来完成的. 只要我们能够继承basic_streambuf,
并且改写其中若干接口, 就可以使得原有的stream使用新的streambuf.

而这个改写的过程, 比想象的要简单的多. 基本上, 如果我们比较懒的话, 改三个就足够了
overflow, underflow, sync. overflow表示写缓冲写满了的时候, 应该怎么办? underflow表示
读缓冲读完了的时候应该怎么办? sync是针对写缓冲的同步.

想象一个典型的读写流程

        ts << str << std::endl;
        ts >> str;

假设开始的时候ts的读写缓冲都是空的.
ts<>str会试图从读buffer中读取内容, 但是读buffer是空的, 所以他会去调用underflow.
一旦str的内容如此之大, 使得ts的写buffer中再也放不下了, 那么overflow会被自动调用

理解了以上流程, 我们就可以动手打造自己的streambuf

template<typename charT, 
         typename traits=std::char_traits<charT>
        >

class basic_tcp_streambuf : public std::basic_streambuf
这是定义的标准方法, 于basic_streambuf类似的是, 我们通过typedef来实现char的和
wchar_t的两种流.

        basic_tcp_streambuf(Socket& so, int bufsize = 512)
        : m_bufsize(bufsize)
        {
                //我们需要两个缓冲区, 一个是put buffer, 一个是get buffer
                //gback()返回get buffer的起始地址, egptr()返回get buffer的结束地址
                //pbase()返回put buffer的起始地址, epptr()返回put buffer的结束地址
                //分别以pptr, gptr表示put buffer和get buffer的当前位置
                m_sock = so;
                char_type* buf;
                buf = new char_type[bufsize];
                setg(buf, buf, buf);      //setg设置gback(), gptr(), egptr()
                buf = new char_type[bufsize];
                setp(buf, buf + bufsize); //setp设置pbase(), pptr(), epptr() 
                                          //其中pptr()被自动设置为pbase()
                                          //有的stl实现给了一个扩展函数, 能够单独
                                          //设置pptr(), 不推荐使用
        }

        virtual int_type overflow(typename traits::int_type c = traits::eof())
        {
                //当sputc失败的时候, 会调用overflow
                //如果c不是eof(), 本函数尝试将traits::to_char_type(c)插入put buffer当中
                
                _flush(); //清空缓冲
                setp(pbase(), epptr()); //重新设定put缓冲, 将pptr()重置到pbase()处
                
                if (traits::eq_int_type(traits::eof(), c))
                        return traits::not_eof(c);
                
                sputc(traits::to_char_type(c));  //put c into buffer again
                return c;
        }
        
        virtual int_type underflow()
        {
                //此时get buffer中已经没有内容, 重新读入
                int r = m_sock.Recv(eback(), m_bufsize * sizeof(char_type));
                if (r == 0)
                        return traits::to_int_type(traits::eof());
                setg(eback(), eback(), eback() + r / sizeof(char_type));
                return traits::to_int_type(*gptr());    
        }
        
        virtual int sync() //比如endl这样的操作符会调用sync()
        {
                _flush();
                setp(pbase(), epptr());
                return 0;
        }

private:
        inline void _flush()
        {
                m_sock.SendAll(pbase(), (pptr() - pbase()) * sizeof(char_type));
        }

这样基本上就可以了.

template<typename charT, typename traits = std::char_traits<charT> >
class basic_tcpstream : public std::basic_iostream<charT, traits>
{
public:
        explicit basic_tcpstream(Socket& so, int bufsize = 512) 
        : m_buf(so, bufsize), std::basic_iostream<charT, traits>(&m_buf)                
        {
        
        }
        
        basic_tcp_streambuf<charT, traits>* rdbuf()
        {
                return &m_buf;
        }
private:
        basic_tcp_streambuf<charT, traits> m_buf;
};

Liars Hackrank

https://www.hackerrank.com/challenges/liars

You have N soldiers numbered from 1 to N. Each of your soldiers is either a liar or a truthful person. You have M sets of information about them. Each set of information tells you the number of liars among a certain range of your soldiers. Let L be the total number of your liar soldiers. Since you can’t find the exact value of L, you want to find the minimum and maximum value of L.

Input Format

  • The first line of the input contains two integers N and M.
  • Each of next M lines contains three integers:
    A B C where the set of soldiers numbered as {A, A+1, A+2, …, B}, exactly C of them are liars. (1 <= Ai <= Bi <= n) and (0 <= Ci <= Bi-Ai).

Note: N and M are not more than 101, and it is guaranteed the given informations is satisfiable.
继续阅读Liars Hackrank

leetcode-friendCircles

There are N students in a class. Some of them are friends, while some are not. Their friendship is transitive in nature. For example, if A is a direct friend of B, and B is a direct friend of C, then A is an indirect friend of C. And we defined a friend circle is a group of students who are direct or indirect friends.

Given a N*N matrix M representing the friend relationship between students in the class. If M[i][j] = 1, then the ith and jth students are direct friends with each other, otherwise not. And you have to output the total number of friend circles among all the students.

Example 1:
Input:
[[1,1,0],
[1,1,0],
[0,0,1]]
Output: 2
Explanation:The 0th and 1st students are direct friends, so they are in a friend circle.
The 2nd student himself is in a friend circle. So return 2.
Example 2:
Input:
[[1,1,0],
[1,1,1],
[0,1,1]]
Output: 1
Explanation:The 0th and 1st students are direct friends, the 1st and 2nd students are direct friends,
so the 0th and 2nd students are indirect friends. All of them are in the same friend circle, so return 1.
Note:
N is in range [1,200].
M[i][i] = 1 for all students.
If M[i][j] = 1, then M[j][i] = 1.

solution:


class Solution(object):
    def findCircleNum(self, friends):
        """
        :type M: List[List[int]]
        :rtype: int
        """
        sets = []
        l = len(friends[0])
        total_s = set(range(0,l))
        for i in range(0,l):
            for s in sets:
                if  i in s:
                    break
            else:
                new_s = set()
                new_s.add(i)
                while True:
                    new_new_s = set()  #BFS search
                    for i in new_s:
                        for j in total_s:
                            if friends[j][i] == 1 and  i != j:
                                new_new_s.add(j)
                    if 0 == len(new_new_s):
                        break
                    else:
                        new_s = new_s | new_new_s
                        total_s = total_s - new_new_s
                sets.append(new_s)
                total_s = total_s - new_s
        return len(sets)

bitshares 比特股源码阅读笔记(二)

比特股底层相关代码均在libraries目录下,libraries目录下有10个模块。
其中fc模块,包含与协议无关的代码。 FC全称是:fast comipling
FC提供的功能主要有:
1、协程支持
2、对boost ASIO提供一个同步封装
3、C++ 反射支持,提供结构体的二进制 、json串行化服务
4、json rpc的原子化操作反射接口,保证数据致性
5、加密、解密算法工具,封装了openssl
6、日志服务
7、封装其他boost服务
8、非官方boost.process 库支持

FC库基本上封装了比特股源码所有用到的系统api,fc库可以算是对C++没有一个大而全的标准库的一个补充,fc作为一个大而全的库,应该也可以在其他程序上使用, 但是文档太少了,差评!另外C++各种三方库,但是确实没有一个事实上的标准库,这也是c++市场份额越来越小的原因吧。

与比特股协议紧密最相关的应该是chain模块里面的代码。
chain模块里面定义了账户,资产,区块等比特投世界里面的所有对象,所有对象的定义在chain/protocol目录里

bitshares 比特股源码阅读笔记(一)

比特股在设计上采用了与比特币uxto完全不同的方式。它采用的是传统会计账户模式。
即每个账户对于每个资产都有一个余额。
账户之间转账就是资产余额的加减。
账户,资产都是一种object的孙子类 ,直接继承自abstract_object,而abstract_object继承自object.
每个object有一个全局唯一的id,object之间只能通过id来相互标识和访问。
每个 id是object_id特例化后的类的实例, 每个id由3个整数组成 ,前面两个是8位无符号整数,后面一个64位无符号整数,但是最大值不超过2的48次方。
每个账户都有两种权限authority,一个所有权,一个authority代表活动权(先把它想象成经营权或者管理权吧)

每个authority可以由多个执行者来实行,每个执行者可以有不同的权重。执行者可以是公钥、地址、或者其他账户。

谈谈个人感受:
1、我觉得比特股源码里,authority 方面的名字没起好,不够直观。
2、object_id的设计,虽然看上去很新奇,我现在还找不出为什么要这样设计?为了性能还是其他方面的考虑,简单的自曾id已经在工程上被证明不是一个好的设计。为了方便记忆的话,每个object已经有一个名字了。而且我觉得这方面明明有url的规范啊,为什么不用呢?直接定义一种url来访问不是更好吗?例如通过
bitshares://asserts/bitcny来获取bitcny的信息,bitshares://accounts/sb来获取sb账户的信息,这样是不是更直观,而容易被大家接受啊
3、大量使用了struct 来替代class ,虽然 c++中,这两个东西基本上是同一个东西,但是这确实不太容易让新人接受,毕竟大多数c++资料上都是用class来定义类的
4、大量使用了模板,代码可读性和可维护性确实是不太好!估计这也是C++是日薄西山的原因之一吧,毕竟在C++搞模板进行元编程的年代,PL界里类型系统好像还不是很成熟。把bitshares的源代码换成rust来写,可读性,可维护性应该要高些吧?毕竟他号称集软件工程15年来的最佳工程实践。
5、文档还是太少了

当然我要承认自己写c++写得很少,以上观点也肯定有些错误和不足,还是报着学习的心态多看看源代码。