Document Distance Program Version 6

From 6.006 Wiki

You do not have permission to edit this page, for the following reason:

You can view and copy the source of this page:

To improve the running time of our document distance program, we replace <tt>insertion_sort</tt> with <tt>merge_sort</tt>, which is known to run in time <math>\Theta(n\lg n)</math>, instead of the <math>\Theta(n^2)</math> running time of <tt>insertion_sort</tt>. Here is code for <tt>merge_sort</tt>: <pre> def merge_sort(A): """ Sort list A into order, and return result. """ n = len(A) if n==1: return A mid = n//2 # floor division L = merge_sort(A[:mid]) R = merge_sort(A[mid:]) return merge(L,R) def merge(L,R): """ Given two sorted sequences L and R, return their merge. """ i = 0 j = 0 answer = [] while i<len(L) and j<len(R): if L[i]<R[j]: answer.append(L[i]) i += 1 else: answer.append(R[j]) j += 1 if i<len(L): answer.extend(L[i:]) if j<len(R): answer.extend(R[j:]) return answer </pre> The revised document distance program is now http://courses.csail.mit.edu/6.006/fall08/source/docdist6.py. Running this on our standard inputs, we obtain: <pre> >docdist6.py t2.bobsey.txt t3.lewis.txt File t2.bobsey.txt : 6667 lines, 49785 words, 3354 distinct words File t3.lewis.txt : 15996 lines, 182355 words, 8530 distinct words The distance between the documents is: 0.574160 (radians) 885435 function calls (861671 primitive calls) in 6.630 CPU seconds Ordered by: standard name ncalls tottime percall cumtime percall filename:lineno(function) 1 0.000 0.000 0.000 0.000 :0(acos) 135633 0.486 0.000 0.486 0.000 :0(append) 34545 0.132 0.000 0.132 0.000 :0(extend) 232140 0.760 0.000 0.760 0.000 :0(has_key) 2 0.018 0.009 0.018 0.009 :0(items) 379456 1.327 0.000 1.327 0.000 :0(len) 2 0.001 0.000 0.001 0.000 :0(open) 2 0.014 0.007 0.014 0.007 :0(readlines) 1 0.004 0.004 0.004 0.004 :0(setprofile) 22663 0.146 0.000 0.146 0.000 :0(split) 1 0.000 0.000 0.000 0.000 :0(sqrt) 22663 0.079 0.000 0.079 0.000 :0(translate) 1 0.003 0.003 6.626 6.626 <string>:1(<module>) 2 0.889 0.445 1.667 0.833 docdist6.py:107(count_frequency) 23766/2 0.335 0.000 3.900 1.950 docdist6.py:122(merge_sort) 11882 1.849 0.000 3.481 0.000 docdist6.py:134(merge) 2 0.001 0.001 6.297 3.148 docdist6.py:176(word_frequencies_for_file) 3 0.177 0.059 0.316 0.105 docdist6.py:194(inner_product) 1 0.000 0.000 0.316 0.316 docdist6.py:220(vector_angle) 1 0.011 0.011 6.624 6.624 docdist6.py:230(main) 2 0.000 0.000 0.014 0.007 docdist6.py:57(read_file) 2 0.176 0.088 0.714 0.357 docdist6.py:73(get_words_from_line_list) 22663 0.223 0.000 0.448 0.000 docdist6.py:91(get_words_from_string) 1 0.000 0.000 6.630 6.630 profile:0(main()) 0 0.000 0.000 profile:0(profiler) </pre> Excellent! We have reduced the overall running time from over three minutes to under six seconds -- almost two orders of magnitude improvement in running time -- and the running time should now scale nearly linearly with the size of the input(s). (Where <math>\Theta(n \lg n)</math> is "nearly linear".) We can now attempt to run this on our large inputs, such as compared the complete works of Shakespeare with the complete works of Winston Churchill: <pre> >docdist6.py t5.churchill.txt t8.shakespeare.txt File t5.churchill.txt : 189685 lines, 1717247 words, 32544 distinct words File t8.shakespeare.txt : 124456 lines, 929462 words, 23881 distinct words The distance between the documents is: 0.462095 (radians) 6926117 function calls (6813271 primitive calls) in 52.886 CPU seconds Ordered by: standard name ncalls tottime percall cumtime percall filename:lineno(function) 1 0.000 0.000 0.000 0.000 :0(acos) 763122 2.828 0.000 2.828 0.000 :0(append) 370564 1.565 0.000 1.565 0.000 :0(extend) 2646709 8.770 0.000 8.770 0.000 :0(has_key) 2 0.280 0.140 0.280 0.140 :0(items) 2034004 7.302 0.000 7.302 0.000 :0(len) 2 0.001 0.000 0.001 0.000 :0(open) 2 0.178 0.089 0.178 0.089 :0(readlines) 1 0.004 0.004 0.004 0.004 :0(setprofile) 314141 1.862 0.000 1.862 0.000 :0(split) 1 0.000 0.000 0.000 0.000 :0(sqrt) 314141 1.108 0.000 1.108 0.000 :0(translate) 1 0.025 0.025 52.882 52.882 <string>:1(<module>) 2 10.369 5.184 19.418 9.709 docdist6.py:107(count_frequency) 112848/2 1.643 0.000 21.717 10.858 docdist6.py:122(merge_sort) 56423 10.385 0.000 19.662 0.000 docdist6.py:134(merge) 2 0.011 0.006 51.227 25.614 docdist6.py:176(word_frequencies_for_file) 3 0.836 0.279 1.491 0.497 docdist6.py:194(inner_product) 1 0.000 0.000 1.492 1.492 docdist6.py:220(vector_angle) 1 0.138 0.138 52.856 52.856 docdist6.py:230(main) 2 0.000 0.000 0.179 0.089 docdist6.py:57(read_file) 2 2.451 1.225 9.902 4.951 docdist6.py:73(get_words_from_line_list) 314141 3.131 0.000 6.101 0.000 docdist6.py:91(get_words_from_string) 1 0.000 0.000 52.886 52.886 profile:0(main()) 0 0.000 0.000 profile:0(profiler) </pre> Very nice! These are large files (many megabytes), and yet we are able to compute the distance between them fairly efficiently (under a minute). If we were to continue searching for efficiency improvements, we would continue to look at sorting and at the data structures involved in <tt>count_frequency</tt>. '''Exercise''': Can you eliminate the need for sorting altogether in this program? Re-code the program to do so. Next: [[Document Distance Program Using Dictionaries]]<br> Previous: [[Document Distance Program Version 5]]<br> Up: [[Document Distance]]

Return to Document Distance Program Version 6.