Как работать с большими массивами / списками - PullRequest
Новая
       172

Как работать с большими массивами / списками

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

в последнее время я пытаюсь выполнять задачи по кодированию.Я часто делаю задачу с массивом в качестве входных данных, где вам нужно решить такую ​​проблему, как: найти наименьшее положительное целое число, которое не встречается в массиве и т. Д. Я могу легко справиться с небольшим массивом, но когда я собираю код и получаю резюме с тестами, включаямассивы, имеющие> 1000 (или 10 000) элементов, у меня почти всегда возникает ошибка времени выполнения.

Так что вы можете сказать мне, как работать с большими массивами?

В основном я пытаюсь преобразовать массив в список следующим образом: 

List<Integer> arrayList = Arrays.stream(A)
                .boxed()
                .filter(c -> (c > -1001 && c < 1001)) // predicate
                .collect(Collectors.toList());

Иногда я использую фильтр, напримерВы видите, иногда я использую отличный / сортировать, если мне нужно.Но все же у меня много ошибок во время выполнения.

Я буду признателен за несколько советов, как с этим справиться.

@ cricket_007 

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

class Solution {
    public int solution(int[] A) {

        List<Integer> integerList = Arrays.stream(A)
                .boxed()
                .collect(Collectors.toList());

        if ((integerList.size() == 2 && integerList.get(0) == integerList.get(1)) || A.length == 1) {
            return 0;
        }
        if ((integerList.size() == 2 && integerList.get(0) != integerList.get(1))) {
            return Math.abs(integerList.get(0) - integerList.get(1));
        }

        int sublistSum1;
        int sublistSum2;

        List<Integer> scoreList = new ArrayList<>();

        Integer temp;
        for (int i = 1; i < integerList.size(); i++) {
            sublistSum1 = integerList.subList(0, i).stream().mapToInt(n -> n).sum();
            sublistSum2 = integerList.subList(i, integerList.size()).stream().mapToInt(n -> n).sum();
            temp = Math.abs(sublistSum1 - sublistSum2);
            scoreList.add(temp);
        }
        return scoreList.stream()
                .min(Integer::compareTo)
                .get();
    }
}

Так что этоМое решение этой задачи: https://app.codility.com/programmers/lessons/3-time_complexity/tape_equilibrium/

Я получил 100% правильности, но 0% производительности, потому что: "ОШИБКА ВРЕМЕНИ. Убита. Достигнут жесткий предел: 6.000 сек."Все 6 тестов производительности возвращают эту ошибку.

Что я могу сделать в этом случае?

Следующая задача, следующая проблема с большим массивом.https://app.codility.com/programmers/lessons/5-prefix_sums/passing_cars/

Мой код: 

import java.util.Arrays;

class Solution {
    public int solution(int[] A) {

        if (Arrays.stream(A).distinct().count() == 1) {
            return 0;
        }
        int score = 0;

        for (int i = 0; i < A.length; i++) {
            if (A[i] == 0) {
                for (int j = 1; j < A.length; j++) {
                    if (A[j] == 1 && j > i) {
                        score++;
                    }
                }
            }
        }
        if (score < 1_000_001) {
            return score;
        }
        return -1;
    }
}

Таким образом, в основном, когда я пытался решить эту задачу с помощью вложенного цикла, я получал O (N ^ 2) алгоритм сложности.Как это решить?

1 Ответ

2 голосов
/ 27 сентября 2019

Прежде всего, вы должны спросить себя, действительно ли вам нужен List<Integer>, для которого требуется бокс, или для вашей задачи будет достаточно массива int[].

Итак 

int[] array = Arrays.stream(A)
    .filter(c -> (c > -1001 && c < 1001))
    .toArray();

будет гораздо эффективнее.Но если вам действительно нужен List<Integer>, вы все равно должны сделать как можно больше работы перед упаковкой значений, то есть 

List<Integer> arrayList = Arrays.stream(A)
    .filter(c -> (c > -1001 && c < 1001))
    .boxed()
    .collect(Collectors.toList());

Таким образом, только соответствующие значения intв штучной упаковке, а не все из них.Это оптимизация, которую реализация Stream не может выполнить сама, так как при использовании .boxed().filter(c -> (c > -1001 && c < 1001)) вы вызываете filter для Stream<Integer>, передавая Predicate<Integer> вместо IntPredicate, и реализация не имеет выборано для передачи Integer этому коду.

Аналогичные вещи применимы к sort;это намного эффективнее, когда применяется к данным примитивного типа, а не к Integer объектам.Аналогичный потенциал есть у distinct, но, на самом деле, это не материализуется с текущей реализацией.

Тогда вам придется самим реализовывать более совершенные алгоритмы, в этом и заключается проблема.

Одним из решений для поиска наименьшего положительного целого числа, не содержащегося в массиве, было бы 

int first = Arrays.stream(A)
    .filter(i -> i >= 0)
    .collect(BitSet::new, BitSet::set, BitSet::or)
    .nextClearBit(0);

Если «положительный» означает «больше нуля», вам придется использовать i > 0 и nextClearBit(1).Это решение также будет поддерживать параллельную обработку.

Изучение существующих алгоритмов и структур данных, предлагаемых Java API , является необходимостью для таких задач.А также знание того, что действительно не существует и должно быть реализовано вами самостоятельно.

...