Как эффективно хранить набор кортежей / пар в Java - PullRequest
Новая
       17

Как эффективно хранить набор кортежей / пар в Java

0 голосов
/ 27 сентября 2018

Мне нужно выполнить проверку, если комбинация длинного значения и целочисленного значения уже была замечена ранее в критически важной для приложения части приложения.Оба значения могут стать довольно большими, по крайней мере, long будет использовать больше значений MAX_INT в некоторых случаях.

В настоящее время у меня есть очень простая реализация, использующая Set<Pair<Integer, Long>>, однако это потребует слишком большого количества выделений, потому что дажекогда объект уже находится в наборе, что-то вроде seen.add(Pair.of(i, l)) для добавления / проверки существования выделит пару для каждого вызова.

Есть ли лучший способ в Java (без таких библиотек, как Guava, Trove или Apache Commons), чтобы сделать эту проверку с минимальными распределениями и с хорошим O(?)?

Два целых было бы легко, потому что я мог бы объединить их в один длинный в наборе, но здесь нельзя избежать длинного.

Есть предложения?

Ответы [ 3 ]

0 голосов
/ 27 сентября 2018

Как насчет 

class Pair {
    int v1;
    long v2;

    @Override
    public boolean equals(Object o) {
        return v1 == ((Pair) o).v1 && v2 == ((Pair) o).v2;
    }

    @Override
    public int hashCode() {
        return 31 * (31 + Integer.hashCode(v1)) + Long.hashCode(v2);
    }
}

class Store {
    // initial capacity should be tweaked
    private static final Set<Pair> store = new HashSet<>(100*1024);
    private static final ThreadLocal<Pair> threadPairUsedForContains = new ThreadLocal<>();

    void init() { // each thread has to call init() first
        threadPairUsedForContains.set(new Pair());
    }

    boolean contains(int v1, long v2) { // zero allocation contains()
        Pair pair = threadPairUsedForContains.get();
        pair.v1 = v1;
        pair.v2 = v2;
        return store.contains(pair);
    }

    void add(int v1, long v2) {
        Pair pair = new Pair();
        pair.v1 = v1;
        pair.v2 = v2;
        store.add(pair);
    }
}
0 голосов
/ 28 сентября 2018

Вот две возможности.

В обоих следующих предложениях одна вещь - хранить несколько пар вместе как тройные int с в int[].Первый int будет int, а следующие два int будут верхней и нижней половиной long.

Если вы не возражаете против 33% -ного дополнительного недостатка пространстваВ обмен на преимущество в скорости адресации вы могли бы вместо этого использовать long[] и хранить int и long в отдельных индексах.

Вы никогда не вызовете метод equals.Вы бы просто сравнили три int с тремя другими int, что было бы очень быстро.Вы бы никогда не вызвали compareTo метод.Вы просто сделали бы пользовательское лексикографическое сравнение трех int с, которое было бы очень быстрым.

B * tree

Если использование памяти является максимальнымВы можете создать дерево B *, используя int[][] или ArrayList<int[]>.B * деревья относительно быстрые и достаточно компактные.

Существуют и другие типы B-деревьев, которые могут быть более подходящими для вашего конкретного случая использования.

Пользовательский хешset

Вы также можете реализовать пользовательский хэш-набор с пользовательской быстро вычисляемой хэш-функцией (возможно, XOR для int и верхней и нижней половин long вместе, что будет очень быстро)вместо того, чтобы полагаться на метод hashCode.

Вы должны выяснить, как реализовать сегменты int[] для наилучшего соответствия производительности вашего приложения.Например, как вы хотите преобразовать свой хэш-код в номер корзины?Вы хотите перегруппировать все, когда корзины начинают получать слишком много элементов?И так далее.

0 голосов
/ 27 сентября 2018

Как насчет создания класса, который вместо этого содержит два примитива?В 64-битной JVM вы бы сбросили как минимум 24 bytes только для заголовков Integer и Long.

В этих условиях вам нужна функция сопряжения илисгенерировать уникальный номер из 2 чисел.На этой странице Википедии есть очень хороший (и простой) пример одной такой возможности.

...