java - Java 省时的稀疏一维数组（双精度）

Question

我需要一个高效的 Java 结构来操作非常稀疏的双精度向量：基本的读/写操作。我在 HashMap 中实现了它，但是访问速度太慢了。我应该使用其他数据结构吗？你推荐任何免费的图书馆吗？

寻找一些和平的建议:)

非常感谢，

玛丽

Answer 1

HashMap是要走的路。它不应该很慢。通过分析器运行您的代码以查看所有时间都在哪里，然后进行相应的优化。如果您需要优化代码的提示，请在此处发布示例，以便我们帮助解决特定问题。

[编辑] 根据索引的大小，您可以使用一种技术Integer.valueOf(int)来缓存对象以进行装箱。但这仅在您创建大量地图并且索引处于有限范围内时才有效。

IntHashMap或者您可以从commons-lang尝试。使用起来有点困难（它是私有包），但您可以复制代码。

最后，您可以使用自己的基于 int 的 HashMap 实现，并针对您的案例进行优化的值查找。

Answer 2

你的数据集有多大？比 Integer.MAX_VALUE 大得多？问题是 HashSet 由数组支持。碰撞会降低性能。也许不是hashmap的机制太慢，而是你有多次冲突的事实。也许如果您首先（例如）使用另一个散列函数对数据进行分区，然后将每个数据分区存储在它自己的散列图中，那么您会有更多的运气。

Answer 3

您可以从我的 Hapax 项目中复制粘贴稀疏向量：ch.akuhn.matrix.SparseVector

PS：对于所有其他不理解为什么使用地图太慢的答案和评论。它很慢，因为地图将所有索引都装箱了 Integer 对象！

这里介绍的稀疏向量对于读取访问和附加值来说是快速的，但对于放置随机索引却不是。它最适合您首先创建 sprase 向量但将值按增加索引的顺序放置，然后主要使用地图进行读取的情况。

稀疏向量类中的重要方法是

// ...

public class SparseVector {

    /*default*/ int[] keys;
    /*default*/ int size, used;
    /*default*/ double[] values;

    public SparseVector(int size, int capacity) {
        assert size >= 0;
        assert capacity >= 0;
        this.size = size;
        this.keys = new int[capacity];
        this.values = new double[capacity];
    }

    public double get(int key) {
        if (key < 0 || key >= size) throw new IndexOutOfBoundsException(Integer.toString(key));
        int spot = Arrays.binarySearch(keys, 0, used, key);
        return spot < 0 ? 0 : values[spot];
    }

    public boolean isUsed(int key) {
        return 0 <= Arrays.binarySearch(keys, 0, used, key);
    }

    public double put(int key, double value) {
        if (key < 0 || key >= size) throw new IndexOutOfBoundsException(Integer.toString(key));
        int spot = Arrays.binarySearch(keys, 0, used, key);
        if (spot >= 0) return values[spot] = (float) value;
        else return update(-1 - spot, key, value);
    }

    public void resizeTo(int newSize) {
        if (newSize < this.size) throw new UnsupportedOperationException();
        this.size = newSize;
    }

    public int size() {
        return size;
    }

    private double update(int spot, int key, double value) {
        // grow if reaching end of capacity
        if (used == keys.length) {
            int capacity = (keys.length * 3) / 2 + 1;
            keys = Arrays.copyOf(keys, capacity);
            values = Arrays.copyOf(values, capacity);
        }
        // shift values if not appending
        if (spot < used) {
            System.arraycopy(keys, spot, keys, spot + 1, used - spot);
            System.arraycopy(values, spot, values, spot + 1, used - spot);
        }
        used++;
        keys[spot] = key;
        return values[spot] = (float) value;
    }

    public int used() {
        return used;
    }

    public void trim() {
        keys = Arrays.copyOf(keys, used);
        values = Arrays.copyOf(values, used);
    }

}

Answer 4

对于一维稀疏数组，映射通常是要走的路。如果它是多维的，你只需要使用一个库。

如果您比较地图和数组之间的访问时间，

   map.get(99);
   array[99];

地图会慢得多。任何图书馆都会有同样的问题。

是那个稀疏数组吗？你用时间换空间。