Эта программа, которую я делаю, посвящена социальной сети, то есть пользователям и их профилям.Структура профилей: 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.Структура Графа будет служить для поиска кратчайшего пути и тому подобного, в то время как Хэш-таблицы служат в качестве быстрого индекса по имени и идентификатору.
Я решил решить мою проблему с Графиком вместоимея значение Hash Tables, указывающее на UserProfile, я указываю на соответствующее Vertex.Это по-прежнему указатель, больше и не меньше места используется, я просто изменяю то, на что указываю.
Таким образом, я могу легко и быстро найти каждую нужную мне вершину и связать их вместе.Это довольно быстро вставит ~ 520000 отношений.
Я подумал об этом решении, потому что у меня уже есть хэш-таблицы, и мне нужно их иметь, почему бы не использовать их для индексации вершин графа вместо профиля пользователя? Это в основном то же самое, я все еще могу довольно быстро получить доступ к UserProfile, просто перейдите к Vertex и затем к UserProfile.
Но вы видите какие-либо минусы в этом втором решении по сравнению с первым? Или только плюсы, которые побеждают плюсы и минусы первого решения?
Другое решение) Если у вас есть другое решение, я весь в ушах. Но, пожалуйста, объясните плюсы и минусы этого решения по сравнению с предыдущим 2. У меня действительно не так много времени, чтобы тратить его на это прямо сейчас, мне нужно двигаться дальше с этим проектом, так что, если я делаю так изменение, мне нужно точно понять, что изменить, и если это действительно так.
Надеюсь, никто не заснул, читая это, и закрыл браузер, извините за большой завет. Но мне действительно нужно решить, что с этим делать, и мне действительно нужно внести изменения.
P.S: Отвечая на мои предложенные решения, перечислите их, как я, чтобы я точно знал, о чем вы говорите, и не путайте меня больше, чем я уже.