5

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

List<Map<String, Object>> tableData;

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

是否有有效的数据结构来存储它？Guava 提供了一个Table集合，但这似乎不符合要求。我正在考虑创建一个界面，例如：

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

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

谢谢

4

4 回答 4

4

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

假设平均不超过 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[].

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

假设许多行共享相同的列集，您可以columnNameToIndexMap在每一行中存储。

于 2013-10-28T19:45:45.160 回答
4

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

我比较的实现如下：

  1. 基于a的实现Map<String,List<Object>>使用aHashMap和ArrayLists；
  2. 基于 a List<Object[]>using an 的实现ArrayList；
  3. 番石榴的HashBasedTable<Integer,String,Object>;
  4. 番石榴的ArrayTable<Integer,String,Object>;

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

但是，让我们来看看结果。有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。

谢谢

于 2013-10-29T13:59:59.883 回答
0

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

但是，如果您仍想坚持当前的方法，为什么不能对数据进行规范化，以便可以通过 'Null' 来表示缺少的字段。因此，当您读取数据并创建地图时，为什么不为缺少的字段添加“null”？这样你至少不需要像 hashmap 这样的键值数据结构，你可以只用 liseList<List<Object>>

于 2013-10-28T18:26:21.843 回答
0

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

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

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;
于 2013-10-28T17:04:28.870 回答