MESSAGE
| DATE | 2016-11-13 |
| FROM | Ruben Safir
|
| SUBJECT | Subject: [Learn] merge sort in parallel assignment
|
From learn-bounces-at-nylxs.com Sun Nov 13 11:20:17 2016
Return-Path:
X-Original-To: archive-at-mrbrklyn.com
Delivered-To: archive-at-mrbrklyn.com
Received: from www.mrbrklyn.com (www.mrbrklyn.com [96.57.23.82])
by mrbrklyn.com (Postfix) with ESMTP id A9C1F161312;
Sun, 13 Nov 2016 11:20:16 -0500 (EST)
X-Original-To: learn-at-nylxs.com
Delivered-To: learn-at-nylxs.com
Received: from [10.0.0.62] (flatbush.mrbrklyn.com [10.0.0.62])
by mrbrklyn.com (Postfix) with ESMTP id 97B67160E77;
Sun, 13 Nov 2016 11:20:13 -0500 (EST)
To: Samir Iabbassen , learn-at-nylxs.com
From: Ruben Safir
Message-ID: <1d19cb98-d071-2914-bf6a-d8e4d3bc81d9-at-mrbrklyn.com>
Date: Sun, 13 Nov 2016 11:20:13 -0500
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:45.0) Gecko/20100101
Thunderbird/45.4.0
MIME-Version: 1.0
Content-Type: multipart/mixed; boundary="------------8FBE83C48F5D221F26A753F5"
Subject: [Learn] merge sort in parallel assignment
X-BeenThere: learn-at-nylxs.com
X-Mailman-Version: 2.1.17
Precedence: list
List-Id:
List-Unsubscribe: ,
List-Archive:
List-Post:
List-Help:
List-Subscribe: ,
Errors-To: learn-bounces-at-nylxs.com
Sender: "Learn"
This is a multi-part message in MIME format.
--------------8FBE83C48F5D221F26A753F5
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 7bit
So in terms of the HW this is done, although I'm not happy this the
code. It errors on me when the merge is too large, likely due to a
combination of compile deficiency and my coding not doing enough error
checking. It might help to define the standard c++ to 11, but I'm not
certain of that. I need some sleep.
Reuvain
--
So many immigrant groups have swept through our town
that Brooklyn, like Atlantis, reaches mythological
proportions in the mind of the world - RI Safir 1998
http://www.mrbrklyn.com
DRM is THEFT - We are the STAKEHOLDERS - RI Safir 2002
http://www.nylxs.com - Leadership Development in Free Software
http://www2.mrbrklyn.com/resources - Unpublished Archive
http://www.coinhangout.com - coins!
http://www.brooklyn-living.com
Being so tracked is for FARM ANIMALS and and extermination camps,
but incompatible with living as a free human being. -RI Safir 2013
--------------8FBE83C48F5D221F26A753F5
Content-Type: text/x-chdr;
name="msort.h"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
filename="msort.h"
/*
* =====================================================================================
*
* Filename: msort.h
*
* Description: Header File for Parrell Msort algorthm
*
* Version: 1.0
* Created: 11/09/2016 04:28:51 AM
* Revision: none
* Compiler: gcc
*
* Author: Ruben Safir
* Company: NYLXS Inc
*
* =====================================================================================
*/
#ifndef MSORT_INC
#define MSORT_INC
namespace merge{
int min(int x, int y);
void track(int , int, int * );
void merge(int j, int l, int m, int k, int * parent);
}
#endif /* ----- #ifndef MSORT_INC ----- */
--------------8FBE83C48F5D221F26A753F5
Content-Type: text/plain; charset=UTF-8;
name="makefile"
Content-Transfer-Encoding: base64
Content-Disposition: attachment;
filename="makefile"
Q1hYOj1nKysgCkNYWEZMQUdTOj0tV2FsbCAtZ2dkYiAgLXBnIC1wdGhyZWFkCgpMREZMQUdT
Oj0tTC91c3IvbG9jYWwvbGliL215c3FsIC1sbXlzcWxwcCAtbG15c3FsY2xpZW50Cgptc29y
dCA6CW1zb3J0Lm8gbWFpbi5vCgkke0NYWH0gICR7Q1hYRkxBR1N9IC1vIG1zb3J0IG1zb3J0
Lm8gbWFpbi5vCgptYWluLm8gOgltYWluLmNwcAoJJHtDWFh9ICAke0NYWEZMQUdTfSAtbyBt
YWluLm8gLWMgbWFpbi5jcHAJCgptc29ydC5vIDoJbXNvcnQuY3BwCW1zb3J0LmgKCSR7Q1hY
fSAgJHtDWFhGTEFHU30gLWMgbXNvcnQuY3BwCgpjbGVhbgk6IAoJcm0gbm9kZXMgKi5vIG1h
a2UuZGVwcwoJdG91Y2ggKi5jcHAgKi5oCgppbmNsdWRlIG1ha2UuZGVwcwptYWtlLmRlcHM6
ICouY3BwIDsgZ2NjIC1NICouY3BwID4kQAo=
--------------8FBE83C48F5D221F26A753F5
Content-Type: text/x-c++src;
name="msort.cpp"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
filename="msort.cpp"
#include "msort.h"
#include
#include
namespace merge{
int min(int x, int y){
int ret;
x std::cout << x << ":" << y << "==>" << ret << std::endl;
return ret;
}
void merge(int j, int l, int m, int k, int * value){
int size = (k-j) + 1;
std::cout << "Allocating scratch ==>" << size << std::endl;
int * scratch = new int[size];
int l_pos1 = j;
int l_pos2 = l;
int r_pos1 = m;
int r_pos2 = k;
int i = 0;
std::cout << "Scratch index: " << i << std::endl;
std::cout << "l_pos1: " << l_pos1 << "\tr_pos1: " << r_pos1 << std::endl;
std::cout << "l_pos2: " << l_pos2 << "\tr_pos2: " << r_pos2 << std::endl;
int l_next = l_pos1;
int r_next = r_pos1;
int cur = -1;//cursor rest position
int cursor[3] = {cur, l_next, r_next};
while((cursor[1] <= l_pos2) && (cursor[2] <= r_pos2)) {
std::cout << "Positions" << cursor[0] << ":" << cursor[1] << ":" << cursor[2] << std::endl;
std::cout << "Values " << value[cursor[1]] << ":" << value[cursor[2]] << std::endl;
if(value[cursor[1]] <= value[cursor[2]]) {
scratch[i] = value[cursor[1]];
cursor[0] = cursor[1];
cursor[1]++;
}else if(value[cursor[1]] > value[cursor[2]]){
scratch[i] = value[cursor[2]];
cursor[0] = cursor[2];
cursor[2]++;
}
std::cout << "Positions" << cursor[0] << ":" << cursor[1] << ":" << cursor[2] << std::endl;
std::cout << "Values " << value[cursor[1]] << ":" << value[cursor[2]] << std::endl;
i++;
}
//we hit the top
while(1){
std::cout << "clearing data...";
if(cursor[2] <= r_pos2 ){
scratch[i] = value[cursor[2]];
i++;
cursor[2]++;
}else if(cursor[1] <= l_pos2){
scratch[i] = value[cursor[1]];
i++;
cursor[1]++;
}else{
break;
}
}
std::cout << "done" << std::endl;
//copy scratch to the array
std::cout << "copying scratch" << std::endl;
for(int pos = j, i=0; i <= (k-j); pos++, i++){
std::cout << i << " : " << scratch[i] <<" to position " << pos << std::endl;
value[pos] = scratch[i];
}
std::cout << "free scratch" << std::endl;
delete[] scratch;
std::cout << "done with scratch" << std::endl;
return;
}
//j is far left of array
//k is far right of array
//l is middle of array - right of left child array
//m is middle + 1 of the array - left of right child array
//
// j l m k
//_____________________________________
//| 0| 1| 2| 3| 4| 5| 6| 7| 8| 9| 10| 11|
//--------------------------------------
//
void track(int j, int k, int * parent )
{
//std::cout << "\n j is far left of array\n k is far right of array\n l is middle of array - right of left child array\n m is middle + 1 of the array - left of right child array\n\n j l m k\n _____________________________________\n | 0| 1| 2| 3| 4| 5| 6| 7| 8| 9| 10| 11|\n --------------------------------------\n ";
std:: cout << "======================" << std::endl;
std::cout << "|| __NEW NODE__ ||\n|| j =>" << j << " " << "k=> " << k << " ||" << std::endl;
std:: cout << "======================" << std::endl;
int length = k - j;
int l = j + (length / 2);
int m = l + 1;
if(j == k )
{
std::cout << "\n\n\n**********RETURN**********" << std::endl;
return;
}
std::cout << "Left Branch: j =>" << j << "\t" << "l => " << l << std::endl;
std::cout << "Right Branch: m =>" << m << "\t" << "k => " << k << std::endl;
std::cout << std::endl;
std::cout << std::endl;
std::cout << std::endl;
std::cout << "***Enter left : j =>" << j << "\t" << "l => " << l << "***" << std::endl;
std::thread sinetro( track, j, l, parent ) ;
std::cout << "Returned to Node j => " << j << "\tk=> " << k << " From the left" << std::endl;
std::cout << std::endl;
std::cout << "***Enter right : m =>" << m << "\t" << "k => " << k << std::endl;
std::thread dextro( track, m, k, parent);
std::cout << "Returned to Node j => " << j << "\tk=> " << k << " From the right" << std::endl;
std::cout << "**********MERGE**********" << std::endl;
sinetro.join();
dextro.join();
merge(j,l,m,k, parent);
}
}//end namespace
--------------8FBE83C48F5D221F26A753F5
Content-Type: text/x-c++src;
name="main.cpp"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
filename="main.cpp"
/*
* =====================================================================================
*
* Filename: main.cpp
*
* Description: merge sort main
*
* Version: 1.0
* Created: 11/09/2016 09:33:20 AM
* Revision: none
* Compiler: gcc
*
* Author: Ruben Safir
* Company: NYLXS
*
* =====================================================================================
*/
#include
#include "msort.h"
#include
#include
#include
#define SIZE 10000
int main(int argv, char **argc)
{
using namespace std;
int *data = new int[SIZE];
// int *cache = new int[SIZE];
struct timespec now;
clock_gettime(CLOCK_REALTIME, &now);
long seed = now.tv_nsec;
srand( (unsigned int) seed);
for(int i = 0; i < SIZE; i++){
data[i] = rand() % 1000000;
cout << data[i] << "\t";
}
cout << endl;
cout << "________________________________________________________" << endl;
cout << "***Size of Array " << SIZE << "****" << endl;
cout << "____________________" << endl;
cout << "Array Before" << endl;
for(int i = 0; i < SIZE; i++){
cout << "--------------------" << endl;
cout << "| " << i << " ==> " << data[i] << "\t |" << endl;
}
cout << "--------------------" << endl;
cout << "--------------------" << endl;
merge::track(0, SIZE - 1, data);
cout << "____________________" << endl;
cout << "Array AFTER" << endl;
for(int i = 0; i < SIZE; i++){
cout << "--------------------" << endl;
cout << "| " << i << " ==> " << data[i] << "\t |" << endl;
}
cout << "--------------------" << endl;
cout << "--------------------" << endl;
return 0;
}
--------------8FBE83C48F5D221F26A753F5
Content-Type: text/plain; charset="us-ascii"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Content-Disposition: inline
_______________________________________________
Learn mailing list
Learn-at-nylxs.com
http://lists.mrbrklyn.com/mailman/listinfo/learn
--------------8FBE83C48F5D221F26A753F5--
|
|
