很长时间都没写过代码了,试着写了这个常见的题目。整体思路:采用整形链表记录大整数的每一位,然后分别遍历乘数和被乘数的每一位,将每两个数字的乘积累加到结果的相应位上面。针对大整数类型,重载输入和输出流,重载乘法。
输出部分实现不是特别好。用STL的容器实现链表也许会简单的多。重载乘法的实现不合常理,本应该返回一个新的对象,为了简单起见,直接返回了新对象的指针;在计算乘法结果时使用了一个递归,理论上来说有可能深度过大,导致栈溢出;另外对于指针和应用的使用不规范。
具体代码:
很长时间都没写过代码了,试着写了这个常见的题目。整体思路:采用整形链表记录大整数的每一位,然后分别遍历乘数和被乘数的每一位,将每两个数字的乘积累加到结果的相应位上面。针对大整数类型,重载输入和输出流,重载乘法。
输出部分实现不是特别好。用STL的容器实现链表也许会简单的多。重载乘法的实现不合常理,本应该返回一个新的对象,为了简单起见,直接返回了新对象的指针;在计算乘法结果时使用了一个递归,理论上来说有可能深度过大,导致栈溢出;另外对于指针和应用的使用不规范。
具体代码:
用户态采用select模型,初始化时建立多个netlinksocket,绑定完成之后,向内核发送握手消息,这样内核可以将已经建立的连接记住,以便后续选择可用的连接发送数据。初始化和握手完成之后,由内核主动向用户态发送数据,用户态主线程在各个socket句柄上面等待读事件的到来,当检测到读事件时,向线程池提交数据读取和处理任务。这样模拟一个连接池和事件分发模型,保证内核数据及时被读取到用户态程序并处理,能做到并发。
而内核态的netlink在接收数据时本身就是以系统调用的方式提供给业务层的发送接口,因此本身就是异步的,性能不是问题。内核态收到数据时,只需要提交给一个内核线程去处理即可。
原型代码如下:
#!/bin/bash
end=`dmesg |wc -l`
while true
do
sleep 1
end2=`dmesg |wc -l`
if [ "$end" != "$end2" ]; then
dmesg |awk '{print NR, $0}'|tail -$((end2-end))
end=$end2
fi
if [ "$end" -ge 1000 ]
then
dmesg -c >/dev/null 2>&1
echo "**********************"
echo "*dmesg -c now; *"
echo "**********************"
end=`dmesg |wc -l`
fi
done
#include<unistd.h>
#include<stdio.h>
int main()
{
for(int i = 0; i < 2; ++i)
{
fork();
printf("-");
}
printf("\n");
return 0;
}
int atoi(const char* strNum);
思路:首先对输入指针判空,然后取出每一位的权值a,用类似下面的算法:Math.pow(10, i) * a 这样的算法实现。用到了乘方算法,似乎不是特别好。另外用一个类似递归的思想:sum = sum * 10 + digitnum; ,下面就后者给出实现代码。
在上一篇中介绍了jetty的反映器模型,selector线程与业务子线程交互的点有:
1、分发事件给子线程做,启动子线程;
2、子线程发现阻塞或者连接关闭等时间时,注册内部changes,等待selector线程调度;
3、检测超时连接,并且关闭连接。
以下分析针对jetty的特定版本:http://dev.eclipse.org/svnroot/rt/org.eclipse.jetty/jetty/tags/jetty-7.2.1.v20101111
首先介绍一下Jetty的反映器模型,Jetty用的经典的NIO异步模型(Scalable IO in Java http://gee.cs.oswego.edu/dl/cpjslides/nio.pdf)。连接管理的示意图如下:
Jetty在使用这个模型的时候,做了一些改动,acceptor是独立出来的一个阻塞线程,用于阻塞地接受新的连接请求,而所有的连接建立之后,都会想selector线程注册网络事件和内部的事件(changes),selector需要同时处理网络事件和内部的changes。同时还要定期检查超时的链接。
按照上一篇中提到的思路,最后问题的焦点在于:怎样快速找到tmp中的为1的bit位在x中的实际位置。这样在计算N值的同时将每一位的权值与索引位置的关系用数组对照起来,最后只需要在遍历tmp的值为1的bit位时作相应的加权累加即可。
也综合评论中提到的递归方案,重新补充了各个方案的代码和性能测试代码。
见“方案1”的代码处:
给定一个long型常量,其值为x,给定long型变量a,要求a & x 的取值集合,结果放入ArrayList中。
思路,x先转换为bit数组,得出其中元素值为1的总数为n,则所有取值的总数为2的n次方,记为N。
在0~N的闭区间中,依次取出各个数值,记为tmp,将tmp也转换为bit数组,依次遍历x的每一个bit位,当x的bit位为1时,到tmp中去取出相应的bit位,如果也为1,则将该位为1时,其他所有位为0时所代表的数值累加到结果中。
遍历完所有的bit位后,得到的结果即为所需要的数值。
整个思路有点复杂,性能也不高,从数值本身的与或运算上面着手,肯定还有更简单的方法。
代码: