运通最近有什么开卡奖励吗？ - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Money - 海外理财

运通最近有什么开卡奖励吗？

运通最近有什么开卡奖励吗？# Money - 海外理财

a*12014-03-09 08:03

1 楼

why do we use circular link list in place of any balanced binary search tree
in storage allocator? One draw back is that to free() a chunk of memory
allocator has to search the link list and then if found that address then
release , so why not tree to reduce this search and merge?
请高手，给出简单解释。
谢谢

d*n2014-03-09 08:03

2 楼

问问

h*n2014-03-09 08:03

3 楼

http://stackoverflow.com/questions/7136790/why-are-circular-lin

f*42014-03-09 08:03

4 楼

开卡奖励一直有

a*12014-03-09 08:03

5 楼

我看了。还是有些模糊，和不确定。
谢谢

h*n2014-03-09 08:03

6 楼

我的理解就是内存分配器的目的是找到一块合适大小的空间，Tree你可以logn找到特定
节点，但是要找到合适大小的空间你依然需要遍历树中的节点，所以也是n，复杂度和
list比没啥优势，大概就这样子吧

d*x2014-03-09 08:03

7 楼

我没用试过用bst来做allocator
我猜一个可能的原因是，circular link list只要单链表就行，搜索的时候首先可以分
bin，其次可以用next-fit，效率不会太差
而bst虽然效率高，但是它需要两个指针的overhead，这对于处理很多小对象的系统来
说是个严重负担

tree

【在 a*****1 的大作中提到】

: why do we use circular link list in place of any balanced binary search tree
: in storage allocator? One draw back is that to free() a chunk of memory
: allocator has to search the link list and then if found that address then
: release , so why not tree to reduce this search and merge?
: 请高手，给出简单解释。
: 谢谢

s*k2014-03-09 08:03

8 楼

tree还是有优势，比如所有节点都是不同大小的内存块，那么你知道了需要分配的内存
在这个内存树种就只需要logn找到合适的，链表要n，不过实际上大多数内存块都不是
完全任意大小，而是分别在几个不同大小的级别，Buddy system algorithm就是这样。
所以实际上应该是array加链表最合适，简单高效

【在 h****n 的大作中提到】

: 我的理解就是内存分配器的目的是找到一块合适大小的空间，Tree你可以logn找到特定
: 节点，但是要找到合适大小的空间你依然需要遍历树中的节点，所以也是n，复杂度和
: list比没啥优势，大概就这样子吧

d*x2014-03-09 08:03

9 楼

exactly.
但是我的point是树的overhead太大，64位系统要两个8 byte指针，好可怕。

特定
度和

【在 s********k 的大作中提到】

: tree还是有优势，比如所有节点都是不同大小的内存块，那么你知道了需要分配的内存
: 在这个内存树种就只需要logn找到合适的，链表要n，不过实际上大多数内存块都不是
: 完全任意大小，而是分别在几个不同大小的级别，Buddy system algorithm就是这样。
: 所以实际上应该是array加链表最合适，简单高效

s*k2014-03-09 08:03

10 楼

其实我觉得内存分配最主要的overhead是速度，而不是内存大小，当然tree是有data
structure方面的overhead，但是其他简单的buddy system或者slab也有external,
internal fragementation的overhead。只是在实际系统中，对内存的要求满足tree形
式的太少了，几乎没有。

【在 d**********x 的大作中提到】

: exactly.
: 但是我的point是树的overhead太大，64位系统要两个8 byte指针，好可怕。
:
: 特定
: 度和

i*12014-03-09 08:03

11 楼

我的感觉是：
1. circular link list不需要额外的data structure,直接在block的前面留两个byte
or word表示状态，即可。而且是直接访问，不想tree，那样间接访问。
2. 当需要merge/de-fragmentation时，link list就很方便了直接merge毫无压力,O(1)
时间。但是tree就不一样了，tree要满足bst的性质，旋转子树是在所难免的。
当然通常的search for a proper size block,link list需要O(N)时间，而tree则只需
要O(logn).但是实际系统应该是用一个额外的list来链接free block的。

tree

【在 a*****1 的大作中提到】