c# - 用于唯一标识节点的最佳集合是什么?

标签 c# .net data-structures collections

目前我正在使用 Dictionary<int,node>存储大约 10,000 个节点。 key 用作稍后查找的 ID 号,“节点”是包含一些数据的类。程序中的其他类使用 ID 号作为指向节点的指针。 (这听起来可能效率低下。但是,解释我为此使用字典的理由超出了我的问题范围。)

但是,20% 的节点是重复的。
我想要做的是当我添加一个节点时检查它是否已经准备就绪。如果确实如此,则使用该 ID 号。如果没有创建一个新的。

这是我目前对该问题的解决方案:

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 毫秒。这是 Not Acceptable ,因为我可能会在任何给定时间添加额外的 1,000 个节点。

那么,有没有更好的方法来做到这一点?我不是在找人为我编写代码,我只是在寻找指导。

最佳答案

听起来你想

  • 确保 LatLng 覆盖 Equals/GetHashCode(最好实现 IEquatable<LatLng> 接口(interface))
  • 将所有项目直接填充到 HashSet<LatLng>

  • 要实现 GetHashCode,请参见此处:Why is it important to override GetHashCode when Equals method is overridden?

    如果您需要以某种方式生成“人工”唯一 ID,我建议您再次使用字典方法,但“相反”:
    // 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
    }
    

    你可以有idMap替换HashSet<> ;实现(和性能特征)本质上是相同的,但作为一个关联容器。

    这是从 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;
    }
    

    关于c# - 用于唯一标识节点的最佳集合是什么?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/7970642/

    相关文章:

    c# - 总是遍历业务层才能到达数据层吗?

    c# - 如何在程序集中查找作为通用抽象类实例的所有类并实现某个接口(interface)

    java - 可移植运行时?

    java - 我不记得固定大小的排序树的数据结构

    javascript - 如何将对象转换成数组?

    javascript - JavaScript 重新路由的 MVC 异常

    c# - 困惑于从Linq2Sql从var中获取int

    c# - 无法在 asp.net core 的 startup.cs 文件中找到 Use.RunTimePageInfo() 方法

    c# - Linq 快速相交查询 - 增强?

    database - Yelp如何进行“立即开放”?