Pce3@ij.net (talk | contribs) |
Pce3@ij.net (talk | contribs) mNo edit summary |
||
| (2 intermediate revisions by the same user not shown) | |||
| Line 19: | Line 19: | ||
| 1 to 8 || Digits |
| 1 to 8 || Digits |
||
|- |
|- |
||
| + | !Setup time<ref>'''Time for setup''' refers to the time required to index the array variables with input data and increment the indexed variable's contents.</ref> |
||
| − | !Setup time |
||
| 5.875 || Seconds |
| 5.875 || Seconds |
||
|- |
|- |
||
| + | !Sort time<ref> '''Time for sort''' refers to the time required to parse the array, i.e., sequentially list or print indexes of variables with non-zero values.</ref> |
||
| − | !Sort time |
||
| 1.484 || Seconds |
| 1.484 || Seconds |
||
|- |
|- |
||
| Line 33: | Line 33: | ||
==== Class Determination==== |
==== Class Determination==== |
||
| − | '''''Class''''' notated sort routines are categorized according to the [http://www.physics.csbsju.edu/stats/chi-square.html Chi Square] analysis of linear ('''L'''), parabolic {'''P'''), logarithmic ('''Ln''') and exponential ('''E''') [http://www.physics.csbsju.edu/stats/chi-square.html best fit] [[Wikipedia:Regression analysis|regression analysis]] applied to their performance data produced under a specified set of constraints. '''''Class''''' notation is used in |
+ | '''''Class''''' notated sort routines are categorized according to the [http://www.physics.csbsju.edu/stats/chi-square.html Chi Square] analysis of linear ('''L'''), parabolic {'''P'''), logarithmic ('''Ln''') and exponential ('''E''') [http://www.physics.csbsju.edu/stats/chi-square.html best fit] [[Wikipedia:Regression analysis|regression analysis]] applied to their performance data produced under a specified set of constraints. '''''Class''''' notation is used in preference to [[Wikipedia:Theta|Theta notation]], a form of [[Wikipedia:Big O notation|Big O notation]], since the advantage '''''Class''''' notation offers is to provide the values of the equation parameters obtained from [[Wikipedia:Regression analysis|regression analysis]] of the performance data such as in the case of a [[Wikipedia:Linear equation|linear equation]] best [http://www.physics.csbsju.edu/stats/chi-square.html Chi Square] fit of the value for slope (or seconds per item) in the case of a '''Class L''' (''linear equation'') category [http://www.physics.csbsju.edu/stats/chi-square.html best fit]. This additional information allows the programmer or user to select the best sort routine for his own application based upon the actual number of items which must be sorted per unit time or the time limit to sort a specific number of items. Since the Check sort performance [http://www.physics.csbsju.edu/stats/chi-square.html best fits] the '''Class L''' category the values for slope '''''m''''' and constant '''''c''''' for the [[Wikipedia:Linear equation|linear equation]] <big> '''''f(x)= m*x+c''''' </big> can be determined by a [http://www.physics.csbsju.edu/stats/chi-square.html best fit] [[Wikipedia:Linear regression|linear regression]] analysis and provided in the table below: |
[[Image:rapidsort_1371_image001.png|320px|right|alt text]] |
[[Image:rapidsort_1371_image001.png|320px|right|alt text]] |
||
| Line 51: | Line 51: | ||
Sort time in this case is 24.87% of setup time <math>{0.0144728 \choose 0.058192715}</math>, If a setup slope of .025 is determined by [[Wikipedia:Scientific method|empirical analysis]] using another [[Wikipedia:Computer|machine]] the projected results would indicate a sorting rate of (.025 *.2487) or 0.00622 seconds per item or the ability to sort 16,083,332 items per second assuming the ratio of setup to sort time will not change from machine to machine for the same implementation of the same language. |
Sort time in this case is 24.87% of setup time <math>{0.0144728 \choose 0.058192715}</math>, If a setup slope of .025 is determined by [[Wikipedia:Scientific method|empirical analysis]] using another [[Wikipedia:Computer|machine]] the projected results would indicate a sorting rate of (.025 *.2487) or 0.00622 seconds per item or the ability to sort 16,083,332 items per second assuming the ratio of setup to sort time will not change from machine to machine for the same implementation of the same language. |
||
| + | ==notes== |
||
| + | <references/> |
||
Latest revision as of 09:49, 20 September 2008
Table of Performance Values[]
Regression Analysis[]
The following table provvides the values of the constraints under which regression analysis of the performance data was performed.
| Value | Units | |
|---|---|---|
| Primary array | 9,999,999 | Cells |
| Secondary array | 7,505,468 | Items |
| Key length | 1 to 8 | Digits |
| Setup time[1] | 5.875 | Seconds |
| Sort time[2] | 1.484 | Seconds |
| Total Ratio | .0.2526 | Percent |
Class Determination[]
Class notated sort routines are categorized according to the Chi Square analysis of linear (L), parabolic {P), logarithmic (Ln) and exponential (E) best fit regression analysis applied to their performance data produced under a specified set of constraints. Class notation is used in preference to Theta notation, a form of Big O notation, since the advantage Class notation offers is to provide the values of the equation parameters obtained from regression analysis of the performance data such as in the case of a linear equation best Chi Square fit of the value for slope (or seconds per item) in the case of a Class L (linear equation) category best fit. This additional information allows the programmer or user to select the best sort routine for his own application based upon the actual number of items which must be sorted per unit time or the time limit to sort a specific number of items. Since the Check sort performance best fits the Class L category the values for slope m and constant c for the linear equation f(x)= m*x+c can be determined by a best fit linear regression analysis and provided in the table below:
| Routine | Slope | c |
|---|---|---|
| Setup | 0.058192715 | 0 |
| Sort | 0.0144728 | 0 |
Sort time in this case is 24.87% of setup time , If a setup slope of .025 is determined by empirical analysis using another machine the projected results would indicate a sorting rate of (.025 *.2487) or 0.00622 seconds per item or the ability to sort 16,083,332 items per second assuming the ratio of setup to sort time will not change from machine to machine for the same implementation of the same language.
