Click here to Skip to main content
15,123,619 members
Home / Discussions / Algorithms
   

Algorithms

 
GeneralRe: Lock free algorithms Pin
Joe Woodbury6-Sep-14 14:44
professionalJoe Woodbury6-Sep-14 14:44 
QuestionAlgorithm for comparing word with randomly distributed substring Pin
asdf232111-Jul-14 0:06
Memberasdf232111-Jul-14 0:06 
AnswerRe: Algorithm for comparing word with randomly distributed substring Pin
Sanmayce3-Jul-14 8:15
MemberSanmayce3-Jul-14 8:15 
AnswerRe: Algorithm for comparing word with randomly distributed substring Pin
Sanmayce5-Jul-14 8:19
MemberSanmayce5-Jul-14 8:19 
QuestionCubesort Pin
Gregorius van den Hoven22-Jun-14 5:09
MemberGregorius van den Hoven22-Jun-14 5:09 
AnswerRe: Cubesort Pin
Sanmayce28-Jun-14 9:02
MemberSanmayce28-Jun-14 9:02 
GeneralRe: Cubesort Pin
Gregorius van den Hoven29-Jun-14 10:58
MemberGregorius van den Hoven29-Jun-14 10:58 
AnswerRe: Cubesort Pin
Sanmayce30-Jun-14 7:48
MemberSanmayce30-Jun-14 7:48 
Having benchmarked Cubesort with Knight-Tours my amateurish evaluation is of two words: Mutsi! Mutsunka!

My Sandokan (r3fix) is inferior compared to Cubesort, 10,000,000 lines (128 bytes each) were sorted and after that sorted file was sorted once more:
------------------------------------------------------------------------------------------
| sorter \ filedataset | KT10000000.txt                      | KT10000000_SORTED.txt     |
------------------------------------------------------------------------------------------
| Cubesort             | 080 seconds                         | 045 seconds               |
| Windows' sort.exe    | 118 seconds                         | 115 seconds               |
| Sandokan             | 131 seconds; swappings: 36,826,242+ | 114 seconds; swappings: 0 |
------------------------------------------------------------------------------------------

The benchmark is downloadable at: www.sanmayce.com/Downloads/TriShowdown_Sandokan_vs_Windows_vs_Cubesort_Intel_64bit.zip[^]

The full log follows:
E:\TriShowdown_Sandokan_vs_Windows_vs_Cubesort_Intel_64bit>dir
 Volume in drive E is SSD_Sanmayce
 Volume Serial Number is 9CF6-FEA3

 Directory of E:\TriShowdown_Sandokan_vs_Windows_vs_Cubesort_Intel_64bit

06/29/2014  11:45 PM    <DIR>          .
06/29/2014  11:45 PM    <DIR>          ..
06/29/2014  11:45 PM            12,566 cubesort-1.0_non-original.c
06/29/2014  11:45 PM            86,016 cubesort-1.0_non-original.exe
06/29/2014  11:45 PM           202,880 Cubesort.zip
06/29/2014  11:45 PM            24,490 Knight-tour_r8dump.c
06/29/2014  11:45 PM            79,872 Knight-tour_r8dump.exe
06/29/2014  11:45 PM               116 Make_EXEs.bat
06/29/2014  11:45 PM             1,604 MokujIN prompt.lnk
06/29/2014  11:45 PM           301,406 Sandokan_Logo.pdf
06/29/2014  11:45 PM           170,433 Sandokan_QuickSortExternal_4+GB_r3fix.c
06/29/2014  11:45 PM           122,368 Sandokan_QuickSortExternal_4+GB_r3fix.exe
06/29/2014  11:45 PM             6,144 timer64.exe
06/29/2014  11:45 PM             1,111 TriShowdown_Sandokan_vs_Windows_vs_Cubesort.bat
              12 File(s)      1,009,006 bytes
               2 Dir(s)  27,537,633,280 bytes free

E:\TriShowdown_Sandokan_vs_Windows_vs_Cubesort_Intel_64bit>move ..\KT10000000.txt
        1 file(s) moved.

E:\TriShowdown_Sandokan_vs_Windows_vs_Cubesort_Intel_64bit>TriShowdown_Sandokan_vs_Windows_vs_Cubesort.bat
Sorting 10,000,000 KT...

E:\TriShowdown_Sandokan_vs_Windows_vs_Cubesort_Intel_64bit>timer64.exe cubesort-1.0_non-original.exe KT10000000.txt
Cubesort: sorted 10000000 elements in 66503 clocks.

Kernel  Time =     6.754 =    8%
User    Time =    54.756 =   68%
Process Time =    61.511 =   76%    Virtual  Memory =   2676 MB
Global  Time =    80.355 =  100%    Physical Memory =   2447 MB
Sorting 10,000,000 KT...

E:\TriShowdown_Sandokan_vs_Windows_vs_Cubesort_Intel_64bit>timer64.exe sort /M 1048576 /T D: KT10000000.txt /O WindowsSORT_ResultantFile.txt

Kernel  Time =     1.466 =    1%
User    Time =    88.249 =   74%
Process Time =    89.716 =   75%    Virtual  Memory =   1028 MB
Global  Time =   118.248 =  100%    Physical Memory =   1021 MB

E:\TriShowdown_Sandokan_vs_Windows_vs_Cubesort_Intel_64bit>fc Cubesort_ResultantFile.txt WindowsSORT_ResultantFile.txt /b
Comparing files Cubesort_ResultantFile.txt and WINDOWSSORT_RESULTANTFILE.TXT
FC: no differences encountered

Sorting 10,000,000 KT...

E:\TriShowdown_Sandokan_vs_Windows_vs_Cubesort_Intel_64bit>timer64.exe "Sandokan_QuickSortExternal_4+GB_r3fix.exe" KT10000000.txt /fast /ascend 512
Sandokan_QuickSortExternal_4+GB, revision 3fix, written by Kaze, using Bill Durango's Quicksort source.
Size of input file: 1,300,000,000
Counting lines ...
Lines encountered: 10,000,000
Longest line (including CR if present): 129
Allocated memory for pointers-to-lines in MB: 76
Assigning pointers ...
sizeof(int), sizeof(void*): 4, 8
Trying to allocate memory for the file itself in MB: 1239 ... OK! Get on with fast internal accesses.
Uploading ...
Sorting 10,000,000 Pointers ...
Quicksort (Insertionsort for small blocks) commenced ...
\ RightEnd: 000,001,500,225; NumberOfSplittings: 0,001,676,176; Done: 100% ...
NumberOfSwappings: 36,826,242
NumberOfComparisons: 255,105,484
The time to sort 10,000,000 items via Quicksort+Insertionsort was 106,704 clocks.
Dumping the sorted data ...
\ Done 100% ...
Dumped 10,000,000 lines.
OK! Incoming and resultant file's sizes match.
Dump time: 6,739 clocks.
Total time: 131,258 clocks.
Performance: 9,904 bytes/clock.
Done successfully.

Kernel  Time =     5.397 =    4%
User    Time =   116.173 =   88%
Process Time =   121.571 =   92%    Virtual  Memory =   1320 MB
Global  Time =   131.461 =  100%    Physical Memory =   1321 MB

E:\TriShowdown_Sandokan_vs_Windows_vs_Cubesort_Intel_64bit>fc QuickSortExternal_4+GB.txt WindowsSORT_ResultantFile.txt /b
Comparing files QuickSortExternal_4+GB.txt and WINDOWSSORT_RESULTANTFILE.TXT
FC: no differences encountered

Sorting sorted 10,000,000 KT...

E:\TriShowdown_Sandokan_vs_Windows_vs_Cubesort_Intel_64bit>timer64.exe cubesort-1.0_non-original.exe WindowsSORT_ResultantFile.txt
Cubesort: sorted 10000000 elements in 28064 clocks.

Kernel  Time =     6.723 =   14%
User    Time =    27.284 =   60%
Process Time =    34.008 =   74%    Virtual  Memory =   2661 MB
Global  Time =    45.474 =  100%    Physical Memory =   2560 MB
Sorting sorted 10,000,000 KT...

E:\TriShowdown_Sandokan_vs_Windows_vs_Cubesort_Intel_64bit>timer64.exe sort /M 1048576 /T D: WindowsSORT_ResultantFile.txt /O WindowsSORT_ResultantFile_.txt

Kernel  Time =     1.170 =    1%
User    Time =    76.237 =   66%
Process Time =    77.407 =   67%    Virtual  Memory =   1028 MB
Global  Time =   115.081 =  100%    Physical Memory =   1021 MB

E:\TriShowdown_Sandokan_vs_Windows_vs_Cubesort_Intel_64bit>fc Cubesort_ResultantFile.txt WindowsSORT_ResultantFile_.txt /b
Comparing files Cubesort_ResultantFile.txt and WINDOWSSORT_RESULTANTFILE_.TXT
FC: no differences encountered

Sorting sorted 10,000,000 KT...

E:\TriShowdown_Sandokan_vs_Windows_vs_Cubesort_Intel_64bit>timer64.exe "Sandokan_QuickSortExternal_4+GB_r3fix.exe" WindowsSORT_ResultantFile.txt /fast /ascend 512
Sandokan_QuickSortExternal_4+GB, revision 3fix, written by Kaze, using Bill Durango's Quicksort source.
Size of input file: 1,300,000,000
Counting lines ...
Lines encountered: 10,000,000
Longest line (including CR if present): 129
Allocated memory for pointers-to-lines in MB: 76
Assigning pointers ...
sizeof(int), sizeof(void*): 4, 8
Trying to allocate memory for the file itself in MB: 1239 ... OK! Get on with fast internal accesses.
Uploading ...
Sorting 10,000,000 Pointers ...
Quicksort (Insertionsort for small blocks) commenced ...
\ RightEnd: 000,010,000,000; NumberOfSplittings: 0,001,611,392; Done: 100% ...
NumberOfSwappings: 0
NumberOfComparisons: 214,016,797
The time to sort 10,000,000 items via Quicksort+Insertionsort was 90,278 clocks.
Dumping the sorted data ...
\ Done 100% ...
Dumped 10,000,000 lines.
OK! Incoming and resultant file's sizes match.
Dump time: 5,429 clocks.
Total time: 114,488 clocks.
Performance: 11,354 bytes/clock.
Done successfully.

Kernel  Time =     6.364 =    5%
User    Time =    99.372 =   86%
Process Time =   105.737 =   92%    Virtual  Memory =   1320 MB
Global  Time =   114.691 =  100%    Physical Memory =   1321 MB

E:\TriShowdown_Sandokan_vs_Windows_vs_Cubesort_Intel_64bit>fc QuickSortExternal_4+GB.txt WindowsSORT_ResultantFile_.txt /b
Comparing files QuickSortExternal_4+GB.txt and WINDOWSSORT_RESULTANTFILE_.TXT
FC: no differences encountered

E:\TriShowdown_Sandokan_vs_Windows_vs_Cubesort_Intel_64bit>

Cubesort is one lovely piece of software, Mr. Hoven I salute you with Beth Ditto's Heavy Cross[^]:

It's a cruel cruel world to face on your own
A heavy cross to carry alone
The lights are on but everyone's gone
And it's cruel
It's a funny way to make ends meet
When the lights are out on every street
It feels alright but never complete
without you
I chose you
If it's already have been done
Undo it
It takes two
It is up to me and you to proove it
On the rainy nights even the coldest days
you're moments ago but seconds away
The principle of Nature it's true but it's a cruel world
See we can play it safe or play it cool
Follow the leader or make up all the rules
Whatever you want the choice is yours
So choose me
I chose you

"If it's already have been done... undo it." - I wish Beth was into programming.

The most decent Quicksort I know is this:
https://code.google.com/p/libdivsufsort/[^]
GeneralRe: Cubesort Pin
Gregorius van den Hoven12-Jul-14 5:01
MemberGregorius van den Hoven12-Jul-14 5:01 
AnswerRe: Cubesort Pin
Sanmayce3-Jul-14 5:30
MemberSanmayce3-Jul-14 5:30 
QuestionReduce a Q2SAT formula Pin
Apurvgupta15-Jun-14 21:48
MemberApurvgupta15-Jun-14 21:48 
QuestionFastest textual decompression in C Pin
Sanmayce10-May-14 9:54
MemberSanmayce10-May-14 9:54 
AnswerRe: Fastest textual decompression in C Pin
Richard MacCutchan10-May-14 22:46
mveRichard MacCutchan10-May-14 22:46 
GeneralRe: Fastest textual decompression in C Pin
Sanmayce12-May-14 1:18
MemberSanmayce12-May-14 1:18 
GeneralRe: Fastest textual decompression in C Pin
Richard MacCutchan12-May-14 2:24
mveRichard MacCutchan12-May-14 2:24 
GeneralRe: Fastest textual decompression in C Pin
Chris Losinger23-May-14 4:12
professionalChris Losinger23-May-14 4:12 
GeneralRe: Fastest textual decompression in C Pin
Sanmayce24-May-14 8:17
MemberSanmayce24-May-14 8:17 
QuestionThe Bessel-Overhauser Spline interpolation - suitable values for the weight function Pin
Kenneth Haugland4-Apr-14 0:34
professionalKenneth Haugland4-Apr-14 0:34 
AnswerRe: The Bessel-Overhauser Spline interpolation - suitable values for the weight function Pin
Kenneth Haugland6-Apr-14 1:30
professionalKenneth Haugland6-Apr-14 1:30 
QuestionFactoring algorithm Pin
Member 41945931-Apr-14 5:46
MemberMember 41945931-Apr-14 5:46 
AnswerRe: Factoring algorithm Pin
Bernhard Hiller1-Apr-14 21:44
MemberBernhard Hiller1-Apr-14 21:44 
GeneralRe: Factoring algorithm Pin
Member 41945932-Apr-14 7:17
MemberMember 41945932-Apr-14 7:17 
GeneralRe: Factoring algorithm Pin
Kornfeld Eliyahu Peter2-Apr-14 10:30
professionalKornfeld Eliyahu Peter2-Apr-14 10:30 
AnswerRe: Factoring algorithm Pin
Peter_in_278023-May-14 16:34
professionalPeter_in_278023-May-14 16:34 
GeneralRe: Factoring algorithm Pin
Member 419459323-May-14 18:03
MemberMember 419459323-May-14 18:03 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.