3

我正在对大型数据集进行一些实验，并希望优化特定部分。目前，我有 5-6 个Models，每个存储一个从Topics 到sList的映射String。s的集合Topic很大，每个之间都一样Model，所以一定有更好的办法。最终我需要执行的查询是：对于某些组合String的位置 x是什么。ListModelTopic

使用映射方法的问题之一是，如果有 500k-5M 个主题，每个主题都有一个包含 20 个字符串的列表。然后我Map<Model, Map<Topic, List<String>>>的将是巨大的。

4

5 回答 5

1

不清楚您想在哪里/如何实现“内存效率”。首先需要查看详细数据的详细信息以查看消耗了多少存储空间，然后检查各种组织方式并根据开销百分比与“真实”数据分析它们的效率。

简单看一下，当您考虑关联的表时，HashMap 的每个条目大约有 80 个字节的开销。一个 ArrayList 看起来平均在 10-12 左右。不用看，我猜 TreeMap 会比 HashMap 多——可能有 100 个。

一般来说，您自己的对象中的链接在存储和访问速度方面都比使用这些聚合对象的链接“更便宜”。但是聚合对象使用起来很方便，并且已经在一定程度上进行了“优化”。

（但是查看您的更新，您可能应该查看数据库应用程序，而不是将所有内容都保存在堆中。）

于 2012-10-19T21:58:03.807 回答
1

你试过 SortedSet / Maps 吗？听起来您需要优化搜索，排序集合（如 TreeMap）应该是 log(n)，而常规列表是 O(1)。当然，这种事情是数据库擅长的......

于 2012-10-19T21:37:50.837 回答
1

您可以使用TopicandModel在单个 Map 中构造复合键，例如

map.put(topic1_id + model1_id, list1_1);
map.put(topic1_id + model2_id, list1_2);
...
map.get(topic_id + model_id)

其中 ID 是字符串（或类似的方案可以与数字标识符一起使用）。

类似的方法是为每个主题分配一个唯一的编号并建模，然后将字符串列表存储在数组中，因此查找给定组合的列表只需查找两个索引，然后访问二维数组中的给定位置. （但是，如果您在构建数据结构之前知道主题和模型的数量，这会更容易）

为了内存效率，还要考虑小细节。通常，您希望最小化对象的数量 - 每个对象都有开销。ArrayList 在动态增长时可能会浪费大量空间，当它们超过当前容量时，其大小会增加一倍。如果您可以将它们预先设置为所需的容量（或使用数组代替），那么您可以节省大量内存。使用大量小型 HashMap 时也是如此。

于 2012-10-19T21:50:36.930 回答
0

一种可能的数据结构是映射的层次结构，导致字符串数组。例如：

HashMap<Model, HashMap<Topic, String[]>> map;

查询函数将如下所示：

public String query(Model model, Topic topic, int x) {

    HashMap<Topic, String[]> childMap = map.get(model);
    if (childMap == null) {
       return null;
    }

    String[] list = childMap.get(topic);
    if (list == null) { 
        return null;
    }

    return list[x];
}

假设您的模型和主题结构实现hashCode()并equals()合理，查询性能应该是相当不错的。

一个潜在的弱点：我假设您需要索引大量模型/主题组合以及相关的字符串列表（如果没有，您可能不会询问优化）。我的猜测是子 String[] 数组会消耗大量内存。每个数组都是一个 Java 对象（大约 20 个字节）+ 每个数组位置的指针。

那里有2条建议：

String[]1）如果许多模型/主题组合共享同一组字符串，您可以通过共享这些实例获得相当多的收益。

2) 如果您使用的是 64 位 VM，请务必使用压缩的普通对象指针 ( -XX:+UseCompressedOops)。这至少会使大多数指针保持 4 个字节而不是 8 个字节。自 1.6.0_23 以来，压缩的 OOP 是默认设置，因此相对较新的 VM 将在此处为您节省一些内存。

于 2012-10-19T21:59:48.843 回答
0

未提及的另一种可能性是在查询时使用String[][][]和模型和主题存储字符串List，ArrayList然后在查询时：

public String query(Model model, Topic topic, int x) {
   return strings[models.indexOf(model)][topics.indexOf(topic)][x];
}

如果对主题和模型进行排序，则可以进一步提高速度，而不是indexOf使用二分搜索。

于 2012-10-19T22:28:34.163 回答