必备基础

1. 实现归并排序。

def merge(left, right):
    i, j = 0, 0
    result = []
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result += left[i:]
    result += right[j:]
    return result
 
def merge_sort(lists):
    # 归并排序
    if len(lists) <= 1:
        return lists
    num = len(lists) / 2
    left = merge_sort(lists[:num])
    right = merge_sort(lists[num:])
    return merge(left, right)

2. 二叉树的S型遍历。

# -*- coding: utf-8 -*-
"""
Created on Mon Apr 03 19:58:58 2017
@author: Administrator
"""
class node(object):
    def __init__(self,data=None,left=None,right=None):
        self.data=data
        self.left=left
        self.right=right
       
#深度
def depth(tree):
    if tree==None:
        return 0
    left,right=depth(tree.left),depth(tree.right)
    return max(left,right)+1
#前序遍历   
def pre_order(tree):
    if tree==None:
        return
    print tree.data
    pre_order(tree.left)
    pre_order(tree.right)
#中序遍历   
def mid_order(tree):
    if tree==None:
        return
    mid_order(tree.left)
    print tree.data
    mid_order(tree.right)    
#后序遍历   
def post_order(tree):
    if tree==None:
        return
    post_order(tree.left)
    post_order(tree.right)   
    print tree.data
    
#层次遍历    
def level_order(tree):
     if tree==None:
        return 
     q=[]
     q.append(tree)
     while q:
         current=q.pop(0)
         print current.data
         if current.left!=None:
            q.append(current.left)
         if current.right!=None:
            q.append(current.right)
#按层次打印
def level2_order(tree):
     if tree==None:
        return 
     q=[]
     q.append(tree)
     results={}
     level=0
     current_level_num=1
     nextlevelnum=0
     d=[]
     while q: 
         current=q.pop(0)
         current_level_num-=1
         d.append(current.data)
         if current.left!=None:
            q.append(current.left) 
            nextlevelnum+=1
         if current.right!=None:
            q.append(current.right) 
            nextlevelnum+=1   
         if current_level_num==0:
            current_level_num=nextlevelnum
            nextlevelnum=0
            results[level]=d
            d=[]
            level+=1
     print results    
     
if __name__=='__main__':  
    tree=node('D',node('B',node('A'),node('C')),node('E',right=node('G',node('F'))))  
    print'前序遍历:'  
    pre_order(tree)  
    print('\n')  
    print('中序遍历:')  
    mid_order(tree)  
    print('\n')  
    print '后序遍历:'  
    post_order(tree)  
    print('\n')  
    print "层次遍历"
    level2_order(tree)

 

堆排序

堆排序(Heapsort)是指利用堆积树(堆)这种数据结构所设计的一种排序算法,它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆,是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值,即A[PARENT[i]] >= A[i]。在数组的非降序排序中,需要使用的就是大根堆,因为根据大根堆的要求可知,最大的值一定在堆顶。

def adjust_heap(lists, i, size):
    lchild = 2 * i + 1
    rchild = 2 * i + 2
    max = i
    if i < size / 2:
        if lchild < size and lists[lchild] > lists[max]:
            max = lchild
        if rchild < size and lists[rchild] > lists[max]:
            max = rchild
        if max != i:
            lists[max], lists[i] = lists[i], lists[max]
            adjust_heap(lists, max, size)
 
def build_heap(lists, size):
    for i in range(0, (size/2))[::-1]:
        adjust_heap(lists, i, size)
 
def heap_sort(lists):
    size = len(lists)
    build_heap(lists, size)
    for i in range(0, size)[::-1]:
        lists[0], lists[i] = lists[i], lists[0]
        adjust_heap(lists, 0, i)

String to int

#include "stdio.h"

int isDigit(int s)//判断是否是数字
{
if(s >= '0' && s <= '9')
return 1;
else
return 0;
}
int my_atoi(const char* str)
{
int c;
int sum = 0;
int sign;
while((*str)==' ' || (*str) == '\n' || (*str) == '\r' || (*str) == '\t')//判断是否是空格换行之类的空字符,有则跳过
str++;

sign = *str; //符号
if(sign == '-' || sign == '+')//若有符号则跳过
str++;
c = (int)*str++;
while(isDigit(c))
{
sum = 10 * sum + (c - '0');
c = (int)*str++;
}
if(sign == '-')
return -sum;
else
return sum;
}


int main()
{
char* str = "-123";
printf("%d\n",my_atoi(str));
return 0;
}
IP to int
    如255.255.255.0,分别把3个2550和0保存在数组arr[]中。(自行判断ip地址合法性)
#include <stdio.h>  
#include <stdlib.h>  
#include <string.h>  
#include <math.h>  
   
#define LEN 16  
   
typedef unsigned int uint;  
   
/**
* 字符串转整形
*/
uint ipTint(char *ipstr)  
{  
    if (ipstr == NULL)  return 0;  
   
    char *token;  
    uint i = 3, total = 0, cur;  
   
    token = strtok(ipstr, ".");  
   
    while (token != NULL) {  
        cur = atoi(token);  
        if (cur >= 0 && cur <= 255) {  
            total += cur * pow(256, i);  
        }  
        i --;  
        token = strtok(NULL, ".");  
    }  
   
    return total;  
}  
   
/**
* 逆置字符串
*/
void swapStr(char *str, int begin, int end)  
{  
    int i, j;  
   
    for (i = begin, j = end; i <= j; i ++, j --) {  
        if (str[i] != str[j]) {  
            str[i] = str[i] ^ str[j];  
            str[j] = str[i] ^ str[j];  
            str[i] = str[i] ^ str[j];  
        }  
    }  
}  
   
/**
* 整形转ip字符串
*/
char* ipTstr(uint ipint)  
{  
    char *new = (char *)malloc(LEN);  
    memset(new, '\0', LEN);  
    new[0] = '.';  
    char token[4];  
    int bt, ed, len, cur;  
   
    while (ipint) {  
        cur = ipint % 256;  
        sprintf(token, "%d", cur);  
        strcat(new, token);  
        ipint /= 256;  
        if (ipint)  strcat(new, ".");  
    }  
   
    len = strlen(new);  
    swapStr(new, 0, len - 1);  
   
    for (bt = ed = 0; ed < len;) {  
        while (ed < len && new[ed] != '.') {  
            ed ++;  
        }  
        swapStr(new, bt, ed - 1);  
        ed += 1;  
        bt = ed;  
    }  
   
    new[len - 1] = '\0';  
   
    return new;  
}  
   
int main(void)  
{  
    char ipstr[LEN], *new;  
    uint ipint;  
   
    while (scanf("%s", ipstr) != EOF) {  
        ipint = ipTint(ipstr);  
        printf("%u\n", ipint);  
   
        new = ipTstr(ipint);  
        printf("%s\n", new);  
    }  
   
    return 0;  
}

给两个字符串,找到第二个在第一个出现的位置(Kmp)

#include <stdio.h>
#include<string.h>
void main()
{
    char M[100], C[100], l1, l2, i, j, k;
    printf("Input STR1: \n");   scanf("%s", C);
    printf("Input STR2: \n");   scanf("%s", M);
    l1 = strlen(C);   printf("Len1 = %d\n", l1);
    l2 = strlen(M);   printf("Len2 = %d\n", l2);
    j = (l2 - l1);
    for (i = 0; i < j; i++) {
      for (k = 0; k < l2; k++) 
        if (M[i + k] != C[k])  break;
      if (k == l1)  break;
    }
    if (i < j) printf("i = %d\n", i + 1);
    else       printf("no \n");
} 

LeetCode第一题“TwoSum”

int* twoSum(int* nums, int numsSize, int target) {
    int *a = (int*)malloc(2*sizeof(int));
    for(int i = 0;i<numsSize;i++)
    {
        for(int j = i+1;(j<numsSize && j != i);j++)
        {
            if(nums[i] + nums[j] == target)
            {
                a[0] = i;
                a[1] = j;
            }
        }
    }
    return a;
}

 

通过简单示例,详细解释ROC曲线,要求给出必要的公式推导。

受试者工作特征曲线 (receiver operating characteristic curve,简称ROC曲线),又称为感受性曲线(sensitivity curve)。得此名的原因在于曲线上各点反映着相同的感受性,它们都是对同一信号刺激的反应,只不过是在几种不同的判定标准下所得的结果而已。接受者操作特性曲线就是以假阳性概率(False positive rate)为横轴,击中概率为纵轴所组成的坐标图,和被试在特定刺激条件下由于采用不同的判断标准得出的不同结果画出的曲线。

 

3、  给出LR(逻辑回归)算法的cost function公式的推导过程。
 2个等长的有序数组,得到中位数;
def getMedian(nums1, nums2, n):
  ans1, ans2 = -1, -1
  i = j = 0
  for count in range(n+1):
    if i < n and (nums1[i] < nums2[j] or j >= n):
      ans1 = ans2
      ans2 = nums1[i]
      i += 1
    else :
      ans1 = ans2
      ans2 = nums2[j]
      j += 1
  return (ans1 + ans2)/2.0
if __name__ == '__main__':
  nums1 = [1, 12, 15, 26, 38]
  nums2 = [2, 13, 17, 30, 45]
  n1 = len(nums1)
  n2 = len(nums2)
  if n1 == n2:
    print("Median is %s", getMedian(nums1, nums2, n1))
  else:
    print("Can't work for nums of unequal size")

 

2个链表判断是否有公共节点(链表带环时的处理)
# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    # 思路一
    def FindFirstCommonNode1(self, pHead1, pHead2):
        # write code here
        if pHead1 is None or pHead2 is None:
            return None

        s1 = []
        s2 = []
        p1 = pHead1
        p2 = pHead2
        while p1 is not None:
            s1.append(p1)
            p1 = p1.next
        while p2 is not None:
            s2.append(p2)
            p2 = p2.next

        res = None
        while len(s1) > 0 and len(s2) > 0:
            v1 = s1.pop()
            v2 = s2.pop()
            if v1 == v2:
                res = v1
            else:
                break
        return res

    # 思路二
    def getIntersectionNode2(self, headA, headB):
        # write your code here
        s1 = 0
        s2 = 0
        h1 = headA
        h2 = headB
        while h1 is not None:
            s1 += 1
            h1 = h1.next
        while h2 is not None:
            s2 += 1
            h2 = h2.next
        if s2 > s1:
            h2 = headB
            while s2 - s1 > 0:
                h2 = h2.next
                s2 -= 1
            h1 = headA
        elif s2 < s1:
            h1 = headA
            while s1 - s2 > 0:
                h1 = h1.next
                s1 -= 1
            h2 = headB
        else:
            h1 = headA
            h2 = headB
        res = None
        while h1 is not None and h2 is not None:
            if h1 == h2:
                res = h1
                return h1
            h1 = h1.next
            h2 = h2.next
        return res

 

给定2个字符串找到最长的公共串

# coding:utf-8
'''
求两个字符串的最长公共子串
思想:建立一个二维数组,保存连续位相同与否的状态
'''

def getNumofCommonSubstr(str1, str2):

    lstr1 = len(str1)
    lstr2 = len(str2)
    record = [[0 for i in range(lstr2+1)] for j in range(lstr1+1)]  # 多一位
    maxNum = 0          # 最长匹配长度
    p = 0               # 匹配的起始位

    for i in range(lstr1):
        for j in range(lstr2):
            if str1[i] == str2[j]:
                # 相同则累加
                record[i+1][j+1] = record[i][j] + 1
                if record[i+1][j+1] > maxNum:
                    # 获取最大匹配长度
                    maxNum = record[i+1][j+1]
                    # 记录最大匹配长度的终止位置
                    p = i + 1
    return str1[p-maxNum:p], maxNum


if __name__ == '__main__':
    str1 = raw_input()
    str2 = raw_input()

    res = getNumofCommonSubstr(str1, str2)
    print res

 

 

 

1、  梯度下降:为什么多元函数在负梯度方向下降最快

因为就那确定的点来说,梯度方向下降最快(有

泰勒

展开式得),而从全局来看,此点的最有方向(负梯度方向)不是全局的最优方向


2、  Sigmoid激活函数为什么会出现梯度消失?Sigmoid函数导数的最大值出现在哪个值?–>(x=0处)
        ReLU激活函数为什么能解决梯度消失问题?
http://blog.csdn.net/DanyHgc/article/details/73850546
  1. 什么是激活函数
  2. 为什么要用
  3. 都有什么
  4. sigmoid ,ReLU, softmax 的比较
  5. 如何选择

1. 什么是激活函数

如下图,在神经元中,输入的 inputs 通过加权,求和后,还被作用了一个函数,这个函数就是激活函数 Activation Function。


2. 为什么要用

如果不用激励函数,每一层输出都是上层输入的线性函数,无论神经网络有多少层,输出都是输入的线性组合。
如果使用的话,激活函数给神经元引入了非线性因素,使得神经网络可以任意逼近任何非线性函数,这样神经网络就可以应用到众多的非线性模型中。


3. 都有什么

(1) sigmoid函数

公式:

曲线:

也叫 Logistic 函数,用于隐层神经元输出
取值范围为(0,1)
它可以将一个实数映射到(0,1)的区间,可以用来做二分类。
在特征相差比较复杂或是相差不是特别大时效果比较好。

sigmoid缺点:
激活函数计算量大,反向传播求误差梯度时,求导涉及除法
反向传播时,很容易就会出现梯度消失的情况,从而无法完成深层网络的训练

下面解释为何会出现梯度消失:

反向传播算法中,要对激活函数求导,sigmoid 的导数表达式为:

sigmoid 原函数及导数图形如下:

由图可知,导数从 0 开始很快就又趋近于 0 了,易造成“梯度消失”现象

(2) Tanh函数

公式

曲线

也称为双切正切函数
取值范围为[-1,1]。
tanh在特征相差明显时的效果会很好,在循环过程中会不断扩大特征效果。
与 sigmoid 的区别是,tanh 是 0 均值的,因此实际应用中 tanh 会比 sigmoid 更好

(3) ReLU

Rectified Linear Unit(ReLU) – 用于隐层神经元输出

公式

曲线

输入信号 <0 时,输出都是0,>0 的情况下,输出等于输入

ReLU 的优点:
Krizhevsky et al. 发现使用 ReLU 得到的 SGD 的收敛速度会比 sigmoid/tanh 快很多

ReLU 的缺点:
训练的时候很”脆弱”,很容易就”die”了
例如,一个非常大的梯度流过一个 ReLU 神经元,更新过参数之后,这个神经元再也不会对任何数据有激活现象了,那么这个神经元的梯度就永远都会是 0.
如果 learning rate 很大,那么很有可能网络中的 40% 的神经元都”dead”了。

(4) softmax函数

Softmax – 用于多分类神经网络输出

公式

举个例子来看公式的意思:

就是如果某一个 zj 大过其他 z, 那这个映射的分量就逼近于 1,其他就逼近于 0,主要应用就是多分类。

为什么要取指数,第一个原因是要模拟 max 的行为,所以要让大的更大。
第二个原因是需要一个可导的函数。


4. sigmoid ,ReLU, softmax 的比较

Sigmoid 和 ReLU 比较:

sigmoid 的梯度消失问题,ReLU 的导数就不存在这样的问题,它的导数表达式如下:

曲线如图

对比sigmoid类函数主要变化是:
1)单侧抑制
2)相对宽阔的兴奋边界
3)稀疏激活性。

Sigmoid 和 Softmax 区别:

softmax is a generalization of logistic function that “squashes”(maps) a K-dimensional vector z of arbitrary real values to a K-dimensional vector σ(z) of real values in the range (0, 1) that add up to 1.

sigmoid将一个real value映射到(0,1)的区间,用来做二分类。

而 softmax 把一个 k 维的real value向量(a1,a2,a3,a4….)映射成一个(b1,b2,b3,b4….)其中 bi 是一个 0~1 的常数,输出神经元之和为 1.0,所以相当于概率值,然后可以根据 bi 的概率大小来进行多分类的任务。

二分类问题时 sigmoid 和 softmax 是一样的,求的都是 cross entropy loss,而 softmax 可以用于多分类问题

softmax是sigmoid的扩展,因为,当类别数 k=2 时,softmax 回归退化为 logistic 回归。具体地说,当 k=2 时,softmax 回归的假设函数为:

利用softmax回归参数冗余的特点,从两个参数向量中都减去向量θ1 ,得到:

最后,用 θ′ 来表示 θ2−θ1,上述公式可以表示为 softmax 回归器预测其中一个类别的概率为

另一个类别概率的为

这与 logistic回归是一致的。

softmax建模使用的分布是多项式分布,而logistic则基于伯努利分布

多个logistic回归通过叠加也同样可以实现多分类的效果,但是 softmax回归进行的多分类,类与类之间是互斥的,即一个输入只能被归为一类;多个logistic回归进行多分类,输出的类别并不是互斥的,即”苹果”这个词语既属于”水果”类也属于”3C”类别。


5. 如何选择

选择的时候,就是根据各个函数的优缺点来配置,例如:

如果使用 ReLU,要小心设置 learning rate,注意不要让网络出现很多 “dead” 神经元,如果不好解决,可以试试 Leaky ReLU、PReLU 或者 Maxout.

 

3、  Softmax是和什么loss function配合使用?–>多项式回归loss
该loss function的公式?
  1. 什么是激活函数
  2. 为什么要用
  3. 都有什么
  4. sigmoid ,ReLU, softmax 的比较
  5. 如何选择

1. 什么是激活函数

如下图,在神经元中,输入的 inputs 通过加权,求和后,还被作用了一个函数,这个函数就是激活函数 Activation Function。


2. 为什么要用

如果不用激励函数,每一层输出都是上层输入的线性函数,无论神经网络有多少层,输出都是输入的线性组合。
如果使用的话,激活函数给神经元引入了非线性因素,使得神经网络可以任意逼近任何非线性函数,这样神经网络就可以应用到众多的非线性模型中。


3. 都有什么

(1) sigmoid函数

公式:

曲线:

也叫 Logistic 函数,用于隐层神经元输出
取值范围为(0,1)
它可以将一个实数映射到(0,1)的区间,可以用来做二分类。
在特征相差比较复杂或是相差不是特别大时效果比较好。

sigmoid缺点:
激活函数计算量大,反向传播求误差梯度时,求导涉及除法
反向传播时,很容易就会出现梯度消失的情况,从而无法完成深层网络的训练

下面解释为何会出现梯度消失:

反向传播算法中,要对激活函数求导,sigmoid 的导数表达式为:

sigmoid 原函数及导数图形如下:

由图可知,导数从 0 开始很快就又趋近于 0 了,易造成“梯度消失”现象

(2) Tanh函数

公式

曲线

也称为双切正切函数
取值范围为[-1,1]。
tanh在特征相差明显时的效果会很好,在循环过程中会不断扩大特征效果。
与 sigmoid 的区别是,tanh 是 0 均值的,因此实际应用中 tanh 会比 sigmoid 更好

(3) ReLU

Rectified Linear Unit(ReLU) – 用于隐层神经元输出

公式

曲线

输入信号 <0 时,输出都是0,>0 的情况下,输出等于输入

ReLU 的优点:
Krizhevsky et al. 发现使用 ReLU 得到的 SGD 的收敛速度会比 sigmoid/tanh 快很多

ReLU 的缺点:
训练的时候很”脆弱”,很容易就”die”了
例如,一个非常大的梯度流过一个 ReLU 神经元,更新过参数之后,这个神经元再也不会对任何数据有激活现象了,那么这个神经元的梯度就永远都会是 0.
如果 learning rate 很大,那么很有可能网络中的 40% 的神经元都”dead”了。

(4) softmax函数

Softmax – 用于多分类神经网络输出

公式

举个例子来看公式的意思:

就是如果某一个 zj 大过其他 z, 那这个映射的分量就逼近于 1,其他就逼近于 0,主要应用就是多分类。

为什么要取指数,第一个原因是要模拟 max 的行为,所以要让大的更大。
第二个原因是需要一个可导的函数。


4. sigmoid ,ReLU, softmax 的比较

Sigmoid 和 ReLU 比较:

sigmoid 的梯度消失问题,ReLU 的导数就不存在这样的问题,它的导数表达式如下:

曲线如图

对比sigmoid类函数主要变化是:
1)单侧抑制
2)相对宽阔的兴奋边界
3)稀疏激活性。

Sigmoid 和 Softmax 区别:

softmax is a generalization of logistic function that “squashes”(maps) a K-dimensional vector z of arbitrary real values to a K-dimensional vector σ(z) of real values in the range (0, 1) that add up to 1.

sigmoid将一个real value映射到(0,1)的区间,用来做二分类。

而 softmax 把一个 k 维的real value向量(a1,a2,a3,a4….)映射成一个(b1,b2,b3,b4….)其中 bi 是一个 0~1 的常数,输出神经元之和为 1.0,所以相当于概率值,然后可以根据 bi 的概率大小来进行多分类的任务。

二分类问题时 sigmoid 和 softmax 是一样的,求的都是 cross entropy loss,而 softmax 可以用于多分类问题

softmax是sigmoid的扩展,因为,当类别数 k=2 时,softmax 回归退化为 logistic 回归。具体地说,当 k=2 时,softmax 回归的假设函数为:

利用softmax回归参数冗余的特点,从两个参数向量中都减去向量θ1 ,得到:

最后,用 θ′ 来表示 θ2−θ1,上述公式可以表示为 softmax 回归器预测其中一个类别的概率为

另一个类别概率的为

这与 logistic回归是一致的。

softmax建模使用的分布是多项式分布,而logistic则基于伯努利分布

多个logistic回归通过叠加也同样可以实现多分类的效果,但是 softmax回归进行的多分类,类与类之间是互斥的,即一个输入只能被归为一类;多个logistic回归进行多分类,输出的类别并不是互斥的,即”苹果”这个词语既属于”水果”类也属于”3C”类别。


5. 如何选择

选择的时候,就是根据各个函数的优缺点来配置,例如:

如果使用 ReLU,要小心设置 learning rate,注意不要让网络出现很多 “dead” 神经元,如果不好解决,可以试试 Leaky ReLU、PReLU 或者 Maxout.

 

 

 

 

4、  (以xx loss function)推导BP算法?

 BP(backpropgationalgorithm ):后向传导算法,顾名思义就是从神经网络的输出(顶层)到输入(底层)进行求解。那么求解什么呢,求解的就是神经网络中的参数的导数,即参数梯度方向,从而就可以使用梯度下降等求解无约束问题(cost function的最值)的方法求得最终的参数。神经网络前向传播的过程比较简单,这里不做讲解(如果不了解,可以参看文献)。

1.问题分析

1.1 Cost function

假设我们有一个固定样本集,它包含 m 个样例。我们可以用批量梯度下降法来求解神经网络。具体来讲,对于单个样例(x,y),其代价函数为:

这是一个(二分之一的)方差代价函数。给定一个包含 m 个样例的数据集,我们可以定义整体代价函数为:

以上公式中的第一项J(W,b) 是一个均方差项。第二项是一个规则化项(也叫权重衰减项),其目的是减小权重的幅度,防止过度拟合。

 

1.2 梯度下降

梯度下降法中每一次迭代都按照如下公式对参数W 和b 进行更新:

由以上公式可以看出我们只需要求解出单个样例对单个参数的导数就可以了。

2. BP算法

如何求取单个样本的costfunction对参数的导数呢,为此我们引入了一个叫做”残差”的概念(也有称为敏感度;残差可以看做是对偏置参数b的导数,偏置变化多少,残差就变化多少,残差就是偏置的变化率)。然后通过这个残差来求解对参数的导数。我们用表示第l层第i个结点的残差,表示第l层第i个结点的激励值,其中:

下面给出反向传导算法的细节:

将上式中的nl-1与nl的关系替换为l和 l+1的关系,就可以得到:

以上逐次从后向前求导的过程即为”反向传导”的本意所在。直观的理解公式就是第l层第i个结点的残差等于第l+1层与其连接的所有结点的权值和残差的加权和再乘以该点对z的导数值。

4:计算我们所需要的偏导数,计算方法如下:

Cost function对参数(第l层第j个结点到第l+1层第i个结点的权值)的导数等于第l层第j个结点的激励值乘以第l+1层第i个结点的残差。

这样反向传播算法就可以表示为以下几个步骤:

实现批量梯度下降法中的一次迭代步骤如下:

5、  CNN中,卷积层的输入为df*df*M(weight,height,channel),输出为df*df*N(或输出为df*df*M),卷积核大小为dk*dk时,请问由输入得到输出的计算量为多少?题中默认stride=1
    计算量–>浮点数计算量:49HWC^2,27HWC^2–>会把滤波器用到每个像素上,即为长x宽x可学习的参数个数
6、  说一下dropout的原理?若在训练时,以p的概率关闭神经元,则在预测(测试)的时候概率1-p怎么使用?https://yq.aliyun.com/articles/68901
测试时,被dropout作用的层,每个神经元的输出都要乘以(1-p)à使训练和测试时的输出匹配

过拟合是深度神经网(DNN)中的一个常见问题:模型只学会在训练集上分类,这些年提出的许多过拟合问题的解决方案;其中dropout具有简单性并取得良好的结果:

Dropout

7e31586d15d887ae0901452e2e1b1c6cb94f882e

上图为Dropout的可视化表示,左边是应用Dropout之前的网络,右边是应用了Dropout的同一个网络。

Dropout的思想是训练整体DNN,并平均整个集合的结果,而不是训练单个DNN。DNNs是以概率P舍弃部分神经元,其它神经元以概率q=1-p被保留,舍去的神经元的输出都被设置为零。

引述作者

在标准神经网络中,每个参数的导数告诉其应该如何改变,以致损失函数最后被减少。因此神经元元可以通过这种方式修正其他单元的错误。但这可能导致复杂的协调,反过来导致过拟合,因为这些协调没有推广到未知数据。Dropout通过使其他隐藏单元存在不可靠性来防止共拟合。

简而言之:Dropout在实践中能很好工作是因为其在训练阶段阻止神经元的共适应。

Dropout如何工作

Dropout以概率p舍弃神经元并让其它神经元以概率q=1-p保留。每个神经元被关闭的概率是相同的。这意味着:

假设:

h(x)=xW+bdi维的输入xdh维输出空间上的线性投影;

a(h)是激活函数

在训练阶段中,将假设的投影作为修改的激活函数:

650f8f00ffeb3ef346a61ee248670abe173c4acb

其中D=(X1,…,Xdh)是dh维的伯努利变量Xi,伯努利随机变量具有以下概率质量分布:

32363b313f65d3bf4231c5c57eace39d6fb7cb2c

其中k是可能的输出。

将Dropout应用在第i个神经元上:

8899c12575bca1550dfd8127fd7eb0a2912a8f2a

其中P(Xi=0)=p

由于在训练阶段神经元保持q概率,在测试阶段必须仿真出在训练阶段使用的网络集的行为。

为此,作者建议通过系数q来缩放激活函数:

训练阶段fdb59b52bfa583cf08eaf7980e26e8fad453d148

测试阶段d6a2b220ee68540890eaf0dc537188c738600fb7

Inverted Dropout

与dropout稍微不同。该方法在训练阶段期间对激活值进行缩放,而测试阶段保持不变。

倒数Dropout的比例因子为223ab9380c566fb9a74ff8a0a127e1174593bdf8,因此:

训练阶段:6ebd718f4256f50134f7428bc5df4d3cc9ddceae

测试阶段6ccbf2b63a56155b6403093e8771952bb3e3515b

Inverted Dropout是Dropout在各种深度学习框架实践中实现的,因为它有助于一次性定义模型,并只需更改参数(保持/舍弃概率)就可以在同一模型上运行训练和测试过程。

一组神经元的Dropout

n个神经元的第h层在每个训练步骤中可以被看作是n个伯努利实验的集合,每个成功的概率等于p

因此舍弃部分神经元后h层的输出等于:

f580cf9006a568171c48ac7ec10f1d8997bf7d81

因为每一个神经元建模为伯努利随机变量,且所有这些随机变量是独立同分布的,舍去神经元的总数也是随机变量,称为二项式:

023627f0453afe34e4bebb9ee10dfb7678d87989

n次尝试中有k次成功的概率由概率质量分布给出:

55460b3bb5d23fc5fbc732366679150a56a67fec

当使用dropout时,定义了一个固定的舍去概率p,对于选定的层,成比例数量的神经元被舍弃。

3be3ad14ec1d82ebafe981d1d3fc40ef6132e020

从上图可以看出,无论p值是多少,舍去的平均神经元数量均衡为np

933a160e2ead33c8ea51c1c7d41a69d3bb369eda

此外可以注意到,围绕在p = 0.5值附近的分布是对称。

Dropout与其它正则化

Dropout通常使用L2归一化以及其他参数约束技术。正则化有助于保持较小的模型参数值。

L2归一化是损失的附加项,其中λ是一种超参数、F(W;x)是模型以及ε是真值y与和预测值y^之间的误差函数。

e596c69e772f833df283a96e806dde994d8b979d

通过梯度下降进行反向传播,减少了更新数量。

a762ce896975e697de82661ee4e69a11f6e92fad

Inverted Dropout和其他正则化

由于Dropout不会阻止参数增长和彼此压制,应用L2正则化可以起到作用。

明确缩放因子后,上述等式变为:

337e71fd721fded5b9298cad73ba6c3310057d6c

可以看出使用Inverted Dropout,学习率是由因子q进行缩放 。由于q在[0,1]之间,η和q之间的比例变化:

71cf583c223c9f4e2d7a3021640ae747b9f5dacd

q称为推动因素,因为其能增强学习速率,将r(q)称为有效的学习速率。

有效学习速率相对于所选的学习速率而言更高:基于此约束参数值的规一化可以帮助简化学习速率选择过程。

总结

1 Dropout存在两个版本:直接(不常用)和反转

2 单个神经元上的dropout可以使用伯努利随机变量建模

3 可以使用二项式随机变量来对一组神经元上的舍弃进行建模

4 即使舍弃神经元恰巧为np的概率是低的,但平均上np个神经元被舍弃。

5 Inverted Dropout提高学习率

6 Inverted Dropout应该与限制参数值的其他归一化技术一起使用,以便简化学习速率选择过程

7 Dropout有助于防止深层神经网络中的过度拟合

7、  传统机器学习是否了解?
第三章:线性模型
第四章:决策树
第五章:神经网络
第六章:支持向量机
第七章:贝叶斯分类器
第八章:集成学习
第九章:聚类
第十章:降维与度量学习
第十一章:特征选择与稀疏学习
第十二章:计算学习理论
第十三章:半监督学习
第十四章:概率图模型
第十五章:规则学习
第十六章:强化学习
8、  说一下作项目时遇到的困难?
数据少
9、  表达式为max(x,y)的激活函数,反向传播时,x、y上的梯度如何计算à

互联网提供了大量的信息,我们只需要一个搜索引擎就可以获取。然而,当大量的信息扑面而来,究竟如何区分相关信息和无关信息呢?

大脑在得到大量信息时,会努力理解和分类有用信息和不那么有用的信息。而在深度学习中,我们也需要一种类似的机制来分类传入的信息。

不是所有信息都是有用的,一些只是噪音。激活函数可以帮助神经网络做这种隔离。它激活有用的信息,并抑制无关的数据点。

激活函数如此重要,那么都有哪些比较热门呢?它们是如何工作的?又适合解决什么问题?本文将为你一一解答。以下是本文目录。

1.简单介绍神经网络

2.什么是激活函数?

3.可以不用激活函数吗?

4.常用的激活函数类型以及使用方法

Binary Step函数

 

线性函数

 

Sigmoid函数

 

tanh函数

 

ReLU函数

 

Leaky ReLU函数

 

Softmax函数

 

5.如何选择正确的激活函数?

 

简单介绍神经网络

 

在深入了解激活函数的细节之前,让我们先回顾一下什么是神经网络,以及它是如何运行的。神经网络是一种非常强大的机器学习机制,它基本上模拟人脑的学习方式。

大脑接受外界的刺激,对输入进行加工,然后产生输出。当任务变得复杂时,多个神经元会形成一个复杂的网络,传递信息。

人工神经网络试图模仿类似的行为。下图所示的网络就是由相互连接的神经元组成的人工神经网络。

上图中的黑色圆圈代表神经元。 每个神经元都有权重、偏差和激活函数。 信息进入输入层,神经元通过权重和偏差对输入信息进行线性变换,而非线性变换由激活函数完成。 信息从输入层传输到隐藏层,隐藏层对信息进行处理并将结果发送到输出层。 这被称为前向传播。如果产生的输出偏离预期值呢? 在神经网络中,我们将根据误差更新神经元的权重和偏差。 这个过程被称为反向传播。 一旦所有训练数据经过了这一过程,则最终的权重和偏差就被用于测试。

什么是激活函数?

激活函数是人工神经网络的一个极其重要的特征。它决定一个神经元是否应该被激活,激活代表神经元接收的信息与给定的信息有关。

激活函数对输入信息进行非线性变换。 然后将变换后的输出信息作为输入信息传给下一层神经元。

可以不用激活函数吗?

如果激活函数增加了许多复杂性,我们可以不用激活函数吗?

当然不行!当我们不用激活函数时,权重和偏差只会进行线性变换。线性方程很简单,但解决复杂问题的能力有限。没有激活函数的神经网络实质上只是一个线性回归模型。激活函数对输入进行非线性变换,使其能够学习和执行更复杂的任务。我们希望我们的神经网络能够处理复杂任务,如语言翻译和图像分类等。线性变换永远无法执行这样的任务。

激活函数使反向传播成为可能,因为激活函数的误差梯度可以用来调整权重和偏差。如果没有可微的非线性函数,这就不可能实现。

常用的激活函数类型以及使用方法

Binary Step函数

当我们有一个激活函数时,首先联想到的是一个自带阈值的分类器,用于激活神经元。下图中,如果y值高于给定的阈值,则激活神经元,否则禁用。

f(x) = 1, x&gt;=0

Binary Step函数非常简单,可以在创建二进制分类器时使用它。当我们只需要对单个类说“是”或“不是”时,Step函数是最好的选择,因为它要么激活神经元要么把它设为零。

函数的理论性比实用性强,在大多数情况下,我们需要将数据分入多个类而不仅仅放在一类中。此时,Step函数就有点不好用了。

此外,step函数的梯度为零,这使得step函数不能用于反向传播过程中。

f &#39;(x) = 0, for all x

线性函数

我们看到了step函数的问题,梯度为零,在反向传播过程中不可能更新权重和偏差。此时,我们可以用线性函数来代替简单的step函数。函数表达式:

f(x)=ax

上图中假设a为4。这时激活与输入成正比,输入的x值将被转换为ax。线性函数可用于不同的神经元,也可以激活多个神经元。当我们有多个类时,可以选择f(x)值最大的类。但线性函数仍然存在一个问题。让我们看看这个函数的导数。

f&#39;(x) = a

线性函数的导数是常数,也就是说它不依赖于输入值x

这意味着每次我们做反向传播时,梯度都是一样的。这是一个大问题,我们并没有真正减少误差。不仅如此,假设我们正在做一项复杂任务,需要使用多层神经网络。然而如果每一层都使用线性变换,不管我们有多少层,最终输出的还是输入的线性变换。因此,线性函数只适用于容易解释的简单任务。

Sigmoid函数

Sigmoid函数曾被广泛应用,但由于其自身的一些缺陷,现在已经很少用了。Sigmoid函数定义如下:

f(x)=1/(1+e^-x)

让我们来看看这个函数。

这是一个平滑函数,并且具有连续性和可微性。与线性函数相比,它的最大优点就是非线性。这意味着多个神经元使用S(Sigmoid简称)形函数作为激活函数时,输出也是非线性的。我们来看看曲线的形状。Y轴范围0-1,x轴在-3到3之间的梯度非常高,但在其他区域形状很平坦。这有什么用吗?

这意味着在[-3,3]这个范围内,x的少量变化也将导致y值的大幅度变化。因此,函数本质上试图将y值推向极值。 当我们尝试将值分类到特定的类时,使用Sigmoid函数非常理想。

让我们来看一下Sigmoid函数的梯度。

它是平滑的,依赖于x值,这意味着在反向传播过程中,我们可以使用这个函数。误差可以被反向传播,权重也可以相应地更新。

即使在今天,sigmoid函数也被广泛使用,但我们仍然需要解决一些问题。正如之前所看到的,这个函数在[-3,3]之外是相当平坦的。这意味着一旦x值不在[-3,3]内,梯度就变得很小,接近于零,而网络就得不到真正的学习。

sigmoid函数的另一个问题是,y轴取值范围[0,1]。这个函数在原点周围不对称,得到的值都是正的。我们不希望下一个神经元得到的值在任何时候都是正值,不过可以通过缩放sigmoid函数来解决这个问题,而这需要在tanh函数中发生。

tanh函数

tanh函数与Sigmoid函数非常相似。它实际上只是Sigmoid函数的一个放大版本。

tanh(x)=2sigmoid(2x)-1

还可以直接表示为:

tanh(x)=2/(1+e^(-2x)) -1

Tanh函数与sigmoid函数相似,但原点对称。它的范围从- 1到1。

它基本上解决了所有值符号相同的问题,而其他属性都与sigmoid函数相同。函数具有连续性和可微性。你可以看到函数是非线性的,所以我们可以很容易地将误差进行反向传播。

让我们看一下tanh函数的梯度。

与Sigmoid函数相比,tanh函数的梯度更陡。 使用sigmoid函数还是tanh函数取决于问题陈述中对梯度的要求。 但是tanh函数出现了Sigmoid函数类似的问题,梯度渐趋平坦,并且值非常低。

ReLU函数

ReLU是近几年非常受欢迎的激活函数。其定义为:

f(x)=max(0,x)

以下是图形表示:

ReLU是如今设计神经网络时使用最广泛的激活函数。首先,ReLU函数是非线性的,这意味着我们可以很容易地反向传播误差,并激活多个神经元。

ReLU函数优于其他激活函数的一大优点是它不会同时激活所有的神经元。这是什么意思?如果输入值是负的,ReLU函数会转换为0,而神经元不被激活。这意味着,在一段时间内,只有少量的神经元被激活,神经网络的这种稀疏性使其变得高效且易于计算。

我们来看看ReLU函数的梯度。

ReLU函数也存在着梯度为零的问题。看上图,x<0时,梯度是零,这意味着在反向传播过程中,权重没有得到更新。这就会产生死神经元,而这些神经元永远不会被激活。好在当我们遇到问题时,我们总能找到解决方案。

Leaky ReLU函数

Leaky ReLU函数只是一个ReLU函数的改良版本。我们看到,在ReLU函数中,x &lt; 0时梯度为0,这使得该区域的神经元死亡。为了解决这个问题, Leaky ReLU出现了。这是它的定义:

f(x)= ax, x&lt;0

= x, x&gt;=0

我们所做的,只是用一个非水平线简单地替换了水平线。这里a是一个很小的值,如0.01。见下图。

替换水平线的主要优点是去除零梯度。在这种情况下,上图左边的梯度是非零的,所以该区域的神经元不会成为死神经元。梯度图如下。

与Leaky ReLU函数类似的,还有PReLU函数,它的定义与Leaky ReLU相似。

f(x)= ax, x&lt;0

= x, x&gt;=0

然而, 在PReLU函数中,a也是可训练的函数。神经网络还会学习a的价值,以获得更快更好的收敛。 当Leaky ReLU函数仍然无法解决死神经元问题并且相关信息没有成功传递到下一层时,可以考虑使用PReLU函数。

Softmax函数

softmax函数也是一种sigmoid函数,但它在处理分类问题时很方便。sigmoid函数只能处理两个类。当我们想要处理多个类时,该怎么办呢?只对单类进行“是”或“不是”的分类方式将不会有任何帮助。softmax函数将压缩每个类在0到1之间,并除以输出总和。它实际上可以表示某个类的输入概率。其定义为:

比如,我们输入[1.2,0.9,0.75],当应用softmax函数时,得到[0.42,0.31,0.27]。现在可以用这些值来表示每个类的概率。

softmax函数最好在分类器的输出层使用。

如何选择正确的激活函数?

现在我们已经了解了这么多的激活函数,接下来就需要分析在哪种情况下应该使用哪种激活函数了。激活函数好或坏,不能凭感觉定论。然而,根据问题的性质,我们可以为神经网络更快更方便地收敛作出更好的选择。

用于分类器时,Sigmoid函数及其组合通常效果更好。

由于梯度消失问题,有时要避免使用sigmoid和tanh函数。

ReLU函数是一个通用的激活函数,目前在大多数情况下使用。

如果神经网络中出现死神经元,那么PReLU函数就是最好的选择。

请记住,ReLU函数只能在隐藏层中使用。

答:较大的输入的梯度为1,较小输入的梯度为0;即较小的输入对输出没有影响;另一个值较大,它通过最大值运算门输出,所以最后只会得到较大输入值的梯度。à这也是最大值门是梯度路由的原因。

前向传播时,最大值往前传播;反向传播时,会把梯度分配给输入值最大的线路,这就是一个梯度路由。
好未来
1、  LeetCode第一题“TwoSum”
2、  通过简单示例,详细解释ROC曲线,要求给出必要的公式推导。
3、  给出LR(逻辑回归)算法的cost function公式的推导过程。
4、  目标检测时,输入的是视频时,如何进行检测?视频中有很多无用的帧(不包含要检测的目标等)–>人工分割视频、每隔一定数量的帧进行检测
5、  项目。
阿里:7月份最早投的阿里(算法工程师),过了2天就收到一面通知,一面最主要的是问简历上写的内容,问基础。对简历上的项目中涉及到的所有知识点必须理清,期间面试官问了一个我简历上写的但我不是很了解的内容,结果我说不是很熟悉,面试官就说了我不熟悉的还敢往上写…面试主要问的其他知识点:有哪些聚类(当时我只熟悉kmeans,下来赶紧找资料https://www.zhihu.com/question/34554321)?优化算法了解多少(批梯度下降、随机梯度下降、mini-batch梯度下降的差异,还有动量的优化算法等等http://blog.csdn.net/xwd18280820053/article/details/77529550)?因为我项目里用到了很多树模型,因此问了RF、GBDT、xgBoost之间的区别(参考http://blog.csdn.net/xwd18280820053/article/details/68927422);
对于大数据方面的问题可参考:http://blog.csdn.net/v_july_v/article/details/7382693
三面:三面不是同一个部门的面试官,应该是交叉面吧,三面问机器学习相关的东西比较少,主要问基础。
对hash表的理解,有哪些解决冲突的方法(分别怎么用),
链地址法中对于映射到同一个地址的数,设计数据结构能够快速查找出其中的数(比如对于1,11,21,31,41,51映射到同一个key(1),如何快速找到31),这个问题没答好,最后问面试官,他说是用树模型,叫我下来好好想想…
最后问了个智力题:一瓶蓝墨水,一瓶红墨水,等量,现在从蓝墨水里舀一勺到红墨水,再从红墨水里舀一勺到蓝墨水,问蓝墨水中的红墨水与红墨水中的蓝墨水量的大小关系。
HR:hr面就是随便聊聊了,问学到最多的是哪个项目,描述整个项目等等,hr姐姐是个老乡,最后聊了20几分钟就结束了。
最后等了2个月左右终于收到意向通知了……
百度:(算法)百度主要考察计算机基础,对底层要求较高。
一面:问项目中的FM与FFM的区别,针对一个做的最久的项目问的比较久,然后就是在想编程,面试官发个链接过来,直接写2个题目,第一个是判断2棵二叉树是否相同,
第二个题目是有2个文件,文件太大无法将一个文件全部加载到内存,找出2个文件中相同的数。(1h左右)
二面:问数组按行、按列存储的区别,问hash表在内存中是怎么查找的(这2个没答好就没继续问了),针对一个项目问到了代价敏感学习(并没用过…),看到我项目中有用过深度学习就开始问深度学习了,看到腾讯比赛问为啥不用深度学习来做,
然后就是问DNN给定结构情况下有哪些关键问题(优化算法,激活函数这2个方面):
有哪些激活函数?relu与逻辑函数的区别?(relu避免梯度消散,加快训练速度,起到稀疏性的作用),交叉熵代价函数与平方损失代价函数的区别,什么情况下两者等价?
百度内推时是上海地区,之后校招时为北京,现场三面,
都是从项目出发,问各种细节(画LSTM框架图),写程序(动态规划相关、汉诺塔实现),晚上11点过通知offer…
好未来:(算法岗机器学习相关)现场面试,全程写代码
一面:2个等长的有序数组,得到中位数;2个链表判断是否有公共节点(链表带环时的处理);还有个题忘了….
二面:2道编程:给定2个字符串,找到最长的公共子串(写完动态规划问能否改进);二路归并排序。问了些hr会问的问题,大学的遗憾,学到的最重要的东西等,随便聊聊结束。
邮件通知offer
Tap4fun:(数据挖掘)
一面:问项目,LSTM与GRU的区别;
二面:问项目,部门有做广告方面的业务,针对广告算法大赛问的比较细,问提了多少特征,那些特征有用;
Hr面:一个智力题,然后就是随便聊聊,对加班的看法,平时的爱好等。
总监面:负梯度下降方向为什么是下降最快的方向,心算一个十进制转二进制,最有成就的事,平时作息习惯,开放题估计一层楼的月用电量。
HR通知offer
总结:都需要自我介绍,都需要准备问面试官的问题;
分词
HMM和CRF
词性标注
HMM
文本分类聚类
sklearn
实体识别/命名实体
CRF
关键词抽取
TextRank/sklearn(特征提取)
热词发现
文本纠错
机器翻译
问答系统
DeepQA
Seq2Seq
LSTM
自动摘要
TextRank
知识推理
知识图谱
推荐系统

何谓海量数据处理?

   所谓海量数据处理,其实很简单,海量,海量,何谓海量,就是数据量太大,所以导致要么是无法在较短时间内迅速解决,要么是数据太大,导致无法一次性装入内存。
    那解决办法呢?针对时间,我们可以采用巧妙的算法搭配合适的数据结构,如Bloom filter/Hash/bit-map/堆/数据库或倒排索引/trie/,针对空间,无非就一个办法:大而化小:分而治之/hash映射,你不是说规模太大嘛,那简单啊,就把规模大化为规模小的,各个击破不就完了嘛。
    至于所谓的单机及集群问题,通俗点来讲,单机就是处理装载数据的机器有限(只要考虑cpu,内存,硬盘的数据交互),而集群,机器有多辆,适合分布式处理,并行计算(更多考虑节点和节点间的数据交互)。
    再者,通过本blog内的有关海量数据处理的文章,我们已经大致知道,处理海量数据问题,无非就是:
  1. 分而治之/hash映射 + hash统计 + 堆/快速/归并排序;
  2. 双层桶划分
  3. Bloom filter/Bitmap;
  4. Trie树/数据库/倒排索引;
  5. 外排序;
  6. 分布式处理之Hadoop/Mapreduce。
    本文接下来的部分,便针对这6种方法模式结合对应的海量数据处理面试题分别具体阐述。

处理海量数据问题之六把密匙

密匙一、分而治之/Hash映射 + Hash统计 + 堆/快速/归并排序

1、海量日志数据,提取出某日访问百度次数最多的那个IP。

    既然是海量数据处理,那么可想而知,给我们的数据那就一定是海量的。针对这个数据的海量,我们如何着手呢?对的,无非就是分而治之/hash映射 + hash统计 + 堆/快速/归并排序,说白了,就是先映射,而后统计,最后排序:

  1. 分而治之/hash映射:针对数据太大,内存受限,只能是:把大文件化成(取模映射)小文件,即16字方针:大而化小,各个击破,缩小规模,逐个解决
  2. hash统计:当大文件转化了小文件,那么我们便可以采用常规的Hashmap(ip,value)来进行频率统计。
  3. 堆/快速排序:统计完了之后,便进行排序(可采取堆排序),得到次数最多的IP。
   具体而论,则是: “首先是这一天,并且是访问百度的日志中的IP取出来,逐个写入到一个大文件中。注意到IP是32位的,最多有个2^32个IP。同样可以采用映射的方法,比如模1000,把整个大文件映射为1000个小文件,再找出每个小文中出现频率最大的IP(可以采用Hash_map进行频率统计,然后再找出频率最大的几个)及相应的频率。然后再在这1000个最大的IP中,找出那个频率最大的IP,即为所求。”–十道海量数据处理面试题与十个方法大总结
2、搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来,每个查询串的长度为1-255字节。
    假设目前有一千万个记录(这些查询串的重复度比较高,虽然总数是1千万,但如果除去重复后,不超过3百万个。一个查询串的重复度越高,说明查询它的用户越多,也就是越热门。),请你统计最热门的10个查询串,要求使用的内存不能超过1G。
    由上面第1题,我们知道,数据大则划为小的,但如果数据规模比较小,能一次性装入内存呢?比如这第2题,虽然有一千万个Query,但是由于重复度比较高,因此事实上只有300万的Query,每个Query255Byte,因此我们可以考虑把他们都放进内存中去,而现在只是需要一个合适的数据结构,在这里,Hash Table绝对是我们优先的选择。所以我们摒弃分而治之/hash映射的方法,直接上hash统计,然后排序。So,
  1. hash统计:先对这批海量数据预处理(维护一个Key为Query字串,Value为该Query出现次数的HashTable,即Hashmap(Query,Value),每次读取一个Query,如果该字串不在Table中,那么加入该字串,并且将Value值设为1;如果该字串在Table中,那么将该字串的计数加一即可。最终我们在O(N)的时间复杂度内用Hash表完成了统计;
  2. 堆排序:第二步、借助堆这个数据结构,找出Top K,时间复杂度为N‘logK。即借助堆结构,我们可以在log量级的时间内查找和调整/移动。因此,维护一个K(该题目中是10)大小的小根堆,然后遍历300万的Query,分别和根元素进行对比所以,我们最终的时间复杂度是:O(N) + N’*O(logK),(N为1000万,N’为300万)。
    别忘了这篇文章中所述的堆排序思路:“维护k个元素的最小堆,即用容量为k的最小堆存储最先遍历到的k个数,并假设它们即是最大的k个数,建堆费时O(k),并调整堆(费时O(logk))后,有k1>k2>…kmin(kmin设为小顶堆中最小元素)。继续遍历数列,每次遍历一个元素x,与堆顶元素比较,若x>kmin,则更新堆(用时logk),否则不更新堆。这样下来,总费时O(k*logk+(n-k)*logk)=O(n*logk)。此方法得益于在堆中,查找等各项操作时间复杂度均为logk。”–第三章续、Top K算法问题的实现
    当然,你也可以采用trie树,关键字域存该查询串出现的次数,没有出现为0。最后用10个元素的最小推来对出现频率进行排序。
3、有一个1G大小的一个文件,里面每一行是一个词,词的大小不超过16字节,内存限制大小是1M。返回频数最高的100个词。
       由上面那两个例题,分而治之 + hash统计 + 堆/快速排序这个套路,我们已经开始有了屡试不爽的感觉。下面,再拿几道再多多验证下。请看此第3题:又是文件很大,又是内存受限,咋办?还能怎么办呢?无非还是:
  1. 分而治之/hash映射:顺序读文件中,对于每个词x,取hash(x)%5000,然后按照该值存到5000个小文件(记为x0,x1,…x4999)中。这样每个文件大概是200k左右。如果其中的有的文件超过了1M大小,还可以按照类似的方法继续往下分,直到分解得到的小文件的大小都不超过1M。
  2. hash统计:对每个小文件,采用trie树/hash_map等统计每个文件中出现的词以及相应的频率。
  3. 堆/归并排序:取出出现频率最大的100个词(可以用含100个结点的最小堆),并把100个词及相应的频率存入文件,这样又得到了5000个文件。最后就是把这5000个文件进行归并(类似于归并排序)的过程了。
4、有10个文件,每个文件1G,每个文件的每一行存放的都是用户的query,每个文件的query都可能重复。要求你按照query的频度排序。
   直接上:
  1. hash映射:顺序读取10个文件,按照hash(query)%10的结果将query写入到另外10个文件(记为)中。这样新生成的文件每个的大小大约也1G(假设hash函数是随机的)。
  2. hash统计:找一台内存在2G左右的机器,依次对用hash_map(query, query_count)来统计每个query出现的次数。注:hash_map(query,query_count)是用来统计每个query的出现次数,不是存储他们的值,出现一次,则count+1。
  3. 堆/快速/归并排序:利用快速/堆/归并排序按照出现次数进行排序。将排序好的query和对应的query_cout输出到文件中。这样得到了10个排好序的文件(记为)。对这10个文件进行归并排序(内排序与外排序相结合)。
     除此之外,此题还有以下两个方法:
    方案2:一般query的总量是有限的,只是重复的次数比较多而已,可能对于所有的query,一次性就可以加入到内存了。这样,我们就可以采用trie树/hash_map等直接来统计每个query出现的次数,然后按出现次数做快速/堆/归并排序就可以了。
    方案3:与方案1类似,但在做完hash,分成多个文件后,可以交给多个文件来处理,采用分布式的架构来处理(比如MapReduce),最后再进行合并。
5、 给定a、b两个文件,各存放50亿个url,每个url各占64字节,内存限制是4G,让你找出a、b文件共同的url?
    可以估计每个文件安的大小为5G×64=320G,远远大于内存限制的4G。所以不可能将其完全加载到内存中处理。考虑采取分而治之的方法。
  1. 分而治之/hash映射:遍历文件a,对每个url求取,然后根据所取得的值将url分别存储到1000个小文件(记为)中。这样每个小文件的大约为300M。遍历文件b,采取和a相同的方式将url分别存储到1000小文件中(记为)。这样处理后,所有可能相同的url都在对应的小文件()中,不对应的小文件不可能有相同的url。然后我们只要求出1000对小文件中相同的url即可。
  2. hash统计:求每对小文件中相同的url时,可以把其中一个小文件的url存储到hash_set中。然后遍历另一个小文件的每个url,看其是否在刚才构建的hash_set中,如果是,那么就是共同的url,存到文件里面就可以了。
    OK,此第一种方法:分而治之/hash映射 + hash统计 + 堆/快速/归并排序,再看最后三道题,如下:
6、怎么在海量数据中找出重复次数最多的一个?
    方案1:先做hash,然后求模映射为小文件,求出每个小文件中重复次数最多的一个,并记录重复次数。然后找出上一步求出的数据中重复次数最多的一个就是所求(具体参考前面的题)。
7、上千万或上亿数据(有重复),统计其中出现次数最多的钱N个数据。
    方案1:上千万或上亿的数据,现在的机器的内存应该能存下。所以考虑采用hash_map/搜索二叉树/红黑树等来进行统计次数。然后就是取出前N个出现次数最多的数据了,可以用第2题提到的堆机制完成。
8、一个文本文件,大约有一万行,每行一个词,要求统计出其中最频繁出现的前10个词,请给出思想,给出时间复杂度分析。
     方案1:这题是考虑时间效率。用trie树统计每个词出现的次数,时间复杂度是O(n*le)(le表示单词的平准长度)。然后是找出出现最频繁的前10个词,可以用堆来实现,前面的题中已经讲到了,时间复杂度是O(n*lg10)。所以总的时间复杂度,是O(n*le)与O(n*lg10)中较大的哪一个。
    接下来,咱们来看第二种方法,双层捅划分。

密匙二、双层桶划分

双层桶划分—-其实本质上还是分而治之的思想,重在“分”的技巧上!
  适用范围:第k大,中位数,不重复或重复的数字
  基本原理及要点:因为元素范围很大,不能利用直接寻址表,所以通过多次划分,逐步确定范围,然后最后在一个可以接受的范围内进行。可以通过多次缩小,双层只是一个例子。
  扩展:
  问题实例:
        1).2.5亿个整数中找出不重复的整数的个数,内存空间不足以容纳这2.5亿个整数。
  有点像鸽巢原理,整数个数为2^32,也就是,我们可以将这2^32个数,划分为2^8个区域(比如用单个文件代表一个区域),然后将数据分离到不同的区域,然后不同的区域在利用bitmap就可以直接解决了。也就是说只要有足够的磁盘空间,就可以很方便的解决。
       2).5亿个int找它们的中位数。
  这个例子比上面那个更明显。首先我们将int划分为2^16个区域,然后读取数据统计落到各个区域里的数的个数,之后我们根据统计结果就可以判断中位数落到那个区域,同时知道这个区域中的第几大数刚好是中位数。然后第二次扫描我们只统计落在这个区域中的那些数就可以了。
  实际上,如果不是int是int64,我们可以经过3次这样的划分即可降低到可以接受的程度。即可以先将int64分成2^24个区域,然后确定区域的第几大数,在将该区域分成2^20个子区域,然后确定是子区域的第几大数,然后子区域里的数的个数只有2^20,就可以直接利用direct addr table进行统计了。

密匙三:Bloom filter/Bitmap

Bloom filter

关于什么是Bloom filter,请参看此文:海量数据处理之Bloom Filter详解
  适用范围:可以用来实现数据字典,进行数据的判重,或者集合求交集
  基本原理及要点:
  对于原理来说很简单,位数组+k个独立hash函数。将hash函数对应的值的位数组置1,查找时如果发现所有hash函数对应位都是1说明存在,很明显这个过程并不保证查找的结果是100%正确的。同时也不支持删除一个已经插入的关键字,因为该关键字对应的位会牵动到其他的关键字。所以一个简单的改进就是 counting Bloom filter,用一个counter数组代替位数组,就可以支持删除了。
  还有一个比较重要的问题,如何根据输入元素个数n,确定位数组m的大小及hash函数个数。当hash函数个数k=(ln2)*(m/n)时错误率最小。在错误率不大于E的情况下,m至少要等于n*lg(1/E)才能表示任意n个元素的集合。但m还应该更大些,因为还要保证bit数组里至少一半为0,则m应该>=nlg(1/E)*lge 大概就是nlg(1/E)1.44倍(lg表示以2为底的对数)。
  举个例子我们假设错误率为0.01,则此时m应大概是n的13倍。这样k大概是8个。
  注意这里m与n的单位不同,m是bit为单位,而n则是以元素个数为单位(准确的说是不同元素的个数)。通常单个元素的长度都是有很多bit的。所以使用bloom filter内存上通常都是节省的。
  扩展:
  Bloom filter将集合中的元素映射到位数组中,用k(k为哈希函数个数)个映射位是否全1表示元素在不在这个集合中。Counting bloom filter(CBF)将位数组中的每一位扩展为一个counter,从而支持了元素的删除操作。Spectral Bloom Filter(SBF)将其与集合元素的出现次数关联。SBF采用counter中的最小值来近似表示元素的出现频率。
  问题实例:给你A,B两个文件,各存放50亿条URL,每条URL占用64字节,内存限制是4G,让你找出A,B文件共同的URL。如果是三个乃至n个文件呢?
  根据这个问题我们来计算下内存的占用,4G=2^32大概是40亿*8大概是340亿,n=50亿,如果按出错率0.01算需要的大概是650亿个bit。现在可用的是340亿,相差并不多,这样可能会使出错率上升些。另外如果这些urlip是一一对应的,就可以转换成ip,则大大简单了。
    同时,上文的第5题:给定a、b两个文件,各存放50亿个url,每个url各占64字节,内存限制是4G,让你找出a、b文件共同的url?如果允许有一定的错误率,可以使用Bloom filter,4G内存大概可以表示340亿bit。将其中一个文件中的url使用Bloom filter映射为这340亿bit,然后挨个读取另外一个文件的url,检查是否与Bloom filter,如果是,那么该url应该是共同的url(注意会有一定的错误率)。

Bitmap

    至于什么是Bitmap,请看此文:http://blog.csdn.net/v_july_v/article/details/6685962。下面关于Bitmap的应用,直接上题,如下第9、10道:
9、在2.5亿个整数中找出不重复的整数,注,内存不足以容纳这2.5亿个整数。
    方案1:采用2-Bitmap(每个数分配2bit,00表示不存在,01表示出现一次,10表示多次,11无意义)进行,共需内存2^32 * 2 bit=1 GB内存,还可以接受。然后扫描这2.5亿个整数,查看Bitmap中相对应位,如果是00变01,01变10,10保持不变。所描完事后,查看bitmap,把对应位是01的整数输出即可。
    方案2:也可采用与第1题类似的方法,进行划分小文件的方法。然后在小文件中找出不重复的整数,并排序。然后再进行归并,注意去除重复的元素。
10、腾讯面试题:给40亿个不重复的unsigned int的整数,没排过序的,然后再给一个数,如何快速判断这个数是否在那40亿个数当中?
    方案1:oo,申请512M的内存,一个bit位代表一个unsigned int值。读入40亿个数,设置相应的bit位,读入要查询的数,查看相应bit位是否为1,为1表示存在,为0表示不存在。

密匙四、Trie树/数据库/倒排索引

Trie树
  适用范围:数据量大,重复多,但是数据种类小可以放入内存
  基本原理及要点:实现方式,节点孩子的表示方式
  扩展:压缩实现。
  问题实例:
  1. 有10个文件,每个文件1G,每个文件的每一行都存放的是用户的query,每个文件的query都可能重复。要你按照query的频度排序。
  2. 1000万字符串,其中有些是相同的(重复),需要把重复的全部去掉,保留没有重复的字符串。请问怎么设计和实现?
  3. 寻找热门查询:查询串的重复度比较高,虽然总数是1千万,但如果除去重复后,不超过3百万个,每个不超过255字节。
  4. 上面的第8题:一个文本文件,大约有一万行,每行一个词,要求统计出其中最频繁出现的前10个词。其解决方法是:用trie树统计每个词出现的次数,时间复杂度是O(n*le)(le表示单词的平准长度),然后是找出出现最频繁的前10个词。
    更多有关Trie树的介绍,请参见此文:从Trie树(字典树)谈到后缀树
数据库索引
  适用范围:大数据量的增删改查
  基本原理及要点:利用数据的设计实现方法,对海量数据的增删改查进行处理。
    关于数据库索引及其优化,更多可参见此文:http://www.cnblogs.com/pkuoliver/archive/2011/08/17/mass-data-topic-7-index-and-optimize.html。同时,关于MySQL索引背后的数据结构及算法原理,这里还有一篇很好的文章:http://www.codinglabs.org/html/theory-of-mysql-index.html
倒排索引(Inverted index)
  适用范围:搜索引擎,关键字查询
  基本原理及要点:为何叫倒排索引?一种索引方法,被用来存储在全文搜索下某个单词在一个文档或者一组文档中的存储位置的映射。
 以英文为例,下面是要被索引的文本:
    T0 = “it is what it is”
    T1 = “what is it”
    T2 = “it is a banana”
我们就能得到下面的反向文件索引:
    “a”:      {2}
    “banana”: {2}
    “is”:     {0, 1, 2}
    “it”:     {0, 1, 2}
    “what”:   {0, 1}
 检索的条件”what”,”is”和”it”将对应集合的交集。
  正向索引开发出来用来存储每个文档的单词的列表。正向索引的查询往往满足每个文档有序频繁的全文查询和每个单词在校验文档中的验证这样的查询。在正向索引中,文档占据了中心的位置,每个文档指向了一个它所包含的索引项的序列。也就是说文档指向了它包含的那些单词,而反向索引则是单词指向了包含它的文档,很容易看到这个反向的关系。
  扩展:
  问题实例:文档检索系统,查询那些文件包含了某单词,比如常见的学术论文的关键字搜索。

密匙五、外排序

  适用范围:大数据的排序,去重
  基本原理及要点:外排序的归并方法,置换选择败者树原理,最优归并树
  扩展:
  问题实例:
  1).有一个1G大小的一个文件,里面每一行是一个词,词的大小不超过16个字节,内存限制大小是1M。返回频数最高的100个词。
  这个数据具有很明显的特点,词的大小为16个字节,但是内存只有1m做hash有些不够,所以可以用来排序。内存可以当输入缓冲区使用。
    关于多路归并算法及外排序的具体应用场景,请参见此文:第十章、如何给10^7个数据量的磁盘文件排序

密匙六、分布式处理 Mapreduce

      适用范围:数据量大,但是数据种类小可以放入内存
  基本原理及要点:将数据交给不同的机器去处理,数据划分,结果归约。
  扩展:
  问题实例:
  1. The canonical example application of MapReduce is a process to count the appearances of each different word in a set of documents:
  2. 海量数据分布在100台电脑中,想个办法高效统计出这批数据的TOP10。
  3. 一共有N个机器,每个机器上有N个数。每个机器最多存O(N)个数并对它们操作。如何找到N^2个数的中数(median)?

 

 

输入首先包含一个整数N,表示有N组测试用例。
接下来的N行表示N个测试用例,每行包括2个时间HH:MM:SS hh:mm:ss
HH:MM:SS表示当前的时间,hh:mm:ss表示希望倒退回去的时间。
[Technical Specification]
00<=HH<=11
00<=hh<=99
00<=MM, SS, mm, ss<=59
输出描述:
请计算并输出钟表倒退后显示的时间,要求输出格式为HH:MM:SS(即时分秒均显示2位,不足则补0),每组数据输出占一行。
示例1

输入

2
11:28:32 02:14:21
05:00:00 96:00:01

输出

09:14:11
04:59:59
//这个题目限定了分和秒的范围,不然就更有意思了。
//比较简单。
#include <iostream>
#include <string>
#include <vector>
using namespace std;
 
vector<int> to_t(string t){
    vector<int> result(3);
    result[0] = (t[0] - '0') * 10 + (t[1] - '0');
    result[1] = (t[3] - '0') * 10 + (t[4] - '0');
    result[2] = (t[6] - '0') * 10 + (t[7] - '0');
    return result;
}
 
void getresult(){
    string t;
    string dt;
    cin >> t;
    cin >> dt;
    vector<int> nowt = to_t(t);
    vector<int> crosst = to_t(dt);
 
    crosst[0] %= 12;
    nowt[0] -= crosst[0];
    nowt[1] -= crosst[1];
    nowt[2] -= crosst[2];
 
    if (nowt[2] < 0){
        nowt[1]--;
        nowt[2] += 60;
    }
    if (nowt[1] < 0){
        nowt[0]--;
        nowt[1] += 60;
    }
    if (nowt[0] < 0)
        nowt[0] += 12;
 
    printf("%02d:%02d:%02d", nowt[0], nowt[1], nowt[2]);
}
 
int main(){
    int n;
    cin >> n;
 
    while (n--){
        getresult();
        cout << endl;
    }
    return 0;
}

 

Leave a Reply

Your email address will not be published. Required fields are marked *