|
Raqamli texnologiyalar vazirligi muhammad al-xorazmiy nomidagi toshkent axborot texnologiyalari universiteti qarshi filiali “kompyuter injiniringi” fakulteti
|
| bet | 12/13 | | Sana | 25.05.2024 | | Hajmi | 143,49 Kb. | | #253828 |
Bog'liq 1-amaliy ishC++Nusxalash
// Functor class for computing the distance between points.
class hash_distance
{
public:
hash_distance(const Point& reference)
: m_reference(reference)
{
}
size_t operator()(const Point& pt) const {
return euclidean_distance(pt, m_reference);
}
private:
Point m_reference;
};
C++Nusxalash
// Use hash_distance to compute the distance between points.
parallel_radixsort(begin(values), end(values), hash_distance(center));
Xesh funksiyasi butun son turini qaytarishi kerak ( std::is_integral::value ). trueBu butun son turi a ga aylantirilishi kerak size_t.
Ko'pgina hollarda, algoritm parallel_sortxotira ishlashi va tezligining optimal muvozanatini ta'minlaydi. Biroq, ma'lumotlar to'plamining o'lchami, mavjud protsessorlar soni va taqqoslash funktsiyasining murakkabligi oshishi bilan parallel_buffered_sortyoki algoritm parallel_radixsortyanada samarali ishlashi mumkin. Har qanday stsenariyda eng mos saralash algoritmini aniqlashning eng yaxshi usuli tajriba o'tkazish va odatiy kompyuter konfiguratsiyasidagi odatiy ma'lumotlarni saralash uchun qancha vaqt kerakligini o'lchashdir. Quyida saralash strategiyasini tanlash bo'yicha ko'rsatmalar keltirilgan.
Ma'lumotlar to'plami hajmi. Ushbu maqolada kichik ma'lumotlar to'plami 1000 dan kam elementni o'z ichiga oladi, o'rta ma'lumotlar to'plami 10 000 dan 100 000 tagacha elementni va katta ma'lumotlar to'plami 100 000 dan ortiq narsalarni o'z ichiga oladi.
Taqqoslash funktsiyasi yoki xesh funksiyasi tomonidan bajarilgan ish hajmi.
Mavjud hisoblash resurslari miqdori.
Ma'lumotlar to'plamining xususiyatlari. Misol uchun, bitta algoritm qisman tartiblangan ma'lumotlarda yaxshi ishlashi mumkin, ammo ma'lumotlar umuman saralanmaganda unchalik yaxshi emas.
Blok hajmi. Ixtiyoriy argument _Chunk_sizealgoritm saralashning paralleldan ketma-ket amalga oshirilishiga qachon o'tishini aniqlaydi, chunki u butun saralash vazifasini kichikroq ish birliklariga ajratadi. Misol uchun, agar siz 512 ni belgilasangiz, ish birligi 512 yoki undan kam elementni o'z ichiga olgan bo'lsa, algoritm ketma-ket amalga oshirishga o'tadi. Ketma-ket amalga oshirish umumiy ish faoliyatini yaxshilashi mumkin, chunki u ma'lumotlarni parallel ravishda qayta ishlash uchun zarur bo'lgan qo'shimcha ishlarni yo'q qiladi.
Kichkina ma'lumotlar to'plamida parallel tartiblash, hatto sizda juda ko'p hisoblash resurslariga ega bo'lsangiz ham yoki taqqoslash yoki xesh funktsiyasi nisbatan katta hajmdagi ishlarni bajarsa ham iqtisodiy jihatdan samarali bo'lmasligi mumkin. std::sort funktsiyasidan kichik ma'lumotlar to'plamini saralash uchun foydalanish mumkin . ( parallel_sortva ma'lumotlar to'plamidan kattaroq blok hajmini belgilashda parallel_buffered_sortchaqiriladi , biroq u O(N) bo'sh joy ajratishni talab qiladi, bu blokirovkalash ziddiyatlari yoki xotira taqsimoti tufayli qo'shimcha vaqt talab qilishi mumkin.)sortparallel_buffered_sort
Agar siz xotira resurslarini tejashingiz kerak bo'lsa yoki xotira ajratuvchisi blokirovkaga duchor bo'lsa, o'rta o'lchamdagi ma'lumotlar to'plamini saralash uchun algoritmdan foydalaning parallel_sort. parallel_sortqo'shimcha joy talab qilmaydi; boshqa algoritmlar uchun O(N) maydoni talab qilinadi.
parallel_buffered_sortO'rta o'lchamdagi ma'lumotlar to'plamlarini saralash va qo'shimcha O(N) bo'sh joy talablarini qo'llashda foydalaniladi . Algoritm, parallel_buffered_sortayniqsa, katta miqdordagi hisoblash resurslari va resurslarni ko'p talab qiladigan taqqoslash funktsiyasi yoki xesh funktsiyasi mavjud bo'lganda samarali bo'ladi.
parallel_radixsortKatta maʼlumotlar toʻplamlarini saralash va qoʻshimcha O(N) boʻsh joy talablarini qoʻllashda foydalaniladi . Algoritm, parallel_radixsortayniqsa, taqqoslash funktsiyasi resurslarni ko'p talab qilganda, shuningdek, taqqoslash funktsiyasi ham, xesh funksiyasi ham resurslarni ko'p talab qilganda samarali bo'ladi.
Diqqat!
Yaxshi xesh funktsiyasini amalga oshirish uchun ma'lumotlar to'plamining diapazoni va ma'lumotlar to'plamining har bir elementini uning tegishli belgilanmagan qiymatiga qanday aylantirish kerakligi haqida ma'lumot kerak. Xesh operatsiyalari imzolanmagan qiymatlarda ishlaganligi sababli, agar siz imzosiz xesh qiymatlarini ololmasa, boshqa tartiblash strategiyasini ko'rib chiqing.
Quyidagi misol tasodifiy ma'lumotlarning bir xil katta to'plamidagi parallel_sort, parallel_buffered_sortva algoritmlarining ishlashini taqqoslaydi .parallel_radixsort
C++Nusxalash
// choosing-parallel-sort.cpp
// compile with: /EHsc
#include
#include
#include
#include
using namespace concurrency;
using namespace std;
// Calls the provided work function and returns the number of milliseconds
// that it takes to call that function.
template
__int64 time_call(Function&& f)
{
__int64 begin = GetTickCount();
f();
return GetTickCount() - begin;
}
const size_t DATASET_SIZE = 10000000;
// Create
// Creates the dataset for this example. Each call
// produces the same predefined sequence of random data.
vector GetData()
{
vector data(DATASET_SIZE);
generate(begin(data), end(data), mt19937(42));
return data;
}
int wmain()
{
// Use std::sort to sort the data.
auto data = GetData();
wcout << L"Testing std::sort...";
auto elapsed = time_call([&data] { sort(begin(data), end(data)); });
wcout << L" took " << elapsed << L" ms." <
// Use concurrency::parallel_sort to sort the data.
data = GetData();
wcout << L"Testing concurrency::parallel_sort...";
elapsed = time_call([&data] { parallel_sort(begin(data), end(data)); });
wcout << L" took " << elapsed << L" ms." <
// Use concurrency::parallel_buffered_sort to sort the data.
data = GetData();
wcout << L"Testing concurrency::parallel_buffered_sort...";
elapsed = time_call([&data] { parallel_buffered_sort(begin(data), end(data)); });
wcout << L" took " << elapsed << L" ms." <
// Use concurrency::parallel_radixsort to sort the data.
data = GetData();
wcout << L"Testing concurrency::parallel_radixsort...";
elapsed = time_call([&data] { parallel_radixsort(begin(data), end(data)); });
wcout << L" took " << elapsed << L" ms." <}
/* Sample output (on a computer that has four cores):
Testing std::sort... took 2906 ms.
Testing concurrency::parallel_sort... took 2234 ms.
Testing concurrency::parallel_buffered_sort... took 1782 ms.
Testing concurrency::parallel_radixsort... took 907 ms.
*/
Ushbu misol, saralash paytida O(N) bo'sh joyini ajratish mumkinligini nazarda tutadi, eng yaxshisi parallel_radixsortushbu kompyuter konfiguratsiyasida ushbu ma'lumotlar to'plamida.
|
|
Bosh sahifa
Aloqalar
Bosh sahifa
Raqamli texnologiyalar vazirligi muhammad al-xorazmiy nomidagi toshkent axborot texnologiyalari universiteti qarshi filiali “kompyuter injiniringi” fakulteti
|
