发表于 | 分类于
字数统计: 144 | 阅读时长 ≈ 1
记录c++STL中vector的一些操作 指定长度vector声明vector<int> vec(n);//长度为nvector<int> vec(n,t);//长度为n,值为t 指定长度二维vector声明声明一个m*n维的矩阵： vector<vector<int> > vec(m,vector<int>(n));vector<vector<int> > vec(n,vector<int>(n,0));//所有元素都是0 vector排序#include<algorithm>sort ...
阅读全文 »

发表于 | 分类于 ，
字数统计: 9,070 | 阅读时长 ≈ 45
什么是回溯回溯是一种穷举，但与brute force有一些区别，回溯带了两点脑子的，并不多，brute force一点也没带。如果用爬山来比喻：第一点脑子是回溯知道回头；相反如果是brute force,发现走不通立刻跳下山摔死，换第二条命从头换一条路走。第二点脑子是回溯知道剪枝；如果有一条岔路走不通，那这条路我们不走，就可以少走很多不必要走的路。 识别回溯问题判断回溯很简单，拿到一个问题，你感觉如果不穷举一下就没法知道答案，那就可以开始回溯了。一般回溯的问题有三种： Find a path to success 有没有解 Find all paths to success 求所有解 求所有 ...
阅读全文 »

发表于 | 分类于
字数统计: 408 | 阅读时长 ≈ 2
方法一：priority_queue这种方法需要#include<queue> 最基本的使用方法，对于一串数字建堆： riority_queue<int> heap; 这种情况下默认为最大堆，也就是堆顶元素值最大。 如果需要建立最小堆，可以采用如下方式： priority_queue<int, vector<int>, greater<int> >qi2;//最小堆priority_queue<int, vector<int>, less<int> >qi2;//最大堆 然而在多数情况下，我们还需要 ...
阅读全文 »

发表于 | 分类于 ，
字数统计: 1,529 | 阅读时长 ≈ 7

求数组/矩阵的第k大元素

涉及leetcode题目

  1. 278. Kth Smallest Number In Matrix
  2. 373. Kth Smallest Sum In Two Sorted Arrays
  3. Kth Largest in N Arrays

278. Kth Smallest Number In Matrix

题目

Given a n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix.

给定一个的矩阵，满足行递增和列递增，要求返回第k大的元素。

example

matrix = [
   [ 1,  5,  9],
   [10, 11, 13],
   [12, 13, 15]
],
k = 8,
return 13.
阅读全文 »

发表于 | 分类于
字数统计: 1,087 | 阅读时长 ≈ 4
准备开题，先看一下国内的相关硕士学位论文，知网上down的。 2017 大数据平台下的互联网广告点击率预估模型 基于腾讯社交广告数据集，hive+hadoop环境下实现GBDT+FM分布式点击率预估，用到贝叶斯平滑等，竞赛在分布式环境下的扩展。 ​ 2016 针对在线广告实时竞价系统的相关算法研究、电子科大、郭威 将竞价策略总结为预算控制和估价算法两个步骤，提出一种预算步进（buget pacing）算法和一个出价模型 数据集：iPinyou 2.2介绍计算广告核心问题和结算方式 核心问题：广告主、用户、媒体三方博弈，涉及信息检索、机器学习、最优化三个领域。 结算方式以及适用场景：CP ...
阅读全文 »

发表于 | 分类于
字数统计: 602 | 阅读时长 ≈ 3
差别两者主要的差别在于：加载数据的时候，静态分区需要手动设定不同的分区，按分区分别导入数据，；而动态分区不需要指定分区key的值，会根据key对应列的值自动分区写入，如果该列值对应的分区目录还没有创建， 会自动创建并写入数据。 静态分区创建分区表create table zhangsiyao.dt_0802_0815 (itime string,uid string,gid string,app_ver string,unet int ,device_type string,device_os string,client_type string,crtv_id int,country stri ...
阅读全文 »

发表于 | 分类于
字数统计: 526 | 阅读时长 ≈ 3
等频划分等频划分：按照数据的分布情况，每个区间的数据数量一样，平均划分成k个区间 等比划分：按照数据的全部取值情况，平均划分成k个区间 Hive 中计算分位数的函数：percentile_approxhive 中的percentile_approx函数可以确定等频划分的分位点percentile_approx(col,array(0.2,0.4,0.6,0.8))[0.0,4001.0,4061.0] 其中col为要划分的列，array中的数字代表划分的位置，比如(0.2,0.4,0.6,0.8)就是钱20%数量的样本被分到一个区间，然后20%-40%的样本被分到一个区间…. 返回值是一个ar ...
阅读全文 »

发表于
字数统计: 2,293 | 阅读时长 ≈ 14
生成步骤 1.在官网上(http://www.tpc.org/tpcds/ )去下载最新的：TPC-DS. 2.解压: 下载的 zip 文件放在 Linux 上解压,并进入他的 tools 目录. 3.编译：make (忽略编译警告，只保证生成过程成功完成). 这里需要Linux安装上了 gcc , gcc c++, expect 等. 4.生成数据：在tools目录下执行：./dsdgen -scale 100 -force (-force:会覆盖原来生成的data,否则不覆盖);生成的25个.dat 的数据文件. 默认只能生成 100GB, 300GB, 1TB, 3TB, 10TB, ...
阅读全文 »

发表于 | 分类于
字数统计: 261 | 阅读时长 ≈ 1

矩阵链乘法问题

矩阵乘法

两个矩阵A和B相乘，维度分别为$ p×q$和$ q×r$，则$A*B$的时间复杂度为$pqr$

MATRIX_MULTIPLY(A,B){
  for (int i = 0;i <A.rows;i++){
    for(int j = 0;j < B.cols;j++){
      for(int k = 0;k < A.cols;k++){
        C[i,j] = A[i,k]*B[k,j];
}}}}

矩阵链乘法

​ 首先，给定一个矩阵链 ，三个矩阵的规模分别为：10×100 ， 100×5 ，5×50 ，计算他们的乘积有两种方式：

$((A_1A_2)A_3)$
$(A_1(A_2A_3))$

可以看出，对一串矩阵做乘法操作，乘法的顺序影响到算法的时间复杂度。由此，引出矩阵链乘法问题：

给定n个矩阵的链，矩阵 的规模为，确定代价最低的计算顺序，使得计算乘积$A_1A_2A_n$所需标量乘法次数最小。

阅读全文 »

发表于 | 分类于
字数统计: 1,389 | 阅读时长 ≈ 6

1. 动态规划（Dynamic programming）

这里programming指的是表格，而非编程。动态规划通常用来求解最优化问题

与分治法对比：

  1. 相同点：都是通过子问题组合求解原问题
  2. 不同点：分治法将问题划分为不相交的子问题，求解再合并，动态规划应用于子问题重叠的情况，即不同的子问题具有公共的子子问题，此时如果用分治法就会出现重复计算求解。为了避免重复动态规划对子问题只求解一次，将其保存在表格中，从而无需每求解一个子子问题时重复计算。

2. 求解步骤

  1. 刻画最优解的结构特征
  2. 递归定义最优解的值
  3. 计算最优解的值，通常采用自底向上的方法
  4. 利用计算出的信息构造最优解

其中不是所有的题目都会要求4，仅仅要求3，要求4的时候，我们需要在得到3的同事维护一些额外的信息来求出4。

看到这四个步骤的时候，还是挺懵逼的，继续往下看=.=

阅读全文 »