地图列表:高效实现

我有创建和使用集合的代码，例如：

List<Map<String, Object>> tableData;

此映射列表填充了 n 个映射，每个映射表示数据库中的一行。每一行都表示为字段名称和与字段对应的对象之间的映射（在这种情况下，类型无关紧要）。某些字段可能丢失。字段数 m 总是远小于行数（n ≈ 10000 × m）。我需要多次重用同一个集合来读取所有行，所以我不能只使用某种惰性迭代器。

是否有有效的数据结构来存储它？番石榴提供了一个Table系列，但这似乎不符合要求。我正在考虑创建一个接口，例如：

interface TableData{
  int size();
  Map<String, Object> get(int i);
  // ... (interators, etc.)
}

然后创建一个使用一个Map<String,List<Object>>的实现，以便我只实例化 m 列表而不是 n 个映射，并且仅在需要时动态创建映射，但我想知道是否有更通用的数据结构。

谢谢

首先，请确保您确实需要优化。

假设平均不超过 50% 的列缺失，List<Object[]>是明显的赢家：

class TableDataImpl implements TableData {
    private List<Object[]> data;
    private Map<String, Integer> columnNameToIndexMap;
    public Map<String, Object> get(int i) {
        return new ArrayMap(data.get(i));
    }
    private class ArrayMap implements Map<String, Object> {
        private Object[] row;
        ArrayMap(Object[] row) {
            this.row = row;
        }
        public Object get(String key) {
            Integer index = columnNameToIndexMap.get(key);
            if (index==null) return null;
            return row[index];
       }
       // all the other Map stuff... a lot of code!
    }
}

我不想说它很简单，所以确保你真的需要优化。

否则，假设平均不超过 95% 的列缺失，应该做一个稍微复杂的结构：对于每一行，使用自产BitSet （ long[] ）来存储存在哪些列。这样，您只会浪费一个位，而不是Object[]中的整个条目（32 或 64 位）。

这甚至更加复杂，因此请确保您确实需要优化。

假设许多行共享同一组列，则可以将columnNameToIndexMap存储在每行中。

我运行了一些测试（无论如何都不是决定性的，但非常具有指示性）来确定不同List<Map<String, Object>>实现的内存占用。基线是Java的ArrayList<>，元素是Guava ImmutableMap的实例。

我比较的实现如下：

基于使用HashMap和ArrayList的Map<String,List<Object>>实施;
基于使用ArrayList的List<Object[]>实现;
番石榴的HashBasedTable<Integer,String,Object> ;
番石榴的ArrayTable<Integer,String,Object> ;

我的测试包括生成 n 个随机行，每个行都有 m 列和一个 k 的"填充因子"，其中填充因子定义为每行包含所有列的值的概率。为简单起见，这些值是使用 Apache Commons RandomStringUtils 生成的长度为 l 的随机字符串。

但是，让我们来看看结果。当 n = 200000， m = 50， l = 10 和 k in （1.0， 7.5， 0.5）时，我得到了以下内存占用量作为基线的百分比：

    | k = 1.0  | k = 0.75 | k = 0.5  |
----------------------------------------
1.  |     71 % |     71 % |     71 % |
2.  |     71 % |     72 % |     73 % |
3.  |    111 % |    107 % |    109 % |
4.  |     71 % |     73 % |     76 % |

我尝试将 n 减少到 20000，结果大致相同。

我发现上面的结果很有趣。首先，看起来在基线的70%之外没有太多的改进空间。其次，我惊喜地发现，高效的Guava的ArrayTable与这个问题中提出的两个实现一样好。我会继续挖掘更多，但我倾向于解决方案 1。

谢谢

好吧，如果将所有表数据一次放在内存中很重要，那么存储数据结构的方向（作为地图列表或列表映射）不会有太大区别。地图列表显然更直观，所以我会保留它。

如果您担心对象创建和清理的效率，我建议您使用对象池。以下是它如何工作的基本概念：

public class TableRowPool {
    private static final int INITIAL_CAPACITY = 10000;
    private Queue<Map<String, Object>> mapObjects;
    public TableRowPool() {
        mapObjects = new LinkedList<Map<String, Object>>();
        for(int i = 0; i < INITIAL_CAPACITY; i++) {
            mapObjects.add(new HashMap<String, Object>());
        }
    }
    public Map<String, Object> getTableRowObject() {
        if(mapObjects.size() == 0) {
            mapObjects.add(new HashMap<String, Object>());
        }
        return mapObjects.remove();
    }
    public void returnTableRowObject(Map<String, Object> obj) {
        mapObjects.add(obj);
    }
}

LinkedList 作为队列性能良好，因此对象检索速度很快。如果您希望它动态增长，它可以快速附加新对象。但是，您可能需要更改数据结构，具体取决于它是否需要线程安全。

要使用对象池，您需要执行以下操作：

//Load data
while((row = getResultSetRow()) != null) {
    Map<String, Object> rowObj = tableRowPool.getTableRowObject();
    //Fill in data
    myRows.add(rowObj);
}
//... Do all your business logic ...
//Cleanup
for(Map<String, Object> rowObj : myRows) {
    tableRowPool.returnTableRowObject(rowObj);
}
myRows = null;

如果我有这么大的数据，我担心我会得到 OOM，那么与其找到一个最佳的数据结构来保存这些数据，我会寻找如何使用 SIMD 并行性或类似 Map-Reduce 的东西。无论您如何优化数据结构，始终会耗尽内存空间。例如，如果您确实找到了在特定机器配置中工作的最佳数据结构，它可能仍然无法在RAM稍少的机器中工作。

但是，如果您仍然想坚持当前的方法，为什么不能规范化数据，以便可以用："Null"表示缺少的字段。因此，当您读取数据并创建地图时，为什么不为缺少的字段添加"null"呢？这样你至少不必像hashmap这样的键值数据结构，你可以List<List<Object>>

相关内容

最新更新

热门标签：