Структура данных для отношений

Question

Я конвертирую VB6 в C # и хочу сделать свою структуру данных, которая содержит значения и отношения, более эффективной. В VB у меня есть коллекция значений и другая коллекция отношений между этими значениями с приоритетами для этих отношений. У меня также есть алгоритм, который, когда ему передают набор значений, возвращает все отношения, необходимые для объединения этих значений. Например, допустим, что коллекция значений содержит 1-10, а коллекция отношений содержит

1,2
3,2
5,2
2,8
8,10
9,10

Если бы ввод был 1,9,10, возвращаемые отношения были бы -

1,2
2,8
8,10
9,10

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

Есть идеи?

Дополнительная информация -

Количество значений обычно будет меньше 100, а отношения меньше 500. Коллекции статичны, и алгоритм будет использоваться снова и снова для поиска путей. Кроме того, я не спрашивал об этом, но будет ли алгоритм в несвязанной структуре данных наиболее эффективным?

Answer 1

Звучит так, как будто у вас есть График . Это структура с узлами и краями. Есть много много библиотек и инструментов, которые имеют дело с графами. Microsoft даже выпустила статью о том, как с ними справиться. Я думаю, что графики хороши и чрезвычайно полезны во многих ситуациях.

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

В вашей ситуации ваши значения - это узлы, а ваши отношения - это ребра.

Answer 2

Вы должны спросить себя (и скажите нам), какой тип использования вы ожидаете. Добавляются ли эти отношения по порядку или случайным образом, поступают ли ваши запросы по порядку (как вы их показываете) или случайным образом, и является ли это, по сути, пакетным процессом - загружайте их, считываете запросы - или вы ожидаете сделать это «в сети» в том смысле, что вы можете добавить некоторые, затем запросить некоторые, затем добавить еще несколько и запросить еще?

Вы будете знать, сколько вы хотите хранить заранее, и сколько вы ожидаете хранить? Десятки? Тысячи? Десятки миллионов?

Вот несколько предложений:

• если вы знаете заранее, сколько вы ожидать, чтобы хранить, это не совсем большое число, вы не ожидаете, чтобы добавить их после первой загрузки там нет ли дубликатов в левая сторона пары, и они достаточно "плотные" в ощущение, что нет больших пробелов между числами в левой пары, то вы, вероятно, хотите массив. Вставка O (1) , доступ O (1) , но не может иметь повторяющиеся индексы и расширять его после постройки - это боль.
• если число действительно большое, например> 10 ⁸ , Вы, вероятно, хотите какую-то базу данных. Базы данных относительно очень медленные - от 4 до 5 порядков величина больше, чем структуры данных в памяти - но обрабатывать действительно большие данные.
• Если у вас есть вставки после Первая загрузка, и вы заботитесь о порядок, вы хотите, чтобы некоторые своего рода дерево, как 2-3 дерева. вставка и получить доступ к обоим O (LG N) . Вы, вероятно, найдете имплементацию под именем типа «упорядоченный список» (Я не парень C #.)
• Почти любой другой случай, вы, вероятно, хочу хеш Средняя вставка и обращаться к обоим O (1) , как к массиву; худший случай эти данные] O (n)