- #1
Monte_Carlo
- 72
- 0
Hi,
Knuth's TAOCP exercise 5.1.1-6 asks to construct an n-log-n algorithm which would generate an inversion table corresponding to a particular permutation.
My algorithm constructs inversion table for a random permutation of 1..N numbers (Knuth, Volume 3, exercise 5.1.1-6) using binary search tree where each node has two additional fields.
I'm trying to understand if my algorithm has complexity n-log-n not just theoretically but by observing performance data. Attached is the algorithm itself (Windows, C++, MinGW) and the resultant dataset which has two columns - first is size of the permutation and the second is the time it took to construct inversion table. I would appreciate if anybody could look into it, plot it in Excel and see if the curve in fact looks like it's n-log-n (I don't see it that way.)
Why am I seeing spikes in my data? Why is there this abrupt drop at datapoint 2070? If it has to do with the cache, can you suggest other programs/experiments clearly demonstrating how exactly spikes are related to cache? My processor is i7 quad core Bloomfield, three levels of cache, all 64 byte line size.
Thanks,
Monte
Knuth's TAOCP exercise 5.1.1-6 asks to construct an n-log-n algorithm which would generate an inversion table corresponding to a particular permutation.
My algorithm constructs inversion table for a random permutation of 1..N numbers (Knuth, Volume 3, exercise 5.1.1-6) using binary search tree where each node has two additional fields.
I'm trying to understand if my algorithm has complexity n-log-n not just theoretically but by observing performance data. Attached is the algorithm itself (Windows, C++, MinGW) and the resultant dataset which has two columns - first is size of the permutation and the second is the time it took to construct inversion table. I would appreciate if anybody could look into it, plot it in Excel and see if the curve in fact looks like it's n-log-n (I don't see it that way.)
Why am I seeing spikes in my data? Why is there this abrupt drop at datapoint 2070? If it has to do with the cache, can you suggest other programs/experiments clearly demonstrating how exactly spikes are related to cache? My processor is i7 quad core Bloomfield, three levels of cache, all 64 byte line size.
Thanks,
Monte