Как мне изменить структуру моего графика (очень медленная вставка)?

Question

Эта программа, которую я делаю, посвящена социальной сети, то есть пользователям и их профилям. Структура профилей UserProfile,

Теперь есть различные возможные реализации Graph, и я не думаю, что я использую лучшую. у меня есть Graph структура и внутри, есть указатель на связанный список типа Vertex, каждый Vertex элемент имеет значение, указатель на следующий Vertex и указатель на связанный список типа Edge, каждый Edge Элемент имеет значение (поэтому я могу определить вес и все, что ему нужно), указатель на следующий Edge и указатель на Vertex владелец.

У меня есть 2 образца файлов с данными для обработки (в стиле CSV) и вставки в график. Первый - это данные пользователя (по одному пользователю на строку); второй - это пользовательские отношения (для графа). Первый файл быстро вставляется в график, потому что я всегда вставляю его в заголовок, и примерно 18000 пользователей. Второй файл занимает много времени, но я все еще вставляю края в голову. Файл содержит около 520000 строк отношений с пользователем и занимает от 13 до 15 минут для вставки в график. Я сделал быстрый тест, и чтение данных происходит довольно быстро, на самом деле мгновенно. Проблема в прошивке.

Эта проблема существует, потому что у меня есть Graph, реализованный со связанными списками для вершин. Каждый раз, когда мне нужно вставить отношение, мне нужно искать 2 вершины, чтобы я мог связать их вместе. Это проблема... Выполнение этого для ~520000 отношений занимает некоторое время.

Как мне решить это?

Решение 1) Некоторые люди рекомендовали мне реализовать Graph (часть вершин) в виде массива вместо связанного списка. Таким образом, у меня есть прямой доступ к каждой вершине, и вставка, вероятно, значительно упадет. Но мне не нравится идея выделения массива с [18000] элементами. Насколько это практически? У моих данных образца ~18000, но что, если мне нужно намного меньше или намного больше? Подход со связным списком обладает такой гибкостью, я могу иметь любой размер, который мне нужен, если для этого есть память. Но массив не, как я собираюсь справиться с такой ситуацией? Каковы ваши предложения?

Использование связанных списков хорошо для пространственной сложности, но плохо для временной сложности. И использование массива хорошо для временной сложности, но плохо для пространственной сложности.

Есть мысли об этом решении?

Решение 2) Этот проект также требует, чтобы у меня была какая-то структура данных, которая обеспечивает быстрый поиск на основе индекса имени и индекса идентификатора. Для этого я решил использовать Hash Tables. Мои таблицы реализованы с отдельной цепочкой в ​​качестве разрешения коллизий, и когда достигается коэффициент загрузки 0,70, я обычно воссоздаю таблицу. Я основываю следующий размер таблицы на этом http://planetmath.org/encyclopedia/GoodHashTablePrimes.html.

В настоящее время обе хеш-таблицы содержат указатель на UserProfile вместо дублирования самого профиля пользователя. Это было бы глупо, изменение данных потребовало бы 3 изменений, и это действительно глупо. Поэтому я просто сохраняю указатель на UserProfile, Этот же указатель профиля пользователя также сохраняется как значение в каждом графике Vertex,

Итак, у меня есть 3 структуры данных, один график и две хэш-таблицы, и каждая из них указывает на один и тот же UserProfile, Структура графика будет использоваться для поиска кратчайшего пути и тому подобного, в то время как хэш-таблицы служат в качестве быстрого индекса по имени и идентификатору.

Что я думаю, чтобы решить мою проблему с графиком, так это вместо того, чтобы хэш-таблицы указывали на UserProfileЯ указываю на соответствующий Vertex, Это все еще указатель, больше и меньше места не используется, я просто изменяю то, на что я указываю.

Таким образом, я могу легко и быстро найти нужные мне вершины и связать их вместе. Это вставит ~520000 отношений довольно быстро.

Я подумал об этом решении, потому что у меня уже есть хеш-таблицы, и мне нужно их иметь, тогда почему бы не использовать их для индексации вершин графа вместо профиля пользователя? Это в основном то же самое, я все еще могу получить доступ к UserProfile довольно быстро, просто иди к Vertex а затем к UserProfile,

Но видите ли вы какие-либо минусы в этом втором решении по сравнению с первым? Или только плюсы, которые перекрывают плюсы и минусы первого решения?

Другое решение) Если у вас есть другое решение, я весь в ушах. Но, пожалуйста, объясните плюсы и минусы этого решения по сравнению с предыдущим 2. У меня действительно не так много времени, чтобы тратить его на это прямо сейчас, мне нужно продолжить этот проект, так что, если я делаю так изменение, мне нужно точно понять, что изменить, и если это действительно так.

Надеюсь, что никто не уснул, читая это, и закрыл браузер, извините за большой завет. Но мне действительно нужно решить, что с этим делать, и мне действительно нужно внести изменения.

PS: Отвечая на мои предложенные решения, перечислите их, как я, чтобы я точно знал, о чем вы говорите, и не путайте себя больше, чем я уже есть.

Answer 1

Первый подход заключается в том, что поскольку основной проблемой здесь является скорость, я бы предпочел массивный подход.

Конечно, вы должны поддерживать хэш-таблицу для поиска по индексу имен.

Если я правильно понял, вы обрабатываете данные только один раз. Таким образом, нет динамической вставки данных.

Чтобы решить проблему с распределением пространства, я бы порекомендовал:

1 - Прочитайте один раз файл, чтобы получить номер вершины.

2 - выделить это пространство

Если ваши данные являются динамическими, вы можете реализовать какой-то простой метод для увеличения размера массива с шагом 50%.

3 - В Edges замените свой связанный список на массив. Этот массив должен динамически увеличиваться с шагом 50%.

Даже с выделенным "дополнительным" пространством при увеличении размера с шагом 50% общий размер, используемый массивом, должен быть лишь незначительно больше, чем с размером связанного списка.

Я надеюсь, что смогу помочь.