These three sorting algorithms grow at approximately the same rate according to this graph.
They are O(nlogn) on average. Selection sort and bubble sort are O(n^2)
Here's a graph of the O(nlogn) algorithms.
Wednesday, March 16, 2011
XBMC script for traffic cameras
XBMC is mighty cool. I use it all the time for my media ... and now for viewing traffic cameras. You can get the source from http://code.google.com/p/xmbc-traffic-cameras
XBMC trafffic camera screenshot |
Wednesday, March 9, 2011
Mergesort performance
Updated Sorting performance graph. My Quicksort implementation has weird variations. I'll have to look at the algorithm to figure out what's going on. Mergesort and Quicksort are practically equivalent for these set sizes.
Monday, March 7, 2011
Debian lenny ipv4 socket bind failing
A certain daemon that had been working elsewhere was refusing to bind to v4 on my box. Strace'ing it showed this
Notice the kernel says IPV4 binding is not supported! I am dual stacked! I had IPV4, I could ping the box and other hosts over IPV4. A quick look at my sysctl.d showedconnect(5, {sa_family=AF_UNSPEC, sa_data="\0\0\0\0\0\0\0\0\0\0\0\0\0\0"}, 16) = 0 connect(5, {sa_family=AF_INET, sin_port=htons(10042), sin_addr=inet_addr("0.0.0.0")}, 16) = -1 EAFNOSUPPORT (Address family not supported by protocol) close(5) = 0 socket(PF_INET, SOCK_DGRAM, IPPROTO_IP) = 5 connect(5, {sa_family=AF_INET, sin_port=htons(10042), sin_addr=inet_addr("0.0.0.0")}, 16) = 0 getsockname(5, {sa_family=AF_INET, sin_port=htons(60862), sin_addr=inet_addr("127.0.0.1")}, [16]) = 0 close(5) = 0 socket(PF_INET6, SOCK_STREAM, IPPROTO_TCP) = 5 setsockopt(5, SOL_SOCKET, SO_REUSEADDR, [1], 4) = 0 bind(5, {sa_family=AF_INET6, sin6_port=htons(10042), inet_pton(AF_INET6, "::", &sin6_addr), sin6_flowinfo=0, sin6_scope_id=0}, 28) = 0 listen(5, 5) = 0 write(2, "Config port: 10042\n", 19Config port: 10042
net.ipv6.bindv6only = 1
Switching this off (0) fixed the issue. You can also do it interactively by
echo 0 > /proc/sys/net/ipv6/bindv6only
Now everything works as expected.
Update:
This is weird. According to the kernel documentation
Update:
This is weird. According to the kernel documentation
bindv6only - BOOLEANWhich as far as I can tell shouldn't touch the IPV4 stack. I expected to find this sysctl check under net/ipv4 but grep can only find the checks in net/ipv6. Any ideas?
Default value for IPV6_V6ONLY socket option,
which restricts use of the IPv6 socket to IPv6 communication
only.
TRUE: disable IPv4-mapped address feature
FALSE: enable IPv4-mapped address feature
Default: FALSE (as specified in RFC2553bis)
Tuesday, March 1, 2011
Sorting in awk
I became interested in playing around with simple sorting algorithms and learning awk at the same time. Here is a quick roundup of the first three.
Divide and conquer rules the roost especially with large datasets. It would be nice to update it to graph these stats using gnuplot
Update: Graphing can now be done by graph_performance.sh. It generates a couple of stats files and the graph in tmp. It expects to find gnuplot in your path. Sort size can be changed by editing make_stats.sh directly.
$ bash make_stats.sh Doing 10 rounds of bubble_sort.awk with a dataset of 100 ints Average real time in seconds: 0.0151 Doing 10 rounds of quick_sort.awk with a dataset of 100 ints Average real time in seconds: 0.0476 Doing 10 rounds of selection_sort.awk with a dataset of 100 ints Average real time in seconds: 0.0048 Doing 10 rounds of bubble_sort.awk with a dataset of 500 ints Average real time in seconds: 0.3663 Doing 10 rounds of quick_sort.awk with a dataset of 500 ints Average real time in seconds: 0.2443 Doing 10 rounds of selection_sort.awk with a dataset of 500 ints Average real time in seconds: 0.0795 Doing 10 rounds of bubble_sort.awk with a dataset of 2500 ints Average real time in seconds: 9.7188 Doing 10 rounds of quick_sort.awk with a dataset of 2500 ints Average real time in seconds: 0.335 Doing 10 rounds of selection_sort.awk with a dataset of 2500 ints Average real time in seconds: 2.1556
Divide and conquer rules the roost especially with large datasets.
Selection sort is obviously much faster than bubblesort.
Probable reasons:
- Selection sort works on progressively smaller arrays with each iteration
- Comparisons in bubble sort are expensive compared to moving an element to the end of the array
- My implementation of bubble sort sucks.. (I'll check it again :( )
Update: Graphing can now be done by graph_performance.sh. It generates a couple of stats files and the graph in tmp. It expects to find gnuplot in your path. Sort size can be changed by editing make_stats.sh directly.
Subscribe to:
Posts (Atom)