我应该如何改变我的图形结构（很慢插入）？

Question

这个程序我做的是关于社交网络，这意味着有用户和他们的个人资料。轮廓结构是UserProfile。

现在，有各种可能的图形实现和我使用的最好的一个，我不认为。我有一个Graph结构和内部，有一个指针类型Vertex的链接列表。每个Vertex元件具有值，指针到下一个Vertex和一个指向型Edge的链接列表。每个Edge元件具有一个值（所以我可以定义权重和任何需要它的），一个指针到下一个Edge和一个指针Vertex所有者。

我有要处理的数据有2个样本文件（CSV样式）和插入件插入所述图形。第一个是用户数据（每行一个用户）;第二个是（对于图）的用户的关系。第一个文件是迅速插入图表，因为我总是在头插入并有喜欢〜18000用户。第二个文件需要年龄，但我还是在头部嵌件的边缘。该文件包含有关〜52万线用户关系和13-15mins之间需要插入到图形。我做了一个快速测试和读取数据是相当快，瞬间真。的问题是在插入

存在此问题，因为我有一个图，其顶点链表实现。每次我需要插入的关系，我需要查找的2个顶点，所以我可以将它们关联起来。这就是问题......这样做的〜520000间的关系，需要一段时间。

我应该如何解决这个问题？

<强>溶液1）有人推荐我实施格拉夫（顶点的部分）作为阵列而不是一个链表。这样，我要每个顶点直接访问，并且插入很可能将大幅下降。但是，我不喜欢与分配[18000]元素的数组的想法。这实际上是如何为？我的样本数据具有18000〜，但如果我需要什么要少得多或更多？链表方法具有灵活性，我可以有我想只要有内存为它不管大小。但数组不，我应该如何处理这种情况呢？你有什么建议？

使用链表是良好的空间复杂度，但时间复杂度不好。和使用阵列是良好的时间复杂度但对于空间复杂度不良。

有关此溶液中的任何想法？

<强>溶液2）：此项目还要求我有某种允许基于一个索引名字和ID索引快速查找数据结构。为此，我决定使用哈希表。我的表是有独立的链接碰撞分辨率和0.70客座率到后，我通常重新创建表来实现。我基地邻桌的大小在此 http://planetmath.org/encyclopedia/GoodHashTablePrimes.html

目前，两个哈希表保持一个指针，指向代替UserProfile重复用户简档本身。这将是愚蠢的，变化的数据将需要更换3次，这真的愚蠢到这样做的。所以，我刚才保存的指针UserProfile。相同的用户简档的指针也被保存在每个图形Vertex值。

所以，我有3层数据结构中，一个图形和两个哈希表和他们中的每一个单一指向同一确切UserProfile。图形结构将有助于找出像的是，虽然散列表作为由名称和ID快捷索引的最短路径和东西的目的。

我在想什么来解决我的图表的问题是，并没有让哈希表值点到UserProfile，我把它指向相应Vertex。它仍然是一个指针，不能多也没有使用更少的空间，我举ST改变我指向。

这样，我可以轻松快速地查找每个顶点，我需要和他们联系在一起。这将插入〜520000个关系很快。

我认为这个解决方案，因为我已经有哈希表，我需要他们，那么，为什么不利用它们来索引图形顶点，而不是用户的个人资料？它基本上是同样的事情，我仍然可以访问UserProfile很快，只要到Vertex然后到UserProfile。

但是，你看到相对于第一个第二个解决方案的任何缺点？或仅优点在于过电力在所述第一溶液中的利弊？

其他解决方案）如果您有任何其他的解决办法，我所有的耳朵。但请解释该解决方案的优劣比上年2.我真的没有太多时间去浪费这个，现在，我需要这个项目继续前进，所以，如果我做的做这样的一个变化，我需要了解什么改变，如果这真的要走的路。

希望没有人睡着了，读这篇文章，关闭浏览器，遗憾的大明证。但我真的需要决定怎样做这件事，我真的需要做出改变。

P.S：：当回答我提出的解决方案，请列举他们和我一样，所以我确切地知道你在说什么，不要混淆我自己比我更已经是

Answer 1

第一种方法是由于主问题这里是速度，我宁愿阵列的方法。

您应，当然，保持哈希表的名称的索引查找。

如果我理解正确的，则仅处理该数据的一个时间。因此不存在动态数据插入。

要处理的空间分配的问题，我建议：

1 - 读取一次的文件，以获得顶点的数目

2 - 分配该空间

如果您数据是动态的，则可以实现一些简单的方法来增加在50％以下步骤的阵列大小。

3 - 中的边缘，代替你链表的阵列。此阵列应当动态地增加50％的步骤。

即使在“额外”的空间分配，当你递增与50％步长的大小，由阵列中使用的总大小应该只是略微大于与链表的尺寸大。

我希望我能有所帮助。