是否有更快的方法来获取列表中不在现有列表中的元素

Question

我正在地图上放置图钉。当用户滚动或缩小时，我现在可以放置额外的图钉。我首先进行查询以获取新地图范围中的所有实体。接下来我需要从该列表中删除地图上已有的所有图钉。

// this gets the properties of all existing pins
var listEventPins = EntitiesDataSource.Shapes
    .Where(s => ReferenceEquals(s.Properties["Type"], _typeEvent))
    .Select(s => s.Properties);

// paramData.EventData is the list of all entities in the new map extent.
// this builds a list of all entities that are not already on the map - which is listEventPins
listEvents = paramData.EventData
    .Where(e => listEventPins.All(p => Convert.ToInt64(p["UniqueId"]) != e.UniqueId))
    .ToList();

对于现有 40K 和总共 40K 的列表（地图范围几乎没有添加任何新内容的情况），其中大部分已经在地图上，第二个 LINQ 语句大约需要 40 秒。

是否有更高效的方法来生成第二个列表？我可以更改第一个 LINQ 查询来创建

Properties["UniqueId"]

条目列表，我相信这会对一些人有所帮助。但是有没有一种不同的方法可以明显更快？

Answer 1

我建议使用 var existingPinIds = listEventPins.Select(p => Convert.ToInt64(p["UniqueId"]).ToHashSet(); 之类的东西构建现有 ID 的 HashSet，然后使用 .Where(e 过滤事件数据=> !existingPinIds.Contains(e.UniqueId)).

这应该比实际上是嵌套循环的现有代码更有效。每个

.Contains

操作的复杂度为O(log N)，因此整个过滤操作的复杂度应该为O(N log N)。

var existingPinIds = listEventPins
    .Select(p => Convert.ToInt64(p["UniqueId"])
    .ToHashSet();

listEvents = paramData.EventData
    .Where(e => !existingPinIds.Contains(e.UniqueId))
    .ToList();