Как избежать двумерного массива в обработке данных?

#массивы #алгоритм #циклы #динамические_массивы

Подскажите, пожалуйста, как эффективнее решить следующее задание: некий офисный клерк
клеит на свою стеклянную дверь стикеры различных размеров. В итоге изнутри офиса и
снаружи получается разная картина из видных с одной или с другой стороны стикеров (они
могут торчать частично друг из под друга, могут быть видны полностью, а могут и вовсе
исчезнуть под всеми остальными). На вход даются следующие данные: ширина этой стеклянной
двери, количество стикеров и данные каждого стикера в следующем формате: расстояние
от левого края двери (дверь это по сути координатная плоскость с началом в (0,0)),
высота и ширина. Пример:  


  8 5
  2 3 2
  6 2 2
  3 3 2
  3 2 2
  0 2 3  


Дверь шириной 8, 5 стикеров, у первого расстояние от левого края двери 2, высота
3 и ширина 2, у остальных аналогично. На выходе необходимо получить 3 числа: количество
стикеров, видных с обеих сторон стеклянной двери, количество стикеров, видных лишь
с одной стороны (либо изнутри, либо снаружи) и количество стикеров, не видных вовсе.
Для выше приведенного примера это будет  


  4 1 0


Визуализация примера:


Я делаю это следующим образом: создаю 2 двумерных массива (дверь спереди и дверь
сзади), заполняю их нулями и "рисую" каждый стикер (занимаю место в массиве его порядковым
номером) в соответствии с актуальным положением всех стикеров, в конце прохожу массив
структур стикеров и смотрю, у кого из них есть место на двери и сколько с каждой стороны. Код:

#include 
#include 

unsigned int doorWidth = 0;
unsigned int papers = 0; // number of notes
int **mapIndoor; // door with notes as a map (inside)
int **mapOutdoor; // door with notes as a map (outside)

typedef struct {
    unsigned int xLeft;
    unsigned int height;
    unsigned int width;
    unsigned int indoor;
    unsigned int outdoor;
} note_t;

note_t *allNotes; // array of notes' data

int main() {

    if((scanf("%d %d", &doorWidth, &papers)) == 0) {
        fprintf(stderr, "Error\n");
        return -1;
    }

    allNotes = (note_t*)malloc(papers*sizeof(note_t));

    int maxHeight = 1;
    mapIndoor = (int**)malloc(maxHeight*sizeof(int*));
    mapOutdoor = (int**)malloc(maxHeight*sizeof(int*));
    for (int i = 0; i < maxHeight; i++) {
        mapIndoor[i] =(int*)calloc(doorWidth, sizeof(int));
        mapOutdoor[i] =(int*)calloc(doorWidth, sizeof(int));
    }

    for (int i = 0; i < papers; i++) {
        scanf("%d ", &allNotes[i].xLeft);
        scanf("%d ", &allNotes[i].height);
        scanf("%d ", &allNotes[i].width);
        allNotes[i].indoor = 0;
        allNotes[i].outdoor = 0;
        /*-------dynamic allocation---------*/
        if (allNotes[i].height > maxHeight) {
            int prevMax = maxHeight;
            maxHeight = allNotes[i].height;
            mapIndoor = (int**)realloc(mapIndoor, maxHeight*sizeof(int*));
            mapOutdoor = (int**)realloc(mapOutdoor, maxHeight*sizeof(int*));
            for (int k = prevMax; k < maxHeight; k++) {
                mapIndoor[k] = (int*)calloc(doorWidth, sizeof(int));
                mapOutdoor[k] = (int*)calloc(doorWidth, sizeof(int));
            }
        }
        /*-----------------------------------*/
        for (int y = 0; y < allNotes[i].height; y++) {
            for (int x = allNotes[i].xLeft; x < allNotes[i].xLeft + allNotes[i].width;
x++) {
                int prevIndoorNumber = mapIndoor[y][x];
                mapIndoor[y][x] = i+1;
                allNotes[i].indoor++;
                if (prevIndoorNumber > 0)
                    allNotes[prevIndoorNumber-1].indoor--;
                if (mapOutdoor[y][x] == 0) {
                    mapOutdoor[y][x] = i+1;
                    allNotes[i].outdoor++;
                }
            }
        }
    }

    unsigned int seenEverywhere = 0;
    unsigned int seenOnlyOnce = 0;
    unsigned int notSeen = 0;

    for (int i = 0; i < papers; i++) {
        if ((allNotes[i].indoor > 0) && (allNotes[i].outdoor > 0))
            seenEverywhere++;
        else if ((allNotes[i].indoor == 0) && (allNotes[i].outdoor == 0))
            notSeen++;
        else if (((allNotes[i].indoor > 0) && (allNotes[i].outdoor == 0)) ||
            ((allNotes[i].indoor == 0) && (allNotes[i].outdoor > 0)))
            seenOnlyOnce++;
    }

    printf("%d %d %d\n", seenEverywhere, seenOnlyOnce, notSeen);

    free(allNotes);

    for (int i = 0; i < maxHeight; i++) {
        free(mapIndoor[i]);
        free(mapOutdoor[i]);
    }
    free(mapIndoor);
    free(mapOutdoor);

    return 0;

}


Массивы  я изменяю динамически, потому что изначально неизвестна высота самого большого
стикера. Это решение работает, но оно жутко неэффективно, программа линейно зависит
от количества входных данных, и в какой то момент она не справляется с ними (например,
10 000 стикеров с шириной двери 250 000). Я понимаю, что много времени у меня занимает
обработка двумерных массивов и динамическая аллокация памяти под них, однако не могу
придумать, как их избежать. Подскажите, пожалуйста :)
    

Ответы

Ответ 1

если вы заметили что динамическая аллокация у вас занимает не малый ресурс, почему
не сделать это в рамках отдельного прохода?

То есть прочли файл в allNotes, и в этом же цикле только наметили размер дверей. 

вторым раундом по papers уже работаете с двумерными массивами - сразу выделяете нужное
пространство и размечаете.

на самом деле по количеству операций это ничего не стоит, это просто +10000 инкрементов,
в остальном без разницы сделаете вы 2 операции в одном цикле или по одной операции
в двух циклах.

Но по поводу отказа от двумерного массива надо еще подумать...

Один из вариантов развития алгоритма больше направлен на распределенное вычисление...
Так как у вас все стикеры привлекаются только к низу хочется вместо 2 мерного массива
хранить массив высот, на каждом делении ширины. И по врожденной формуле пересечения
прямоугольников вычислять какие стикеры видны на данном сечении(по сути результат это
массив номеров стикеров). Потом эти результаты можно собрать чтобы убрать дубликаты.
По сути это как раз ложиться на map reduce. То есть задачу можно маштабировать. Осталось
только более детально проработать алгоритм вычисления наложения по формуле на этапе
map. Хотя при имеющихся возможностьях (типа многоядерности) сам факт возможности маштабирования
уже может существенно повысить эффективность потребеления ресурсов для поставленной
задачи, тем самым уменьшив время обработки до приемлемых результатов даже без существенного
изменения самого подхода то есть будет не один двумерный массив, а несколько одномерных,
на каждый поток свой и каждый по нему будет возвращать не кол-во, а номера, по которым
уже достаточно просто посчитать количество, когда все потоки закончат свою работу


Ответ 2

Могу предложить решение на джаве... Рефакторинг на вашей совести, потому как написано
на быструю руку. Собственно, все ваши стикеры клеятся исключительно снизу вверх. Это
значит, что нам по сути не нужно отслеживать целую поверхность двери. Почему? Представьте,
что у вас есть стикер высотой 3, второй стикер при этом высотой 2. Даже если второй
стикер занимает всю длину двери, то третий все равно будет виден, т.к.он просто выше.
Это значит, что для того, чтобы отследить видимость одного стикера с одной стороны
двери нам достаточно иметь одномерный массив , который будет обозначать перекрытие
самого верхнего ряда. длина массива совпадет с шириной стикера. Т.е. для стикера размером
2(ширина) на 3(высота) при площади в условных 6 квадратов (2*3) нам нужно отслеживать
лишь верхних 2 квадрата, остальные 4 не имеют никакого значения. Посему в алгоритме,
который отслеживает всю поверхность двери, необходимости нет от слова совсем. Она больше
не важна. Более того, нам даже не нужно следит за всей поверхностью конкретного стикера.
Каждый стикер - экземпляр класса и он сам знает, как расчитать видимость и с какой
стороны он виден. ООП рулит)) Мало того, каждый раз, когда у стикера вызывается метод,
который позволяет вычислить, перекрывает ли его второй стикер, все вычисления происходят
поэтапно. Для начала сравнивается положение относительно края и ширина на предмет того,
пересекаются ли стикеры по ширине. Если первый результат показал, что стикеры не перекрывают
друг друга, то второй и третий шаги не выполняются. Нет смысла высчитывать полное перекрытие
или частичное перекрытие, если уже установлено, что стикеры не соприкасаются. Второй
шаг - вычисление полного перекрытия. Здесь учитывается еще и высота. И последний -
частичное перекрытие выполняется только после первых двух (если установлено, что это
именно частичное перекрытие). Только последний метод работает с массивом. Все остальные
выполняют достаточно тривиальные математические вычисления, следовательно, выполняются
очень быстро.  А до последнего очередь доходит далеко не всегда.  Одновременно у нас
есть энумератор, описывающий 3 ситуации - полное перекрытие, частичное перекрытие стикеры
не соприкасаются. Этот флаг используется, чтобы вычислить финальный результат, не перебирая
все вложенные массивы. Кроме того, если первое сравнение стикеров установило, что 2
стикер полностью перекрыл первый, то выставляется флаг , что стикер перекрыт и все
дальнейшие вычисления не производятся в силу их бессмысленности (нам все равно , что
стикер перекрыли много раз). Аналогичная ситуация , если путем многократного частичного
перекрытия стикер закрывается полностью. Флаг о полном перекрытии также высталяется
и дальнейшие действия не производятся.

import static doorsticker.OverlayEnum.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Sticker {

    private OverlayEnum overlayFirstSide = NOT_OVERLAY;
    private OverlayEnum overlaySecondSide = NOT_OVERLAY;

    private final int leftMargin, height, width;
    private final boolean []overlaying1;
    private final boolean []overlaying2;

    public Sticker(int leftMargin, int height, int width) {
        this.leftMargin = leftMargin;
        this.width = width;
        this.height = height;
        this.overlaying1 = new boolean[width];
        this.overlaying2 = new boolean[width];
    }

    private int[]createResult(){
        int[] result = new int[3];
        //all overlay for 2 sides
        if (overlayFirstSide == ALL_OVERLAY && overlaySecondSide == ALL_OVERLAY) {
            result[2]=1; 
            return result; 
        }
        //all overlay for 1 sides
        if ((overlayFirstSide==ALL_OVERLAY && overlaySecondSide!=ALL_OVERLAY) || 
                (overlaySecondSide==ALL_OVERLAY && overlayFirstSide!=ALL_OVERLAY)) 
            result[1]=1;
        // not overlay
        else result[0]=1;        
        return result;
    }

    private void compareSticker(final Sticker sticker, boolean isFirstSideComparing) {
        if (overlayFirstSide==ALL_OVERLAY && isFirstSideComparing) return;
        if (overlaySecondSide==ALL_OVERLAY && !isFirstSideComparing) return;
        boolean notOverlay = notOverlay(sticker);
        boolean fullOverlay = fullOverlay(sticker);        
        if (fullOverlay && isFirstSideComparing) overlayFirstSide=ALL_OVERLAY;
        if (fullOverlay && !isFirstSideComparing) overlaySecondSide=ALL_OVERLAY;
        if (!notOverlay && !fullOverlay) partOverlay(sticker,isFirstSideComparing);
    }


    private boolean notOverlay (final Sticker sticker) {
        int leftOverlay = leftMargin-sticker.getLeftMargin()-sticker.getWidth();
        int rightOverlay = sticker.getLeftMargin()-leftMargin-width;
        return leftOverlay>=0 || rightOverlay>=0;
    }
    private boolean fullOverlay (final Sticker sticker) {
        return leftMargin>=sticker.getLeftMargin() && 
                leftMargin+width<=sticker.getLeftMargin()+sticker.getWidth() &&
                height<=sticker.getHeight();
    }
    private void partOverlay (final Sticker sticker, boolean isFirstSideComparing) {
        if (height>sticker.getHeight()) return;
        int startOverlay = Math.max(0,sticker.getLeftMargin() - leftMargin);
        int endOverlay = width-Math.max(0,((leftMargin+width)-
                (sticker.getLeftMargin()+sticker.getWidth())));        
        if (isFirstSideComparing) overlayFirstSide=partOverlay(overlaying1, startOverlay,
endOverlay);
        else overlaySecondSide=partOverlay(overlaying2, startOverlay, endOverlay);
    }
    private OverlayEnum partOverlay(boolean [] overlaying,
            int startOverlay, int endOverlay){
        boolean chackAllOverlay = true;
        for (int i = 0; i < overlaying.length; i++) {
            if (i>=startOverlay && i stickers){

    int[] result = new int[3];

    for (int i = 0; i < stickers.size(); i++) {
        for (int j = i + 1; j < stickers.size(); j++) {
            stickers.get(i).compareSticker(stickers.get(j), true);
            stickers.get(j).compareSticker(stickers.get(i), false);
        }

    }

    for (Sticker sticker : stickers) {
        int[] stickerResult = sticker.createResult();
        result[0] = result[0] + stickerResult[0];
        result[1] = result[1] + stickerResult[1];
        result[2] = result[2] + stickerResult[2];
    }
    return result;
}

}

enum OverlayEnum{
    NOT_OVERLAY, ALL_OVERLAY, PART_OVERLAY;
}

class Main {

    public static void main(String[] args) {

        List stickers = new ArrayList<>();
        stickers.add(new Sticker(2, 3, 2));
        stickers.add(new Sticker(6, 2, 2));
        stickers.add(new Sticker(3, 3, 2));
        stickers.add(new Sticker(3, 2, 2));
        stickers.add(new Sticker(0, 2, 3));

        int[]result = Sticker.execute(stickers);

        System.out.println("RESULT: " + Arrays.toString(result));

    }

}