0
현재 해커 크랜크 (Hackerrank)의 문제를 해결하기 위해 노력하고 있으며, 문제의 기한을 넘 어 가고 있습니다. 나는 이유를 알 수없는 것 같습니다.루프/방법이 너무 느립니다.
가장 작은 차이를 가진 숫자 쌍을 출력하십시오. 쌍이 여러 개인 경우 모든 쌍을 숫자의 오름차순으로 모두 출력합니다 (연속적으로 같은 줄에 표시). 두 쌍으로 된 숫자가있는 경우 두 번 인쇄하십시오 (설명을 위해 샘플 사례 # 3 참조). 입력 의
는수 공백에 의해 분리 된 모든 요소를 포함하는 문자열
샘플 :
4
5 4 3 2
출력 :
가2 3 3 4 4 5
I가 실패있어 테스트 케이스 100,000 입력을 가지고 . 내 코드를 타임 드로우하고 코드에서 가장 느린 부분은 함수 closest의 루프입니다. 나는 원래 벡터를 가지고 있었고 std : sort를 사용했다. 그런 다음 std :: sort를 호출하는 대신 멀티 세트를 사용하여 성능을 향상 시키려고했습니다. 그것은 여전히 시험에 실패했습니다. 루프를 개선하는 방법에 대한 아이디어는 closest 또는 addPair?
#include <iostream>
#include <set>
#include <utility>
#include <cmath>
#include <string>
#include <algorithm>
#include <ctime>
#define NUMBER 10000
double diffclock(clock_t clock1, clock_t clock2)
{
double diffticks = clock1 - clock2;
double diffms = (diffticks)/(CLOCKS_PER_SEC/NUMBER);
return diffms;
}
class ClosestPair
{
private:
long _distance;
const char UNSET = -1;
std::multiset<int> _list;
long getDistance(const int number1, const int number2) const;
public:
ClosestPair();
~ClosestPair();
void addPair(const int number1, const int number2);
const std::multiset<int>& getList() const;
const std::string toString() const;
void sort();
};
ClosestPair::ClosestPair()
{
_distance = UNSET;
}
ClosestPair::~ClosestPair()
{
}
void ClosestPair::addPair(const int number1, const int number2)
{
long distance = getDistance(number1, number2);
if(distance < _distance || _distance == UNSET)
{
_list.clear();
_distance = distance;
//std::pair<int, int> newPair(number1, number2);
//_list.push_back(newPair);
_list.insert(number1);
_list.insert(number2);
}
else if(distance == _distance)
{
_list.insert(number1);
_list.insert(number2);
//std::pair<int, int> newPair(number1, number2);
//_list.push_back(newPair);
}
}
inline long ClosestPair::getDistance(const int number1, const int number2) const
{
return std::abs(number1 - number2);
}
const std::multiset<int>& ClosestPair::getList() const
{
return _list;
}
const std::string ClosestPair::toString() const
{
std::string allPairs;
for(auto iterator = _list.begin(); iterator != _list.end(); iterator++)
{
allPairs += std::to_string(*iterator);
allPairs += " ";
//allPairs += std::to_string(iterator->second);
//allPairs += " ";
}
if(allPairs.size() > 0)
{
allPairs.substr(0, allPairs.size() - 1);
}
return allPairs;
}
void ClosestPair::sort()
{
//std::sort(_list.begin(), _list.end());
}
void closest(int* array, int size)
{
ClosestPair closestPairs;
clock_t begin = clock();
for(int i = 0; i < size; i++)
{
for(int j = i + 1; j < size; j++)
{
closestPairs.addPair(array[i], array[j]);
}
}
clock_t end = clock();
std::cout << "AddPair time: " << diffclock(end, begin) << " ms." << std::endl;
//closestPairs.sort();
begin = clock();
std::cout << closestPairs.toString();
std::cout << "toString time: " << diffclock(end, begin) << " ms." << std::endl;
end = clock();
}
int main()
{
int sizeOfList;
std::string allNumbers;
std::cin >> sizeOfList >> std::ws;
std::getline(std::cin, allNumbers);
size_t position = 0;
size_t nextPosition = 0;
int count = 0;
int array[sizeOfList];
clock_t begin = clock();
do
{
position = nextPosition;
nextPosition = allNumbers.find(' ', position + 1);
if(position > 0)
position++;
array[count] = atoi(allNumbers.substr(position, nextPosition - position).c_str());
count++;
}
while(nextPosition != std::string::npos);
clock_t end = clock();
std::cout << "Tokenize time: " << diffclock(end, begin) << " ms." << std::endl;
closest(array, sizeOfList);
return 0;
}
'옷장에서 루프를 개선하는 방법이나 addPair 메서드'에 대한 아이디어가 있습니까? 괜찮은 프로파일 러를 사용하고 병목 지점을 확인하십시오. –
코드를 작성한 방식을 알기는 어렵지만 기본적으로 거품 정렬을 수행하고있는 것처럼 보입니다. 100,000 개의 항목을 사용하면 100,000 * 100,000 회 반복이 될 수 있습니다. 대부분의 코딩 문제 사이트에서 60 초 제한을 훨씬 능가합니다. –
문제를 더 잘 설명합니다. 난 당신이 해결하려고하는 문제가 당신의 설명에서 무엇인지 전혀 모르겠다. – Yakk