hard DOM question - gordian knot of lagging :)

[rravenn]

I created a form for some webapp. It features account numbers that are in and out of some group respectively presented in two listboxes, with js to allow selecting multiple numbers in a listbox and moving them to another e.g. moving accounts in and out of the group.
I move item using document fragment - i append moved options from one listbox to it and then append it to another listbox and it works quick even if the user moves 500 accounts at once.

Problem is, the number of accounts in a list box can be up to 20k, so searching for a single account is tiresome for users.
Thus I added a textbox above them and added some js to allow selecting matching account in listboxes as the user types it.

However, searching thru 20k units one by one turned out to be really slow so i added binary search to perform autoselection.

Unfortunately, binary search depends on sorting, so as soon as the user moves some accounts back and forth, moved accounts stop showing up when their name is typed cause sorting is screwed in the listboxes (items are initially sorted).

So then, to keep the listbox sorted I have two options. I either resort it after the addition by moving all the options to the array, sorting it and readding them back. This is very slow when the items are moved into a big list, even if i use documentfragment to insert them all at once again.

I can also insert them into place at once, e.g. for each moved item, search for the position that won't break searching and insert it there using insertBefore. It is slow again cause instead of inserting options to the destination listbox all at once I add them one by one.

Is there a good solution for this situation?
The best I found now is dynamically grouping asjasten inserted options into document fragments (when there are several groups where they go one after another (1,2,3,4,5 without skipped values)), searching the destination listbox for the position for each group and inserting it there.
This work for ~60% of the cases if big moves, for the remaining 40% accounts are spread thru the list and it doesn't work.

Another option is maintaining a list of moved options in an Array variable and searching main list and moved options separately but that's not really good cause when many options are moved, the 2nd search will become slow (I think so, haven't yet implemented that).

 

[LFI]

Here's some code I once wrote that re-sorts options as they move or are returned to the original list. Perhaps it will help you:

//add(...), remove(...), and addOrRemove(...) are used by all of the paired
// multiple select lists of names for moving names from the left (list of all names) to the
// right (list of selected names) or vice-versa.
function add(listName)
{
	var selectList = document.forms[0].elements["POSSIBLE_"+listName];
	var moveToList = document.forms[0].elements["SELECTED_"+listName];

	addOrRemove(selectList, moveToList);
}//end add(var)

function remove(listName)
{
	var selectList = document.forms[0].elements["SELECTED_"+listName];
	var moveToList = document.forms[0].elements["POSSIBLE_"+listName];

	addOrRemove(selectList, moveToList);
}//end remove(var)

function addOrRemove(selectList, moveToList)
{
	var index;

	for(i=0; i<selectList.options.length; i++)
	{
		if(selectList.options[i].selected)
		{
			insertNewOption(selectList.options[i], moveToList, 0, moveToList.options.length-1);
			selectList.options[i] = null;
			i--; //because the selectList is now 1 smaller and what was once in
				 // position (i+1) is now in position i.  i is about to increment in the
				 // for-loop, so we need to decrement it one now to avoid skipping the
				 // option now in the i-spot.
		}//end if
	}//end for
}//end addOrRemove(var, var)

//inserts movingOption into the moveToList in the appropriate
// place, using indeces of the moveToList (low, high) to determine
// the appropriate location, and recursively calling itself with
// a new low or high to pinpoint the exact right place.  Uses
// binary method to do it.
function insertNewOption(movingOption, moveToList, low, high)
{
	var indexToCompare = extractIndex(movingOption.value);

	if(moveToList.options.length == 0)
	{
		moveToList.options[0] = new Option();
		moveToList.options[0].value = movingOption.value;
		moveToList.options[0].text = movingOption.text;
		moveToList.options[0].NAME = movingOption.NAME;
	}//end if
	else
	{
		var lowIndex = extractIndex(moveToList.options[low].value);
		var highIndex = extractIndex(moveToList.options[high].value);
		if(lowIndex > indexToCompare)
		{
			moveToList.options[moveToList.options.length] = new Option();

			for(j=moveToList.length-1; j>low; j--)
			{
				moveToList.options[j].value = moveToList.options[j-1].value;
				moveToList.options[j].text = moveToList.options[j-1].text;
				moveToList.options[j].NAME = moveToList.options[j-1].NAME;
			}//end for

			moveToList.options[low].value = movingOption.value;
			moveToList.options[low].text = movingOption.text;
			moveToList.options[low].NAME = movingOption.NAME;
		}//end if
		else if(highIndex <= indexToCompare)
		{
			moveToList.options[moveToList.options.length] = new Option();

			for(j=moveToList.length-1; j>high+1; j--)
			{
				moveToList.options[j].value = moveToList.options[j-1].value;
				moveToList.options[j].text = moveToList.options[j-1].text;
				moveToList.options[j].NAME = moveToList.options[j-1].NAME;
			}//end for

			moveToList.options[high+1].value = movingOption.value;
			moveToList.options[high+1].text = movingOption.text;
			moveToList.options[high+1].NAME = movingOption.NAME;
		}//end else if
		else if((low+1) == high)
		{
			moveToList.options[moveToList.options.length] = new Option();

			for(j=moveToList.length-1; j>low+1; j--)
			{
				moveToList.options[j].value = moveToList.options[j-1].value;
				moveToList.options[j].text = moveToList.options[j-1].text;
				moveToList.options[j].NAME = moveToList.options[j-1].NAME;
			}//end for

			moveToList.options[low+1].value = movingOption.value;
			moveToList.options[low+1].text = movingOption.text;
			moveToList.options[low+1].NAME = movingOption.NAME;
		}//end else if
		else
		{
			var midListSize = Math.floor((high+low)/2);
			var midIndex = extractIndex(moveToList.options[midListSize].value);

			if(indexToCompare < midIndex)
				high = midListSize;
			else
				low = midListSize;

			insertNewOption(movingOption, moveToList, low, high);
		}//end else
	}//end else
}//end insertNewOption

function extractIndex(indexField)
{
	// form of indexField:  <last name>_<id>_<option number>
	// only the <option_number> is desired here
	return parseInt(indexField.substring(indexField.lastIndexOf("_")+1));
}//end extractId(var)

Here is some sample HTML for my select lists:

<TD ALIGN=CENTER VALIGN=MIDDLE>
   <SELECT MULTIPLE SIZE=10 NAME=POSSIBLE_VENDOR>
   ... <!--OPTIONS LIST*-->
   </SELECT>
  </TD>
  <TD ALIGN=CENTER VALIGN=MIDDLE>
   <INPUT TYPE=BUTTON VALUE='ADD -->' ONCLICK=add("VENDOR")>
   <BR>
   <BR>
   <INPUT TYPE=BUTTON VALUE='<-- REMOVE' ONCLICK=remove("VENDOR")>
  </TD>
  <TD ALIGN=CENTER VALIGN=MIDDLE>
   <SELECT MULTIPLE SIZE=10 STYLE="WIDTH:200" NAME=SELECTED_VENDOR>
   </SELECT>
  </TD>

*note: the options list in the left-hand-side list was created by JSP/data-base hit. The SQL ordered the results alphabetically AND tagged the rownum-1 value onto the results. I then had a record of the original index of the items and, as you can see in the JavaScript, this aids in keeping the items in order whether you move them to the right-hand-side list or return them back to the left.

'hope this helps!

--Dave