Làm thế nào để giữ cho bản sao chỉ có hiệu quả?

Question

Với một vector STL, chỉ đưa ra các bản sao theo thứ tự sắp xếp, ví dụ,

INPUT : { 4, 4, 1, 2, 3, 2, 3 } 
OUTPUT: { 2, 3, 4 } 

Thuật toán là tầm thường, nhưng mục đích là để làm cho nó hiệu quả như std :: duy nhất(). thực hiện ngây thơ của tôi sẽ thay đổi container tại chỗ:

thực hiện ngây thơ của tôi:

void not_unique(vector<int>* pv) 
{ 
    if (!pv) 
     return; 

// Sort (in-place) so we can find duplicates in linear time 
sort(pv->begin(), pv->end()); 

vector<int>::iterator it_start = pv->begin(); 
while (it_start != pv->end()) 
{ 
    size_t nKeep = 0; 

    // Find the next different element 
    vector<int>::iterator it_stop = it_start + 1; 
    while (it_stop != pv->end() && *it_start == *it_stop) 
    { 
    nKeep = 1; // This gets set redundantly 
    ++it_stop; 
    } 

    // If the element is a duplicate, keep only the first one (nKeep=1). 
    // Otherwise, the element is not duplicated so erase it (nKeep=0). 
    it_start = pv->erase(it_start + nKeep, it_stop); 
} 
} 

Nếu bạn có thể làm này hiệu quả hơn, thanh lịch, hay nói chung, xin vui lòng cho tôi biết. Ví dụ, một thuật toán sắp xếp tùy chỉnh hoặc sao chép các phần tử trong vòng lặp thứ hai để loại bỏ lệnh gọi xóa().

Answer 1

Ngắn hơn và nhiều hơn STL-ish so với các mục nhập trước đó. Giả định đầu vào được sắp xếp.

#include <algorithm> 
#include <functional> 

template< class I, class P > 
I remove_unique(I first, I last, P pred = P()) { 
    I dest = first; 
    while (
     (first = std::adjacent_find(first, last, pred)) 
      != last) { 
     * dest = * first; 
     ++ first; 
     ++ dest; 
     if ((first = std::adjacent_find(first, last, std::not2(pred))) 
      == last) break; 
     ++ first; 
    } 
    return dest; 
} 

template< class I > 
I remove_unique(I first, I last) { 
    return remove_unique(first, last, 
     std::equal_to< typename std::iterator_traits<I>::value_type >()); 
} 

Answer 2

Đề xuất của tôi sẽ là loại sắp xếp sửa đổi, để bạn có thể sắp xếp các lần quét bộ lọc & cùng một lúc.

Answer 3

Tôi nghĩ rằng từ một quan điểm O lớn, bạn có nó được thực hiện tốt như nó được. Chi phí ghi đè là loại, là O (N log N). Một khả năng, tuy nhiên, sẽ là xây dựng một vectơ mới với các mục trùng lặp hơn là sử dụng vectơ hiện có với thao tác xóa loại bỏ các phần tử không trùng lặp. Tuy nhiên, điều này sẽ chỉ tốt hơn nếu số lượng bản sao riêng biệt nhỏ so với tổng số mục nhập.

Hãy xem xét ví dụ cực đoan. Nếu mảng ban đầu bao gồm 1.000 mục nhập chỉ với một bản sao, thì đầu ra sẽ là một vectơ chỉ với một giá trị. Nó có thể hiệu quả hơn một chút để tạo vectơ mới với một mục thay vì xóa các mục 999 khác khỏi vectơ gốc. Tuy nhiên, tôi nghi ngờ rằng trong thử nghiệm thế giới thực, sự tiết kiệm của thay đổi đó có thể khó đo lường.

Chỉnh sửa Tôi chỉ đang nghĩ về điều này về câu hỏi "phỏng vấn". Nói cách khác, đây không phải là câu trả lời hữu ích khủng khiếp. Nhưng nó sẽ có thể giải quyết điều này trong O (N) (thời gian tuyến tính) trái ngược với O (N Log N). Sử dụng dung lượng lưu trữ thay vì CPU. Tạo hai mảng "bit" với chúng được xóa ban đầu. Lặp qua vectơ của các giá trị số nguyên. Tra cứu từng giá trị trong mảng bit đầu tiên. Nếu nó không được thiết lập, sau đó thiết lập bit (đặt nó thành 1). Nếu nó được thiết lập, sau đó thiết lập bit tương ứng trong mảng thứ hai (chỉ ra một bản sao). Sau khi tất cả các mục vectơ được xử lý, quét qua mảng thứ hai và xuất các số nguyên trùng lặp (được chỉ ra bởi các bit được đặt trong mảng bit thứ hai). Lý do sử dụng mảng bit chỉ dành cho hiệu quả không gian. Nếu xử lý các số nguyên 4 byte, thì không gian thô được yêu cầu là (2 * 2^32/8). Nhưng điều này thực sự có thể được biến thành một thuật toán có thể sử dụng bằng cách biến nó trở thành một mảng thưa thớt. Mã giả giả rất giống như sau:

bitarray1[infinite_size]; 
bitarray2[infinite_size]; 

clear/zero bitarrays 

// NOTE - do not need to sort the input 
foreach value in original vector { 
    if (bitarray1[value]) 
     // duplicate 
     bitarray2[value] = 1 
    bitarray1[value] = 1 
} 

// At this point, bitarray2 contains a 1 for all duplicate values. 
// Scan it and create the new vector with the answer 
for i = 0 to maxvalue 
    if (bitarray2[i]) 
     print/save/keep i 

Answer 4

Gọi "xóa (it_start + keep, it_stop);" từ bên trong vòng lặp while sẽ dẫn đến việc sao chép các phần tử còn lại lặp đi lặp lại.

Tôi khuyên bạn nên trao đổi tất cả các phần tử duy nhất cho mặt trước của vectơ, sau đó xóa tất cả các phần tử còn lại cùng một lúc.

int num_repeats(vector<int>::const_iterator curr, vector<int>::const_iterator end) { 
    int same = *curr; 
    int count = 0; 
    while (curr != end && same == *curr) { 
    ++curr; 
    ++count; 
    } 
    return count; 
} 

void dups(vector<int> *v) { 
    sort(v->begin(), v->end()); 
    vector<int>::iterator current = v->begin(); 
    vector<int>::iterator end_of_dups = v->begin(); 
    while (current != v->end()) { 
    int n = num_repeats(current, v->end()); 
    if (n > 1) { 
     swap(*end_of_dups, *current); 
     end_of_dups++; 
    } 
    current += n; 
    } 
    v->erase(end_of_dups, v->end()); 
} 

Answer 5

tôi đau khổ thất bại với nỗ lực đầu tiên của tôi, giả định rằng std::unique di chuyển tất cả các bản sao đến cuối của dãy núi này (nó không). Rất tiếc. Đây là một nỗ lực khác:

Dưới đây là triển khai not_unique.Nó loại bỏ bất kỳ phần tử nào chỉ xuất hiện một lần trong phạm vi được sắp xếp và các bản sao của bất kỳ phần tử nào xuất hiện nhiều lần. Do đó, phạm vi kết quả là danh sách các phần tử duy nhất xuất hiện nhiều lần.

Chức năng có độ phức tạp tuyến tính và thực hiện một lần vượt qua phạm vi (std::unique có độ phức tạp tuyến tính). It phải đáp ứng các yêu cầu của trình lặp chuyển tiếp. Sự kết thúc của phạm vi kết quả được trả về.

template <typename It> 
It not_unique(It first, It last) 
{ 
    if (first == last) { return last; } 

    It new_last = first; 
    for (It current = first, next = ++first; next != last; ++current, ++next) 
    { 
     if (*current == *next) 
     { 
      if (current == new_last) 
      { 
       ++new_last; 
      } 
      else 
      { 
       *new_last++ = *current; 
       while (next != last && *current == *next) 
       { 
        ++current; 
        ++next; 
       } 
       if (next == last) 
        return new_last; 
      } 
     } 
    } 
    return new_last; 
} 

Answer 6

Đây là kiểu thư viện chuẩn. Tín dụng cho thuật toán goes to James! (Nếu bạn +1 tôi, bạn nên +1 anh ấy, hoặc người khác). Tất cả những gì tôi đã làm là làm cho phong cách thư viện chuẩn là:

#include <algorithm> 
#include <functional> 
#include <iostream> 
#include <iterator> 
#include <vector> 

// other stuff (not for you) 
template <typename T> 
void print(const char* pMsg, const T& pContainer) 
{ 
    std::cout << pMsg << "\n "; 
    std::copy(pContainer.begin(), pContainer.end(), 
     std::ostream_iterator<typename T::value_type>(std::cout, " ")); 
    std::cout << std::endl; 
} 

template <typename T, size_t N> 
T* endof(T (&pArray)[N]) 
{ 
    return &pArray[0] + N; 
} 

// not_unique functions (for you) 
template <typename ForwardIterator, typename BinaryPredicate> 
ForwardIterator not_unique(ForwardIterator pFirst, ForwardIterator pLast, 
          BinaryPredicate pPred) 
{ 
    // correctly handle case where an empty range was given: 
    if (pFirst == pLast) 
    { 
     return pLast; 
    } 

    ForwardIterator result = pFirst; 
    ForwardIterator previous = pFirst; 

    for (++pFirst; pFirst != pLast; ++pFirst, ++previous) 
    { 
     // if equal to previous 
     if (pPred(*pFirst, *previous)) 
     { 
      if (previous == result) 
      { 
       // if we just bumped bump again 
       ++result; 
      } 
      else if (!pPred(*previous, *result)) 
      { 
       // if it needs to be copied, copy it 
       *result = *previous; 

       // bump 
       ++result; 
      } 
     } 
    } 

    return result; 
} 

template <typename ForwardIterator> 
ForwardIterator not_unique(ForwardIterator pFirst, ForwardIterator pLast) 
{ 
    return not_unique(pFirst, pLast, 
       std::equal_to<typename ForwardIterator::value_type>()); 
} 


//test 
int main() 
{ 
    typedef std::vector<int> vec; 

    int data[] = {1, 4, 7, 7, 2, 2, 2, 3, 9, 9, 5, 4, 2, 8}; 
    vec v(data, endof(data)); 

    // precondition 
    std::sort(v.begin(), v.end()); 
    print("before", v); 

    // duplicatify (it's a word now) 
    vec::iterator iter = not_unique(v.begin(), v.end()); 
    print("after", v); 

    // remove extra 
    v.erase(iter, v.end()); 
    print("erased", v); 
} 

Answer 7

Bạn thậm chí có thể sử dụng không khớp, cho thêm điểm!
Btw: bài tập hay.

template<class TIter> 
/** Moves duplicates to front, returning end of duplicates range. 
* Use a sorted range as input. */ 
TIter Duplicates(TIter begin, TIter end) { 
    TIter dup = begin; 
    for (TIter it = begin; it != end; ++it) { 
     TIter next = it; 
     ++next; 
     TIter const miss = std::mismatch(next, end, it).second; 
     if (miss != it) { 
      *dup++ = *miss; 
      it = miss; 
     } 
    } 
    return dup; 
} 

Answer 8

Một số khác:

template <typename T> 
void keep_duplicates(vector<T>& v) 
{ 
    set<T> 
     u(v.begin(), v.end()), // unique 
     d; // duplicates 
    for (size_t i = 0; i < v.size(); i++) 
     if (u.find(v[i]) != u.end()) 
      u.erase(v[i]); 
     else 
      d.insert(v[i]); 

    v = vector<T>(d.begin(), d.end()); 
} 

Answer 9

này sửa chữa các lỗi trong James McNellis's phiên bản gốc. Tôi cũng cung cấp các phiên bản tại chỗ và ngoài vị trí.

// In-place version. Uses less memory and works for more container 
// types but is slower. 
template <typename It> 
It not_unique_inplace(It first, It last) 
{ 
    if (first == last) 
     return last; 

    It new_last = first; 
    for (It current = first, next = first + 1; next != last; ++current, ++next) 
    { 
     if (*current == *next && 
      (new_last == first || *current != *(new_last-1))) 
      *new_last++ = *current; 
    } 
    return new_last; 
} 

// Out-of-place version. Fastest. 
template <typename It, typename Container> 
void not_unique(It first, It last, Container pout) 
{ 
    if (first == last || !pout) 
     return; 

    for (It current = first, next = first + 1; next != last; ++current, ++next) 
    { 
     if (*current == *next && 
      (pout->empty() || *current != pout->back())) 
      pout->push_back(*current); 
    } 
} 

Answer 10

Điều gì có nghĩa là "hiệu quả như std :: duy nhất"? Hiệu quả về thời gian chạy, thời gian phát triển, sử dụng bộ nhớ, hay cái gì?

Như những người khác đã chỉ ra, std :: unique yêu cầu đầu vào được sắp xếp, mà bạn chưa cung cấp, do đó, đây không phải là thử nghiệm hợp lý để bắt đầu.

Cá nhân tôi sẽ chỉ có một tiêu chuẩn :: bản đồ làm tất cả công việc của tôi cho tôi. Nó có rất nhiều thuộc tính mà chúng ta có thể sử dụng cho sự tao nhã/ngắn gọn tối đa. Nó giữ các phần tử của nó được sắp xếp rồi, và toán tử [] sẽ chèn một giá trị bằng không nếu khóa không tồn tại. Bằng cách tận dụng các thuộc tính đó, chúng ta có thể thực hiện điều này trong hai hoặc ba dòng mã, và vẫn đạt được độ phức tạp thời gian chạy hợp lý.

Về cơ bản, thuật toán của tôi là: Đối với mỗi phần tử trong vectơ, tăng thêm một mục nhập bản đồ được khóa bằng giá trị của phần tử đó. Sau đó, chỉ cần đi bộ bản đồ, xuất ra bất kỳ khóa nào có giá trị lớn hơn 1. Không thể đơn giản hơn.

#include <iostream> 
#include <vector> 
#include <map> 

void 
output_sorted_duplicates(std::vector<int>* v) 
{ 
    std::map<int, int> m; 

    // count how many of each element there are, putting results into map 
    // map keys are elements in the vector, 
    // map values are the frequency of that element 
    for (std::vector<int>::iterator vb = v->begin(); vb != v->end(); ++vb) 
     ++m[*vb]; 

    // output keys whose values are 2 or more 
    // the keys are already sorted by the map 
    for (std::map<int, int>::iterator mb = m.begin(); mb != m.end(); ++mb) 
     if ((*mb).second >= 2) 
     std::cout << (*mb).first << " "; 
    std::cout << std::endl; 
} 

int main(void) 
{ 
    int initializer[] = { 4, 4, 1, 2, 3, 2, 3 }; 
    std::vector<int> data(&initializer[0], &initializer[0] + 7); 
    output_sorted_duplicates(&data); 
} 

janks@phoenix:/tmp$ g++ test.cc && ./a.out 
2 3 4 

Vì vậy, chúng tôi truy cập từng phần tử trong vectơ của bạn một lần, sau đó mỗi phần tử trong bản đồ của tôi một lần, trong đó số lượng phần tử trong bản đồ của tôi kém nhất không lớn hơn vectơ của bạn. Những hạn chế đối với giải pháp của tôi là rất nhiều không gian lưu trữ hơn so với các giải pháp liên quan đến sắp xếp lại vector của bạn tại chỗ. Những lợi thế, tuy nhiên, là rõ ràng. Nó cực kỳ ngắn và đơn giản, nó rõ ràng là chính xác mà không cần kiểm tra nhiều hay xem xét mã, và nó có các đặc tính hiệu suất hợp lý.

Làm cho chức năng của tôi trở thành mẫu và làm cho mẫu hoạt động trên các dải kiểu STL thay vì chỉ các vectơ của int, được để lại dưới dạng bài tập.