基础篇-数据结构+除法器+动态规划

你有种再说一遍

数据结构+除法器+动态规划
# 数据结构
自从知道了数据结构能够代替某些算法,那么还有什么好算的,能构造和懂得用就得了.
例如排序,总不会自己用Linq排吧,直接用二叉树不也一样吗?为什么?懒惰?no,no,no,因为有几个理由来令你使用:
1,会发现各种数据结构的操作源自对于硬件的认知,很多一环扣一环的.
2,改为同类的线程安全结构,大部分就只需要改个名称而已.
3,你需要频繁改动数据,此时反复计算排序的速度达不到.
4,数据量巨大,此时计算排序也是造成内存飙升.
5,考虑内存碎片,这恐怕就是工程化的魅力,内存碎片最好的办法就是固定分块占用,分块被系统回收之后再次复用能够直接拿回来这个区域,否则内存不够时候,系统会进行碎片整理,SWAP算法将和硬盘交换.CLR指针浮动也将在垃圾回收时候产生某些重排行为.
6,你为了性能考虑可以否定以上所有.

数据结构特点:
B+树是因为磁盘每次都会读取4K(扇区对齐),而你就必须要每次读写扇区大小,否则不写也浪费,并且这最好就是顺序写就能顺序读,减少随机IO次数.
会发现很多写txt,json的人从来没有意识到的对齐问题.并且二级索引也是B+树,相当于复用了结构.
四叉树的节点容量阈值不是单纯为了递归爆栈,而是为了再次散列十字区的节点图元.
hashmap为解决除法器过慢,实现了数组长度为2次方并且强行把用户输入长度转为2次方,减少重新散列的机制.

# 除法器
intel drv i64: 90.4>18
amd drv i64: 46>20
整数除法器最慢,因为它要试商,也就是累加器每次+1比较,再+1比较...直到33次循环之后试好了...无论这33次循环是通过组合电路还是时序电路,都是非常慢,而且并行成本太高了,i64比i32慢三分之二...
所以也有直接用了浮点数除法器代替.即使是最新的除法器,也看见优化有限.
浮点数除法器简单来说,就是通过三角函数夹逼,加多了减,减多了加,而且它基本上能够折半速度完成.浮点数SRT除法优化手段还能查表...
x86:提升成浮点数运算的话就会更耗电,所以还是分离设计的.
ARM:我压根没除法器
1,协处理器,也就是特定的运算模块.
2,修改高频使用的数据结构,例如JDK1.8的hashmap.
3,分母有理化,IEEE754标准把浮点数序列化就是16进制,变成了一个整数表示的浮点数分母.
例如我们无法除以9,但是可以乘9分之一,先在计算9分之一,再把运行的代码改为乘法.
手算:把9分之一的浮点数转为整数就是
(2^32)/9=477218588.444444,再抹去小数+1补偿.
代码计算:
static void Main()
{
    byte[] bytes = BitConverter.GetBytes(1/9);
    string hexString = BitConverter.ToString(bytes);
}
这就是定点数查表完成三角函数的原理,同样还有快速平方根倒数.这也是SIMD没有除法器的惯用手段.
4,编译器优化:a,编译器还能折叠常量.
b,变量上面的整数常数除法编译成位运算和加法补偿.
c,整数变量则进入除法器.
所以要知道编译期也会修改.
例如:
int x = 12345 / 100;//这里100会被编译为a =>>6; a =>>4;优化为位运算,而不是除法器指令集.
但是int*0.01却要进入浮点乘法器.
5,CPU层面可以缓存除法入参和结果进行比较.
6,如果n次命中除法,CLR还可以通过JIT特化.

除法器1文章:https://www.zhihu.com/question/429639008?utm_id=0
除法器2文章:https://www.cnblogs.com/KSongKing/p/14290763.html
编译器优化除法文章:https://www.cnblogs.com/shines77/p/4189074.html

韦易笑的快速255范围判断:https://zhuanlan.zhihu.com/p/147039093

# 软件中的动态规划
我们得到了一个名词:试商.然后发现软件也有"试试"的操作.
举个例子,如果要建设一条桥,这条桥有三种钢梁长度不一,又因为钢梁决定了柱,柱子落点的勘探点是否允许?也存在柱深,柱深又决定了造价.
在这种多参数问题,你必须要试试每种梁,直到落点,产生造价.三种梁组合是无穷的.
这种问题基本上无解,要么穷举.要么只能通过走两步之后的概率和数据库比较一下,预测未来可能性...

这是一种动态规划里面比较无解的后效性问题,解释起来就是后面的结果决定了前面的运算.
当然了动态规划还是有很多解的,记忆化搜索,产生状态转移方程之类的.

tranque

不明觉厉，我先水下经验

qwh923820

用到线性规划的我都是用python编的，现成的库