Эта программа, которую я делаю, посвящена социальной сети, а значит, есть пользователи и их профили. Структура профилей UserProfile.
Существуют различные возможные реализации Graph, и я не думаю, что использую лучшую из них. У меня есть структура Graph, а внутри есть указатель на связанный список типа Vertex. Каждый элемент Vertex имеет значение, указатель на следующий Vertex и указатель на связанный список типа Edge. Каждый элемент Edge имеет значение (поэтому я могу определить веса и все, что нужно), указатель на следующий Edge и указатель на владельца Vertex.
У меня есть 2 образца файлов с данными для обработки (в стиле CSV) и вставки в график. Первый — это данные пользователя (один пользователь в строке); второй — пользовательские отношения (для графа). Первый файл быстро вставляется в график, потому что я всегда вставляю в начало, а пользователей около 18000. Второй файл занимает много времени, но я все еще вставляю края в голову. Файл содержит около ~ 520 000 строк пользовательских отношений, и его вставка в график занимает от 13 до 15 минут. Я сделал быстрый тест, и чтение данных происходит довольно быстро, на самом деле мгновенно. Проблема в прошивке.
Эта проблема существует из-за того, что у меня есть график, реализованный со связанными списками для вершин. Каждый раз, когда мне нужно вставить отношение, мне нужно найти 2 вершины, чтобы я мог связать их вместе. Вот в чем проблема... Выполнение этого для ~ 520000 отношений занимает некоторое время.
Как мне это решить?
Решение 1) Некоторые люди рекомендовали мне реализовать график (часть вершин) как массив вместо связанного списка. Таким образом, у меня есть прямой доступ к каждой вершине, и вставка, вероятно, значительно упадет. Но мне не нравится идея размещения массива с [18000] элементами. Насколько это практично? В моем образце данных ~ 18000, но что, если мне нужно намного меньше или намного больше? Подход связанного списка обладает такой гибкостью, я могу иметь любой размер, какой захочу, если для него есть память. Но массив не работает, как мне поступить в такой ситуации? Каковы ваши предложения?
Использование связанных списков хорошо для пространственной сложности, но плохо для временной сложности. И использование массива хорошо для временной сложности, но плохо для пространственной сложности.
Любые мысли об этом решении?
Решение 2) Этот проект также требует, чтобы у меня были какие-то структуры данных, позволяющие осуществлять быстрый поиск на основе индекса имени и индекса идентификатора. Для этого я решил использовать Hash Tables. Мои таблицы реализованы с отдельной цепочкой для разрешения коллизий, и когда достигается коэффициент загрузки 0,70, я обычно воссоздаю таблицу. Я основываю следующий размер таблицы на этом http://planetmath.org/encyclopedia/GoodHashTablePrimes.html.
В настоящее время обе хеш-таблицы содержат указатель на UserProfile вместо дублирования самого профиля пользователя. Это было бы глупо, для изменения данных потребовалось бы 3 изменения, и делать это таким образом действительно глупо. Поэтому я просто сохраняю указатель на файл UserProfile. Тот же указатель профиля пользователя также сохраняется как значение на каждом графике Vertex.
Итак, у меня есть 3 структуры данных, один график и две хеш-таблицы, и каждая из них указывает на одно и то же точно UserProfile. Структура Graph будет служить для поиска кратчайшего пути и тому подобного, в то время как хеш-таблицы служат быстрым индексом по имени и идентификатору.
То, что я думаю, чтобы решить мою проблему с графиком, заключается в том, чтобы вместо того, чтобы значение хэш-таблицы указывало на UserProfile, я указывал на соответствующее Vertex. Это все еще указатель, не больше и не меньше места используется, я просто меняю то, на что указываю.
Таким образом, я могу легко и быстро найти каждую нужную мне вершину и связать их вместе. Это довольно быстро вставит отношения ~ 520000.
Я подумал об этом решении, потому что у меня уже есть хэш-таблицы, и они мне нужны, тогда почему бы не воспользоваться ими для индексации вершин графа вместо профиля пользователя? Это в основном то же самое, я все еще могу получить доступ к UserProfile довольно быстро, просто перейдите к Vertex, а затем к UserProfile.
Но видите ли вы какие-либо недостатки этого второго решения по сравнению с первым? Или только плюсы, которые перевешивают плюсы и минусы первого решения?
Другое решение) Если у вас есть другое решение, я внимательно слушаю. Но, пожалуйста, объясните плюсы и минусы этого решения по сравнению с предыдущими двумя. У меня действительно не так много времени, чтобы тратить его прямо сейчас, мне нужно двигаться дальше с этим проектом, поэтому, если я делаю это изменение, мне нужно точно понять, что нужно изменить и действительно ли это правильный путь.
Надеюсь, никто не заснул, читая это, и закрыл браузер, извините за большое завещание. Но мне действительно нужно решить, что с этим делать, и мне действительно нужно внести изменения.
P.S. Отвечая на предложенные мной решения, пожалуйста, перечисляйте их так же, как и я, чтобы я точно знал, о чем вы говорите, и не запутывал себя больше, чем я уже сделал.
