c++ - sort - 10 নম্বর বাছাই করার দ্রুততম উপায়?(সংখ্যা 32 বিট)




selection sort in c++ (7)

আমি একটি সমস্যা সমাধান করছি এবং এতে খুব দ্রুত 10 নম্বর (ইন্ট 32) বাছাই করা জড়িত। আমার অ্যাপ্লিকেশনটিতে 10 টি সংখ্যা যথাসম্ভব লক্ষ লক্ষ বার সাজানো দরকার। আমি কোটি কোটি উপাদানগুলির একটি ডেটা সেট নমুনা দিচ্ছি এবং প্রতিবারই এর থেকে 10 সংখ্যা বাছাই করতে হবে (সরলীকৃত) এবং তাদের বাছাই করতে হবে (এবং সাজানো 10 উপাদান তালিকার থেকে সিদ্ধান্তে নেওয়া)।

বর্তমানে আমি সন্নিবেশ বাছাইটি ব্যবহার করছি তবে আমি ধারণা করছি যে আমার 10 নম্বরগুলির নির্দিষ্ট সমস্যার জন্য আমি খুব দ্রুত কাস্টম বাছাই করা অ্যালগরিদমকে প্রয়োগ করতে পারি যা সন্নিবেশকে বাছাই করে।

কীভাবে এই সমস্যার কাছে যাওয়া যায় সে সম্পর্কে কারও কি ধারণা আছে?


(বাছাই করা নেটওয়ার্কগুলি সন্ধান করার জন্য হ্যালোওয়ার্ল্ডের পরামর্শ অনুসরণ করে।)

দেখে মনে হচ্ছে যে একটি 29-তুলনা / সোয়াপ নেটওয়ার্ক 10-ইনপুট বাছাই করার দ্রুততম উপায় way আমি ১৯69৯ সালে ওয়াকসম্যানের দ্বারা আবিষ্কৃত নেটওয়ার্কটি জাভাস্ক্রিপ্টে এই উদাহরণের জন্য ব্যবহার করেছি, যা সরাসরি সিতে অনুবাদ করা উচিত, কারণ এটি কেবল বিবৃতি, তুলনা এবং অদলবদলের একটি তালিকা।

function sortNet10(data) {	// ten-input sorting network by Waksman, 1969
    var swap;
    if (data[0] > data[5]) { swap = data[0]; data[0] = data[5]; data[5] = swap; }
    if (data[1] > data[6]) { swap = data[1]; data[1] = data[6]; data[6] = swap; }
    if (data[2] > data[7]) { swap = data[2]; data[2] = data[7]; data[7] = swap; }
    if (data[3] > data[8]) { swap = data[3]; data[3] = data[8]; data[8] = swap; }
    if (data[4] > data[9]) { swap = data[4]; data[4] = data[9]; data[9] = swap; }
    if (data[0] > data[3]) { swap = data[0]; data[0] = data[3]; data[3] = swap; }
    if (data[5] > data[8]) { swap = data[5]; data[5] = data[8]; data[8] = swap; }
    if (data[1] > data[4]) { swap = data[1]; data[1] = data[4]; data[4] = swap; }
    if (data[6] > data[9]) { swap = data[6]; data[6] = data[9]; data[9] = swap; }
    if (data[0] > data[2]) { swap = data[0]; data[0] = data[2]; data[2] = swap; }
    if (data[3] > data[6]) { swap = data[3]; data[3] = data[6]; data[6] = swap; }
    if (data[7] > data[9]) { swap = data[7]; data[7] = data[9]; data[9] = swap; }
    if (data[0] > data[1]) { swap = data[0]; data[0] = data[1]; data[1] = swap; }
    if (data[2] > data[4]) { swap = data[2]; data[2] = data[4]; data[4] = swap; }
    if (data[5] > data[7]) { swap = data[5]; data[5] = data[7]; data[7] = swap; }
    if (data[8] > data[9]) { swap = data[8]; data[8] = data[9]; data[9] = swap; }
    if (data[1] > data[2]) { swap = data[1]; data[1] = data[2]; data[2] = swap; }
    if (data[3] > data[5]) { swap = data[3]; data[3] = data[5]; data[5] = swap; }
    if (data[4] > data[6]) { swap = data[4]; data[4] = data[6]; data[6] = swap; }
    if (data[7] > data[8]) { swap = data[7]; data[7] = data[8]; data[8] = swap; }
    if (data[1] > data[3]) { swap = data[1]; data[1] = data[3]; data[3] = swap; }
    if (data[4] > data[7]) { swap = data[4]; data[4] = data[7]; data[7] = swap; }
    if (data[2] > data[5]) { swap = data[2]; data[2] = data[5]; data[5] = swap; }
    if (data[6] > data[8]) { swap = data[6]; data[6] = data[8]; data[8] = swap; }
    if (data[2] > data[3]) { swap = data[2]; data[2] = data[3]; data[3] = swap; }
    if (data[4] > data[5]) { swap = data[4]; data[4] = data[5]; data[5] = swap; }
    if (data[6] > data[7]) { swap = data[6]; data[6] = data[7]; data[7] = swap; }
    if (data[3] > data[4]) { swap = data[3]; data[3] = data[4]; data[4] = swap; }
    if (data[5] > data[6]) { swap = data[5]; data[5] = data[6]; data[6] = swap; }
    return(data);
}

alert(sortNet10([5,7,1,8,4,3,6,9,2,0]));

এখানে নেটওয়ার্কের একটি গ্রাফিকাল উপস্থাপনা, স্বতন্ত্র পর্যায়ে বিভক্ত।

সমান্তরাল প্রক্রিয়াকরণের সুবিধা গ্রহণের জন্য, 5-4-3-4-4-4-4-3-2-2 গোষ্ঠীকরণ একটি 4-4-4-4-4-4-4-3-3-2 গ্রুপিংয়ে পরিবর্তন করা যেতে পারে।


আপনি insertion sort সম্পূর্ণরূপে তালিকাভুক্ত করতে insertion sort

এটি আরও সহজ করার জন্য, পুনরাবৃত্ত template গুলি কোনও ফাংশন ওভারহেড ছাড়াই ব্যবহার করা যেতে পারে। যেহেতু এটি ইতিমধ্যে একটি template , তাই int একটি template প্যারামিটারও হতে পারে। এটি 10 ​​টি তুচ্ছ ব্যতীত কোডিং অ্যারে মাপগুলি তৈরি করে।

নোট করুন যে int x[10] কে সাজানোর জন্য কলটি insert_sort<int, 9>::sort(x); যেহেতু ক্লাসটি শেষ আইটেমের সূচি ব্যবহার করে। এটি মোড়ানো হতে পারে, তবে এটি পড়তে আরও কোড হবে।

template <class T, int NUM>
class insert_sort;

template <class T>
class insert_sort<T,0>
// stop template recursion
// sorting 1 item is a no-op
{
public:
    static void place(T *x) {}
    static void sort(T * x) {}
};

template <class T, int NUM>
class insert_sort
// use template recursion to do insertion sort
// NUM is the index of the last item, eg. for x[10] call <9>
{
public:
    static void place(T *x)
    {
        T t1=x[NUM-1];
        T t2=x[NUM];
        if (t1 > t2)
        {
            x[NUM-1]=t2;
            x[NUM]=t1;
            insert_sort<T,NUM-1>::place(x);
        }
    }
    static void sort(T * x)
    {
        insert_sort<T,NUM-1>::sort(x); // sort everything before
        place(x);                    // put this item in
    }
};

আমার পরীক্ষায় এটি বাছাই করা নেটওয়ার্ক উদাহরণগুলির চেয়ে দ্রুত ছিল।


আমি here বর্ণিত কার্যের অনুরূপ কারণের জন্য, নিম্নলিখিত বাছাই করা ফাংশনগুলি, sort6_iterator() এবং sort10_iterator_local() ভালভাবে সঞ্চালন করা উচিত, যেখান থেকে বাছাইয়ের নেটওয়ার্কটি নেওয়া হয়েছিল:

template<class IterType> 
inline void sort10_iterator(IterType it) 
{
#define SORT2(x,y) {if(data##x>data##y)std::swap(data##x,data##y);}
#define DD1(a)   auto data##a=*(data+a);
#define DD2(a,b) auto data##a=*(data+a), data##b=*(data+b);
#define CB1(a)   *(data+a)=data##a;
#define CB2(a,b) *(data+a)=data##a;*(data+b)=data##b;
  DD2(1,4) SORT2(1,4) DD2(7,8) SORT2(7,8) DD2(2,3) SORT2(2,3) DD2(5,6) SORT2(5,6) DD2(0,9) SORT2(0,9) 
  SORT2(2,5) SORT2(0,7) SORT2(8,9) SORT2(3,6) 
  SORT2(4,9) SORT2(0,1) 
  SORT2(0,2) CB1(0) SORT2(6,9) CB1(9) SORT2(3,5) SORT2(4,7) SORT2(1,8) 
  SORT2(3,4) SORT2(5,8) SORT2(6,7) SORT2(1,2) 
  SORT2(7,8) CB1(8) SORT2(1,3) CB1(1) SORT2(2,5) SORT2(4,6) 
  SORT2(2,3) CB1(2) SORT2(6,7) CB1(7) SORT2(4,5) 
  SORT2(3,4) CB2(3,4) SORT2(5,6) CB2(5,6) 
#undef CB1
#undef CB2
#undef DD1
#undef DD2
#undef SORT2
}

এই ফাংশনটি কল করতে আমি এটি একটি std::vector পুনরুক্তি দিয়েছি।


আমি সম্প্রতি একটি সামান্য ক্লাস লিখেছিলাম যা বোস-নেলসন অ্যালগরিদম ব্যবহার করে সংকলনের সময় বাছাইয়ের নেটওয়ার্ক তৈরি করে।

এটি 10 ​​টি সংখ্যার জন্য খুব দ্রুত বাছাই করতে ব্যবহৃত হতে পারে।

/**
 * A Functor class to create a sort for fixed sized arrays/containers with a
 * compile time generated Bose-Nelson sorting network.
 * \tparam NumElements  The number of elements in the array or container to sort.
 * \tparam T            The element type.
 * \tparam Compare      A comparator functor class that returns true if lhs < rhs.
 */
template <unsigned NumElements, class Compare = void> class StaticSort
{
    template <class A, class C> struct Swap
    {
        template <class T> inline void s(T &v0, T &v1)
        {
            T t = Compare()(v0, v1) ? v0 : v1; // Min
            v1 = Compare()(v0, v1) ? v1 : v0; // Max
            v0 = t;
        }

        inline Swap(A &a, const int &i0, const int &i1) { s(a[i0], a[i1]); }
    };

    template <class A> struct Swap <A, void>
    {
        template <class T> inline void s(T &v0, T &v1)
        {
            // Explicitly code out the Min and Max to nudge the compiler
            // to generate branchless code.
            T t = v0 < v1 ? v0 : v1; // Min
            v1 = v0 < v1 ? v1 : v0; // Max
            v0 = t;
        }

        inline Swap(A &a, const int &i0, const int &i1) { s(a[i0], a[i1]); }
    };

    template <class A, class C, int I, int J, int X, int Y> struct PB
    {
        inline PB(A &a)
        {
            enum { L = X >> 1, M = (X & 1 ? Y : Y + 1) >> 1, IAddL = I + L, XSubL = X - L };
            PB<A, C, I, J, L, M> p0(a);
            PB<A, C, IAddL, J + M, XSubL, Y - M> p1(a);
            PB<A, C, IAddL, J, XSubL, M> p2(a);
        }
    };

    template <class A, class C, int I, int J> struct PB <A, C, I, J, 1, 1>
    {
        inline PB(A &a) { Swap<A, C> s(a, I - 1, J - 1); }
    };

    template <class A, class C, int I, int J> struct PB <A, C, I, J, 1, 2>
    {
        inline PB(A &a) { Swap<A, C> s0(a, I - 1, J); Swap<A, C> s1(a, I - 1, J - 1); }
    };

    template <class A, class C, int I, int J> struct PB <A, C, I, J, 2, 1>
    {
        inline PB(A &a) { Swap<A, C> s0(a, I - 1, J - 1); Swap<A, C> s1(a, I, J - 1); }
    };

    template <class A, class C, int I, int M, bool Stop = false> struct PS
    {
        inline PS(A &a)
        {
            enum { L = M >> 1, IAddL = I + L, MSubL = M - L};
            PS<A, C, I, L, (L <= 1)> ps0(a);
            PS<A, C, IAddL, MSubL, (MSubL <= 1)> ps1(a);
            PB<A, C, I, IAddL, L, MSubL> pb(a);
        }
    };

    template <class A, class C, int I, int M> struct PS <A, C, I, M, true>
    {
        inline PS(A &a) {}
    };

public:
    /**
     * Sorts the array/container arr.
     * \param  arr  The array/container to be sorted.
     */
    template <class Container> inline void operator() (Container &arr) const
    {
        PS<Container, Compare, 1, NumElements, (NumElements <= 1)> ps(arr);
    };

    /**
     * Sorts the array arr.
     * \param  arr  The array to be sorted.
     */
    template <class T> inline void operator() (T *arr) const
    {
        PS<T*, Compare, 1, NumElements, (NumElements <= 1)> ps(arr);
    };
};

#include <iostream>
#include <vector>

int main(int argc, const char * argv[])
{
    enum { NumValues = 10 };

    // Arrays
    {
        int rands[NumValues];
        for (int i = 0; i < NumValues; ++i) rands[i] = rand() % 100;
        std::cout << "Before Sort: \t";
        for (int i = 0; i < NumValues; ++i) std::cout << rands[i] << " ";
        std::cout << "\n";
        StaticSort<NumValues> staticSort;
        staticSort(rands);
        std::cout << "After Sort: \t";
        for (int i = 0; i < NumValues; ++i) std::cout << rands[i] << " ";
        std::cout << "\n";
    }

    std::cout << "\n";

    // STL Vector
    {
        std::vector<int> rands(NumValues);
        for (int i = 0; i < NumValues; ++i) rands[i] = rand() % 100;
        std::cout << "Before Sort: \t";
        for (int i = 0; i < NumValues; ++i) std::cout << rands[i] << " ";
        std::cout << "\n";
        StaticSort<NumValues> staticSort;
        staticSort(rands);
        std::cout << "After Sort: \t";
        for (int i = 0; i < NumValues; ++i) std::cout << rands[i] << " ";
        std::cout << "\n";
    }

    return 0;
}

নোট করুন যে একটি if (compare) swap স্টেটমেন্টের পরিবর্তে, আমরা পরিষ্কারভাবে ন্যূনতম এবং সর্বাধিক জন্য টার্নারি অপারেটরগুলি কোড আউট করি। এটি শাখাবিহীন কোড ব্যবহার করে সংকলককে টোকা দিতে সহায়তা করে।

benchmarks

নিম্নলিখিত মানদণ্ডগুলি ঝনঝন -৩৩ এর সাথে সংকলিত হয়ে আমার ২০১২ সালের মাঝামাঝি ম্যাকবুক এয়ারে চলেছে।

এলোমেলো তথ্য বাছাই করা হচ্ছে

দারিওপির কোডের সাথে এটির তুলনা করে, 10 মাপের 1 মিলিয়ন 32-বিট ইন্টি অ্যারেগুলি সাজানোর জন্য এখানে মিলি সেকেন্ডের সংখ্যা রয়েছে:

হার্ডকোডযুক্ত বাছাই নেট 10: 88.774 এমএস
টেম্প্লেটেড বোস-নেলসন সাজান 10: 27.815 এমএস

এই টেম্পলেটেড পদ্ধতির ব্যবহার করে আমরা অন্যান্য সংখ্যক উপাদানের সংকলনের সময় বাছাই করা নেটওয়ার্কগুলিও তৈরি করতে পারি।

বিভিন্ন আকারের 1 মিলিয়ন অ্যারে বাছাই করার জন্য সময় (মিলিসেকেন্ডে)।
আকার 2, 4, 8 এর অ্যারেগুলির জন্য মিলিসেকেন্ডগুলির সংখ্যা যথাক্রমে 1.943, 8.655, 20.246।

নিবন্ধিত সন্নিবেশ সাজানোর জন্য গ্লেন টিটেলবাউমে ক্রেডিট।

এখানে 6 টি উপাদানের ছোট অ্যারেগুলির জন্য সাজানোর জন্য গড় ঘড়ি রয়েছে। এই প্রশ্নটিতে মানদণ্ডের কোড এবং উদাহরণগুলি পাওয়া যাবে:
দ্রুততম ধরণের দৈর্ঘ্যের 6 ইন্ট অ্যারে sort

Direct call to qsort library function       : 326.81
Naive implementation (insertion sort)       : 132.98
Insertion Sort (Daniel Stutzbach)           : 104.04
Insertion Sort Unrolled                     : 99.64
Insertion Sort Unrolled (Glenn Teitelbaum)  : 81.55
Rank Order                                  : 44.01
Rank Order with registers                   : 42.40
Sorting Networks (Daniel Stutzbach)         : 88.06
Sorting Networks (Paul R)                   : 31.64
Sorting Networks 12 with Fast Swap          : 29.68
Sorting Networks 12 reordered Swap          : 28.61
Reordered Sorting Network w/ fast swap      : 24.63
Templated Sorting Network (this class)      : 25.37

এটি 6 টি উপাদানের জন্য প্রশ্নের দ্রুততম উদাহরণ হিসাবে তত দ্রুত সম্পাদন করে।

বাছাই করা ডেটা বাছাইয়ের জন্য পারফরম্যান্স

প্রায়শই, ইনপুট অ্যারেগুলি ইতিমধ্যে বাছাই করা বা বেশিরভাগ বাছাই করা যেতে পারে।
এই ধরনের ক্ষেত্রে, সন্নিবেশ সাজানোর ভাল পছন্দ হতে পারে।

আপনি ডেটা উপর নির্ভর করে একটি উপযুক্ত বাছাই অ্যালগরিদম চয়ন করতে চাইতে পারেন।

মাপদণ্ডের জন্য ব্যবহৃত কোডটি এখানে পাওয়া যাবে


একটি শ্রেণিবদ্ধ নেটওয়ার্ক ব্যবহার করুন যার মধ্যে 4 টি গ্রুপের তুলনা রয়েছে, তাই আপনি এটি সিমডি রেজিস্টারে করতে পারেন। এক জোড়া প্যাকড মিনি / সর্বাধিক নির্দেশাবলী একটি প্যাকযুক্ত তুলনামূলক ফাংশন প্রয়োগ করে। দুঃখিত, এই পৃষ্ঠাটি আমার মনে থাকার মতো একটি পৃষ্ঠাগুলি সন্ধান করার জন্য আমার কাছে এখনই সময় নেই, তবে আশা করি সিমড বা এসএসই বাছাই করা নেটওয়ার্কগুলিতে অনুসন্ধান করা কিছু পরিবর্তন করবে।

x86 এসএসইতে 32 টি 32 বিট ইন্টের ভেক্টরগুলির জন্য প্যাকড -32 বিট-ইন্টিজার ন্যূনতম এবং সর্বাধিক নির্দেশনা রয়েছে। এভিএক্স 2 (হাসওয়েল এবং তার পরে) এর সাথে একই তবে 8 ইন্টের 256 বি ভেক্টর রয়েছে। দক্ষ সাফ করার নির্দেশাবলীও রয়েছে।

আপনার যদি স্বতন্ত্র ছোট আকারের অনেকগুলি থাকে তবে ভেক্টরগুলি ব্যবহার করে সমান্তরালে 4 বা 8 ধরণের করা সম্ভব হতে পারে। ESP। যদি আপনি এলোমেলোভাবে উপাদানগুলি বেছে নিচ্ছেন (যাতে সাজানো তথ্যটি যাইহোক মেমরির ক্ষেত্রে স্বাদযুক্ত হবে না), আপনি এলোমেলো এড়ানো এবং আপনার প্রয়োজনীয় ক্রমের সাথে তুলনা করতে পারেন। 4 (এভিএক্স 2: 8) থেকে 10 টি ইনটগুলির তালিকা থেকে সমস্ত ডেটা ধরে রাখতে 10 টি রেজিস্টার এখনও স্ক্র্যাচ স্পেসের জন্য 6 টি রেজি রেখে দেয়।

আপনার যদি সম্পর্কিত ডেটা বাছাই করতে প্রয়োজন হয় তবে ভেক্টর বাছাই করার নেটওয়ার্কগুলি কম দক্ষ। সেক্ষেত্রে সর্বাধিক দক্ষ উপায়টি হ'ল যে কোনও উপাদানগুলির পরিবর্তিত হয়েছে তার মুখোশ পাওয়ার জন্য একটি প্যাকড-তুলনা ব্যবহার করা এবং সেই মাস্কটি সম্পর্কিত ডেটার (রেফারেন্স) মিশ্রিত করতে ব্যবহার করুন।


একটি সন্নিবেশ সাজানোর জন্য 9 টির সবচেয়ে ভাল ক্ষেত্রে এবং 45 টির মধ্যে সবচেয়ে খারাপ (10 টি ইনপুট যা বিপরীত ক্রমে থাকে) দিয়ে 10 ইনপুটগুলি বাছাই করতে গড়ে 29,6 তুলনা প্রয়োজন।

একটি {9,6,1} শেলসোর্টের 10 ইনপুটগুলি বাছাই করতে গড়ে 25.5 তুলনা প্রয়োজন require সেরা কেসটি 14 তুলনা, সবচেয়ে খারাপ 34 এবং বিপরীত ইনপুটটি বাছাইয়ের জন্য 22 টি প্রয়োজন।

সুতরাং সন্নিবেশ বাছাইয়ের পরিবর্তে শেলসোর্ট ব্যবহার করে গড় কেস 14% কমে যায়। যদিও সেরা ক্ষেত্রে 56% বৃদ্ধি পেয়েছে সবচেয়ে খারাপ ক্ষেত্রে 24% হ্রাস পেয়েছে যা অ্যাপ্লিকেশনগুলিতে উল্লেখযোগ্য যেখানে সবচেয়ে খারাপ ক্ষেত্রে কর্মক্ষমতা চেক রাখা গুরুত্বপূর্ণ check বিপরীত কেসটি 51% হ্রাস পেয়েছে।

যেহেতু আপনি সন্নিবেশ সাজানোর সাথে পরিচিত বলে মনে হচ্ছে আপনি {9,6 for এর জন্য বাছাইকারী নেটওয়ার্ক হিসাবে অ্যালগরিদমটি প্রয়োগ করতে পারেন এবং তারপরে সন্নিবেশ সাজানোর ({1}) এ আলতো চাপুন:

i[0] with i[9]    // {9}

i[0] with i[6]    // {6}
i[1] with i[7]    // {6}
i[2] with i[8]    // {6}
i[3] with i[9]    // {6}

i[0 ... 9]        // insertion sort

যদিও ছোট ছোট অ্যারেগুলিতে কোনও নেটওয়ার্ক সাজানোর দ্রুত পরিবর্তন হওয়ার পক্ষে ভাল প্রতিক্রিয়া রয়েছে, তবে কখনও কখনও যথাযথভাবে অপ্টিমাইজ করা থাকলে আপনি সন্নিবেশ সাজানোর পক্ষেও বীট করতে পারবেন না। উদাহরণস্বরূপ ব্যাচ 2 টি উপাদান সহ সন্নিবেশ করান:

{
    final int a=in[0]<in[1]?in[0]:in[1];
    final int b=in[0]<in[1]?in[1]:in[0];
    in[0]=a;
    in[1]=b;
}
for(int x=2;x<10;x+=2)
{
    final int a=in[x]<in[x+1]?in[x]:in[x+1];
    final int b=in[x]<in[x+1]?in[x+1]:in[x];
    int y= x-1;

    while(y>=0&&in[y]>b)
    {
        in[y+2]= in[y];
        --y;
    }
    in[y+2]=b;
    while(y>=0&&in[y]>a)
    {
        in[y+1]= in[y];
        --y;
    }
    in[y+1]=a;
}





sorting-network