有谁用ADT/IBRINK系统吗 (转载) - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Living

有谁用ADT/IBRINK系统吗 (转载)

有谁用ADT/IBRINK系统吗 (转载)# Living

r*h2010-07-26 07:07

1 楼

面试中被问到，如果需要根据边的信息创建一个有1千万个节点的有向图的邻接表供后
续程序使用，问如何在创建过程中有效存储（邻接矩阵肯定大于物理内存），以及创建
好了，用什么方式存储最有效？
直观的想当然是邻接表存入文件，但是问题是等到图越来越大，添加信息就很费时费力
了，不知道啊各位高人有什么建议？请教了。

a*t2010-07-26 07:07

2 楼

【以下文字转载自 Carolinas 讨论区】
发信人: angryfist (脑残村高手), 信区: Carolinas
标题: 有谁用ADT/IBRINK系统吗
发信站: BBS 未名空间站 (Mon Jul 26 19:39:11 2010, 美东)
询问了一下，不算初装费用，每个月的费用是42+TAX，而且是3年霸王条款，中间不能
退出。感觉很不爽。请问大家都在用吗？
觉得在Amazon上200刀就可以买差不多同样一套东西了，没有月费。效果也差不多，都
是有人闯入的时候尖叫。
当然ADT会通知警察，自己装系统的就只有靠自己报警了。不过绝大多数情况下小贼听
到警报就会跑掉吧？

c*72010-07-26 07:07

3 楼

图的访问肯定是要访问邻接的节点，那么将矩阵分块存储在虚拟内存也就是硬盘上，每
次读取需要的块，大多数操作应该在一个块上，主要是碰到访问块的边界的时候可能需
要多次调用不同的块。

a*e2010-07-26 07:07

4 楼

这个拘说还是找local的服务商比较好

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

: 【以下文字转载自 Carolinas 讨论区】
: 发信人: angryfist (脑残村高手), 信区: Carolinas
: 标题: 有谁用ADT/IBRINK系统吗
: 发信站: BBS 未名空间站 (Mon Jul 26 19:39:11 2010, 美东)
: 询问了一下，不算初装费用，每个月的费用是42+TAX，而且是3年霸王条款，中间不能
: 退出。感觉很不爽。请问大家都在用吗？
: 觉得在Amazon上200刀就可以买差不多同样一套东西了，没有月费。效果也差不多，都
: 是有人闯入的时候尖叫。
: 当然ADT会通知警察，自己装系统的就只有靠自己报警了。不过绝大多数情况下小贼听
: 到警报就会跑掉吧？

r*h2010-07-26 07:07

5 楼

多谢多谢，分块存储是个很好的建议，还可以利用raid加快读取速度。
但是当时面试官反复询问我在创建这个图的时候的设计，我还是有点糊涂，
因为创建的过程中每个节点的邻接点是动态增加的，我就不知道怎么搞了。

【在 c*********7 的大作中提到】

: 图的访问肯定是要访问邻接的节点，那么将矩阵分块存储在虚拟内存也就是硬盘上，每
: 次读取需要的块，大多数操作应该在一个块上，主要是碰到访问块的边界的时候可能需
: 要多次调用不同的块。

c*e2010-07-26 07:07

6 楼

Several things to consider in designing a graph data structure:
1. Is there a need to add/delete graph Nodes?
2. Is there a need to add/delete graph Edges?
3. How to check whether there is a edge between two Nodes?
4. How to iterate all the edges incoming/outgoing to one Node?
5. How to calculate the shortest path between two Nodes?
6. How to calculate the shortest path of each node pair?
7. How to serialize and deserialize a graph data structure?
Seems the problem here is on how to serialize/deserialize all the edges.

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

: 面试中被问到，如果需要根据边的信息创建一个有1千万个节点的有向图的邻接表供后
: 续程序使用，问如何在创建过程中有效存储（邻接矩阵肯定大于物理内存），以及创建
: 好了，用什么方式存储最有效？
: 直观的想当然是邻接表存入文件，但是问题是等到图越来越大，添加信息就很费时费力
: 了，不知道啊各位高人有什么建议？请教了。

c*e2010-07-26 07:07

7 楼

This seems to be a good idea. It is also friendly for Edge/Node Add/Delete
operation. As to get all the edges from/to an Node, also not bad (but we
need to read the extra information for the other Nodes in the same block,
any way to improve?). I assume each bit in the file system denotes an edge.
We need a mechanism to index each block and it should be easy.

【在 c*********7 的大作中提到】