1. http://en.wikipedia.org/wiki/Code_signing
An article from Wikipedia. Not very good and does not provide a lot of information. But explains the general concepts of application signing and its purposes.
2. http://msdn.microsoft.com/en-us/library/ms537361.aspx
Introduction to code signing by Microsoft. General, no specifics, formal words.... Microsoft style. But one can understand some global purposes of signing from that.
Have not found anything useful yet....
Monday, March 5, 2012
Friday, March 2, 2012
Timsort
http://www.drmaciver.com/2010/01/understanding-timsort-1adaptive-mergesort/
Very good and clear article about the ideas under Timsoft algorithm.
http://svn.python.org/projects/python/trunk/Objects/listsort.txt
Original Tim Peterson description of the proposed algorithm and its evaluation.
http://warp.povusers.org/SortComparison/
Good and colorful comparison of standard sort algorithms (without optimization) but does not include Timsort.
Minus of the algorithm is that it uses O(n) space while normal merge sort algorithm uses only O(ln(n)) additional space in the stack (because it uses recursion). May be unsatisfying with really big N.
Very good and clear article about the ideas under Timsoft algorithm.
http://svn.python.org/projects/python/trunk/Objects/listsort.txt
Original Tim Peterson description of the proposed algorithm and its evaluation.
http://warp.povusers.org/SortComparison/
Good and colorful comparison of standard sort algorithms (without optimization) but does not include Timsort.
Minus of the algorithm is that it uses O(n) space while normal merge sort algorithm uses only O(ln(n)) additional space in the stack (because it uses recursion). May be unsatisfying with really big N.
List Sort
A very simple programming problem gave me the idea to look what modern search algorithm is the best. At the moment, I know and have used only merge sort and insertion sort. But I have never tried to compare their performance in different cases (different list lengths, different data, etc.).
After several minutes of search, I found that the insertion sort performs better on small array while merge soft performs better on large arrays and is theoretically better. It takes O(n*ln(n)) time comparing to O(n^2) time for the insertion cost. BUT! Python introduced TimSort in 2002 and have been using it since. As I understood, Android uses it since API Level 5 and a discussion about Java sort algorithm started in 2009 leaded to Java using TimSort now too.
From Wikipedia I understood that Timsort (invented by Tim Tim's_Lastname but described in some paper in 1990s) is an adaptive search algorithm that uses the idea that real world data is usually not random but partially sorted. Thus, it explores different data features and adapt to them. It achieves O(ln(n)) result on partially sorted data and is only 1.5% slower that optimized merge sort on the completely random data.
To be continued....
After several minutes of search, I found that the insertion sort performs better on small array while merge soft performs better on large arrays and is theoretically better. It takes O(n*ln(n)) time comparing to O(n^2) time for the insertion cost. BUT! Python introduced TimSort in 2002 and have been using it since. As I understood, Android uses it since API Level 5 and a discussion about Java sort algorithm started in 2009 leaded to Java using TimSort now too.
From Wikipedia I understood that Timsort (invented by Tim Tim's_Lastname but described in some paper in 1990s) is an adaptive search algorithm that uses the idea that real world data is usually not random but partially sorted. Thus, it explores different data features and adapt to them. It achieves O(ln(n)) result on partially sorted data and is only 1.5% slower that optimized merge sort on the completely random data.
To be continued....
Subscribe to:
Posts (Atom)