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

你有种再说一遍

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


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


[JDK1.8的hashmap]
0x01 取模就是整数除法器,为了除法器太慢的问题,map内数组长度必须用2次方,然后索引用了按位与代替取模:
hash&(array.length-1)等价hash%array.length(非二次方也行)
0x02 强行把用户预设长度改为2次方长度,所以有了计算邻近数值,capacity容量(数组长度)
static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0)? 1 : (n >= maximum_capacity)? maximum_capacity : n + 1;
}
0x03 hashmap扩容和缩容时候,考虑负载因子0.75(泊松分布概率),红黑树阶数.
哈希冲突时候,利用链表+红黑树,减少上层数组的扩容再散列,给我的感觉就是重复占用的格子面积来决定扩容和缩容.
Rehash扩容算法,遍历每个元素,当 e.hash & oldCap = 0,则节点在新数组中的索引值与旧索引值相同.当 e.hash & oldCap = 1,则节点在新数组中的索引值为旧索引值+旧数组容量.为什么不重新GetHashCode呢?因为计算字符串hash算法慢,需要处理负数hash,高位和低位异或等等.
所以你会发现,为了除法器这碗醋,所以Java包了一顿饺子.
0x04 那么最快的hash结构其实不是上面的,只是上面的结构显得平均度最好,而最快的则是采用开放寻址法这种极少冲突的hash结构,这种方式通常用在已知数据量情况作出的最优设计,大家可以参考Java版的十亿行天文台挑战.


[整数除法器最慢]
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编的，现成的库