昨天面试,面试官问到一个问题,vector怎么扩容的,我大概记得C++ premier有那么一句扩两倍。我说好像是扩两倍,面试官也没继续问也没反馈对错。甚是好奇对错,索性自己试验一把,并看下源码。

试验

代码

#include<iostream>
#include<vector>
using namespace std;

int main(int argc, char *argv[])
{
	vector<int> vInt;

	for(int i = 0; i < 100; i++ )
	{
		cout << "size:" << vInt.size() << "\t" << "capacity:" << vInt.capacity() << endl;
		vInt.push_back(1);
	}

	return 0;
}

输出

size:0	capacity:0
size:1	capacity:1
size:2	capacity:2
size:3	capacity:4
size:4	capacity:4
size:5	capacity:8
size:6	capacity:8
size:7	capacity:8
size:8	capacity:8
size:9	capacity:16
size:10	capacity:16
size:11	capacity:16
size:12	capacity:16
size:13	capacity:16
size:14	capacity:16
size:15	capacity:16
size:16	capacity:16
size:17	capacity:32
size:18	capacity:32
......

源码

在这只把扩容相关代码贴出来罢了。

//SGI STL v3.3
void push_back(const _Tp& __x) {
if (_M_finish != _M_end_of_storage) {
  construct(_M_finish, __x);
  ++_M_finish;
}
else
  _M_insert_aux(end(), __x);
}

iterator insert(iterator __position, const _Tp& __x) {
size_type __n = __position - begin();
if (_M_finish != _M_end_of_storage && __position == end()) {
  construct(_M_finish, __x);
  ++_M_finish;
}
else
  _M_insert_aux(__position, __x);
return begin() + __n;
}

template <class _Tp, class _Alloc>
void 
vector<_Tp, _Alloc>::_M_insert_aux(iterator __position, const _Tp& __x)
{
  if (_M_finish != _M_end_of_storage) {
    construct(_M_finish, *(_M_finish - 1));
    ++_M_finish;
    _Tp __x_copy = __x;
    copy_backward(__position, _M_finish - 2, _M_finish - 1);
    *__position = __x_copy;
  }
  else {
    const size_type __old_size = size();
    //原容量为0扩为1,否则扩为原2倍
    const size_type __len = __old_size != 0 ? 2 * __old_size : 1;
    iterator __new_start = _M_allocate(__len);
    iterator __new_finish = __new_start;
    __STL_TRY {
      __new_finish = uninitialized_copy(_M_start, __position, __new_start);
      construct(__new_finish, __x);
      ++__new_finish;
      __new_finish = uninitialized_copy(__position, _M_finish, __new_finish);
    }
    __STL_UNWIND((destroy(__new_start,__new_finish), 
                  _M_deallocate(__new_start,__len)));
    destroy(begin(), end());
    _M_deallocate(_M_start, _M_end_of_storage - _M_start);
    _M_start = __new_start;
    _M_finish = __new_finish;
    _M_end_of_storage = __new_start + __len;
  }
}

在push_back或者inster的时候,vetor容量不够扩容为原长度两倍。
这个增长因子和各版本STL实现有关,有的版本用1.5

为什么是扩为原长度2倍

因为每次扩容都涉及到原来元素的copy。空间和时间的权衡。
简单来说, 空间分配的多,平摊时间复杂度低,但浪费空间也多。
具体参见算法导论中,平摊分析那一章关于动态表扩张的分析。

参考:https://www.zhihu.com/question/36538542/answer/67929747

总结

面试无非:语言、数据结构、算法、工作经验。
看来是时候看下《STL源码剖析》,阅读下STL源码了。(*^▽^*)

确定想扫描的IP范围

首先要确定要扫描的ip范围,可以自己定手写,我是按地域从网站上爬取的。

#coding:utf-8
import requests
from bs4 import BeautifulSoup
from urllib import quote
import re
place_name = "日本"
url_ = 'http://ip.yqie.com/search.aspx?searchword=' + quote(place_name) + "&pagecurrent="
pagecount = re.findall('页码:1/(\d*?)<',requests.get(url_+'1').content)
index = 1
fp = open('ip_range.txt','a')
while index < int(pagecount[0]):
    url = url_ + str(index)
    page = requests.get(url)
    soup = BeautifulSoup(page.content,'lxml').find_all("tr")
    j = 0
    for i in soup:
        if j == 0:
            j = 1
            continue
        fp.write(i.contents[1].contents[0]  + '    ' + i.contents[3].contents[0] + '\n')
    index = index + 1
fp.close()

生成以下格式的文本:
171.105.32.0 171.105.33.255
171.105.34.0 171.105.35.255
171.105.36.0 171.105.36.255
171.105.37.0 171.105.38.255
171.105.39.0 171.105.79.255

继续阅读

概述

跳表是一种有序数据结构,它通过在每个节点维持多个指向其他节点的指针,从而达到快速访问节点的目的。

跳表基于并联的链表,其效率可比拟于二叉查找树(对于大多数操作需要O(log n)平均时间)。

插入新节点时,该节点层数随机。

更详尽的解释参见维基百科或自行google。贴两张维基百科的图片,便于大家理解。

大家有兴趣也可以去看redis的skiplist实现(zskiplist)。

继续阅读

概述

一个高性能的服务器端程序,内存的使用非常重要。多次的申请和释放引起的内存碎片,一旦碎片到达一定程度,即使剩余内存总量够用,但由于缺乏足够的连续空闲空间,导致内存不够用的假象。为了避免小块内存的频繁分配,最简单的做法就是申请大块的内存,多次分给客户。

一般的策略都是:
小块内存-->从内存池里拿;不够的话,内存池向系统申请新的大块。
大块内存-->直接问系统拿。

如果对这块感兴趣可以自行研究一下:ptmalloc、tcmalloc、Jemalloc、Nginx内存池。

Redis默认使用jemalloc,我们公司的项目也是使用jemalloc。

Redis的Makefile片段:

# Default allocator
ifeq ($(uname_S),Linux)
	MALLOC=jemalloc
else
	MALLOC=libc
endif

# Backwards compatibility for selecting an allocator
ifeq ($(USE_TCMALLOC),yes)
	MALLOC=tcmalloc
endif

ifeq ($(USE_TCMALLOC_MINIMAL),yes)
	MALLOC=tcmalloc_minimal
endif

ifeq ($(USE_JEMALLOC),yes)
	MALLOC=jemalloc
endif

ifeq ($(USE_JEMALLOC),no)
	MALLOC=libc
endif

好,言归正传。leveldb中实现了一个"一次性"的简单的内存池Arena,不是所有的地方都使用了这个内存池,主要是memtable(skiplist)使用

继续阅读

最近在读leveldb源码,发现了这篇文章,感觉蛮不错,转载了过来。

转载:https://www.ezlippi.com/blog/2014/11/leveldb.html

 

在说LevelDb之前,先认识两位大牛,Jeff Dean和Sanjay Ghemawat,这两位是Google公司重量级的工程师,为数甚少的Google Fellow之二。

Jeff Dean其人:http://research.google.com/people/jeff/index.html,Google大规模分布式平台Bigtable和MapReduce主要设计和实现者。

Sanjay Ghemawat其人:http://research.google.com/people/sanjay/index.html,Google大规模分布式平台GFS,Bigtable和MapReduce主要设计和实现工程师。

LevelDb就是这两位大神级别的工程师发起的开源项目,简而言之,LevelDb是能够处理十亿级别规模Key-Value型数据持久性存储的C++ 程序库。正像上面介绍的,这二位是Bigtable的设计和实现者,如果了解Bigtable的话,应该知道在这个影响深远的分布式存储系统中有两个核心的部分:Master Server和Tablet Server。其中Master Server做一些管理数据的存储以及分布式调度工作,实际的分布式数据存储以及读写操作是由Tablet Server完成的,而LevelDb则可以理解为一个简化版的Tablet Server。

继续阅读

QQ和微信数据本地数据库,可以获取聊天信息以及好友信息等。

QQ

安卓手机QQ数据库:/data/data/com.tencent.qq/databases/QQ号.db(手机root后可获取 RE浏览器);
数据库文件为sqlite数据库;
私聊天记录放在表:mr_friend_MD5(QQ号)_New
群聊天记录放在表:mr_troop_MD5(群号)_New

sqlcipher.exe打开数据库发现一些信息乱码,经过加密。加密方法循环异或IMEI号。

解密demo:

# -*- coding: utf-8 -*-
import sqlite3

IMEI="866536022175869"
conn = sqlite3.connect("971774262.db")
cursor = conn.execute("SELECT frienduin,selfuin,senderuin,msgdata  from mr_troop_158C59D128304F55302B275E6427CA1E_New ")
print "select database successfully";
print "群号\t\t己方QQ\t\t发送方QQ\t\t聊天内容"
for row in cursor:
    a= row[0]
    #print a
    sbstr=""
    for i in range(0,len(a)):
        sbstr+=chr(ord(a[i])^ord(IMEI[i%15]))
    sbstr+="\t"
    a= row[1]
    for i in range(0,len(a)):
        sbstr+=chr(ord(a[i])^ord(IMEI[i%15]))
    sbstr+="\t"
    a= row[2]
    for i in range(0,len(a)):
        sbstr+=chr(ord(a[i])^ord(IMEI[i%15]))
    sbstr+="\t"
    a= row[3]
    for i in range(0,len(a)):
        sbstr+=chr(ord(a[i])^ord(IMEI[i%15]))
    print sbstr

微信

安卓微信数据库:/data/data/com.tencent.mm/MicroMsg    EnMicroMsg.db (需要ROOT)

数据库整个加密,可以用sqlcipher.exe软件直接打开,也可以自己写代码。

数据库密码:拼接IMEI和uin,通过md5加密后,取前7位小写的字符串

uin获取:/data/data/com.tencent.mm/shared_prefs/auth_info_key_prefs.xml (需要ROOT)

在vps上抓包分析telegram协议时,意外发现有人尝试登录我的wordpress后台,很是意外,看来安全意识不能没有啊。

然后我装了个wordpress插件simple login log来记录登录日志,实验发现并不能记录登录失败的日志,所以看了下simple login log插件源码,simple-login-log.php文件中有以下代码行,

if( isset($this->opt['failed_attempts']) )

因为对php语言不是很了解,也没太仔细看opt在哪初始化或者修改的,索性直接把以上代码全替换成

if( 1 )

估计simple login log作者这么做是怕有攻击者对你网站实施密码爆破,使得mysql数据库爆掉。

而后就能看到登录失败的日志了。

仔细观察一下时间,你会发现这些人还蛮专业,隔两个小时尝试一次,怕短时间内多次访问被禁掉。

有一些插件可以做一些防护,比如:WP Limit Login Attempts、WP-Ban等,但考虑到本来vps内存cpu呀就不够用的,我就没安装这些插件了黑客还是蛮多的,不过我这小站也没啥,任他们去吧

 

由于之前一直使用的http未使用https,最近在用https时修改Nginx配置文件导致除主页外其他页面404。
解决办法:

在nginx的conf文件夹下创建个wordpress.conf ,将下面的代码粘贴进去

location / {
try_files $uri $uri/ /index.php?$args;
}
rewrite /wp-admin$ $scheme://$host$uri/ permanent;

修改博客nginx虚拟机配置文件在 conf/vhost/www.lpeiqing.conf
在root /home/wwwroot/www.dapiqing.cn;那行下面,添加一行:

include wordpress.conf;

重启Nginx

lnmp reload

买vps两年了,之前主要功能就是shadowsocks翻GFW查资料(百度忒垃圾),哈哈哈,当然偶尔也看些其它东西;偶尔在上边写写test代码;

以前也搭建WordPress博客,但是一直没写啥。这次趁着重装系统重新搭了一下WordPress博客,在这儿记录一下。

写的很笼统,只是一个纲。有啥不懂请点击www.google.com,本就不是写给不熟悉linux环境的人看的。

lnmp

LNMP(Linux Nginx/MySQL/PHP)

lnmp的安装可以到https://lnmp.org/install.html查看教程。

  1. 安装直接执行wget -c http://soft.vpser.net/lnmp/lnmp1.4.tar.gz && tar zxf lnmp1.4.tar.gz && cd lnmp1.4 && ./install.sh lnmp即可(wget获取安装包,tar加压安装包,cd进目录,执行./install.sh脚本)
  2. lnmp添加虚拟主机 https://lnmp.org/faq/lnmp-vhost-add-howto.html (前提是你要买域名,我在美橙互联注册的),这一步可以放到解压完WordPress后做。  请记住你填写的信息,安装完会打印一个信息汇总,也可以复制粘贴保存起来免得你忘了。

lnmp命令蛮好用,在自己不熟悉Nginx、php的情况下,直接使用lnmp集成的命令更加容易些也会避免一些错误。

Usage: lnmp {start|stop|reload|restart|kill|status}
Usage: lnmp {nginx|mysql|mariadb|php-fpm|pureftpd} {start|stop|reload|restart|kill|status}
Usage: lnmp vhost {add|list|del}
Usage: lnmp database {add|list|edit|del}
Usage: lnmp ftp {add|list|edit|del|show}
Usage: lnmp ssl add

继续阅读