Lucas Daniel

Pessoal abaixo o mergesort .... agora preciso de ajuda para paralelizar ele ... tipo vou paralelizar a parte onde divide o vetor em partes .... +- isso ? #include <stdio.h> #include <stdlib.h> #include <time.h> //Autores: Lucas Daniel Küster Vieira, Ronneesley int main(int argc, char *argv[]) { srand(time(NULL)); int i, tam = 20; int vet[tam]; for (i=0; i<tam; i++){ vet = rand() % 50; } printf("Vetor desordenado:\n\n"); for (i = 0; i < tam; i++){ if (i != 0) printf(", "); printf("%d", vet); } //chama o método ordenarMergeSortIterativa(tam, vet); printf("\n\nVetor ordenado: \n\n"); for (i = 0; i < tam; i++){ if (i != 0) printf(", "); printf("%d", vet); } printf("\n\n"); system("PAUSE"); return 0; } void intercala(int p, int q, int r, int v[]){ int i, j, k, *w; w = malloc( (r - p) * sizeof (int) ); i = p; j = q; k = 0; while (i < q && j < r){ if (v <= v[j]) w[k++] = v[i++]; else w[k++] = v[j++]; } while (i < q) w[k++] = v[i++]; while (j < r) w[k++] = v[j++]; for (i = p; i < r; i++) v = w[i - p]; free(w); } int ordenarMergeSortIterativa(int n, int v[]){ int p, r, b = 1; while (b < n){ p = 0; while (p + b < n){ r = p + 2 * b; if (r > n) r = n; intercala(p, p + b, r, v); p = p + 2 * b; } b = 2 * b; } }

Aê pessoal preciso de uma mão .... para implementar o algoritmo d ordenação o mergesort em paralelo openMP .... quem puder me dar dicas como iniciar agradeço .... abrass

#!/usr/bin/env python """ Some of these algorithms are taken rather literally from Knuth - as a consequence they're not very Pythonic, and not terribly readable. In some cases I've modified the algorithm to make sure that all items are present once and only once in the array of sortables every time we memoizePath (i.e. that the algorithm is in-place). Page numbers refer to The Art of Computer Programming vol. 3. This code is in the public domain - do whatever you like with it. """ import random, math, sys from optparse import OptionParser import cairo def intRGB(r, g, B): return (r/255.0, g/255.0, b/255.0) HIGHLIGHT=intRGB(0xff, 0x72, 0x72) class NiceCtx(cairo.Context): defaultBorderColour = intRGB(0x7d, 0x7d, 0x7d) def stroke_border(self, border): src = self.get_source() width = self.get_line_width() self.set_source_rgba(*self.defaultBorderColour) self.stroke_preserve() self.set_source(src) self.set_line_width(width - (border * 2)) self.stroke() class Canvas: def __init__(self, width, height): self.width, self.height = width, height self.surface = cairo.ImageSurface(cairo.FORMAT_ARGB32, width, height) self.background(1, 1, 1) def ctx(self): return NiceCtx(self.surface) def background(self, r, g, B): c = self.ctx() c.set_source_rgb(r, g, B) c.rectangle(0, 0, self.width, self.height) c.fill() c.stroke() def save(self, fname, vertical): """ Save the image to a file. If vertical is true, rotate by 90 degrees. """ if vertical: surf = cairo.ImageSurface(cairo.FORMAT_ARGB32, self.height, self.width) ctx = cairo.Context(surf) ctx.translate(self.height*0.5, self.width*0.5) ctx.rotate(math.pi/2) ctx.translate(-self.width*0.5, -self.height*0.5) ctx.set_source_surface(self.surface) ctx.paint() else: surf = self.surface surf.write_to_png(fname) class PathDrawer: def __init__(self, width, height, line, border, highlights): self.width, self.height = width, height self.line, self.border = line, border self.highlights = highlights def _lineCoords(self, elem, l): init = 0.02 # Proportional initial length lst = [] xscale = (1.0-init)/len(elem.path) yscale = 1.0/l lst.append((0, yscale/2 + (yscale * elem.path[0]))) lst.append((init, yscale/2 + (yscale * elem.path[0]))) for i, v in enumerate(elem.path): lst.append(((xscale * i) + init, yscale/2 + (yscale * v))) lst.append((1, lst[-1][1])) return lst def draw(self, algo, fname, vertical=False): c = Canvas(self.width, self.height + 20) # Clearer when drawn in this order l = reversed(algo.lst) ctx = c.ctx() for elem in l: for i in self._lineCoords(elem, len(algo.lst)): ctx.line_to(self.width * i[0], self.height * i[1]) ctx.set_line_cap(cairo.LINE_CAP_BUTT) ctx.set_line_join(cairo.LINE_JOIN_ROUND) if elem.i in self.highlights: ctx.set_source_rgb(*HIGHLIGHT) else: x = 1 - (float(elem.i)/len(algo.lst)*0.7) ctx.set_source_rgb(x, x, x) ctx.set_antialias(cairo.ANTIALIAS_SUBPIXEL) ctx.set_line_width(self.line) ctx.stroke_border(self.border) ctx.select_font_face("Sans") ctx.set_font_size(15) ctx.set_source_rgb(0.3, 0.3, 0.3) ctx.move_to(5, self.height + 15) # Don't put the number of comparisons in until we've revisited the algorithms # to make sure the figures are sensible # ctx.text_path(algo.name + " " + "[%s comparisons]"%algo.comparisons) ctx.text_path(algo.name) ctx.fill() c.save("%s.png"%fname, vertical) class Sortable: comparisons = 0 def __init__(self, i): self.i = i self.path = [] def __cmp__(self, other): Sortable.comparisons += 1 return cmp(self.i, other.i) def __repr__(self): return str(self.i) class TrackList: def __init__(self, itms, wrapper=None): self.lst = [sortable(i) for i in itms] if wrapper: self.lst = [wrapper(i) for i in self.lst] self.start = self.lst[:] def reset(self): Sortable.comparisons = 0 self.lst = self.start[:] def __getattr__(self, attr): return getattr(self.lst, attr) def memoizePath(self): for i, v in enumerate(self): v.path.append(i) class Algorithm: def __init__(self, entries): self.lst = self.makeList(entries) self.lst.reset() self.lst.memoizePath() self.sort(self.lst) self.comparisons = Sortable.comparisons def makeList(self, entries): return TrackList(entries) # The TimSort stuff can be done more neatly, by inspecting the list from witin # the __cmp__ method. This way we can also perform the entire trick with only # one sort. Then again, I'm lazy, and this works. ;) class TimBreak(Exception): pass class TimWrapper: comparisons = 0 limit = 0 def __init__(self, n): self.n = n def __cmp__(self, other): if TimWrapper.comparisons > TimWrapper.limit: raise TimBreak TimWrapper.comparisons += 1 return cmp(self.n, other.n) def __getattr__(self, attr): return getattr(self.n, attr) class Tim(Algorithm): name = "timsort" def makeList(self, entries): return TrackList(entries, TimWrapper) def sort(self, lst): prev = [i.n for i in lst] while 1: TimWrapper.comparisons = 0 TimWrapper.limit += 1 lst.reset() try: lst.sort() except TimBreak: if prev != [i.n for i in lst]: lst.memoizePath() prev = [i.n for i in lst] else: lst.memoizePath() break class Bubble(Algorithm): name = "bubblesort" def sort(self, lst): bound = len(lst)-1 while 1: t = 0 for j in range(bound): if lst[j] > lst[j+1]: lst[j], lst[j+1] = lst[j+1], lst[j] lst.memoizePath() t = j if t == 0: break bound = t class ListInsertion(Algorithm): """ Broadly based on the list insertion sort on p 97. """ name = "insertionsort" def sort(self, lst): for i in range(1, len(lst)): for j in range(i): if lst < lst[j]: x = lst.pop(i) lst.insert(j, x) lst.memoizePath() class Shell(Algorithm): """ Shell's method, p. 84 """ name = "shellsort" def sort(self, lst): t = [5, 3, 1] for h in t: for j in range(h, len(lst)): i = j - h r = lst[j] flag = 0 while i > -1: if r < lst: flag = 1 lst[i+h], lst = lst, lst[i+h] i -= h lst.memoizePath() else: break lst[i+h] = r class Selection(Algorithm): """ Selection Sort, p. 139 """ name = "selectionsort" def sort(self, lst): for j in range(len(lst)-1, 0, -1): m = lst.index(max(lst[:j])) # No, this is not efficient ;) lst[m], lst[j] = lst[j], lst[m] lst.memoizePath() class Heap(Algorithm): """ Algorithm from http://en.wikipedia.org/wiki/Heapsort """ name = "heapsort" def sift(self, lst, start, count): root = start while (root * 2) + 1 < count: child = (root * 2) + 1 if child < (count-1) and lst[child] < lst[child+1]: child += 1 if lst[root] < lst[child]: lst[root], lst[child] = lst[child], lst[root] lst.memoizePath() root = child else: return def sort(self, lst): start = (len(lst)/2)-1 end = len(lst)-1 while start >= 0: self.sift(lst, start, len(lst)) start -= 1 while end > 0: lst[end], lst[0] = lst[0], lst[end] lst.memoizePath() self.sift(lst, 0, end) end -= 1 class Quick(Algorithm): """ http://www.cs.indiana.edu/classes/a348-dge...tAlgorithm.java """ name = "quicksort" def sort(self, lst, left=0, right=None): if right is None: right = len(lst) - 1 l = left r = right if l <= r: mid = lst[(left+right)/2] while l <= r: while l <= right and lst[l] < mid: l += 1 while r > left and lst[r] > mid: r -= 1 if l <= r: lst[l], lst[r] = lst[r], lst[l] lst.memoizePath() l+=1 r-=1 if left < r: self.sort(lst, left, r) if l < right: self.sort(lst, l, right) algorithms = [Tim, Quick, Heap, Selection, ListInsertion, Bubble, Shell] def main(): usage = "usage: %prog [options]" parser = OptionParser(usage) parser.add_option( "-a", dest="algorithm", default=[], type="choice", action="append", choices=[i.name for i in algorithms], help="Draw only a named algorithm." ) parser.add_option( "-n", dest="numelements", default="20", type="int", help="Generate a random sorting sequence of length n" ) parser.add_option( "-f", dest="readfile", help="Read data from file" ) parser.add_option( "-o", dest="ofname", help="Output file name. Only usable when a single algorithm is being drawn.", default="" ) parser.add_option( "-d", dest="dump", default=False, action="store_true", help="Dump sequence" ) parser.add_option( "-x", dest="width", type="int", default=None, help="Image width" ) parser.add_option( "-y", dest="height", type="int", default=None, help="Image height" ) parser.add_option( "-l", dest="line", type="int", default=6, help="Total line width" ) parser.add_option( "-b", dest="border", type="int", default=1, help="Border width" ) parser.add_option( "-r", dest="rotate", default=False, action="store_true", help="Rotate images 90 degrees" ) parser.add_option( "-i", dest="highlight", type="int", default=[], action="append", help="Highlight digit N (0-based). Can be passed muiltiple times." ) options, args = parser.parse_args() if args: parser.error("Script takes no arguments.") if options.readfile: txt = file(options.readfile).read().split() lst = [int(i) for i in txt] else: lst = range(options.numelements) random.shuffle(lst) if options.highlight: if max(options.highlight) > (len(lst)-1): parser.error("Highlight element > than list length.") if options.dump: for i in lst: print i, if not options.height: options.height = (options.line + options.border + 5) * len(lst) if not options.width: options.width = int(options.height * 3) ldrawer = PathDrawer( options.width, options.height, options.line, options.border, options.highlight, ) if options.algorithm: selected = [i.lower() for i in options.algorithm] if options.algorithm: todraw = [i for i in algorithms if i.name in options.algorithm] else: todraw = [i for i in algorithms] if options.ofname and len(todraw) > 1: parser.error("Cannot specify output file name when drawing more than one algorithm.") for i in todraw: a = i(lst) ldrawer.draw(a, options.ofname or a.name, options.rotate) if __name__ == "__main__": main()