c++에소팅 후 다차원 배열에 집어넣기 vs 다차원 배열에 그냥 집어넣기
ㅇㅅㅇ(90.27)
2017-01-06 18:46
추천 0
갤럼들중에 해본적이 있는 분이 있다면 알려주세용~
질문 - n차원 배열 array[i][j][k][l] 에다가 소팅 안된 random한 variable (var) 를 집어넣는것과
같은 n차원 배열인데 소팅 후에 variable을 집어넣는 속도가 많이 차이가 있을까?
캐쉬 활용하려고 하는데 이게 조건문이 누더기처럼 붙어있어서 캐시 활용이 잘 될지 의문이라..
예를 들자면..
요런식인데
float array[iN
][jN
][kN
][lN
];
float var
[nvar
] = Random
();
for (int ivar
= 0; ivar
< nvar
; ivar
++) {
if (conditions
) array[ii
][jj
][kk
][ll
] = var
[ivar
];
else if (conditions
) array[ii_1
][jj_1
][kk_1
][ll_1
] = var
[ivar
];
else if (conditions
) array[ii_2
][jj_2
][kk_2
][ll_2
] = var
[ivar
];
....
}
//-----------------------------------------
std::vector<float> varvector
(var
, nvar
);
std::sort(varvector
.begin
(), varvector
.end
());
for (int ivar
= 0; ivar
< nvar
; ivar
++) {
if (conditions
) array[ii
][jj
][kk
][ll
] = var
[ivar
];
else if (conditions
) array[ii_1
][jj_1
][kk_1
][ll_1
] = var
[ivar
];
else if (conditions
) array[ii_2
][jj_2
][kk_2
][ll_2
] = var
[ivar
];
....
}
ㅇ소팅이 잡아먹는 시간이 길어서 도찐개찐일까?
소팅이 된다면 var들은 ll : ll+1, ll+2, ll+3.. 순으로 증가하고 ll = llN이 되면 kk로 넘어가서 kk+1/ll .. ll+1 .. ll+N 까지 증가하는 양상을 보인다고 할때..
직접 해보기 전에 혹시 이런거 해보신 분 있으면 답변점 ㅎ..
다차원배열을 쓰지 말고 그리고 배열 자체를 쓰지마 - return 0;
넣기 전에 소팅하는게 더 빠르긴 할듯. O(NlogN) 소팅일테니까 원소 갯수가 더 중요하지 - return 0;
그럼 뭐쓰져
N은 대충 2000개 내외
벡터
으아니 배열을 쓰지 말라니 ㅜ
아 저기선 그냥 다차원 배열이라고 표기했는데 사실은 다차원 벡터 쓰고있어여.. vector< vector < vector <float> > >
그런데 벡터를 쓰나 배열을 쓰나 특정 배열부분에 접근하는 속도는 차이가 없을거같아서..
문제 내용을 몰라서 정확한 답변을 못주지만, 이런 형태의 문제는 보통 이런 방법으로 풀면 안됨.
너무 1차원적인 알고리즘이야
띠용
그럼 성능향상을 어떻게 꾀하져
구조 자체를 바꿔야지... DB같은 형태로 보이는데
서칭이 중요한 이슈면 해시 테이블로 처리할 수 없는 문제야??
db랑 비슷하긴 해여..
저 배열컨테이너를 해시로 바꾸라는 말씀이신가요?
Map으로 짜고 조건에 따라서 Key를 합성해낸 다음 Value를 가져오는게 나을거 같은데...
난 왜 들어도 모르겠지
Map, 즉 해시테이블 장점이 어느 데이터를 가져오던간에 일정한 속도를 보장한다는 점이지
벡터에 벡터 넣고 그런거 하지 마... - return 0;
인덱싱 함수 써서 2차원 좌표를 1차원 좌표로 환산해서 써 벡터에 벡터 넣는건 발에 총쏘는거야 - return 0;
map은 해시테이블 아니다. unordered_map 이 해시테이블이지 - return 0;
오.. 오..
미안... C++안해서 잘 몰랏어...
이게 뭔 상황이고 소팅은 왜하는거임?
그 일정한 속도라는게 배열의 i / i+1 보다는 느리지만 i / j 왔다갔다 하는것보다는 빠르다는거죠?
그냥 배열을 쓰지 말라는 이유는 이터레이터가 없어서 불편하거든 동적할당 하면 자기 관리도 안되고 - return 0;
소팅을 하면 변수를 갖고있는 배열이 (N= 2000) 다차원 배열에 순서대로 집어넣을 수 있으니까.. 단순하게 생각해봤어요
도찐개찐->도긴개긴 (국어사전 - 도긴개긴 [명사] : 조금 낫고 못한 정도의 차이는 있으나 본질적으로는 비슷비슷하여 견주어 볼 필요가 없음을 이르는 말.) [리듬 맞춤법 봇♬]
캐쉬->캐시 (sh는 시로 표기함. 스킨십 멤버십 플래그십 플래시 등등...) [리듬 맞춤법 봇♬]
커헠//갯수->개수 (개수 (個數)[명사] : 한 개씩 낱으로 셀 수 있는 물건의 수효.) [리듬 맞춤법 봇♬]
걍 벡터써도 될거같은데
한번 해시테이블로 변환하는거 생각해보고 소팅먼저 하는거랑 속도 비교도 해볼게요~
근데 소팅은 먼말임 소팅하고 넣기 vs 넣고 소팅하기?
해시맵은 왜나오는지 잘 모르겠음 어차피 배열로 접근 되면 그게 젤 빠른데
넹 소팅하고 넣으면 캐시 접근에서 이득을 볼 수 있지 않을까라고 생각했어요
넣고 소팅은 필요없구요
결과물은 소팅을 안해도 되는 상황입니다
소팅한다는거 보면 나중에 배열에 들어있는 값을 서칭하려는거 아님?
소팅을 왜한건지 모르겠음\
아뇽 저게 다차원배열이긴 한데 단순히 float가 아니라 어떤 클래스라..
넣고 나서는 소팅할필요가 없어요
제가 먼상황인지 몰라서 설명을 못해드리겠음
XY 냄새가 나는데 - return 0;
Xy가 뭔가요
답변 감사드립니다 ㅎ 일단 시도를 해볼게요