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

Question

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

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

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

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

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

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

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

Любые мысли об этом решении?

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

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

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

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

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

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

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

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

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

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

Answer 1

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

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

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

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

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

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

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

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

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

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