问用于对象类索引的数据结构

EN

好的，我来试一试。如果您担心内存限制，那么它可能不是您想要的。

下面是一些红宝石代码：

# hash of all objects by type
#
# heirarchy:
#
#   animal
#     amphibian
#     mammal
#       hominid
#
objects_by_type = {
  animal: [:snake, :fish]
  amphibian: [:frog, :newt]
  mammal: [:whale, :rabbit]
  hominid: [:gorilla, :chimpanzee]
}

# print all objects that are of type `search_type`, or a subtype of `search_type`
def print_objects_of_type(search_type)
  #get a list of all valid types
  all_types = [search_type] + search_type.subtypes

  #print all objects belonging to a type in all_types
  all_types.each do |t|
    objects_by_type[t].each do |obj|
      print obj.to_s + ' '
    end
  end

  print "\n"
end

print_objects_of_type(:animal)
# snake fish frog newt whale rabbit gorilla chimpanzee human

print_objects_of_type(:mammal)
# whale rabbit gorilla chimpanzee human

print_objects_of_type(:amphibian)
# frog newt

所有这些都依赖于散列，其中键是类型，值是对象的列表。

搜索给定类型的对象将比O(n)更好，因为您直接进入正确的对象，而不测试不正确的对象。散列查找将是O(1)，其余的取决于获得给定类型的子类型列表的速度。

对于插入和删除，只要对象列表是链接列表，就应该能够实现O(1)。插入和删除将需要一个哈希表查找(O(1))和一个插入/删除链接列表(也是O(1))。

现在，唯一的问题是这种方法所需的内存量。类型的数量影响哈希表内存的使用，对象的数量影响链接列表内存的使用。您可以用连续内存(如C++ std::vector)替换链接列表，这可以消除每个对象的开销，但是插入/删除将不再是O(1)。您只需计算每个类型和每个对象的开销，乘以预期的类型和对象数，然后从那里做出决定。

我能想到的所有解决方案都需要一个哈希表，所以如果这有太多的内存开销，那么我就没有想法了。

就内存成本而言，汤姆·达林的方法相当接近最优。但是，正如前面提到的，有些算法可以用这些代价来换取更快的超级类型和计算一个类型所拥有的直接/间接超级类型的数量。下面是几个这样做的算法，这取决于您决定是否值得这样做。最后，这两种算法的性能在很大程度上取决于类型图(子类型和超类型之间的连接)是什么样的。如果类型图是相当多余的或其他有利的(与性能相关的变量更接近性能界限的下限)，那么以下算法的平均(摊销)性能可以使它们值得使用。

与业绩有关的变量：

• N是类型的数目。
• D是平均深度(子类型向下有多远)。界O(1)到O(N)
• M是编号最高的ID的值，该ID是给定类型的子类型。界O(1)到O(N)
• K是一个类型的直接超级类型的数目。界O(1)到O(N)
• K是一个类型的总唯一超级类型的平均数量。界O(1)到O(N)
• L是一个类型所具有的总唯一子类型的平均数目。界O(1)到O(N)
• E是子类型-超级类型连接的数目。界O(N)到O(N^2)

算法：

1. O(1)超型查找与O(N*D)额外的空间成本。这样做的目的是让每个类型维护一个(动态)布尔数组的所有它的超级类型。超级类型数组的大小将等于最大超级类型ID数。该数组将通过复制每个继承的超级类型的超级类型数组来构建，然后为继承的超级类型本身添加每个ids。Pythonic检查类型是否有超级类型，如下所示： 返回len(supertype_array) > supertype_id，supertype_arraysupertype_id为True 为每个直接的超级类型添加一个子类型等于在超级类型列表上设置联合，即O(k*N)。
2. 如果E相对接近N，而其他地方的成本则更高，则另一种方法提供了优于#1的空间性能。supertype查找是O(log )，在这里添加一个子类型等于对每个直接超级类型的超级类型列表进行集合合并，但最终在每个超级类型列表的元素之和中是线性的。这样做的想法是，每当it占用的空间小于布尔数组时，就使用it的按位trie。如果ID号为10、20和1000，则可以清楚地看出其好处。按位trie所需的位数将远远少于布尔数组中所需的1000位。但是，如果it是1,2,3,4,5，...,100，那么它至少需要573位(计算)的位，而对于布尔数组，只需要100位。要确定一个子类何时应该使用布尔数组(当数组已经足够满时)，以及应该根据超级类型中的位总数使用位数，那么跟踪每个布尔数组或按位Trie的上限并不太困难。从trie复制到新trie是线性的位数。当从布尔数组复制到trie时，在位数中是线性日志。如果一个布尔数组具有更高的空间效率，那么要确定一个类型是否具有给定的超级类型，只需要执行像#1中那样的查找，否则就会使用二进制搜索。如果您想尝试实现Y-快速trie，您也可以使用类似于它的东西。按位基数trie可以提高空间效率。

这两种算法的插入/删除成本与Tom Dalling的相同，尽管基函数Trie可能更快/更节省空间。也不难为每种类型保留一个超级类型数量的计数器，但这需要额外的O(N log N)额外空间。

注意，尺寸要求假定最小位数用来表示一个数字，以最小化空间。从这些不重要的位数中删除不应超过O(log )的因子对时间性能的影响。