SitePoint Sponsor

User Tag List

Results 1 to 3 of 3
  1. #1
    SitePoint Enthusiast Sjoerd's Avatar
    Join Date
    Jun 2005
    Location
    Leimuiden, The Netherlands
    Posts
    83
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    Speed up while-loop with lookup table

    For a compression/decompression project I work on, I created a small loop which is used to replace a bit sequence with an unknown length with normal characters. To accomplish this, I use an array where the key names are the bit sequences and the values are the values which should be outputted. The only problem is that arrayName[keyname] lookups are pretty slow: I tested it and the "if (arrLookup[strTempBits])" line is taking 80% (!) of the time needed to execute the complete function. Does anybody know of another way to do such a lookup table without having to worry it takes that much time?

    My compression function takes only about 1 second to compress 50KB of data with a compression ratio of 40 to 50%. Decompression the compressed string takes 4 to 5 secondes only because of the "if (arrLookup[strTempBits])" line so I really want to speed it up.

    Once the decompression function is faster, I will implement a self made Run Length Encoding technique which can (together with my current compression) give a compression ratio of 60 to 80%, based on the input text. I am planning to release the algorithm as open-source.


    HTML Code:
    <script>
    
    document.write(convert());
    
    function convert()
    {
    	// The string to be converted
    	strBits = "100101110001101010000100110010111000110101000010010100101000011011100101100";
    	// An array which holds all the values and their replacements
    	arrLookup = new Array()
    	arrLookup["100"] = "a";
    	arrLookup["101"] = "b";
    	arrLookup["1100"] = "c";
    	arrLookup["01101"] = "d";
    	arrLookup["01000"] = "e";
    	arrLookup["01001"] = "f";
    
    	// Array to keep the converted values
    	var arrOutput = new Array();
    	// Temporary variable which remembers the bits read by strBits.charAt(i)
    	var strTempBits = "";
    	
    	var i = 0;
    	intLoopLength = strBits.length;
    	while (i < intLoopLength)
    	{
    		// Read a bit and put it at the end of strTempBits
    		strTempBits += strBits.charAt(i);
    		i++;
    		// If the bit sequence in strTempBits is the same as a key name of the 
    		// arrLookup array, output the value of that array item to arrOutput
    		if (arrLookup[strTempBits])
    		{
    			arrOutput.push(arrLookup[strTempBits]);
    			strTempBits = strBits.charAt(i);
    			i++;
    		}
    	}
    	// Put the array into a string variable
    	var strOutput = arrOutput.join("");
    	// Output
    	return strOutput;
    }
    
    </script>

  2. #2
    SitePoint Wizard
    Join Date
    Nov 2004
    Location
    Nelson BC
    Posts
    2,310
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    *edit* hmm it doesn't work the way it is because 010001 is read as 100 before the entire sequence can be read in. Maybe if each character were a fixed length sequence which kind of defeats the purpose of the function. I'll see if I can figure something else out.

    *edit 2* I guess you could use my technique to limit the amount of lookups done on the original array, something like:
    Code:
    if( aNum[nDec] ) {
    	if (arrLookup[strTempBits]) {
    		arrOutput.push(arrLookup[strTempBits]);
    		strTempBits = strBits.charAt(i);
    		i++;
    	}
    }
    *original response*

    Something to try, I don't know if it would really be faster.

    IF your bit sequences are distinct binary numbers, for example 2 sequences that are binary equals dont exist (eg 0100 and 100 are not allowed as 2 diff patterns), then you could do this:

    Instead of an array with keys, use a normal array with the decimal equivalent of the bit pattern:
    Code:
    var aNum = new Array();
    	
    aNum[4] = "a";
    aNum[5] = "b";
    aNum[12] = "c";
    aNum[13] = "d";
    aNum[8] = "e";
    aNum[9] = "f";
    then do your lookup like this:
    Code:
    while (i < intLoopLength)
    {
    	// Read a bit and put it at the end of strTempBits
    	strTempBits += strBits.charAt(i);
    	i++;
    	// If the bit sequence in strTempBits is the same as a key name of the 
    	// arrLookup array, output the value of that array item to arrOutput
    	nDec = parseInt(strTempBits, 2);
    	if( aNum[nDec] ) {
    		arrOutput.push(aNum[nDec]);
    		strTempBits = strBits.charAt(i);
    		i++;
    	}
    }
    Like I said, not sure if it'd be faster but I get the impression that yes.

  3. #3
    SitePoint Enthusiast Sjoerd's Avatar
    Join Date
    Jun 2005
    Location
    Leimuiden, The Netherlands
    Posts
    83
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Seems to be a good idea, your original one Jim If I, before I add the decimal value of the binary string, put a "1" in front of the original binary sequence, 0100 will be written as 10100 and 100 as 1100, which will be 20 and 12 as decimal values! I'll try to see if it works and let you know. Thanks for now


Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •