Какую коллекцию лучше всего использовать для уникальной идентификации узлов?

Question

В настоящее время я использую Dictionary<int,node> для хранения около 10000 узлов. Ключ используется в качестве идентификационного номера для последующего поиска, а «узел» - это класс, который содержит некоторые данные. Другие классы в программе используют идентификационный номер в качестве указателя на узел. (это может показаться неэффективным. Однако объяснение моих аргументов в пользу использования словаря для этого выходит за рамки моего вопроса.)

Однако 20% узлов являются дубликатами. Что я хочу сделать, это когда я добавляю проверку узла, чтобы увидеть, существует ли все это готово. если это так, то используйте этот идентификационный номер. Если нет, создайте новый.

Это мое текущее решение проблемы:

public class nodeDictionary 
{

    Dictionary<int, node> dict = new Dictionary<int, node>( );
    public int addNewNode( latLng ll )
    {
        node n = new node( ll );
        if ( dict.ContainsValue( n ) )
        {
            foreach ( KeyValuePair<int, node> kv in dict )
            {
                if ( kv.Value == n )
                {
                    return kv.Key;
                }
            }
        }
        else
        {
            if ( dict.Count != 0 )
            {
                dict.Add( dict.Last( ).Key + 1, n );
                return dict.Last( ).Key + 1;
            }
            else
            {
                dict.Add( 0, n );
                return 0;
            }
        }
        throw new Exception( );
    }//end add new node
}

Проблема заключается в том, что при попытке добавить новый узел в список из 100 000 узлов, для добавления узла требуется 78 миллисекунд. Это неприемлемо, потому что я мог бы добавить дополнительные 1000 узлов в любой момент времени.

Итак, есть ли лучший способ сделать это? Я не ищу кого-то, чтобы написать код для меня, я просто ищу руководство.

Answer 1

Звучит так, как ты хочешь

• убедитесь, что LatLng переопределяет Equals / GetHashCode (желательно реализовать интерфейс IEquatable<LatLng>)
• соберите все предметы прямо в HashSet<LatLng>

Для реализации GetHashCode см. Здесь: Почему важно переопределить GetHashCode, когда переопределен метод Equals?

Если вам нужно каким-то образом сгенерировать «искусственные» уникальные идентификаторы, я предлагаю вам снова использовать словарный подход, но «наоборот»:

// uses the same hash function for speedy lookup/insertion
IDictionary<LatLng, int> idMap = new Dictionary<LatLng, int>(); 

foreach (LatLng latLng in LatLngCoords)
{
    if (!idMap.ContainsKey(latLng))
        idMap.Add(latLng, idMap.Count+1); // to start with 1
}

Вы можете заменить HashSet<> на idMap; реализация (и характеристики производительности), по сути, такие же, как и ассоциативный контейнер.

Вот функция поиска для перехода от LatLng к Id:

int IdLookup(LatLng latLng)
{
     int id;
     if (idMap.TryGetValue(latLng, id))
         return id;
     throw new InvalidArgumentException("Coordinate not in idMap");
}

Вы можете добавить его точно в срок:

int IdFor(LatLng latLng)
{
     int id;
     if (idMap.TryGetValue(latLng, id))
         return id;

     id = idMap.Count+1;
     idMap.Add(latLng, id);
     return id;
}

Answer 2

Ваше решение не только медленное, но и неправильное.Порядок элементов в Dictionary не определен, поэтому dict.Last() не гарантирует возврат элемента, который был добавлен последним.(Хотя часто это может выглядеть так.)

Использование идентификатора для идентификации объекта в вашем приложении также кажется неправильным.Вы должны рассмотреть возможность использования ссылок на объект напрямую.

Но если вы хотите использовать свой текущий дизайн и предполагать, что вы сравниваете узлы на основе их latLng, вы можете создать два словаря: тот, который у вас уже есть, ивторой, Dictionary<latLng, int>, который можно использовать для эффективного определения того, существует ли уже определенный узел.И если это так, он дает вам свой идентификатор.

Answer 3

Я бы добавил второй словарь для обратного направления. т.е. Dictionary<Node,int>

Тогда вы либо

• Довольны ссылочным равенством и ничего не делаем.
• Создайте IEqualityComparer<Node> и добавьте его в словарь
• Переопределить Equals и GetHashCode на Node

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

Answer 4

Какова цель этого кода?

if ( dict.ContainsValue( n ) )
{
    foreach ( KeyValuePair kv in dict )
    {
        if ( kv.Value == n )
        {
            return kv.Key;
        }
    }
}

ContainsValue ищет значение (вместо ключа) и очень неэффективно (O (n)).То же самое для foreach.Не говоря уже о том, что вы делаете оба, когда необходим только один (вы можете полностью удалить ContainsValue, переставив немного if sa)!

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

Answer 5

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

1. Поиск элемента по целочисленному ключу теперь O (1) (и очень быстрый O (1), учитывая, что это просто разыменование массива внутри).*

2. Когда вы вставляете новый элемент, вы выполняете поиск O (n), чтобы увидеть, существует ли он уже в списке.Если это не так, вы также уже просмотрели список и, возможно, записали, столкнулись ли вы с записью с нулевой записью.Если у вас есть, этот индекс является новым ключом.Если нет, то новым ключом будет текущий список Count.Вы перечисляете коллекцию один раз, а не несколько раз, и само перечисление намного быстрее, чем перечисление словаря.

Answer 6

Вы можете попробовать использовать HashSet<T>