Tag Archives: Sorting

Intel Threading Challenge #1

Posted by on July 10, 2009 No comments

While I never participated in the Intel Threading Challenge, I still find the problems really intriguing. Why? Because they are problems designed to test threaded development which is not only cool but is also going to play a large part in the future of computing. I would call all this problem for the most part concurrent, not parallel. Why? Read this and you'll understand completely. Now, on to the challenge!

Problem # 1 states:

Problem description: Given a set of unsorted items with keys that can be considered as a binary representation of an integer, the bits within the key can be used to sort the set of items. This method of sorting is known as Radix Sort.

Write a program that includes a threaded version of a Radix Sort algorithm that sorts the keys read from an input file, then output the sorted keys to another file. The input and output file names shall be the first and second arguments on the command line of the application execution.

The first line of the input text file is the total number of keys (N) to be sorted; this is followed by N keys, one per line, in the file.  A key will be a seven-character string made up of printable characters not including the space character (ASCII 0x20). The number of keys within the file is less than 2^31 - 1.  Sorted output must be stored in a text file, one key per line.

Timing: If you put timing code into your application to time the sorting process and report the elapsed time, this time will be used for scoring.  If no timing code is added, the entire execution time (including time for input and output) will be used for scoring.


Example Input file:
8
H@skell
surVEYs
sysTEMS
HASKELL
Surveys
1234567
SURveys
systEMS

Example Output file:
1234567
H@skell
HASKELL
SURveys
Surveys
surVEYs
sysTEMS
systEMS

My solution (both serial and parallel):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;
using System.Diagnostics;
using System.Threading;
using System.IO;
 
namespace RadixSort {
 
    class Program {
        static void Main(string[] args) {
            StreamReader sr;
            int length;
            TimeSpan serial, parallel;
            sr = File.OpenText(@"C:\Documents and Settings\rgreen\Desktop\Threading\Threading\rsTestK100.dat");
 
            length = Convert.ToInt32(sr.ReadLine().Trim());
            string[] values = new string[length];
            string[] newValues = new string[length];
            for(int x = 0; x < length; x++) {
                values[x] = sr.ReadLine().Trim();
            }
 
            Stopwatch sw = new Stopwatch();
 
            //
            // Serial
            //
            sw.Start();
            RadixSort(values).CopyTo(newValues, 0);
            sw.Stop();
            serial = sw.Elapsed;
 
            //
            // Parallel
            //
            sw.Reset();
            sw.Start();
            ParallelRadixSort(values).CopyTo(newValues, 0);
            sw.Stop();
            parallel = sw.Elapsed;
 
 
            Console.WriteLine("Serial Time: " + serial);
            Console.WriteLine("Parallel Time: " + parallel);
            Console.ReadLine();
        }
 
        public static string[] ParallelRadixSort(string[] array) {
            int length = array.Length;
 
            Parallel.For(0, array[0].Length - 1, delegate(int curRadix) {
                int index = array[0].Length - 1 - curRadix;
                array = new MergeSort(array, array[0].Length - 1 - index).Results;
            });
 
            return array;
        }
 
        public static string[] RadixSort(string[] array) {
 
            int length = array.Length;
 
            for(int curRadix = array[0].Length - 1; curRadix >= 0; curRadix--) {
                array = new MergeSort(array, array[0].Length - 1 - curRadix).Results;
            }
 
            return array;
        }
    }
}

And there you have it!

Sorting a XMLListCollection in Flex

Posted by on October 20, 2008 4 comments

Recently I had the need to sort and XMLListCollection in Flex. This seems to be a rather straightforward task. I had a XMLList where each item had an element called 'Image'. I wanted to sort by the value of the 'Image' node in descending order.

The original code was as follows:

1
2
3
4
5
6

var z:XMLListCollection = new XMLListCollection(xmlList);
var mySort:Sort = new Sort();
 
mySort.fields = [new SortField("Image",false,true)];
z.sort = mySort;
z.refresh();

This seemed to work fine for some time. Eventually, the client came back and alerted us that values were now be returned incorrectly. In fact, the set of values being returned was simply a repetition of the value of the first node of the first element. How can this be corrected? Quite simply actually. I first decided not to use the built in sorting capabilities of ActionScript. I found a function and modified the code as follows (the code I modified can be found <a href="http://www.nuff-respec.com/technology/sort-xml-by-attribute-in-actionscript-3">here</a>):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

public static function sortXMLByAttribute($xml:XMLList, $element:String, $options:Object = null):XMLList{
 
	//store in array to sort on
	var xmlArray:Array = new Array();
 
	for each(var item:XML in $xml){
		var object:Object = {
			data	: item,
			order	: item.elements($element)
		};
		xmlArray.push(object);
	}
 
	//sort using the power of Array.sortOn()
	xmlArray.sortOn('order',$options);
 
	//create a new XMLList with sorted XML
	var sortedXmlList:XMLList = new XMLList();
 
	for each(var xmlObject:Object in xmlArray ){
		sortedXmlList += xmlObject.data;
	}
 
	return sortedXmlList.copy();
}

The I changed my original code to the following:

1

var z:XMLListCollection = new XMLListCollection(sortXMLByAttribute(xmlList,"Image",Array.DESCENDING));

And that solved the problem. So why the issue in the first place? I'm not really 100% sure at the moment, but I'm looking into it. Maybe someone else out there has some input?