Сравнение двух отсортированных массивов int - PullRequest
Новая
       28

Сравнение двух отсортированных массивов int

12 голосов
/ 21 января 2011

У меня миллионы int-массивов фиксированного размера (100).Каждый массив отсортирован и имеет уникальные элементы.Для каждого массива я хочу найти все массивы, которые имеют 70% общих элементов.Сейчас я получаю около 1 миллиона сравнений (используя Arrays.binarySearch ()) в секунду, что для нас слишком медленно

Кто-нибудь может порекомендовать лучший алгоритм поиска?

Ответы [ 3 ]

3 голосов
/ 21 января 2011

Примерно так должно работать (при условии, что массивы отсортированы и содержат уникальные элементы): 

public static boolean atLeastNMatchingElements(final int n,
    final int[] arr1,
    final int[] arr2){

    /* check assumptions */
    assert (arr1.length == arr2.length);

    final int arrLength = arr2.length;

    { /* optimization */
        final int maxOffset = Math.max(arrLength - n, 0);
        if(arr1[maxOffset] < arr2[0] || arr2[maxOffset] < arr1[0]){
            return false;
        }
    }

    int arr2Offset = 0;
    int matches = 0;

    /* declare variables only once, outside loop */
    int compResult; int candidate;

    for(int i = 0; i < arrLength; i++){
        candidate = arr1[i];
        while(arr2Offset < arrLength - 1){
            compResult = arr2[arr2Offset] - candidate;
            if(compResult > 0){
                break;
            } else{
                arr2Offset++;
                if(compResult == 0){
                    matches++;
                    break;
                }
            }
        }
        if(matches == n){
            return true;
        }
        /* optimization */
        else if(matches < n - (arrLength - arr2Offset)){
            return false;
        }
    }
    return false;
}

Пример использования: 

public static void main(final String[] args){
    final int[] arr1 = new int[100];
    final int[] arr2 = new int[100];
    int x = 0, y = 0;
    for(int i = 0; i < 100; i++){
        if(i % 10 == 0){
            x++;
        }
        if(i % 12 == 0){
            y++;
        }
        arr1[i] = x;
        arr2[i] = y;
        x++;
        y++;
    }
    System.out.println(atLeastNMatchingElements(70, arr1, arr2));
    System.out.println(atLeastNMatchingElements(95, arr1, arr2));
}

Вывод:

true
false

Преждевременная оптимизация ™

Я попытался оптимизировать приведенный выше код.Пожалуйста, проверьте, заметно ли изменились блоки кода, помеченные как 

/* optimization */

.После оптимизации я бы реорганизовал код, чтобы свести его к одному или двум операторам возврата.

3 голосов
/ 21 января 2011

Есть две быстрые оптимизации, которые вы можете сделать.

Если начальный элемент массива A больше, чем конечный элемент B, у них обычно не может быть общих элементов.

Они - другойвещь, похожая на неравенство треугольника: 

f(B,C) <= 100 - |f(A,B)-f(A,C)|

Причина этого заключается в том, что (при условии f(A,B) > f(A,C)) есть как минимум f(A,B) - f(A,C) элементов, которые находятся как в A, так и в B, но не в C. Это означает, чтоони не могут быть общими элементами B и C.

3 голосов
/ 21 января 2011

Вы можете попробовать сортировку слиянием, игнорируя дубликаты. Это операция O (n) для отсортированных массивов. Если два массива имеют 70% общих элементов, результирующая коллекция будет иметь 130 или менее уникальных целых. В вашем случае вам не нужен результат, поэтому вы можете просто посчитать количество уникальных записей и остановиться, как только достигнете 131 или конца обоих массивов.

EDIT (2) Следующий код может выполнить ~ 176 миллиардов сравнений за 47 секунд при использовании 4 ядер. Создание многопоточного кода с 4 курсами было всего на 70% быстрее.

Использование BitSet работает, только если диапазон значений int довольно мал. В противном случае вы должны сравнить int [] (я оставил код, если вам это нужно)

Проведено 176 467 034 428 сравнений за 47,712 секунд и найдено 444 888 совпадений 

public static void main(String... args) throws InterruptedException {
    int length = 100;
    int[][] ints = generateArrays(50000, length);
    final BitSet[] bitSets = new BitSet[ints.length];
    for(int i=0;i<ints.length;i++) {
        int[] ia = ints[i];
        BitSet bs = new BitSet(ia[ia.length-1]);
        for (int i1 : ia)
            bs.set(i1);
        bitSets[i] = bs;
    }

    final AtomicInteger matches = new AtomicInteger();
    final AtomicLong comparisons = new AtomicLong();
    int nThreads = Runtime.getRuntime().availableProcessors();
    ExecutorService executorService = Executors.newFixedThreadPool(nThreads);

    long start = System.nanoTime();
    for (int i = 0; i < bitSets.length - 1; i++) {
        final int finalI = i;
        executorService.submit(new Runnable() {
            public void run() {
                for (int j = finalI + 1; j < bitSets.length; j++) {
                    int compare = compare(bitSets[finalI], bitSets[j]);
                    if (compare <= 130)
                        matches.incrementAndGet();
                    comparisons.addAndGet(compare);
                }
            }
        });
    }
    executorService.shutdown();
    executorService.awaitTermination(1, TimeUnit.HOURS);
    long time = System.nanoTime() - start;
    System.out.printf("Peformed %,d comparisons in %.3f seconds and found %,d matches %n",comparisons.longValue(),time/1e9, matches.intValue());
}

private static int[][] generateArrays(int count, int length) {
    List<Integer> rawValues = new ArrayList<Integer>(170);
    for (int i = 0; i < 170; i++)
        rawValues.add(i);

    int[][] ints = new int[count][length];
    Random rand = new Random(1);
    for (int[] ia : ints) {
        Collections.shuffle(rawValues, rand);
        for (int i = 0; i < ia.length; i++)
            ia[i] = (int) (int) rawValues.get(i);
        Arrays.sort(ia);
    }
    return ints;
}

private static int compare(int[] ia, int[] ja) {
    int count = 0;
    int i=0,j=0;
    while(i<ia.length && j<ja.length) {
        int iv = ia[i];
        int jv = ja[j];
        if (iv < jv) {
            i++;
        } else if (iv > jv) {
            j++;
        } else {
            count++; // duplicate
            i++;
            j++;
        }
    }
    return ia.length + ja.length - count;
}
private static int compare(BitSet ia, BitSet ja) {
    BitSet both = new BitSet(Math.max(ia.length(), ja.length()));
    both.or(ia);
    both.or(ja);
    return both.cardinality();
}
...