15,117,095 members
Home / Discussions / Algorithms

# Algorithms

 Re: Algorithm for comparing word with randomly distributed substring Sanmayce3-Jul-14 8:15 Sanmayce 3-Jul-14 8:15
 Re: Algorithm for comparing word with randomly distributed substring Sanmayce5-Jul-14 8:19 Sanmayce 5-Jul-14 8:19
 Cubesort Gregorius van den Hoven22-Jun-14 5:09 Gregorius van den Hoven 22-Jun-14 5:09
 Re: Cubesort Sanmayce28-Jun-14 9:02 Sanmayce 28-Jun-14 9:02
 Re: Cubesort Gregorius van den Hoven29-Jun-14 10:58 Gregorius van den Hoven 29-Jun-14 10:58
 Re: Cubesort Sanmayce30-Jun-14 7:48 Sanmayce 30-Jun-14 7:48
 Re: Cubesort Gregorius van den Hoven12-Jul-14 5:01 Gregorius van den Hoven 12-Jul-14 5:01
 Re: Cubesort Sanmayce3-Jul-14 5:30 Sanmayce 3-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: Copy Code ```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): Copy Code ```----------------- |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: Copy Code ```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 . 07/03/2014 04:19 AM .. 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: Copy Code `fread(&z_array[cnt].key, sizeof(keyType), 1, ifp);` While in Tcheburaschkasort the parsing is byte-by-byte, as in real-world rippers: Copy Code ``` 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: Copy Code ```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.
 Reduce a Q2SAT formula Apurvgupta15-Jun-14 21:48 Apurvgupta 15-Jun-14 21:48
 Fastest textual decompression in C Sanmayce10-May-14 9:54 Sanmayce 10-May-14 9:54
 Re: Fastest textual decompression in C Richard MacCutchan10-May-14 22:46 Richard MacCutchan 10-May-14 22:46
 Re: Fastest textual decompression in C Sanmayce12-May-14 1:18 Sanmayce 12-May-14 1:18
 Re: Fastest textual decompression in C Richard MacCutchan12-May-14 2:24 Richard MacCutchan 12-May-14 2:24
 Re: Fastest textual decompression in C Chris Losinger23-May-14 4:12 Chris Losinger 23-May-14 4:12
 Re: Fastest textual decompression in C Sanmayce24-May-14 8:17 Sanmayce 24-May-14 8:17
 The Bessel-Overhauser Spline interpolation - suitable values for the weight function Kenneth Haugland4-Apr-14 0:34 Kenneth Haugland 4-Apr-14 0:34
 Re: The Bessel-Overhauser Spline interpolation - suitable values for the weight function Kenneth Haugland6-Apr-14 1:30 Kenneth Haugland 6-Apr-14 1:30
 Factoring algorithm Member 41945931-Apr-14 5:46 Member 4194593 1-Apr-14 5:46
 Re: Factoring algorithm Bernhard Hiller1-Apr-14 21:44 Bernhard Hiller 1-Apr-14 21:44
 Re: Factoring algorithm Member 41945932-Apr-14 7:17 Member 4194593 2-Apr-14 7:17
 Re: Factoring algorithm Kornfeld Eliyahu Peter2-Apr-14 10:30 Kornfeld Eliyahu Peter 2-Apr-14 10:30
 Re: Factoring algorithm Peter_in_278023-May-14 16:34 Peter_in_2780 23-May-14 16:34
 Re: Factoring algorithm Member 419459323-May-14 18:03 Member 4194593 23-May-14 18:03
 Team Contract Algorithm Laurence Senna27-Mar-14 21:23 Laurence Senna 27-Mar-14 21:23
 Re: Team Contract Algorithm Richard MacCutchan28-Mar-14 1:22 Richard MacCutchan 28-Mar-14 1:22
 Last Visit: 31-Dec-99 19:00     Last Update: 1-Dec-21 0:06 Refresh ᐊ Prev1...48495051525354555657 Next ᐅ