Better approach for this function? 2

[hererxnl]

This is an update question to a previously answered thread found here:

http://www.tek-tips.com/viewthread.cfm?qid=1261519&page=1

A quick synopsis:
The function below provides a quick "jump to" navigation of approx 3000 links from a textbox to a different frame. User enters "T" and the first link starting with "T" is made visible.

The question is whether there is a better way to do this. Using Opera and FF this work reasonably well, but the JS execution in IE (as we all know) is terrible and the lag makes it almost useless.

<script type="text/javascript">
function jumpToLink(str){
	var linkList=top.frames['List'].document.getElementsByTagName("a");
	for(i=0;i<linkList.length;i++){
		if(linkList[i].getElementsByTagName("span")[0].innerHTML.substr(0,str.length).toLowerCase()==str.toLowerCase()){
			linkList[i].focus();
			break;
		}
	}
	document.searchform.searchbox.focus();
	}
</script>

The Textbox is coded as:

<input type="text" name="searchbox" onkeyup="jumpToLink(this.value)" title="Jump To...">

A typical link looks like this:

<a href="Details.asp?Link=Link1" target="Details" title="View Details..."><span class="splnk">Today - Tomorrow</span></a>

and is generated dynamically using ASP.

Any ideas would be greatly appreciated. As always, thanks in advance.

 

[trollacious]

If you put all the elements in arrays as soon as the page loads, you wouldn't have to access them through the DOM each time. That would be faster.

Also, unrolling the for loop would speed up the search. I generally use sets of 10 for unrolling. If you don't know what that means, do a Google search for "Javascript optimization" and "unroll loop".

Lee

 

[theniteowl]

This may not be necessary after following trollacious' recommendation above but the thought occured to me so I thought I would throw it out there.

As trollacious said, store your data in an array, not in a text string. Sort the array alphabetically.
When the function executes and it goes to search the array for a match, when it finds a match store the array index position of the match in a global variable.
When the next key is pressed unless the key was a backspace or delete you know that the word is going to be past the previously saved index position so you start your loop there instead of at the beginning and you can save a whole lot of iterations through the loop.

Another idea that can be added to the above is to keep an index of where each character begins in the array.
For instance if the first searchable character is an A then you will know that in the array you can begin searching for words beginning with A at index 0. But you may have 200 words beginning with A and the first one starting with B would begin at index 199, C at 312, etc.
If you have an index as to where in the array these letters begin then you can grab the first character typed into the field to know where in the array to begin searching even before having a saved index position from a previous search. Then your very first look through the array will be in a very limited section and not looping through areas that are absolutely not related.

Also, make sure you break out of the loop once you find a match rather than letting it run through the rest of the array.

I have never tried these approaches myself but when working with large amounts of information I think they would pay off.

At my age I still learn something new every day, but I forget two others.

 

[hererxnl]

Good suggestions. The help around here is exemplary.

trollacious:

Unrolling a loop is a new concept to me. I've been trying to work through some rather poor examples I found elsewhere and am not having success.

Care to provide an example based on this function? I also read about the Duff technique of unrolling and several faster versions, if you don't feel like showing me the technique with this function could you tell me what the most effective would be with this particular case? I was thinking the Duff technique because I don't know the number of iterations.

theniteowl:

You make some good points about handling this data. Most of your suggestions are concepts that are familiar to me so I won't trouble you to go further. I think your ideas will pay off for my users, thanks.

 

[theniteowl]

I had not heard about the unroll technique until trollacious mentioned it but I have to say it is something I have actually done on my own. I tend to think in terms of efficiency where possible so...

All the unroll technique is really doing is performing multiple tasks in the same pass of the loop and incrementing the counter so the loop will run fewer times.
It helps if multiple tasks can be done without running them through a logic block which would slow things down.
In your situation I do not immediately see how unrolling can be applied since you have to test every array value anyway and it is the logic that will slow you down.

Unrolling will not work in every situation and I do not see an easy way to apply it here but have not spent much time pondering it. Perhaps someone else can see it more clearly.


At my age I still learn something new every day, but I forget two others.

 

[hererxnl]

Thanks for the comment nite. I had a similiar thought but JS is fairly new to me and I'm interested in all coding concepts. Soon or later they all come in handy.

Does anyone else have a comment about this?

 

[hererxnl]

So stars were awarded for two great comments. I haven't unrolled the for loop and I'll be working on implementing some of nite's more advanced suggestions, but just taking dom out of the loop has made a dramatic improvement in this function's performance. Here's the gist of the current solution:

Page 1 builds a dynamic list of links using asp. After asp has built the link list I'm creating an array and passing it to a global on my search page. Once the global on the search page has been defined I can query the list without accessing the dom in my for loop.

Page 1 (list page) function (in <body> after asp code):

<script type="text/javascript">
var linkList=document.getElementsByTagName("a");
var linkarray=new Array()
for(i=0;i<linkList.length;i++){
	linkarray[i]=linkList[i].getElementsByTagName("span")[0].innerHTML.toLowerCase();
}
top.frames['Nav'].linkarray=linkarray;
</script>

Page 2 (search page) function (in <head>):

<script type="text/javascript">
var listarray=new Array()
function jumpToLink(str){
	var linkList=top.frames['List'].document.getElementsByTagName("a");
	str=str.toLowerCase()
	for(i=0;i<listarray.length;i++){
		if(listarray[i].substr(0,str.length)==str){
			linkList[i].focus();
			break;
			}
	}
	document.searchform.searchbox.focus();
}
</script>

Excellent performance even in IE, the jump from 0 to z is fast enough so you don't have real typing lag when typing a full word. I'm continuing to refine this as the list will never get smaller.

Thanks again to troll and nite for their great suggestions! (ps, I still want to know if troll or anyone else thinks "unrolling" this loop would help, it's currently at 3164 iterations and growing!)

 

[theniteowl]

Do you need to generate the list on the page or is that just how you got the data from ASP to your javascript array?

You can query the database and output the javascript array directly if that works in your situation.

Here is a bit of ASP that I use to pull data from the DB and output it as a javascript array.

<%
  mysql = "SELECT * FROM mytable"
  set rs=conn.execute(mySQL) 
    rsstring = rs.GetString(,,"','","','","")
    outstr=Left(rsstring,len(rsstring)-2)
    Response.Write "<SCR" & "IPT LANGUAGE=""JavaScript"">" & vbCrlf
    Response.Write "var myarray = new Array('" & outstr & ");" & vbCrLf
    Response.Write "</SCR" & "IPT>" & vbCrlf
  rs.Close
  Set rs = Nothing

conn.Close
Set conn = Nothing
%>

When you are dealing with a lot of records the getstring method gets less efficient but you can specify the number of records to retrieve in a chunk and that helps performance. getstring will pull all the content and output it as a string rather than having to loop through the recordset and build the string manually.
Once the string is complete I response.write it to the page including the javascript script tags. It works very efficiently and all the work occurs server-side.

It has been suggested that if you are pulling greater than 2000 records you should specify the upper limit to return at once but since your records are just a single word rather than a whole bunch of fields per record you will probably not have to bother limiting the size in getstring.


At my age I still learn something new every day, but I forget two others.

 

[trollacious]

Here's an example of unrolling a loop using some of your code:

<script type="text/javascript">
var listarray=new Array();

function jumpToLink(str)
{
var linkList=top.frames['List'].document.getElementsByTagName("a");
str=str.toLowerCase();

var over = listarray.length % 10, found = false;

for(var i=0;i<over;i++)
  {
  if(listarray[i].substr(0,str.length)==str)
    {
    linkList[i].focus();
    found = true;
    break;
    }
  }

if (!found)
  {
  var counter = over
  for(i=over;i<listarray.length;i+=10)
    {
    if(listarray[counter].substr(0,str.length)==str)
      {
      linkList[counter].focus();
      found = true;
      break;
      }
    counter++;

    if(listarray[counter].substr(0,str.length)==str)
      {
      linkList[counter].focus();
      found = true;
      break;
      }
    counter++;

    if(listarray[counter].substr(0,str.length)==str)
      {
      linkList[counter].focus();
      found = true;
      break;
      }
    counter++;

    if(listarray[counter].substr(0,str.length)==str)
      {
      linkList[counter].focus();
      found = true;
      break;
      }
    counter++;

    if(listarray[counter].substr(0,str.length)==str)
      {
      linkList[counter].focus();
      found = true;
      break;
      }
    counter++;

    if(listarray[counter].substr(0,str.length)==str)
      {
      linkList[counter].focus();
      found = true;
      break;
      }
    counter++;

    if(listarray[counter].substr(0,str.length)==str)
      {
      linkList[counter].focus();
      found = true;
      break;
      }
    counter++;

    if(listarray[counter].substr(0,str.length)==str)
      {
      linkList[counter].focus();
      found = true;
      break;
      }
    counter++;

    if(listarray[counter].substr(0,str.length)==str)
      {
      linkList[counter].focus();
      found = true;
      break;
      }
    counter++;

    if(listarray[counter].substr(0,str.length)==str)
      {
      linkList[counter].focus();
      found = true;
      break;
      }
    counter++;
    }
  }
if (!found)
  {
  alert(str + ' not found');
  }
document.searchform.searchbox.focus();
}
</script>

I added a boolean variable found to allow skipping the second loop if there's a match in the first one. Added into the second loop, it allows an alert if the character sequence isn't found.

Lee