Click here to Skip to main content
15,117,095 members
Home / Discussions / Algorithms
   

Algorithms

 
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 
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 
Cubesort is awesome, with big potential on top of that.
The thing that impresses me most is its construction speed, not to mention the 'free' dump.

Couldn't resist not to try my 'secret weapon' - a frozen/unfinished sub-project called 'Tcheburaschkasort'.
It is entirely based on the titaniumESQUEly strong Bayer-McCreight algorithm which I implemented specifically and only as order 3 (three children maximum).
It's been some time since I wrote it, enough to forget this-and-that, but the initial idea was to use next dimension i.e. to use millions of B-trees.

My unfinished Tcheburaschkasort currently uses 24bit pseudo-hash (in fact first 1|2|3 byte(s) ARE a slot) giving a forest of 16,777,216 B-Trees of order 3:
UINT PseudoHash(const char *str, unsigned int wrdlen)
{
	UINT hash32 = 0;
	const char *p = str;
	// Use 256-based system for first 3 bytes i.e. left is more significant:
	// Currently 3bytes long i.e. 24bit:
	if (wrdlen>=1) {
		hash32 =  hash32 | ((*p)<<16);
		p += 1;
	}
	if (wrdlen>=2) {
		hash32 =  hash32 | ((*p)<<8);
		p += 1;
	}
	if (wrdlen>=3) {
		hash32 =  hash32 | ((*p)<<0);
		p += 1;
	}
	return hash32;
}

Each slot houses the root of a tree.
Not using any hash Tcheburaschkasort resembles a hypercube of order 0, using hash makes it 1D i.e. of order 1 - lookup hashtable is the axis.

Blah-blah, in short the randomness of those prefixes (1..3bytes long) decides the speed performance.
In example with KT10000000.txt all first 3 bytes are equal, 'A8C', so there is one only tree and performance is poor.
Because all the 10,000,000 lines start from board position A8.
Knight-tours: each square represents a board position, as A1(bottom-left), H8(top-right):
-----------------
|a8 |b8 |...|h8 |
-----------------
|a7 |...|       |
-----------------
|...|...|       |
-----------------
|a1 |...|...|h1 |
-----------------

When making the data more diverse, e.g. reverse the order of tours then for KT10000000.txt we will have 50 trees, see below.
Let us see what boost comes from this diversity.

So, Tcheburaschkasort vs Cubesort results for KT10M filedataset (10,000,000 Knight-Tours from A8, reversed):

NOTE:
Tcheburaschkasort is based on my superfast multi-purpose text ripper Leprechaun.
Tcheburaschkasort still DOES NOT make in-order dump/traversal, resultant file is unsorted, to be done. This DOES NOT affect results, though.

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

 Directory of E:\BiShowdown_Cubesort_Tcheburaschkasort_Intel_64bit

07/03/2014  04:19 AM    <DIR>          .
07/03/2014  04:19 AM    <DIR>          ..
07/03/2014  04:20 AM               823 BiShowdown_Cubesort_Tcheburaschkasort.bat
07/03/2014  04:20 AM            12,566 cubesort-1.0_non-original.c
07/03/2014  04:20 AM            86,016 cubesort-1.0_non-original.exe
07/03/2014  04:20 AM           202,880 Cubesort.zip
07/03/2014  04:20 AM            24,490 Knight-tour_r8dump.c
07/03/2014  04:20 AM            79,872 Knight-tour_r8dump.exe
07/03/2014  04:20 AM            25,071 Knight-tour_r8dump_REVERSE.c
07/03/2014  04:20 AM            79,360 Knight-tour_r8dump_REVERSE.exe
07/03/2014  04:20 AM               216 Make_EXEs.bat
07/03/2014  04:20 AM             1,604 MokujIN prompt.lnk
07/03/2014  04:20 AM           170,433 Sandokan_QuickSortExternal_4+GB_r3fix.c
07/03/2014  04:20 AM           122,368 Sandokan_QuickSortExternal_4+GB_r3fix.exe
07/03/2014  04:20 AM           327,819 TcheburaschkaSort.c
07/03/2014  04:20 AM         1,771,134 TcheburaschkaSort.cod
07/03/2014  04:20 AM           140,288 TcheburaschkaSort.exe
07/03/2014  04:20 AM             6,144 timer64.exe
              16 File(s)      3,051,084 bytes
               2 Dir(s)  29,523,390,464 bytes free

E:\BiShowdown_Cubesort_Tcheburaschkasort_Intel_64bit>BiShowdown_Cubesort_Tcheburaschkasort.bat
Dumping 10,000,000 reversed KT...

E:\BiShowdown_Cubesort_Tcheburaschkasort_Intel_64bit>Knight-tour_r8dump_REVERSE A8 10000000 1>KT10000000_from-end-to-start.txt

E:\BiShowdown_Cubesort_Tcheburaschkasort_Intel_64bit>sort /M 1048576 /T D: /R KT10000000_from-end-to-start.txt /O KT10000000_from-end-to-start-SORTED-IN-REVERSE.txt
Sorting 10,000,000 KT...

E:\BiShowdown_Cubesort_Tcheburaschkasort_Intel_64bit>timer64.exe cubesort-1.0_non-original.exe KT10000000_from-end-to-start.txt
Cubesort: sorted 10000000 elements in 94349 clocks.

Kernel  Time =     8.283 =    7%
User    Time =    59.592 =   55%
Process Time =    67.876 =   62%    Virtual  Memory =   2689 MB
Global  Time =   108.217 =  100%    Physical Memory =   2497 MB
Sorting 10,000,000 KT...

E:\BiShowdown_Cubesort_Tcheburaschkasort_Intel_64bit>timer64.exe sort /M 1048576 /T D: KT10000000_from-end-to-start.txt /O KT10000000_from-end-to-start-SORTED.txt

Kernel  Time =     1.778 =    1%
User    Time =    83.132 =   48%
Process Time =    84.911 =   49%    Virtual  Memory =   1028 MB
Global  Time =   173.113 =  100%    Physical Memory =   1021 MB

E:\BiShowdown_Cubesort_Tcheburaschkasort_Intel_64bit>fc Cubesort_ResultantFile.txt KT10000000_from-end-to-start-SORTED.txt /b
Comparing files Cubesort_ResultantFile.txt and KT10000000_FROM-END-TO-START-SORTED.TXT
FC: no differences encountered

Sorting 10,000,000 KT...

E:\BiShowdown_Cubesort_Tcheburaschkasort_Intel_64bit>dir KT10000000_from-end-to-start.txt/b 1>TcheburaschkaSort.lst

E:\BiShowdown_Cubesort_Tcheburaschkasort_Intel_64bit>timer64.exe TcheburaschkaSort TcheburaschkaSort.lst TcheburaschkaSort.txt 2900123 y
Leprechaun_singleton (Fast-In-Future Greedy n-gram-Ripper), rev. 16FIXFIX, written by Svalqyatchx.
Purpose: Rips all distinct 1-grams (1-word phrases) with length 1..128 chars from incoming texts.
Feature1: All words within x-lets/n-grams are in range 1..31 chars inclusive.
Feature2: In this revision 128MB 1-way hash is used which results in 16,777,216 external B-Trees of order 3.
Feature3: In this revision, 1 pass is to be made.
Feature4: If the external memory has latency 99+microseconds then !(look no further), IOPS(seek-time) rules.
Pass #1 of 1:
Size of input file with files for Leprechauning: 34
Allocating HASH memory 134,217,793 bytes ... OK
Allocating memory 2833MB ... OK
Size of Input TEXTual file: 1,300,000,000
\; 00,222,222P/s; Phrase count: 10,000,000 of them 10,000,000 distinct; Done: 64/64
Bytes per second performance: 28,888,888B/s
Phrases per second performance: 222,222P/s
Time for putting phrases into trees: 45 second(s)
Flushing UNsorted phrases: 100%; Shaking trees performance: 00,952,380P/s
Time for shaking phrases from trees: 21 second(s)
Leprechaun: Current pass done.

Total memory needed for one pass: 2,133,638KB
Total distinct phrases: 10,000,000
Total time: 67 second(s)
Total performance: 149,253P/s i.e. phrases per second
Leprechaun: Done.

Kernel  Time =     6.193 =    9%
User    Time =    59.732 =   89%
Process Time =    65.926 =   99%    Virtual  Memory =   2967 MB
Global  Time =    66.580 =  100%    Physical Memory =   2218 MB

E:\BiShowdown_Cubesort_Tcheburaschkasort_Intel_64bit>type Leprechaun.LOG
Leprechaun report:
Number Of Hash Collisions(Distinct WORDs - Number Of Trees): 9,999,950
Number Of Trees(GREATER THE BETTER): 50
Number Of LEAFs(littler THE BETTER) not counting ROOT LEAFs: 7,533,898
Highest Tree not counting ROOT Level i.e. CORONA levels(littler THE BETTER): 15
Used value for third parameter in KB: 2,900,123
Use next time as third parameter: 2,133,638
Total Attempts to Find/Put WORDs into B-trees order 3: 164,504,421

E:\BiShowdown_Cubesort_Tcheburaschkasort_Intel_64bit>type KT10000000_from-end-to-start.txt|more
E3D1C3E4F6D5B6A4C5E6F4D3B2C4E5F3D4F5D6B5A3B1D2F1H2G4H6G8E7C8A7C6D8B7A5B3A1C2E1G2H4G6H8F7G5H7F8D7B8A6B4A2C1E2G1H3F2H1G3H5G7E8C7A8
F6E4C3D1E3D5B6A4C5E6F4D3B2C4E5F3D4F5D6B5A3B1D2F1H2G4H6G8E7C8A7C6D8B7A5B3A1C2E1G2H4G6H8F7G5H7F8D7B8A6B4A2C1E2G1H3F2H1G3H5G7E8C7A8
E3D1C3A4B6D5F6E4C5E6F4D3B2C4E5F3D4F5D6B5A3B1D2F1H2G4H6G8E7C8A7C6D8B7A5B3A1C2E1G2H4G6H8F7G5H7F8D7B8A6B4A2C1E2G1H3F2H1G3H5G7E8C7A8
B6A4C3D1E3D5F6E4C5E6F4D3B2C4E5F3D4F5D6B5A3B1D2F1H2G4H6G8E7C8A7C6D8B7A5B3A1C2E1G2H4G6H8F7G5H7F8D7B8A6B4A2C1E2G1H3F2H1G3H5G7E8C7A8
E3D1C3E4F6D5F4E6C5D3B2A4B6C4E5F3D4F5D6B5A3B1D2F1H2G4H6G8E7C8A7C6D8B7A5B3A1C2E1G2H4G6H8F7G5H7F8D7B8A6B4A2C1E2G1H3F2H1G3H5G7E8C7A8
F6E4C3D1E3D5F4E6C5D3B2A4B6C4E5F3D4F5D6B5A3B1D2F1H2G4H6G8E7C8A7C6D8B7A5B3A1C2E1G2H4G6H8F7G5H7F8D7B8A6B4A2C1E2G1H3F2H1G3H5G7E8C7A8
E3D1C3D5F6E4C5E6F4D3B2A4B6C4E5F3D4F5D6B5A3B1D2F1H2G4H6G8E7C8A7C6D8B7A5B3A1C2E1G2H4G6H8F7G5H7F8D7B8A6B4A2C1E2G1H3F2H1G3H5G7E8C7A8
C3D1E3D5F6E4C5E6F4D3B2A4B6C4E5F3D4F5D6B5A3B1D2F1H2G4H6G8E7C8A7C6D8B7A5B3A1C2E1G2H4G6H8F7G5H7F8D7B8A6B4A2C1E2G1H3F2H1G3H5G7E8C7A8
F6D5E3D1C3E4C5E6F4D3B2A4B6C4E5F3D4F5D6B5A3B1D2F1H2G4H6G8E7C8A7C6D8B7A5B3A1C2E1G2H4G6H8F7G5H7F8D7B8A6B4A2C1E2G1H3F2H1G3H5G7E8C7A8
...


Oh, and for those who are interested here are the stats (memory requirement and number of attempts i.e. depthness of the B-tree):
Simply you need 15 (in worst case) attempts in order to find a key within 10,000,000 keys.
Nothing impressive, 15 tries, yet with no unpleasant surprises like unbalancing.
Also for data 1,240MB (the 130x10,000,000) the tree is 2,133,638KB=2,083MB in size.

There are three reasons for Tcheburaschkasort's poor performance, first is the slow dumping of sorted data:
66 seconds are divided in:
Sorting: Time for putting phrases into trees: 45 second(s)
Dumping: Time for shaking phrases from trees: 21 second(s)

Second is the way I insert new keys, for speed boost (when incoming data is not of unique keys as here) fast-search is performed and if failed new search-insert is enforced, grmbl.
In simple words, insertion is slow, especially for order 3, double-grmbl.

Third is the parsing of keys, in Cubesort I wrote it synthetically:
fread(&z_array[cnt].key, sizeof(keyType), 1, ifp);

While in Tcheburaschkasort the parsing is byte-by-byte, as in real-world rippers:
                if ( workbyte < '0' ) // Most characters are under alphabet - only one if // Cheburashka
                {
ElStupido:
                        // This fragment is MIRRORed: #1 copy [
                        if (workbyte == 10) {NumberOfLines++;}
...
// Cheburashka [ 
                else if( workbyte <= '9' )
		{
                        //if( wrdlen < 31 )
                        if( wrdlen < 128 ) // Cheburashka
                        //if( wrdlen < LongestLineInclusive )
                        { wrd[ wrdlen ] = workbyte; }
                        wrdlen++;
		}
                else if( workbyte >= 'A' &&  workbyte <= 'Z' )
		{
                        //if( wrdlen < 31 )
                        if( wrdlen < 128 ) // Cheburashka
                        //if( wrdlen < LongestLineInclusive )
                        { wrd[ wrdlen ] = workbyte; }
                        wrdlen++;
		}
// Cheburashka ]
                else if( workbyte >= 'a' &&  workbyte <= 'z' )
		{
                        //if( wrdlen < 31 )
                        if( wrdlen < 128 ) // Cheburashka
                        //if( wrdlen < LongestLineInclusive )
                        { wrd[ wrdlen ] = workbyte; }
                        wrdlen++;
		}
		else
                {
                        // This fragment is MIRRORed: #2 copy [
                goto ElStupido;
                        // This fragment is MIRRORed: #2 copy ]
		}

Scared! Well above fragment handles 'words' of alpha-numerical type 1..128 bytes in length.

Having an old Samsung 470 SSD on my laptop (Core 2 T7500 2200MHz) I ran the scariest sort of all, with all-external memory operations i.e. no physical no virtual used:
E:\BiShowdown_Cubesort_Tcheburaschkasort_Intel_64bit>timer64.exe TcheburaschkaSort TcheburaschkaSort.lst TcheburaschkaSort.txt 2900123 z
Leprechaun_singleton (Fast-In-Future Greedy n-gram-Ripper), rev. 16FIXFIX, written by Svalqyatchx.
Purpose: Rips all distinct 1-grams (1-word phrases) with length 1..128 chars from incoming texts.
Feature1: All words within x-lets/n-grams are in range 1..31 chars inclusive.
Feature2: In this revision 128MB 1-way hash is used which results in 16,777,216 external B-Trees of order 3.
Feature3: In this revision, 1 pass is to be made.
Feature4: If the external memory has latency 99+microseconds then !(look no further), IOPS(seek-time) rules.
Pass #1 of 1:
Size of input file with files for Leprechauning: 34
Allocating HASH memory 134,217,793 bytes ... OK
Allocating/ZEROing 2,969,725,966 bytes swap file ... OK
Size of Input TEXTual file: 1,300,000,000
\; 00,008,643P/s; Phrase count: 10,000,000 of them 10,000,000 distinct; Done: 64/64
Bytes per second performance: 1,123,595B/s
Phrases per second performance: 8,643P/s
Time for putting phrases into trees: 1157 second(s)
Flushing UNsorted phrases: 100%; Shaking trees performance: 00,056,179P/s
Time for shaking phrases from trees: 356 second(s)
Leprechaun: Current pass done.

Total memory needed for one pass: 2,133,638KB
Total distinct phrases: 10,000,000
Total time: 1528 second(s)
Total performance: 6,544P/s i.e. phrases per second
Leprechaun: Done.

Kernel  Time =  1096.609 =   71%
User    Time =   217.449 =   14%
Process Time =  1314.058 =   86%    Virtual  Memory =    130 MB
Global  Time =  1527.601 =  100%    Physical Memory =    131 MB

E:\BiShowdown_Cubesort_Tcheburaschkasort_Intel_64bit>

Only 1527/108=14 times slower than Cubesort, not bad in my eyes.

As for Tcheburaschka, few things remain to be done, in-order traversal dump and few more raw ideas, however I lost my momentum, now I am interested in textual decompression.

Ah, and the name, Чебурашка, it is a little supercalm soullet (English lacks double diminutives), in fact the golden Russian animatronics movie, love it.
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 
QuestionTeam Contract Algorithm Pin
Laurence Senna27-Mar-14 21:23
MemberLaurence Senna27-Mar-14 21:23 
AnswerRe: Team Contract Algorithm Pin
Richard MacCutchan28-Mar-14 1:22
mveRichard MacCutchan28-Mar-14 1:22 

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.