글 읽기 - 왜 제 코드는 디게 느린걸까요...?

wyldecat 8년 전 0

평범하게 이분매칭 돌려서했어요..!

https://www.acmicpc.net/source/1085607

이분건 저랑 거의 비슷한데.. 속도가 7배 정도 빠르네요!!!

다른 분들거는 봐도 잘 모르겠구요.. ㅠㅠ

 
#include<stdio.h>
#include<vector>
 
using namespace std;
 
int N,M;
bool like[1005][1005];
vector<int> aMatch,bMatch;
vector<bool> visited;
 
bool dfs(int a)
{
    if(visited[a]) return false;
    visited[a]=true;
     
    for(int b=0;b<M;b++)
    {
        if(like[a][b])
        {
            if(bMatch[b]==-1 || dfs(bMatch[b]))
            {
                aMatch[a]=b;
                bMatch[b]=a;
                return true;
            }
        }
    }
    return false;
}
int maximum_flow()
{
    aMatch=vector<int>(N,-1);
    bMatch=vector<int>(M,-1);
     
    int size=0;
     
    for(int start=0;start<N;start++)
    {
        visited=vector<bool>(N,false);
        if(dfs(start)) ++size;
    }
     
    return size;
     
}
int main( )
{
    scanf("%d %d",&N,&M);
    for(int i=1;i<=N;i++)
    {
        int k,x;
        scanf("%d",&k);
        for(int j=0;j<k;j++)
        {
            scanf("%d",&x);
            like[i-1][x-1]=1;
        }
    }
    printf("%d\n",maximum_flow());
    return 0;
}

ckdgus2482 8년 전 1

39번 라인에서 성능저하가 발생할 수 있을것 같습니다.

벡터 객체의 생성을 N번이나 수행하네요. 거기다가 N개의 데이터로 초기화까지 진행하니 오버헤드가 상당합니다.

wyldecat 8년 전 0

오오..!!!!!!!! 그렇군요.. memset을 사용해서 다시 테스트해봐야겠어요ㅎㅎ

wyldecat 8년 전 0

큽.. for문으로 대체를 해도 똑같은 시간이 뜨네요... 댓글 감사합니다 (_ _)

ckdgus2482 8년 전 1

우선 37라인~41라인의 for문 돌때마다 새로운 벡터 객체를 생성하는것 자체가 오버헤드가 발생하구요. 초기화도 생성자를 통해서 하든 memeset이나 for문을 이용해서 수행하든 오버헤드가 발생할 수 밖에 없습니다.

그럴게 아니라 N최대값*N최대값 사이즈의 전역변수 배열로 바꿔서 해보세요. 0으로 초기화하는 것이므로 전역변수로 선언만하면 러닝타임중 별다른 초기화과정을 수행할 필요가 없겠죠.

wyldecat 8년 전 0

ㅎㅎ 댓글감사합니다..!! 아예 벡터를 안쓰고 배열을 정적으로 할당해서 해봐도 똑같네요 ㅠ-ㅠ

#include<stdio.h>
#include<cstring>
#include<string.h>
#include<vector>

using namespace std;

int N,M;
bool like[1005][1005];
int bMatch[1005];
bool visited[1010];

bool dfs(int a)
{
    if(visited[a]) return false;
    visited[a]=true;
    
    for(int b=0;b<M;b++)
    {
        if(like[a][b])
        {
            if(bMatch[b]==-1 || dfs(bMatch[b]))
            {
                bMatch[b]=a;
                return true;
            }
        }
    }
    return false;
}
int maximum_flow()
{
    int size=0,i;
    for(i=0;i<N;i++) bMatch[i]=-1;
    for(int start=0;start<N;start++)
    {
        for(i=0;i<N;i++) visited[i]=0;
        if(dfs(start)) ++size;
    }
    
    return size;
    
}
int main( )
{
    scanf("%d %d",&N,&M);
    for(int i=1;i<=N;i++)
    {
        int k,x;
        scanf("%d",&k);
        for(int j=0;j<k;j++)
        {
            scanf("%d",&x);
            like[i-1][x-1]=1;
        }
    }
    printf("%d\n",maximum_flow());
    return 0;
}

ckdgus2482 8년 전 1

아뇨... 37라인에서 배열 초기화하고 계시잖아요. 제 말은 bool visited[N최대값][N최대값]; 이렇게 선언하라는 얘기였어요.

배열을 재활용하려면 배열 초기화를 N번 진행해야하지만 애초에 배열 자체를 N개 만들어놓으면 초기화를 전혀 할 필요가 없잖아요.

wyldecat 8년 전 0

앗!!! 그렇군요 ㅎㅎ 막줄을 제대로 안읽었네요 ㅠㅠ

wyldecat 8년 전 0

ㅠㅠ 계속 귀찮게해드려 죄송해유.. 이렇게했더니 시간이 오히려 늘었네용..

#include<stdio.h>
#include<cstring>
#include<string.h>
#include<vector>
  
using namespace std;
  
int start;
int N,M;
bool like[1005][1005];
int bMatch[1005];
bool visited[1010][1010];
  
bool dfs(int a)
{
    if(visited[start][a]) return false;
    visited[start][a]=true;
      
    for(int b=0;b<M;b++)
    {
        if(like[a][b])
        {
            if(bMatch[b]==-1 || dfs(bMatch[b]))
            {
                bMatch[b]=a;
                return true;
            }
        }
    }
    return false;
}
int maximum_flow()
{
    int size=0,i;
    for(i=0;i<N;i++) bMatch[i]=-1;
    for(start=0;start<N;start++)
    {
        if(dfs(start)) ++size;
    }
      
    return size;
      
}
int main( )
{
    scanf("%d %d",&N,&M);
    for(int i=1;i<=N;i++)
    {
        int k,x;
        scanf("%d",&k);
        for(int j=0;j<k;j++)
        {
            scanf("%d",&x);
            like[i-1][x-1]=1;
        }
    }
    printf("%d\n",maximum_flow());
    return 0;
}

ckdgus2482 8년 전 1

dfs정의에서 bool*를 인자로 받게 하고 38라인에서 아래와같이 호출하면 조금 더 빨라집니다.

dfs(visited[start], start)

물론 16, 17라인은 다시 1차원배열로 바꾸시구요.

근데 이렇게해도 맨처음 비교하신분만큼 속도는 안나오네요... 코드수준의 최적화 문제는 아닌것 같습니다.

아무래도 DFS부분을 좀더 면밀히 비교해볼 필요가 있을것 같습니다.

wyldecat 8년 전 0

넵 ㅎㅎ 신경써주셔서 감사합니다 (_ _)

ckdgus2482 7년 전 0

전역변수는 프로그램이 메모리에 로드되는 시점에서 모두 초기화 되는 것입니다.

main에 진입하기 전에 이미 다 초기화가 된 상태죠.

ckdgus2482 7년 전 0

그리고 이 문제에서 실제로 비교해본 결과 160ms정도 차이가 났고요.

ckdgus2482 7년 전 0

우선 blinkingstar님 이전 댓글에서 '배열에 접근할때마다' 라고 하셔서 의도를 제대로 파악하지 못했습니다.

OS가 bss섹션 관리에 있어서 zero-fill-on-demand 정책을 사용한다는 것은 알고 있습니다.

다만 그건 페이지 폴트가 발생했을때라는 조건이 있죠.

이 프로그램 규모가 굉장히 작은 편이라서 프리페이징 과정에서 프로세스 전체가 메모리에 로드될 가능성이 굉장히 높습니다.

만약 그렇지 않다면 채점머신의 램을 증설해야겠죠.

굳이 초기화가 아니더라도 프로그램 실행 중 페이지폴트가 발생하면 오버헤드가 꽤 발생할 것입니다.

그러면 같은 소스라도 채점머신의 상태에 따라 시간이 상이해질 수 있다는 것인데 그러면 공정한 채점이라고 할 수 없겠죠.

pjh6792 3년 전 1

아주 예전 질문이지만, 저처럼 이 질문과 같은 궁금증을 가지고 찾아오신 분에게 혹시나 도움이 될까 해서 댓글을 남깁니다.

저도 질문자 분과 마찬가지로 시간이 약 500ms가 발생하였고, 코드도 질문자분과 유사하게 작성했는데, 제일 처음의 코드에서 21번째 줄을 보면

f(bMatch[b]==-1 || dfs(bMatch[b])) 구문이 있습니다.

여기서 bMatch[b] == -1 을 만족하더라도 dfs함수를 수행하기 때문에 불필요한 작업이 수행되는 것 같습니다.

저 같은 경우에는 먼저 bMatch[b] == -1 조건문만 반복문을 돌면서 수행을 하고, 그때도 return이 되지 않는다면 다시 반복문을 한번 더 돌면서 dfs함수를 체크해주는 방식으로 구현하였더니, 시간이 약 500ms에서 80ms로 줄어들었습니다.

배열 초기화하는 과정을 간소화시켜도 시간이 크게 줄어들지가 않아서, 혹시나 궁금하신 분은 이 방식으로 한번 시도해보시면 좋을 것 같습니다 ^----^

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

왜 제 코드는 디게 느린걸까요...?

wyldecat 8년 전 0

ckdgus2482 8년 전 1

wyldecat 8년 전 0

wyldecat 8년 전 0

ckdgus2482 8년 전 1

wyldecat 8년 전 0

ckdgus2482 8년 전 1

wyldecat 8년 전 0

wyldecat 8년 전 0

ckdgus2482 8년 전 1

wyldecat 8년 전 0

ckdgus2482 7년 전 0

ckdgus2482 7년 전 0

ckdgus2482 7년 전 0

pjh6792 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말