循環/方法太慢

Question

我目前正在處理來自hackerrank的一個問題，而且我正在考慮我的問題的時間限制。我似乎無法弄清楚爲什麼。

輸出具有最小差異的數字對。如果有多個對，則按升序輸出所有對，全部在同一行（連續），每對數之間只有一個空格。如果有一對數字位於兩對中，則打印兩次（參見樣本案例＃3以獲得解釋）。

輸入 數量包含所有由空格隔開的字符串的元素

樣品：

4 
5 4 3 2 

輸出：

2 3 3 4 4 5 

測試情況下，我失敗上具有100000級的輸入。我計算了我的代碼，並且我的代碼中最慢的部分是函數closest中的循環。我原本有一個向量，然後在列表後使用std：sort。然後我嘗試使用multiset而不是調用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; 
} 

Answer 1

// requires [b,e) is sorted: 
template<typename Iterator> 
std::vector<Iterator> find_close_pairs(Iterator b, Iterator e){ 
    if (b==e || std::next(b) == e) return {}; 
    std::vector<std::size_t> retval = {0}; 
    auto old = *std::next(b) - *b; 
    for(auto it = std::next(b); std::next(it) != e; ++it) { 
    auto delta = *std::next(it) - *it; 
    if (delta < old) { 
     retval.clear(); 
     old = delta; 
    } 
    if (delta <= old) { 
     retval.push_back(it); 
    } 
    } 
    return retval; 
} 
// requires: iterators are writable. Sorts range. Faster with random access: 
template<typename Iterator> 
std::vector<std::pair<int,int>> solve(Iterator b, Iterator e) { 
    std::sort(b, e); 
    auto close_pairs_indexes = find_close_pairs(b, e); 
    std::vector<std::pair<int,int>> retval; 
    retval.reserve(close_pairs_indexes.size()); 
    for(auto it:close_pairs_indexes) { 
    retval.push_back({*it, *std::next(it)}); 
    } 
    return retval; 
} 
// requires: numbers is a container, not a C array: 
template<typename Container> 
std::vector<std::pair<int,int>> solve(sContainer numbers) { 
    using std::begin; using std::end; 
    return solve(begin(numbers), end(numbers)); 
} 

是C++ 11並可能有錯別字，但應該這樣做。在手機上，代碼過於簡潔。

Answer 2

如果我正確理解你的問題，你也可以使用multimap。該映射的鍵/值是int/pair（int，int）。

一次檢查您的排序列表中的2個數字。計算兩個數字之間的差異。這種差異成爲地圖中的一個關鍵值，這兩個數字是你用來提出差異的兩個數字。

完成之後，您可以保證最小的差異在地圖的開頭，因爲地圖使用<對按鍵進行排序。你現在有最小的差異加上導致差異的那對數字的信息。

例如：

#include <map> 
#include <vector> 
#include <algorithm> 

typedef std::multimap<int, std::pair<int, int>> IntMap; 
typedef std::vector<int> IntVect; 

void getDifferences(const IntVect& intVect, IntMap& theMap) // assume intVect is  sorted 
{ 
    theMap.clear(); 
    if (intVect.size() < 2) 
     return; 

    size_t nItems = intVect.size(); 
    for (size_t i = 0; i < nItems - 1; ++i) 
    { 
     int num1 = intVect[i+1]; 
     int num2 = intVect[i]; 
     int diff = num1 - num2 
     theMap.insert(std::make_pair(diff, std::make_pair(num2, num1))); 
    } 
} 

int main() 
{ 
    int Test[] = { 3, 4, 2, 7, 1, 11 }; 
    IntVect testV(Test, Test + sizeof(Test)/sizeof(Test[0])); 
    std::sort(testV.begin(), testV.end()); 
    IntMap myMap; 
    getDifferences(testV, myMap); 
} 

注意，要同時建立地圖來完成的最小從來沒有檢查。有點讓這個「安全」，但其他非映射答案更可能執行得更快。