 | |
Simple disk-based sorting method
comp.database comp.database
 |
| | Thread Tools | Search this Thread | Display Modes |
#11
 
| |||
| |||
|
Re: Simple disk-based sorting method -
04-16-2007
, 06:53 AM
|
I think what you describe is clumsy |
Quote:
|
and only barely works in the specific application you describe. Grow the application and it will break as your solution is delicate. |
only 20 days of data, whereas my collection thus far is 37 days and
grows each work day.
Therefore the full flat file has 684,981 records and a size of
38,828,711 bytes. The key has 9 decimal digits. The procedure has to
do 6,164,829 sorting operations total.
I am able to sort it in 63 seconds on a 2.4 GHz Celeron D with 512 MB
RAM running Win2K/SP4 DVM and a WD Caviar IDE drive. I was prepared to
accept as much as an hour, and it only takes 1 minute. That is not my
idea of "clumsy" or "only barely works".
I was able to get around negative numerical keys by offsetting them
with the minimum value, sorting and restoring them. If the keys were
alphanumeric, I would convert each character to its ACSII hex value
and expand the sort bins to 16 to accommodate hex numbers.
As I mentioned the thing that makes the Radix Sort so valueable,
besides being disk-file-based, is that its complexity is O(N). Other
sort methods in general are either O(N^2) or O(N log N).
Another thing I like is the simplicity of the Radix Sort. I am not a
database person, so for me this is an excursion into an area I have
not mastered. The fact that the Radix Sort is so easy to implement in
C is a blessing.
It is overkill for small sorts, for which I use the C Library function
"qsort". Now I have both ends of the spectrum covered.
--
"Prediction is very difficult, especially about the future."
--Niels Bohr
#12
| |||
| |||
|
|
As I mentioned the thing that makes the Radix Sort so valueable, besides being disk-file-based, is that its complexity is O(N). Other sort methods in general are either O(N^2) or O(N log N). |
Your solution is clumsy because it depends on your source data having
some sort of order and uniform distribution.
Quote:
|
Another thing I like is the simplicity of the Radix Sort. I am not a database person, so for me this is an excursion into an area I have not mastered. The fact that the Radix Sort is so easy to implement in C is a blessing. |
What I described wasn't so much as a sort algorithm but a means of
overflowing in temporary files. I said to sort in memory, but didn't
make any recommendations as to how one should sort in memory.
Quote:
|
It is overkill for small sorts, for which I use the C Library function "qsort". Now I have both ends of the spectrum covered. |
#13
| |||||
| |||||
|
|
I see nothing about the Radix sort which makes it "disk based." |
it is O9N) makes it ideal for disk based operations.
Quote:
|
Your solution is clumsy because it depends on your source data having some sort of order and uniform distribution. |
I do not understand your comment about "uniform distribution".
Quote:
|
Should be several sort routines in your existing C libraries. |
Optimizing C Compiler. The only sort routine that exists in that
library is qsort.
Quote:
|
What I described wasn't so much as a sort algorithm but a means of overflowing in temporary files. I said to sort in memory, but didn't make any recommendations as to how one should sort in memory. |
need to build memory-based arrays.
Win2K builds a very large disk cache which means that a lot of the
disk-based operations are implemented in memory. By using the disk
file system as storage for the sort procedure, I am taking advantage
of this very large, efficient system.
Quote:
|
It is overkill for small sorts, for which I use the C Library function "qsort". Now I have both ends of the spectrum covered. Most any in-memory sort will be faster than any disk-based sort. |
manage the memory-to-disk operations, which you have described as " a
means of overflowing in temporary files".
Sorting 38MB in 63 seconds it fast enough for my purposes. Going to
all the trouble of writing the procedures for "means of
overflowing in temporary files" is not worth any potential savings in
time. And I am not convinced it would actually reduce the time,
because the overhead could be excessive.
--
"Prediction is very difficult, especially about the future."
--Niels Bohr
#14
| |||
| |||
|
|
I have a disk file which contains 370,260 records of average length 60 ASCII text characters. I need to sort them on the first 9 characters, which are set off from the rest by a space. Once sorted the first record looks like 100100100 08:35-08:39 4 0 0 1 -115 -1 75 -100 dd17.txt and the last one looks like 500900900 12:41-13:25 44 1 885 0 0 1 925 -200 dd21.txt |
What's wrong with importing it into Excel?
Paul...
#15
| |||
| |||
|
|
Citizen Bob wrote: I have a disk file which contains 370,260 records of average length 60 ASCII text characters. I need to sort them on the first 9 characters, which are set off from the rest by a space. Once sorted the first record looks like 100100100 08:35-08:39 4 0 0 1 -115 -1 75 -100 dd17.txt and the last one looks like 500900900 12:41-13:25 44 1 885 0 0 1 925 -200 dd21.txt What's wrong with importing it into Excel? |
it was way less than 370,260.
/Lennart
#16
| |||
| |||
|
|
I have a disk file which contains 370,260 records of average length 60 ASCII text characters. I need to sort them on the first 9 characters, which are set off from the rest by a space. Once sorted the first record looks like 100100100 08:35-08:39 4 0 0 1 -115 -1 75 -100 dd17.txt and the last one looks like 500900900 12:41-13:25 44 1 885 0 0 1 925 -200 dd21.txt There is not enough memory in my Win2K/SP4 system to implement the traditional memory-based sorting algorithms, so I need to use a method that is disk-file based. I have plenty of disk space. I imagine that this method would open the input disk file and begin reading records one at a time and performing some kind of sort algorithm placing the result in a temporary output file. Once the original file has been swept, the process starts over and runs again and again for the required number of iterations until the entire list is sorted in ascending order. I will implement this method in standard DOS-based C (Microsoft Optimizing C Compiler "cl") using the Win2K DVM. I suggest you use the Microsoft supplied sort. You can obtain |
#17
| |||
| |||
|
|
I suggest you use the Microsoft supplied sort. You can obtain instructions by typing HELP SORT at the command prompt. |
Or try downloading the bash shell at www.cygwin.com and
using the unix sort on windows.
Paul...
#18
| |||
| |||
|
|
What's wrong with importing it into Excel? What is the maximum number of rows in an XL sheet? Last time I checked it was way less than 370,260. |
Oops - silly me! It's 65536.
www.cygwin.com could be a way of doing it. Or use perl
with cygwin. Or the Microsoftoft sort as suggested by another poster.
Paul...
Quote:
|
/Lennart |
#19
| |||
| |||
|
| David Segall wrote: I suggest you use the Microsoft supplied sort. You can obtain instructions by typing HELP SORT at the command prompt. Or try downloading the bash shell at www.cygwin.com and using the unix sort on windows. Shame on you! That is not supplied by Microsoft. Everything you need |
from Microsoft
<http://technet.microsoft.com/en-us/interopmigration/bb380242.aspx>.
It can be downloaded from
<http://www.microsoft.com/downloads/details.aspx?familyid=896c9688-601b-44f1-81a4-02878ff11778&displaylang=en>.
|
« Previous Thread
|
Next Thread »
| Thread Tools | Search this Thread |
| Display Modes | |
Linear Mode
| |
Powered by vBulletin Version 3.5.3
Copyright ©2000 - 2008, Jelsoft Enterprises Ltd.
Copyright ©2000 - 2008, Jelsoft Enterprises Ltd.