我怎样才能有效地找到一套在地图上的子集？ [英] How can I efficiently find subsets of a set in a map?

问题描述

考虑我刚才套值来值的地图，在Java中该图的类型是：

Consider that I have a map of sets of values to values, in Java the type of this map would be:

Map<Set<Object>, Object> setToObjMap;

赋予了新的对象集设置，我希望能够找到在setToObjMap所有值，其中相关的关键是一个一个的集搜索集。

Given a new set of objects set, I wish to find all values in the setToObjMap where the associated key is a subset of a "search set".

因此​​，举例来说，如果我的地图是：

So, for example, if my map was:

["telephone", "hat"] -> "book"
["laugh", "fry", "mouse"] -> "house"
["dog", "cat"] -> "monster"

然后，给出的检索集 [电话，帽子，书，狗，猫] 我会检索值的书和怪物。

Then, given the search set ["telephone", "hat", "book", "dog", "cat"] I would retrieve the values "book" and "monster".

在实践中可能存在的条目数以万计的 setToObjectMap ，以在可能值几万。搜索组通常有大约10个元素。

In practice there may be tens of thousands of entries in the setToObjectMap, with tens of thousands of possible values in the sets. The search set will typically have around 10 elements.

我希望有一个有效的方法来做到这一点，并不需要通过在地图上的所有按键迭代。任何人都可以提供什么建议？

I'm hoping there is an efficient way to do this that doesn't require iterating through all keys in the map. Can anyone offer any suggestions?

推荐答案

您可以创建一个查找数据结构

You can create a lookup data structure

Map<String,List<Finder>>

使用搜索有一个int 计数和最高和 RES 字。请注意该列表是那里采取了这样的情况，许多集 setToObjMap 可以共享同一个词，这是不是在你的例子。

With Finder having an int count and max, and a res word. Take note that the list is there to take care of the case where many sets in setToObjMap can share the same word, which is not in your examples.

"telephone" -> [{res:"book",count=0,max=2}]
"hat" -> same object as above
"laugh" -> [{res:"house",count=0,max=3}]
...

此查询收集是快速建立和更快的查找后刷新。

This lookup collection is quick to build and even quicker to flush after a lookup.

到设置，每个字，每个搜索这个词，它增加了计数变量。第二遍，把查找地图的所有值，如果计数==最大，把 RES 的结果。

The lookup algorithm iterates through set, for each word, and each Finder for this word, it increases the count variable. Second pass, take all values of the lookup map, if count==max, put res in the result.

初​​始化算法：

for Entry e in setToObjMap
  Finder f = new Finder(e.value, 0, e.key.size) // res, count, max
  for String word in e.key
    lookup.get(word).add(f)

查找算法：

for String word in set
  for Finder f in lookup.get(word)
    f.count ++
for Finder f in lookup.values()
  if (f.count==f.max)
    res.add(f.res)

重置算法：

for Finder f in lookup.values()
    f.count = 0

对于复杂性，如果n是元素的数量设置和m值的数量 setToObjMap ，复杂性将是O（N + M）

As for the complexity, if n is the number of elements in set and m the number of values in setToObjMap, the complexity will be O(n+m)

这篇关于我怎样才能有效地找到一套在地图上的子集？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！