线性同余发生器

线性同余发生器

线性同余发生器(Linear congruential generator,LCG)是一种能产生具有不连续计算的伪随机序列的分段线性方程的算法,它代表了最古老和最知名的伪随机序列生成器算法之一。

生成器定义

$$
X_{n+1}=\left(a X_{n}+c\right) \bmod m
$$

  • $X​$是伪随机序列

  • $m,m>0​$表示模量

  • $a,0<a<m​$表示乘数

  • $c,\leq0<m​$表示增量

  • $ X_{0},0\leq X_{0}<m $表示初始值

当$c=0$时,该发生器称为乘法同余发生器MCG

MCG的实现

#include <stdio.h>

#define A 48271L
#define M 2147483647L

double Random(void) {
    Seed = (A * Seed) % M;
    return (double)Seed / M;
}
void Initialize(unsigned InitVal) {
    Seed = InitVal;
}

这种实现方法实现地很直观,但存在一个问题。在32位机器上A * Seed会导致乘法溢出与截断,虽然程序能继续运行,但它影响最终的计算结果,从而影响伪随机性。

Schrage's method

Schrage方法推导过程
推导过程
因为$R<Q$,故所有的余项均可计算而没有溢出。此外,仅当余项的值小于0时候$\delta\left(x_{i}\right)=1$。

#include <stdio.h>

#define A 48271L
#define M 2147483647L
#define Q ( M / A )
#define R ( M % A )

static unsigned long Seed = 1;

double Random(void) {
    long TmpSeed;
    TmpSeed = A * (Seed % Q) - R * (Seed / Q);
    if (TmpSeed >= 0)
    {
        Seed = TmpSeed;
    }
    else
    {
        Seed = TmpSeed + M;
    }
    return (double)Seed / M;
}
void Initialize(unsigned InitVal) {
    Seed = InitVal;
}

Levenshtein distance

概念

莱文斯坦距离Levenshtein distance)是将一个单词更改为另一个单词所需的最少编辑操作次数。莱文斯坦距离允许的编辑操作包括单个字符的 替换/插入/删除。

实例

给定字符串kittensitting,前者可以通过以下步骤变换成后者:

  1. kitten → sitten (将k替换为s)

  2. sitten → sittin (将e替换为i)

  3. sittin → sitting (在尾部插入g)

无法通过更少的步骤完成替换,故两者的莱文斯坦距离为3

算法

请输入图片描述

实现

def levenshteinDistance(s1, s2):
    m = len(s1)
    n = len(s2)
    dt = []

    # 初始化距离表
    for i in range(m+1):
        temp = []
        for j in range(n+1):
            if i==0:
                temp.append(j)
            elif j==0:
                temp.append(i)
            else:
                temp.append(0)
        dt.append(temp)

    
    for i in range(1, m+1):
        for j in range(1, n+1):
            if s1[i-1] == s2[j-1]:
                dt[i][j] = dt[i-1][j-1]
            else:
                dt[i][j] = min(dt[i-1][j], dt[i][j-1], dt[i-1][j-1]) +1 
    return dt[m][n]

A站视频信息分析

1.使用scrapy框架重写了一下a站的视频爬虫,共爬取895,799条视频信息。爬取了包括标题、播放量、弹幕数、评论数、收藏数、香蕉数量、作者信息、视频类别等信息。

2.各类别视频数量

各类别视频数量统计图

3.播放量TOP20视频(TOP1有点假,刷的)

播放量TOP20视频

4.播放量区间统计

('1-10', 9),
('10-100', 807),
('100-1k', 58297),
('1k-10k', 716989),
('10k-100k', 98948),
('100k-1m', 19524),
('1m-10m', 1164),
('10m-100m', 58),
('>100m', 3);

请输入图片描述

A站视频数据-201902-可用phpMyAdmin导入.sql

Oracle硬解析与软解析

概述

  • 当客户端进程,将SQL语句通过监听器发送到Oracle时, 会触发一个Server process生成,来对该客户进程服务。Server process得到SQL语句之后,对SQL语句进行Hash运算,然后根据Hash值到library cache中查找,如果存在,则直接将library cache中的缓存的执行计划拿来执行,最后将执行结果返回该客户端,这种SQL解析叫做软解析;如果不存在,则会对该SQL进行解析parse,然后执行,返回结果,这种SQL解析叫做硬解析。

硬解析

  1. 对SQL语句进行语法检查,看是否有语法错误。比如select from where 等的拼写错误,如果存在语法错误,则退出解析过程;
  2. 通过数据字典(row cache),检查SQL语句中涉及的对象和列是否存在。如果不存在,则退出解析过程
  3. 检查SQL语句的用户是否对涉及到的对象是否有权限。如果没有则退出解析;
  4. 通过优化器创建一个最优的执行计划。这个过程会根据数据字典中的对象的统计信息,来计算多个执行计划的cost,从而得到一个最优的执行计划。这一步涉及到大量的数据运算,从而会消耗大量的CPU资源;(library cache最主要的目的就是通过软解析来减少这个步骤);
  5. 将该游标所产生的执行计划,SQL文本等装载进library cache中的heap中。

软解析

  • 所谓软解析,就是因为相同文本的SQL语句存在于librarycache中,所以本次SQL语句的解析就可以去掉硬解析中的一个或多个步骤。从而节省大量的资源的耗费。

测试数据

请输入图片描述

JAVA代码

pstmt = conn.prepareStatement(sql);
pstmt.setString(1, value1);
pstmt.setString(2, value2);
rs = pstmt.excuteQuery();
...
sql语句中变量用?代替