maiff / blog Goto Github PK
View Code? Open in Web Editor NEWThis is a blog
This is a blog
其实我大二的时候学过数据结构跟算法,然后下学期学过算法分析设计,但是现在跟我自己看书学,效果完全不一样,我就是以自我为驱动型,自己想干的事干好的可能性别人叫我干的成功性大的多的多。废话不多少直接来干货。
这里就要我说的惰性交换。
先上书上所说的插入排序的代码:
void InsertionSort(int A[], int N){
int j ,p;
int Tmp;
for(p=1;p<N;p++){
Tmp = A[p];
for(j=p;j>0&&A[j-1]>Tmp;j--)
A[j]=A[j-1];
A[j]=Tmp;
}
}
这里说一下几点:
快速排序在数字少的时候有奇效。
这个我以前是懂得,而现在忘记了。代码:
void ShellSort(int a[], int n){
int i,j,increment;
int tmp;
for(increment = n/2;increment>0;increment/=2)
for(i=increment;i<n;i++){
tmp = a[i];
for(j=i;j>=increment;j-=increment){
if(tmp<a[j-increment])
a[j]=a[j-increment];
else
break;
}
a[j]=tmp;
}
}
堆是我最喜欢的数据结构之一。堆排序上一篇文章就说了。就是不停地deleteMin然后percdown就可以了,在这里编写算法又做了一个处理,deletemin出来的数字并没有开辟一个新的空间放而是放到堆的尾部,堪称实现的完美。
void precDown(int a[],int i ,int n){
int child;
int tmp;
for(tmp=a[i];leftchild(i)<n;i=child){
child = leftchild(i);
if(child!=n-1&&a[child+1]>a[child])
child++;
if(tmp<a[child])
a[i]=a[child];
else
break;
}
a[i]=tmp;
}
void swap(int *a, int *b){
int temp = *a;
*a = *b;
*b= temp;
}
void heapSort(int a[],int n){
int i;
for(i=n/2;i>=0;i--)
precDown(a,i,n);
for(i=n-1;i>0;i--){
swap(&a[0],&a[i]);
precDown(a,0,i);
}
}
堆排序的平均O(NlogN)
我觉得这个实现跟快排差不多,后来仔细想想再跟快排比较有很大区别,而且这里开辟了一个新的tmpArray,对比较大的数据排序很是不友好,但是他的平均复杂度跟堆排序是一样的。
void merge(int a[],int tmpArray[],int lpos,int rpos,int rightEnd){
int i,leftEnd,numelements,tmpPos;
leftEnd = rpos - 1;
tmpPos = lpos;
numelements = rightEnd-lpos+1;
while(lpos<=leftEnd&&rpos<=rightEnd)
if(a[lpos]<=a[rpos])
tmpArray[tmpPos++]=a[lpos++];
else
tmpArray[tmpPos++]=a[rpos++];
while(lpos<=leftEnd)
tmpArray[tmpPos++]=a[lpos++];
while(rpos<=rightEnd)
tmpArray[tmpPos++]=a[rpos++];
for(i=0;i<numelements;i++,rightEnd--)
a[rightEnd]=tmpArray[rightEnd];
}
void Msort(int a[],int tmpArray[],int left,int right){
int center;
if(left<right){
center=(left+right)/2;
Msort(a,tmpArray,left,center);
Msort(a,tmpArray,center+1,right);
merge(a,tmpArray,left,center+1,right);
}
}
void mergeSort(int a[],int n){
int *tmpArray;
tmpArray=malloc(n*sizeof(int));
if(tmpArray!=NULL){
Msort(a,tmpArray,0,n-1);
free(tmpArray);
}
}
代码可以说还是比较复杂的,但是理解了递归的过程就很简单了。
最后说的是快速排序简直惊了我的呆,原来,快排可以这么写。
我的python版
def quickSort(arr):
length = len(arr)
if length <= 1:
return arr
else:
index = length / 2
left = []
right = []
for i in range(0,length):
if i == index:
continue
if arr[i] < arr[index]:
left.append(arr[i])
else:
right.append(arr[i])
return quickSort(left)+[arr[index]]+quickSort(right)
中规中矩,这也是我是看阮一峰老师写的js版翻译过来的,再看书上的版本。
void swap(int *a,int *b){
int temp = *a;
*a = *b;
*b = temp;
}
int median3(int a[],int left ,int right){
int center = (left+right)/2;
if(a[left]>a[center])
swap(&a[left],&a[center]);
if(a[left]>a[right])
swap(&a[left],&a[right]);
if(a[center]>a[right])
swap(&a[center],&a[right]);
swap(&a[center],&a[right-1]);
return a[right-1];
}
void qsort(int a[],int left, int right){
int i,j;
int pivot;
if(left+cutoff<=right){
pivot=median3(a,left,right);
i=left;j=right-1;
for(;;){
while(a[++i]<pivot){}
while(a[--j]>pivot){}
if(i<j)
swap(&a[i],&a[j]);
else
break;
}
swap(&a[i],&a[right-1]);
qsort(a,left,i-1);
qsort(a,i+1,right);
}else
insertionSort(a,right-left+1);
}
void quickSort(int a[],int n){
qsort(a,0,n-1);
}
这里的median3是干什么的,书上是这样说的这个叫三数中值分割,防止随机选择一个可能会多造成一次递归,导致数据全部都在一边,同时书上实现的没有重新开辟一个数组,防止空间的浪费,最后在小数组的时候判断情况下用插入排序。不得不感叹算法的优化要考虑的情况有很多种~
itchat基于webweixin提供的api
时间:2017.2.9
API | 获取 UUID |
---|---|
url | https://login.weixin.qq.com/jslogin |
method | POST |
data | URL Encode |
params | appid: 应用ID fun: new 应用类型 lang: zh_CN 语言 _: 时间戳 |
注:这里的appid就是在微信开放平台注册的应用的AppID。网页版微信有两个AppID,早期的是wx782c26e4c19acffb,在微信客户端上显示为应用名称为Web微信;现在用的是wxeb7ec651dd0aefa9,显示名称为微信网页版。
API | 生成二维码 |
---|---|
url | https://login.weixin.qq.com/qrcode/`uuid` |
API | 二维码扫描登录 |
---|---|
url | https://login.weixin.qq.com/cgi-bin/mmwebwx-bin/login |
method | GET |
params | tip: 1 未扫描 0 已扫描 uuid: xxx _: 时间戳 loginicon true(可选) |
返回数据(String):
window.code=xxx;
xxx:
408 登陆超时
201 扫描成功
200 确认登录
当带有loginicon时扫码就会返回头像
当返回200时,还会有
window.redirect_uri="https://wx.qq.com/cgi-bin/mmwebwx-bin/webwxnewloginpage?ticket=xxx&uuid=xxx&lang=xxx&scan=xxx";
API | webwxnewloginpage |
---|---|
url | https://wx.qq.com/cgi-bin/mmwebwx-bin/webwxnewloginpage |
method | GET |
params | ticket: xxx uuid: xxx lang: zh_CN 语言 scan: xxx fun: new |
tips
注意这里的api地址和之后的api地址都需要动态获得不然会出现问题,根据前面的redirect_url的host决定如果前面的地址是wx2.qq.com这里的及后面的都要为wx2.qq.com
返回数据(XML):
<error>
<ret>0</ret>
<message>OK</message>
<skey>xxx</skey>
<wxsid>xxx</wxsid>
<wxuin>xxx</wxuin>
<pass_ticket>xxx</pass_ticket>
<isgrayscale>1</isgrayscale>
</error>
API | webwxinit |
---|---|
url | https://wx.qq.com/cgi-bin/mmwebwx-bin/webwxinit?pass_ticket=xxx&skey=xxx&r=xxx |
method | POST |
data | JSON |
header | ContentType: application/json; charset=UTF-8 |
params | { BaseRequest: { Uin: xxx, Sid: xxx, Skey: xxx, DeviceID: xxx, } } |
返回数据(JSON):
{
"BaseResponse": {
"Ret": 0,
"ErrMsg": ""
},
"Count": 11,
"ContactList": [...],
"SyncKey": {
"Count": 4,
"List": [
{
"Key": 1,
"Val": 635705559
},
...
]
},
"User": {
"Uin": xxx,
"UserName": xxx,
"NickName": xxx,
"HeadImgUrl": xxx,
"RemarkName": "",
"PYInitial": "",
"PYQuanPin": "",
"RemarkPYInitial": "",
"RemarkPYQuanPin": "",
"HideInputBarFlag": 0,
"StarFriend": 0,
"Sex": 1,
"Signature": "Apt-get install B",
"AppAccountFlag": 0,
"VerifyFlag": 0,
"ContactFlag": 0,
"WebWxPluginSwitch": 0,
"HeadImgFlag": 1,
"SnsFlag": 17
},
"ChatSet": xxx,
"SKey": xxx,
"ClientVersion": 369297683,
"SystemTime": 1453124908,
"GrayScale": 1,
"InviteStartCount": 40,
"MPSubscribeMsgCount": 2,
"MPSubscribeMsgList": [...],
"ClickReportInterval": 600000
}
注意这里的SyncKey和UserName后文要用到
API | webwxstatusnotify |
---|---|
url | https://wx.qq.com/cgi-bin/mmwebwx-bin/webwxstatusnotify?lang=zh_CN&pass_ticket=xxx |
method | POST |
data | JSON |
header | ContentType: application/json; charset=UTF-8 |
params | { BaseRequest: { Uin: xxx, Sid: xxx, Skey: xxx, DeviceID: xxx }, Code: 3, FromUserName: 自己ID , ToUserName: 自己ID , ClientMsgId: 时间戳 } |
返回数据(JSON):
{
"BaseResponse": {
"Ret": 0,
"ErrMsg": ""
},
...
}
这里的notify不知道是不是必要步骤因为web weixin有这个步骤我也就没有深究
API | webwxgetcontact |
---|---|
url | https://wx.qq.com/cgi-bin/mmwebwx-bin//webwxgetcontact?pass_ticket=xxx&skey=xxx&r=xxx |
method | POST |
data | JSON |
header | ContentType: application/json; charset=UTF-8 |
返回数据(JSON):
{
"BaseResponse": {
"Ret": 0,
"ErrMsg": ""
},
"MemberCount": 334,
"MemberList": [
{
"Uin": 0,
"UserName": xxx,
"NickName": "Urinx",
"HeadImgUrl": xxx,
"ContactFlag": 3,
"MemberCount": 0,
"MemberList": [],
"RemarkName": "",
"HideInputBarFlag": 0,
"Sex": 0,
"Signature": "你好,我们是地球三体组织。在这里,你将感受到不一样的思维模式,以及颠覆常规的世界观。而我们的目标,就是以三体人的智慧,引领人类未来科学技术500年。",
"VerifyFlag": 8,
"OwnerUin": 0,
"PYInitial": "URINX",
"PYQuanPin": "Urinx",
"RemarkPYInitial": "",
"RemarkPYQuanPin": "",
"StarFriend": 0,
"AppAccountFlag": 0,
"Statues": 0,
"AttrStatus": 0,
"Province": "",
"City": "",
"Alias": "Urinxs",
"SnsFlag": 0,
"UniFriend": 0,
"DisplayName": "",
"ChatRoomId": 0,
"KeyWord": "gh_",
"EncryChatRoomId": ""
},
...
],
"Seq": 0
}
API | synccheck |
---|---|
protocol | https |
host | webpush.host.qq.com |
path | /cgi-bin/mmwebwx-bin/synccheck |
method | GET |
data | URL Encode |
params | r: 时间戳 sid: xxx uin: xxx skey: xxx deviceid: xxx synckey: xxx _: 时间戳 |
返回数据(String):
window.synccheck={retcode:"xxx",selector:"xxx"}
retcode:
0 正常
1100 失败/登出微信
selector:
0 正常
2 新的消息
7 进入/离开聊天界面
API | webwxsync |
---|---|
url | https://wx.qq.com/cgi-bin/mmwebwx-bin/webwxsync?sid=xxx&skey=xxx&pass_ticket=xxx |
method | POST |
data | JSON |
header | ContentType: application/json; charset=UTF-8 |
params | { BaseRequest: { Uin: xxx, Sid: xxx, Skey: xxx, DeviceID: xxx }, SyncKey: xxx, rr: 时间戳取反 } |
返回数据(JSON):
{
'BaseResponse': {'ErrMsg': '', 'Ret': 0},
'SyncKey': {
'Count': 7,
'List': [
{'Val': 636214192, 'Key': 1},
...
]
},
'ContinueFlag': 0,
'AddMsgCount': 1,
'AddMsgList': [
{
'FromUserName': '',
'PlayLength': 0,
'RecommendInfo': {...},
'Content': "",
'StatusNotifyUserName': '',
'StatusNotifyCode': 5,
'Status': 3,
'VoiceLength': 0,
'ToUserName': '',
'ForwardFlag': 0,
'AppMsgType': 0,
'AppInfo': {'Type': 0, 'AppID': ''},
'Url': '',
'ImgStatus': 1,
'MsgType': 51,
'ImgHeight': 0,
'MediaId': '',
'FileName': '',
'FileSize': '',
...
},
...
],
'ModChatRoomMemberCount': 0,
'ModContactList': [],
'DelContactList': [],
'ModChatRoomMemberList': [],
'DelContactCount': 0,
...
}
这里deviceid是e后面跟随机数什么好像都行,然后这里说一下这个check,第一次请求没有问题的情况下一定返回
window.synccheck={retcode:"0",selector:"2"}
然后这里要随机跟一个webwxsync请求,然后第一次的synccheck请求synckey是init获得的,后面的synckey是动态的。然后每次synccheck有消息来了,后面都要跟webwxsync请求然后里面含消息信息。
目前只写了发送文本信息的api
API | webwxsendmsg |
---|---|
url | https://wx.qq.com/cgi-bin/mmwebwx-bin/webwxsendmsg?pass_ticket=xxx |
method | POST |
data | JSON |
header | ContentType: application/json; charset=UTF-8 |
params | { BaseRequest: { Uin: xxx, Sid: xxx, Skey: xxx, DeviceID: xxx }, Msg: { Type: 1 文字消息 , Content: 要发送的消息 , FromUserName: 自己ID , ToUserName: 好友ID , LocalID: 与clientMsgId相同 , ClientMsgId: 时间戳左移4位随后补上4位随机数 } } |
返回数据(JSON):
{
"BaseResponse": {
"Ret": 0,
"ErrMsg": ""
},
...
}
(未完待续)
如果你还想看别的api请看我的参考:
cdecl的实现
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#define MAX_LEN 100
enum type_token {IDENTIFIER,QUALIFIER,TYPE};
typedef struct token{
char string[100];
char type;
}token;
token tmp_token;
typedef struct stack{
token array[MAX_LEN];
int top;
}stack;
struct stack token_stack;
void init(stack *sta)
{
sta->top=-1;
}
int push(stack *sta,token s)
{
if(sta->top>=254)
{
printf("the stack is full.\n");
return 1;
}
else
{
sta->array[++(sta->top)]=s;
}
return 0;
}
token pop(stack *sta)
{
return sta->array[(sta->top)--];
}
int stack_empty(const stack s)
{
if(s.top==-1)
return 0;
else
return 1;
}
token top_stack(const stack s)
{
return s.array[s.top];
}
enum type_token classify_string(void);
void gettoken()
{//读取token函数,如果是字母,数字,下划线就一直读取,否则就停止存入tmp_token中处理
memset(tmp_token.string,'\0',sizeof(tmp_token.string));//先把tmp_token清空
char *p=tmp_token.string;
while((*p=getchar())==' ');//略过空白字符
if(isalnum(*p) || *p=='_'){
//读入的标志符要是字母,数字或者下划线,表示是标志符
while(1)
{
*(++p)=getchar();
if(isalnum(*p) || *p=='_')
continue;
else
break;
}
ungetc(*p,stdin);//把非满足的字符放回缓冲区,下次再用
*p='\0';
tmp_token.type=classify_string();
return;
}
if(*p=='*'){
strcpy(tmp_token.string,"pointer to ");
tmp_token.type='*';
return;
}
tmp_token.string[1]='\0';
tmp_token.type=*p;
return;
}
enum type_token classify_string()
{//推断标志符的类型
char *s=tmp_token.string;
if(!strcmp(s,"const")){
strcpy(s,"read-only ");
return QUALIFIER;
}
if(!strcmp(s,"volatile")) return QUALIFIER;
if(!strcmp(s,"extern")) return QUALIFIER;
if(!strcmp(s,"void")) return TYPE;
if(!strcmp(s,"char")) return TYPE;
if(!strcmp(s,"signed")) return TYPE;
if(!strcmp(s,"unsigned")) return TYPE;
if(!strcmp(s,"short")) return TYPE;
if(!strcmp(s,"int")) return TYPE;
if(!strcmp(s,"long")) return TYPE;
if(!strcmp(s,"float")) return TYPE;
if(!strcmp(s,"double")) return TYPE;
if(!strcmp(s,"struct")) return TYPE;
if(!strcmp(s,"union")) return TYPE;
if(!strcmp(s,"enum")) return TYPE;
return IDENTIFIER;
}
void read_first_identifier(){
gettoken();
while(tmp_token.type!=IDENTIFIER){
push(&token_stack,tmp_token);
gettoken();
}
printf("%s is ",tmp_token.string);
gettoken();
}
void deal_with_array()
{
while(tmp_token.type=='[')
{
printf("array");
gettoken();
if(isdigit(tmp_token.string[0]))
{
printf(" 0..%d ",atoi(tmp_token.string)-1);
gettoken();
}
gettoken();//读取‘】’之后的token
printf("of ");
}
}
void deal_with_function()
{
while(tmp_token.type != ')')
gettoken();
gettoken();
printf(" function returning ");
}
void deal_with_pointer()
{
token t;
t=top_stack(token_stack);
while(t.type=='*')
{
printf("%s",t.string);
pop(&token_stack);
t=top_stack(token_stack);
}
}
void deal_with_declarator(){//递归处理的过程
switch(tmp_token.type){
case '[': deal_with_array();break;
case '(': deal_with_function();
}
deal_with_pointer();
while(stack_empty(token_stack)==1)
{
token t=top_stack(token_stack);
if(t.type=='('){
pop(&token_stack);
gettoken();//读取‘)’之后的符号
deal_with_declarator();
}
else
{
printf("%s",pop(&token_stack).string);
}
}
}
int main()
{
init(&token_stack);
read_first_identifier();
deal_with_declarator();
printf("\n");
return 0;
}
我发现我在stdin里,getchar和ungetc的走向不是很熟悉。
然后
晓得union和struct的区别
还有struct里的位段(节省空间)
因为训练需要数据,数据在某个app上。所以开始进行爬虫工作,主要分下面几步:
抓请求无非就是使用fiddler ,让手机和电脑连接同一个局域网开始抓包。
因为是app,某些请求是加密的,后来我发现这个加密方式在页面上有个js的库是负责的,但是我用了一个复杂的方式使用,使用了apk反编译,注意生成的可能没有dex文件,运行命令需要一个参数,见知乎
看懂了反编译的代码,知道加密怎么办到,准备用python重写,但是奈何python的加密不是很熟,也就作罢,直接运行反编译的java代码,这也给后面部署带来了麻烦。
只要把请求放到postman上,基本的爬虫代码是不用手动撰写,复制过来改改参数就好了。
这里爬虫使用了一个MapReduce的结构,数据是从redis拉下来的,具体怎么操作看印象笔记。mongo操作redis操作都很简单。
注意这种json结构的数据的key值应该都是一样的,不然之后遍历检索都很困难。
mongo有可视化工具很方便
mongodb和redis可以直接使用docker部署,也很方便。
遭遇到封ip、封账号。封ip解决办法。使用代理解决
sslocal -c json
sudo polipo socksParentProxy=localhost:1080 proxyPort=1087
request(proxy={}) # 具体看代码
整个项目使用docker部署,一个部署自己带上一个数据库,这样就没有太大瓶颈。
一个人大过年的跑去看乘风破浪,还可以但是最后镜头中出现一个算24的题目——7,7,6,1.算了半天我都没有算出来,但是我是不知道到底能不能算出来于是我就准备回去写一个能算任意四个数字的24的程序。于是我在回家的路上就构思什么样的逻辑。
肯定是穷举发把所有的可能性都例出来然后等于24的就是答案,无非就是4个数字4中运算符,因为是所有情况可以完全不用考虑括号,考虑括号其实也很简单就是一个中缀到后缀的转换。
回来说干就干,然后一上手就遇到一个问题,怎么列出4个数字的所有可能,隐约感觉出来要用递归,于是在没有搜索的情况下自己就开始干起来了。
我的是一种递归思路,想知道4个数字的全排列,知道三个数字的全排列然后拿第四个数字去插空就好了,于是说干就干写出了下面的程序:
最后整个程序是写出来了,算了一下那个7761真的不能算24.来说一下我那个程序的思路,有更好的思路欢迎来讨论。
function calc(arr,num_list){
if(arr.length<=1) {
num_list.push(arr[0])
let str = num_list.join('')
return eval(str)
}
else{
let num = arr.shift()
num_list.push(num)
if(num_list.length===3){
let str = num_list.join('')
num_list=[eval(str)]
}
return calc(arr,num_list)
}
}
然后最后得到了我想要的结果。
但是我觉得我这个全排列的方法不好。不好在哪里呢?我用c语言不好实现,因为算法用js和用c实现那是不一样的用c显然更有成就感,于是我就上网去搜搜到一篇我看不懂的代码:
#include <stdio.h>
int n = 0;
void swap(int *a, int *b)
{
int m;
m = *a;
*a = *b;
*b = m;
}
void perm(int list[], int k, int m)
{
int i;
if(k > m)
{
for(i = 0; i <= m; i++)
printf("%d ", list[i]);
printf("\n");
n++;
}
else
{
for(i = k; i <= m; i++)
{
swap(&list[k], &list[i]);
perm(list, k + 1, m);
swap(&list[k], &list[i]);
}
}
}
int main()
{
int list[] = {1, 2, 3, 4, 5};
perm(list, 0, 4);
printf("total:%d\n", n);
return 0;
}
看了半天没看懂,最后google半天终于看到一个好的解释文章是怎么说的我来解释一下。
我们知道全排列的含义就是一个序列所有的排序可能性,那么我们现在做这样的一个假设,假设给定的一些序列中第一位都不相同,那么就可以认定说这些序列一定不是同一个序列,这是一个很显然的问题。有了上面的这一条结论,我们就可以同理得到如果在第一位相同,可是第二位不同,那么在这些序列中也一定都不是同一个序列,这是由上一条结论可以获得的。
那么,这个问题可以这样来看。我们获得了在第一个位置上的所有情况之后,抽去序列T中的第一个位置,那guihua么对于剩下的序列可以看成是一个全新的序列T1,序列T1可以认为是与之前的序列毫无关联了。同样的,我们可以对这个T1进行与T相同的操作,直到T中只一个元素为止。这样我们就获得了所有的可能性。所以很显然,这是一个递归算法。
也就是第一个元素跟后面的元素全部交换的全排列。
详细看文章说的很详细。
这篇文章就是总结一下我之前在百度面试回来的感觉就是,递归的应用真的很有用重点找到return和终止条件,然后就是要好好看看算法,下一个要好好看看动态规划。
标签(空格分隔): 未分类
详见code split
为什么要分开打包依赖文件?
CommonsChunkPlugin
插件 ,官方推荐配置很简单,但是这是一个复杂的插件:var webpack = require('webpack');
var path = require('path');
module.exports = function() {
return {
entry: {
main: './index.js' //Notice that we do not have an explicit vendor entry here
},
output: {
filename: '[name].[chunkhash].js',
path: path.resolve(__dirname, 'dist')
},
plugins: [
new webpack.optimize.CommonsChunkPlugin({
name: 'vendor',
minChunks: function (module) {
// this assumes your vendor imports exist in the node_modules directory
return module.context && module.context.indexOf('node_modules') !== -1;
}
}),
//CommonChunksPlugin will now extract all the common modules from vendor and main bundles
new webpack.optimize.CommonsChunkPlugin({
name: 'manifest' //But since there are no more common modules between them we end up with just the runtime code included in the manifest file
})
]
};
}
详见cache
To enable long-term caching of static resources produced by webpack:
- Use [chunkhash] to add a content-dependent cache-buster to each file.
- Extract the webpack manifest into a separate file.
- Ensure that the entry point chunk containing the bootstrapping code doesn’t change hash over time for the same set of dependencies.
For an even more optimized setup:
- Use compiler stats to get the file names when requiring resources in HTML.
- Generate the chunk manifest JSON and inline it into the HTML page before loading resources.
这里我们就要结合上面那个把库代码分离,这样每次迭代部署上线,用户就不用新缓存文件,这里改成chunkhash保证每个文件的hash值不一样
后面一点可以不用懂,可以用下面一种方式来动态的生成index.html
最简单的配置
var HtmlWebpackPlugin = require('html-webpack-plugin');
var webpackConfig = {
entry: 'index.js',
output: {
path: 'dist',
filename: 'index_bundle.js'
},
plugins: [new HtmlWebpackPlugin()]
};
document
这里我就简单的用了一个template的选项,可以很好的解决目前缓存的问题。
之前搜到知乎上一个问题,贺老的回答,我觉得很有意思,同时我也是赞同这种观点,loader的颗粒度肯定比bunding细,因为runtime我们能控制的更多,比如首屏我们并不需要所有的依赖,用户首屏会停留多长时间?用户之后有更大的概率跳到别的页面,我们可以提前缓存,所以我们能在loader的层面上控制,之后好好研究一下。
这个问题是写九章的项目发现的,他们把后端接口写好了,然后涉及到跨域,一般如果是我写的接口我回加载一个之前我写的一个中间件允许所有头,显然在这里是不实际的,在这里webpack有个转发功能proxy,我的配置如下:
new WebpackDevServer(webpack(config), {
publicPath: config.output.publicPath,
hot: true,
historyApiFallback: {
rewrites: [
{ from: /^\/$/, to: '/index.html' },
],
},
proxy: {
'/api': {
target: 'http://localhost:8000/api/',
pathRewrite: {'^/api' : ''},
secure: false,
},
},
setup: function (app) {
// app.get('/some/path', function (req, res) {
// you can set mock there,
// });
},
}).listen(3000, 'localhost', function (err, result) {
if (err) {
return console.log(err)
}
opn('http://localhost:3000/');
console.log('Listening at http://localhost:3000/')
});
然后我把之前给node写的脚手架用在这了,写了一个新的模板:
以后这样就可以方便的搭建环境:
npm install my-boom -g
boom reactBoom my-project
就可以了。
AlexNet has five CNN and three full connection
like this
using active function called RuLU(max(0,x)),which is non-saturating,but is not zero-meaning.the initialization is crucial.
using multiple GPUs by separating net like pic
using local response normalizaton
using overlapping pool
Date Augmentation
Drpout
0.5 output set zero
Dropout roughly doubles the number of iterations required to converge.
using momentum of 0.9
VGGNet has muti-structure followed the pic
using smaller convolutional cell and more deeper than AlexNet
training image size is random sampling from the pic,which is rescaling S.
We consider two approaches for setting the training scale S. The first is to fix S, which correspondsto single-scale training (note that image content within the sampled crops can still represent multi-scale image statistics). In our experiments, we evaluated models trained at two fixed scales: S =256 (which has been widely used in the prior art (Krizhevsky et al., 2012; Zeiler & Fergus, 2013;Sermanet et al., 2014)) and S = 384. Given a ConvNet configuration, we first trained the networkusing S = 256. To speed-up training of the S = 384 network, it was initialised with the weightspre-trained with S = 256, and we used a smaller initial learning rate of 10−3.
The second approach to setting S is multi-scale training, where each training image is individuallyrescaled by randomly sampling S from a certain range [Smin,Smax] (we used Smin = 256 andSmax = 512). Since objects in images can be of different size, it is beneficial to take this into accountduring training. This can also be seen as training set augmentation by scale jittering, where a single model is trained to recognise objects over a wide range of scales. For speed reasons, we trainedmulti-scale models by fine-tuning all layers of a single-scale model with the same configuration,pre-trained with fixed S = 384.
what is Internal Covariate Shif?I think the simplest answer is that the difference of distribution. For the machine problem, it shows that the different training distribution between testing distribution. Using normalizing, which make them to have zero means and unit variance, can handle this problem.
We define Internal Covariate Shift as the change in the distribution of network activations due to the change in network parameters during training.
Note that simply normalizing each input of a layer may change what the layer can represent. For instance, normalizing the inputs of a sigmoid would constrain them to the linear regime of the onlinearity. To address this, we make sure that the transformation inserted in the network can represent the identity transform. To accomplish this, we introduce, for each activation x(k) , a pair of parameters γ (k) , β(k), which scale and shift the normalized value:
the derivative shows that:
the detail about how to derivate
We use the unbiased variance estimate Var[x] = m/(m−1)· EB[σ2], where the expectation is over training mini-batches of size m and σ2 are their sample variances.
harris https://blog.csdn.net/zizi7/article/details/50112169
sift https://www.cnblogs.com/Alliswell-WP/p/SIFT.html
hog https://shartoo.github.io/2019/03/04/HOG-feature/
Seam-Carving
huofu变换
提取直线可以用这些
mean-shift
在未被标记的数据点中随机选择一个点作为起始中心点center;
找出以center为中心半径为radius的区域中出现的所有数据点,认为这些点同属于一个聚类C。同时在该聚类中记录数据点出现的次数加1。
以center为中心点,计算从center开始到集合M中每个元素的向量,将这些向量相加,得到向量shift。
center = center + shift。即center沿着shift的方向移动,移动距离是||shift||。
重复步骤2、3、4,直到shift的很小(就是迭代到收敛),记住此时的center。注意,这个迭代过程中遇到的点都应该归类到簇C。
如果收敛时当前簇C的center与其它已经存在的簇C2中心的距离小于阈值,那么把C2和C合并,数据点出现次数也对应合并。否则,把C作为新的聚类。
重复1、2、3、4、5直到所有的点都被标记为已访问。
分类:根据每个类,对每个点的访问频率,取访问频率最大的那个类,作为当前点集的所属类。
supervisorctl配置 mongo
supervisorctl出现 unix:///var/run/supervisor.sock refuseing error
把这个文件删掉 ,然后重新运行
supervisord -c /etc/supervisord.conf
[program:song] ;
;directory = /home/ubuntu/songSpider;
command = python3 /home/ubuntu/songSpider/getPlayList.py ;
startsecs = 10 ;
redirect_stderr = true ;
autorestart = true ;
stdout_logfile_maxbytes = 50MB ;
stdout_logfile = /home/ubuntu/super_song.log
[supervisorctl]
serverurl=unix:///tmp/supervisor.sock ; use a unix:// URL for a unix socket
mongo第一次运行的时候可能没有/data/db文件,然后添加登录验证
db.createUser({user: "simpleUser",pwd: "simplePass",roles: ["root" ]})
mongo --port 27017 -u "adminUser" -p "adminPass" --authenticationDatabase "admin"
mongod --auth --port 27017 --dbpath /data/db1
关闭mongo
pkill mongod
python连接
import pymongo
connection = pymongo.MongoClient('mongodb://xxx:pwd@localhost:27017/')
print('连接成功')
# user_info_db = connection.user_info
db = connection.song
user_info_coll = db.user_info
songs_coll = db['songlist' + songlistID]
注意 mongo的概念先db 在collection 再document
Body Mapping Templates
{
"address": "$input.params('address')",
"content": "$input.params('content')",
"title": "$input.params('title')"
}
注意双引号!
这就是个数学题出的不好,但是以后记得求中间和可以用前面的和减后面和
注意求解问题,可以先转化为部分问题求解,就像求数学题一样
def camelMatch(self, qs, p):
def u(s):
return [c for c in s if c.isupper()]
def issup(s, t):
it = iter(t)
return all(c in it for c in s)
return [u(p) == u(q) and issup(p, q) for q in qs]
注意这里iter的迭代情况
longest = collections.defaultdict(lambda: 2)
# dict's key can be tupe
动态规划双向考虑一下
我发现上题不用反过来也可以解。
这个可以用一个o(nlogn)的算法,维护一个数组,遍历原数组
def largestDivisibleSubset(self, nums):
S = {-1: set()}
for x in sorted(nums):
S[x] = max((S[d] for d in S if x % d == 0), key=len) | {x}
return list(max(S.values(), key=len))
对于有sqare的题目,使用数组缓存需要+1,一维数组可以用后缀数组求和
二维同样也可以
dp[i+1][j+1] = dp[i+1][j] + dp[i][j+1] + matrix[i][j] - dp[i][j]
这题用动态规划是o(n^2)如果不加if条件就会超时,还有种n的方法用的广度优先搜索
遇到 这种题真的……就是个排列组合的问题
跟 309的**差不多,在动态规划中维护了前几个好几个状态
class Solution:
def nthUglyNumber(self, n: int) -> int:
k = [1] *n
t2,t3,t5 = 0,0,0
for i in range(1,n):
k[i] = min(k[t2]*2, k[t3]*3, k[t5]*5)
if k[i] == k[t2] * 2:
t2+=1
if k[i] == k[t3] * 3:
t3+=1
if k[i] == k[t5] * 5:
t5+=1
return k[-1]
Partition Equal Subset Sum
注意转化问题,subsetSum为整个 array的一半
然后最大的和的dp数组,dp[0]=1 遍历每个数,逆序遍历 dp如果存在 dp[sum+num]=1,为什么要逆序,就是防止这次更改了dp的影响
Can I Win
就是搜索,加memo
Unique Substrings in Wraparound String
from functools import lru_cache
class Solution:
def findSubstringInWraproundString(self, p: str) -> int:
res = {i: 1 for i in p}
l = 1
for i,j in zip(p,p[1:]):
l = l + 1 if (ord(j) - ord(i))%26 == 1 else 1
res[j] = max(res[j], l)
return sum(res.values())
# 想清楚 dp的状态是哪一个 这题是以什么字母为结尾
# 最优子结构之间的关系这种
# 只要得到最大的去重这步自然就解决了,因为对于相同字母结尾有相同顺序的一定有一样的结构按顺序的精妙!
像413. Arithmetic Slices
这种dp中安某种顺序序列增长的个数dp问题,一般都为O(n)解法,并且dp[i]= dp[i-1]+1 if some true else 1
c语言指针跟数组的区别——和mapreduce的**
关键要知道每个符号的地址在编译时可知。所以如果编译器需要地址加上偏移量这种操作就可以直接进行操作,比如数组。相反,指针必须在运行的时取得它当前值,然后才能进行应用操作。
char *p = "abcdefgh";
c = p[i]
编译器具有一个p 地址为4624
运行时取4624的内容 5081
取得i的值与5081相加
取地址[5081+i]的内容
声明extern char *p;却定义是char p[10],当用P[10]这种形式提取这个声明内容时,实际上得到是一个字符。但按照上面的方法,编译器却把它当做是一个指针把ascii字符解释为地址显然是牛头不对马嘴。
以上内容来自expert c programming
function map(String name, String document):
// name: document name
// document: document contents
for each word w in document:
emit (w, 1)
function reduce(String word, Iterator partialCounts):
// word: a word
// partialCounts: a list of aggregated partial counts
sum = 0
for each pc in partialCounts:
sum += pc
emit (word, sum)
//from wikipedia
按照我的理解,MapReduce有个map函数,和一个reduce函数,他们接受的参数也是一定的,跟状态没有关系,而且返回时key-value也跟状态没有关系,这样就可以在分布式里运用消息队列和键值数据库。
看别人代码还是很有好处的,无意中看到朋友的circleci构建流程,原本我总是以为这样的ci也就是跑一个测试,后来发现可以构建一个docker然后服务器直接部署,为什么我会想到用docker部署,因为服务器学生优惠到期了……上面跑了好多项目,要是我一个个迁移得累死我……
因为circleci只支持github和bu啥的后者真的太难用,但是这些部署构建涉及到密码,必须搞一个私人项目,没办法测试一下,整个流程直接看项目配置就好没什么难点,但是有一点需要更正我对容器的理解,并不能像虚拟机那么理解。
提到
CMD
就不得不提容器中应用在前台执行和后台执行的问题。这是初学者常出现的一个混淆。Docker 不是虚拟机,容器中的应用都应该以前台执行,而不是像虚拟机、物理机里面那样,用 upstart/systemd 去启动后台服务,容器内没有后台服务的概念。
一些初学者将
CMD
写为:CMD service nginx start
然后发现容器执行后就立即退出了。甚至在容器内去使用
systemctl
命令结果却发现根本执行不了。这就是因为没有搞明白前台、后台的概念,没有区分容器和虚拟机的差异,依旧在以传统虚拟机的角度去理解容器。对于容器而言,其启动程序就是容器应用进程,容器就是为了主进程而存在的,主进程退出,容器就失去了存在的意义,从而退出,其它辅助进程不是它需要关心的东西
而使用
service nginx start
命令,则是希望 upstart 来以后台守护进程形式启动nginx
服务。而刚才说了CMD service nginx start
会被理解为CMD [ "sh", "-c", "service nginx start"]
,因此主进程实际上是sh
。那么当service nginx start
命令结束后,sh
也就结束了,sh
作为主进程退出了,自然就会令容器退出。正确的做法是直接执行
nginx
可执行文件,并且要求以前台形式运行。比如:CMD ["nginx", "-g", "daemon off;"]
标签(空格分隔): 未分类
组件的子组件以this.props.children形式传进去默认是不会update。
这个很好理解:
显示申明
this.props.children
但是如果组件上是有context无论是否改变也会更新子组件(this.props.children形式)
官网链接
tip: 子组件一定要写像这样的,不然收到的会是空的对象
P.contextTypes = {
color: PropTypes.string
}
这里重点说一个bug,当我们用react-intel和mobx的时候,由于各种各样的原因无法改变了context无法更新,所以我们很好奇。是不是context被block掉。
看这篇文章
要点:
I'd recommend going with
<IntlProvider key={locale}>
to force a full teardown until the underlying React context issue is resolved.
react-intl issue 234
todo react context should
标签(空格分隔): JS
先看一段代码:
setImmediate(function(){
console.log(1);
},0);
setTimeout(function(){
console.log(2);
},0);
new Promise(function(resolve){
console.log(3);
resolve();
console.log(4);
}).then(function(){
console.log(5);
});
console.log(6);
process.nextTick(function(){
console.log(7);
});
console.log(8);
正确顺序: 3 4 6 8 7 5 2 1
为什么了,原来我以前的理解js里只有一个队列,但是经过最近的搜索发现不是,js里有两种task queue,一个叫microtask一个是macrotask。
分别有什么了?
macrotasks: script(整体代码),setTimeout, setInterval, setImmediate, I/O, UI rendering
microtasks: process.nextTick, Promises, Object.observe, MutationObserver
PS.MutationObserver 的解释
那执行顺序是什么了?
One go-around of the event loop will have exactly one task being processed from the macrotask queue (this queue is simply called the task queue in the WHATWG specification). After this macrotask has finished, all available microtasks will be processed, namely within the same go-around cycle. While these microtasks are processed, they can queue even more microtasks, which will all be run one by one, until the microtask queue is exhausted.
简单来说,就是JavaScript引擎首先从macrotask queue中取出第一个任务,
执行完毕后,将microtask queue中的所有任务取出,按顺序全部执行;
然后再从macrotask queue中取下一个,
执行完毕后,再次将microtask queue中的全部取出;
循环往复,直到两个queue中的任务都取完。
那上面代码理解了吧,至于process.nextTick在promise前面,正如他字面的意思就是,在主任务队列运行玩就立马运行,详细见这篇官方文章
这篇文章解答了上面大部分问题:
- setImmediate() is designed to execute a script once the current poll phase completes.
The order in which the timers are executed will vary depending on the context in which they are called. If both are called from within the main module, then timing will be bound by the performance of the process (which can be impacted by other applications running on the machine).
// timeout_vs_immediate.js
setTimeout(function timeout () {
console.log('timeout');
},0);
setImmediate(function immediate () {
console.log('immediate');
});
$ node timeout_vs_immediate.js
timeout
immediate
$ node timeout_vs_immediate.js
immediate
timeout
// timeout_vs_immediate.js
var fs = require('fs')
fs.readFile(__filename, () => {
setTimeout(() => {
console.log('timeout')
}, 0)
setImmediate(() => {
console.log('immediate')
})
})
$ node timeout_vs_immediate.js
immediate
timeout
$ node timeout_vs_immediate.js
immediate
timeout
简而言之在没有IO包括的情况下,运行是不确定的但是在IO圈下是setImmediate立即执行,但是加了上面的示例代码中却setImmediate永远是最后。(等会研究一下)
We recommend developers use setImmediate() in all cases because it's easier to reason about (and it leads to code that's compatible with a wider variety of environments, like browser JS.)
在setImmediate和process.nextTick()都可以的情况下优先用setImmediate因为可以兼容大部分环境。
然后有以下几种情况用process.nextTick()
Allow users to handle errors, cleanup any then unneeded resources, or perhaps try the request again before the event loop continues.
At times it's necessary to allow a callback to run after the call stack has unwound but before the event loop continues.
打个比方
const EventEmitter = require('events');
const util = require('util');
function MyEmitter() {
EventEmitter.call(this);
this.emit('event');
}
util.inherits(MyEmitter, EventEmitter);
const myEmitter = new MyEmitter();
myEmitter.on('event', function() {
console.log('an event occurred!');
});
这个事件永远不会运行,因为触发事件在new的时候就触发了,所以要这样:
const EventEmitter = require('events');
const util = require('util');
function MyEmitter() {
EventEmitter.call(this);
// use nextTick to emit the event once a handler is assigned
process.nextTick(function () {
this.emit('event');
}.bind(this));
}
util.inherits(MyEmitter, EventEmitter);
const myEmitter = new MyEmitter();
myEmitter.on('event', function() {
console.log('an event occurred!');
});
在http模块就是这样:
var server = net.createServer();
server.on('connection', function(conn) { });
server.listen(8080);
server.on('listening', function() { });
最后
// this has an asynchronous signature, but calls callback synchronously
function someAsyncApiCall (callback) { callback(); };
// the callback is called before `someAsyncApiCall` completes.
someAsyncApiCall(() => {
// since someAsyncApiCall has completed, bar hasn't been assigned any value
console.log('bar', bar); // undefined
});
var bar = 1;
function someAsyncApiCall (callback) {
process.nextTick(callback);
};
someAsyncApiCall(() => {
console.log('bar', bar); // 1
});
var bar = 1;
设计回调的时候要想清楚~
参考链接:
为什么突然想到搞动态规划,毕设搞的分词实现vetebi算法的时候需要动态规划愣是看不懂。话说我接触动态规划挺久的但就是老是忘,就像有的刷的题我觉得还是没真正的理解,如果真正理解应该是不会忘的。
动态规划是通过拆分问题,定义问题状态和状态之间的关系,使得问题能够以递推(或者说分治)的方式去解决。
本题下的其他答案,大多都是在说递推的求解方法,但如何拆分问题,才是动态规划的核心。
而拆分问题,靠的就是状态的定义和状态转移方程的定义。
上面就是我在知乎上找到的定义,之前理解的不是很深刻,但是最近结合做题什么的,理解的还行我们直接先看一题进入状态。
每天可以做简单的任务或者难的任务,难的只有在前一天没做的时候才可以做。
dp[n] = max(dp[n-1]+list[n][0], dp[n-2]+list[n][1])
动态规划最经典的问题就是背包问题,我找了两个参考链接1,2,需要结合起来看才能看懂。
首先动态规划可以用递归去做,而且更好理解对于初学者来说,但是不得不说有个问题。会有重复计算导致做题超时啥的。
f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}
for(int i = 1; i <= n; i++)
{
for(int j = 0; j <= W; j++)
{
if(j < w[i]) dp[i][j] = dp[i-1][j];
else
dp[i][j] = max(dp[i-1][j], dp[i-1][j - w[i]] + v[i]);
}
}
还有个节省内存的方法
int f[w+1];
for (int i=0; i<n; i++)
for (int j=w; j>=size[i]; j--)
f[j] = max(f[j], f[j-size[i]]+value[i]);
case
int w[] = {1,4,1,1};
int v[] = {2,3,4,6};
// 总容量 4
过程
w:4 3 2 1
2 2 2 2
3
6 6 6 4
12 12 10 6
我们看到的求最优解的背包问题题目中,事实上有两种不太相同的问法。有的题目要求“恰好装满背包”时的最优解,有的题目则并没有要求必须把背包装满。一种区别这两种问法的实现方法是在初始化的时候有所不同。
如果是第一种问法,要求恰好装满背包,那么在初始化时除了f[0]为0其它f[1..V]均设为-∞,这样就可以保证最终得到的f[N]是一种恰好装满背包的最优解。
如果并没有要求必须把背包装满,而是只希望价格尽量大,初始化时应该将f[0..V]全部设为0。
为什么呢?可以这样理解:初始化的f数组事实上就是在没有任何物品可以放入背包时的合法状态。如果要求背包恰好装满,那么此时只有容量为0的背包可能被价值为0的nothing“恰好装满”,其它容量的背包均没有合法的解,属于未定义的状态,它们的值就都应该是-∞了。如果背包并非必须被装满,那么任何容量的背包都有一个合法解“什么都不装”,这个解的价值为0,所以初始时状态的值也就全部为0了。
物品不止一件
f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k*c[i]<=v}
for (int i=0; i<n; i++)
for (int j=size[i]; j<=w; j++)
f[j] = max(f[j], f[j-size[i]]+value[i]);
f[i][v] = max{f[i − 1][v − k × c[i]] + k × w[i]} 0 <= k <= n[i]
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int Value[105];
int Cost[105];
int Bag[105];
int dp[105];
int main()
{
int C,m,n;
scanf("%d",&C);
while(C--)
{
scanf("%d%d",&n,&m);
for(int i = 1; i <= m; i++)
scanf("%d%d%d",&Cost[i],&Value[i],&Bag[i]);
memset(dp,0,sizeof(dp));
for(int i=1; i<= m; i++)
for(int j=1; j<=Bag[i]; j++)
for(int k=n; k>=Cost[i]; k--)
dp[k]=max(dp[k], dp[k-Cost[i]]+Value[i]);
printf("%d\n",dp[n]);
}
return 0;
}
上面是没经过优化的多重背包,一个一个的考虑,经过优化的用二进制进行分解然后转化为01背包就ok。
#include <iostream>
using namespace std;
int main()
{
int nCase,Limit,nKind,i,j,k, v[111],w[111],c[111],dp[111];
//v[]存价值,w[]存尺寸,c[]存件数
//在本题中,价值是米的重量,尺寸是米的价格
int count,Value[1111],size[1111];
//count存储分解完后的物品总数
//Value存储分解完后每件物品的价值
//size存储分解完后每件物品的尺寸
cin>>nCase;
while(nCase--)
{
count=0;
cin>>Limit>>nKind;
for(i=0; i<nKind; i++)
{
cin>>w[i]>>v[i]>>c[i];
//对该种类的c[i]件物品进行二进制分解
for(j=1; j<=c[i]; j<<=1)
{
//<<左移1位,相当于乘2
Value[count]=j*v[i];
size[count++]=j*w[i];
c[i]-=j;
}
if(c[i]>0)
{
Value[count]=c[i]*v[i];
size[count++]=c[i]*w[i];
}
}
//经过上面对每一种物品的分解,
//现在Value[]存的就是分解后的物品价值
//size[]存的就是分解后的物品尺寸
//count就相当于原来的n
//下面就直接用01背包算法来解
memset(dp,0,sizeof(dp));
for(i=0; i<count; i++)
for(j=Limit; j>=size[i]; j--)
if(dp[j]<dp[j-size[i]]+Value[i])
dp[j]=dp[j-size[i]]+Value[i];
cout<<dp[Limit]<<endl;
}
return 0;
}
之后准备把母函数加上去的,但是这个内容真的太多了,等下一篇再加吧。
一文读懂faster rcnn
feture上的anchor box是通过缩放到原图上的
目标检测|SSD原理与实现
1、negative example过多造成它的loss太大,以至于把positive的loss都淹没掉了,不利于目标的收敛;
2、大多negative example不在前景和背景的过渡区域上,分类很明确(这种易分类的negative称为easy negative),训练时对应的背景类score会很大,换个角度看就是单个example的loss很小,反向计算时梯度小。梯度小造成easy negative example对参数的收敛作用很有限,我们更需要loss大的对参数收敛影响也更大的example,即hard positive/negative example。
这里要注意的是前一点我们说了negative的loss很大,是因为negative的绝对数量多,所以总loss大;后一点说easy negative的loss小,是针对单个example而言。
最开始认识到堆是从知乎看来的,当时是看到一个题目:
有一个数量很大的乱序的数的集合,找出其中的top100
当时排名最高的答案是维护一个长度为100的min堆然后扫一遍就可以当时给的时间复杂度是O(NlogN)就觉得很是神奇。
堆真的很神奇,这里只说是二叉堆,因为二叉堆的性质,完全可以用数组来表示。
一般可能在0上放一个head,这样二叉堆的左儿子就是2i,右儿子就是(2i+1)
def insert(self,element):
i = self.getSize() + 1
self.elements.append(None)
while self.elements[i/2] > element:
self.elements[i] = self.elements[i/2]
i/=2
self.elements[i] = element
其中涉及到一个percolate up过程,就是先插入一个空的,插入的值跟父节点比较,一直往上一直大于父节点就停止。
删除最小涉及到一个percolate down的过程。代码如下:
def siftdown(self,i):
elements = self.elements
tmp=elements[i]
while(2*i<len(elements)):
child=2*i
if child+1 < len(elements):
if(elements[child+1]<elements[child]):
child+=1
if(tmp>elements[child]):
elements[i]=elements[child]
else:
break
i=child
elements[i]=tmp
def deleteMin(self):
if self.isEmpty():
raise Exception('heap is empty')
temp = self.elements[1]
self.elements[1]=self.elements[-1]
self.elements.pop()
self.siftdown(1)
return temp
说一下这里的思路,这里这个下滤比上滤难理解一点。我这里借鉴了这里的思路,但是实现思路还是书(《数据结构与算法分析》下同)上的。
首先传进来的i就是要下滤的元素,找到他的子节点,左右比一下看谁更大或者更小,然后再跟父节点比较看是否需要交换,然后一直往下沉。这里需要强调两点:
给你一堆数你怎么把他变成堆呢?
for(i=n/2; i>0; i--)
PercolateDown(i)
就是从最后一个叶子节点的父节点不停的下滤就得到一个heap,时间复杂度O(N)
我最开始说了一个问题完全可以还有另外一种方式,把所有的数构造成heap然后不停的deleteMax就可以了。
堆排序的思路很简单,我上面说的思路就是堆排序的思路当然有些优化方式,具体请看下一节算法篇————排序
堆其实还有另外一个名字————优先队列,在操作系统里进程的调度也是通过堆实现的,具体怎么实现,我也不知道,不过我最近正在看linux内核
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.