Solved

How can I EFFICIENTLY sort a JavaScript multi-dimensioned array?

Posted on 2001-09-08
21
611 Views
Last Modified: 2012-06-21
I am trying to sort a multi-dimensioned array in JavaScript that I load into the page as a comma delimited JS file.  Essentially, I have a table, where when you click on the headings, the table resorts by that column.  I have seen solutions that work on the post html table but they are too slow when one has hundreds of entries.  I want to sort the array and then convert to HTML.  I also need to be able to specify if the column is alpha or numeric for the sort.  Thanks in advance.
0
Comment
Question by:wmgraham
  • 8
  • 8
  • 2
  • +3
21 Comments
 
LVL 22

Expert Comment

by:CJ_S
ID: 6466652
We need a small example of the data you have, and how it should be sorted and then shown on the page.

Regards,
CJ
0
 

Author Comment

by:wmgraham
ID: 6468411
I have a server side database program that populates an array in a js file as follows

DataArray = new Array(
new Array("col_1", col_2, "col_3", col_4),
new Array("col_1", col_2, "col_3", col_4),
new Array("col_1", col_2, "col_3", col_4),
new Array("col_1", col_2, "col_3", col_4),
etc. for several hundred rows
new Array("col_1", col_2, "col_3", col_4)
);

I then wrap this client side in HTML (an HTML table) along with all the other HTML for a complete page and do a document.write.  The table headings are hyperlinked to a sort routine that is supposed ot sort the original array and then rewrite the table and redo a document.write.  (I have seen a javascript function that sorts the table object, which works fine with just a dozen or so entries, but my tables have hundrds of entries and it takes up to a minute (reformatting the array into HTML is just a few seconds).

Before appearance on screen:
   Hdg1    Hdg2    Hdg3
    A        M     11
    B        C      4
    C        F      3

After clicking on Hdg2:
   Hdg1    Hdg2    Hdg3
    B        C      4
    C        F      3
    A        M     11

After Clicking on Hdg3:
   Hdg1    Hdg2    Hdg3
    C        F      3
    B        C      4
    A        M     11

Trying to check one of the proposals of the other respondents, I realize I have a basic problem that my outer array is an array of rows, not columns.  I have been trying to write a simple tarnsposition function that converts the rows into columns, but am having trouble (and it should be so simple).

Thanks for any help.

Bill
0
 
LVL 1

Expert Comment

by:snakehollywood
ID: 6469076
If your not going to try and support that Nasty Netscape browser, then this is quite simple, as IE has some nice methos that allow you to reorder table rows on the fly.
Basically all the rows in a table are a collection, which you can sort and order. An each row has a collection of cells.

I am presuming you already have the skills to apply a sort routine, you just need to know how to apply it in Javascript.

So the easiest option is if I point you at the MSDN reference for these collections.

msdn.microsoft.com/workshop

Look under
web development
 -HTML and Dynamic HTML
  -SDK Documentation
   -DHTML Reference
    -DHTML collections

Here you can find details on the CELLS and ROWS collections.

If you are not able to figure it out from here, let me know as I have actually written a clientside table sorter b4, I just need to find what the hell website I did it on so I can grab the sourcecode.


0
 
LVL 2

Accepted Solution

by:
rabanero earned 100 total points
ID: 6469929
You need to define correct sort function to apply to your table. I'm going to explain you with a easy case:

First, you need to define standard sort method. The standard constructor is:

function sort_method (elemA, elemB);

For a 2-dimensional array we have to pass the number of column to sort. But the standard sort has only two parameters (the A and B elements). The sollution is to encapsulate the method into a class, and add a variable to control the column. For a 2-dimensional array could be:

function sortedArray() {
    this.content = new Array();  // the data
    this.sort = sortedArray_sort;  // Rewrites default method
}

Now we have data and sort method encapsulated in a Javascript class. In your code, you will need to declare a var with this new class:

var myArray = new sortedArray();

And start to write data:

myArray.content[0] = new Array("col_1", col_2, "col_3", col_4);
myArray.content[1] = new Array("col_1", col_2, "col_3", col_4);
...

content varable class will be filled then. But let's continue writting the sort method for the class:

function sortedArray_sort(sortColumn) {
    sortMethod.column = sortColumn;
    this.content.sort(sortMethod);
}

Let's see: First, sort method has a parameter that indicates for what column want to sort. Then, you will sort writting:

myArray.sort(0);
/* Sorts by first column (Read the class to understand the sort method: It's sort, not sortedArray_sort! We are rewritting standard sort)*/
myArray.sort(1);
myArray.sort(2);
...

Second, we are overcharge "sortMethod" with a extra parameter: column. We are doing this -and not by normal parameter- because sortMethod must be agree with standard Javascript sort, that only has 2 paramters (A and B elements).

It's time to write the sortMethod (Yeah!):

function sortMethod(elemA, elemB) {
    var numCol = this.column; // Get the extra parameter. I'm bad XD
    // get the comparision items for entire arrays
    var val1 = elemA[numCol];
    var val2 = elemB[numCol];

    // Always ascending sort. Can be extended
    return val1 < val2 ? -1 : val1 == val2 ? 0 : 1;
}

Well, what a piece of code! I'll try to explain you how does it work:

sortMethod has 2 params: elemA and elemB, complishing standard Javascript. Since it's called by this.content.sort(sortMethod), elemA and elemB are direct elements of content array: two array elements in second level. This method is automatly called by Javascript each time it has to sort two element of first level array.

The indirect parameter "column" is passed throught function class variable. Javascript is jelly :)

With val1 and val2 we get the items of two second level arrays to do the comparision: Example: If it's time to sort 2 rows of array by second column:

elemA: "eo"  32 4
elemB: "ras" 13 3

Then val1 = 32 and val2 = 13. Remember, they are used to sort elemA with elemB, not only 32 with 13. They are the items to compare entire rows, not the target of sort.

Finnaly, returns -1, 0 or 1 if val1 < val2, val1 == val2 or val1 > val2. They are standard sort return values for Javascript sort methods.

And... That's all! your multidimensional array will be sorted calling normal sort and passing column number.

And now, I will post you the "proffesional" code. It includes methods to sort ascending or descending, numbers, chars, etc...

Wait...
0
 
LVL 2

Expert Comment

by:rabanero
ID: 6469983
I have uploaded a complete code:

http://usuarios.tripod.es/rabanero/

This is very complex code. Used to sort with text, decimals, integers and dates. It has also a js to syncronize four frames: Try to reduce the window until scrollbars appears and scroll with them. Moving central frame you move frames at edge -titles and first column-.

I hope you find it usefull, and not very confuse. Write back to know your oppinion.

Bye.
0
 
LVL 2

Expert Comment

by:rabanero
ID: 6469985
This works on NS and IE. And it's not to easy! HE HE HEEE
0
 
LVL 2

Expert Comment

by:rabanero
ID: 6470300
Have you been answered?

If yes, please assing the points to correct comment (me! me! :)). If no, explains your reasons and we'll help you.

Bye.
0
 

Author Comment

by:wmgraham
ID: 6472800
I am in the process of reviewing it now (having a little trouble with the Spanish - German or English are easier for me - but I'll work my way through).  Unfortunately, I broke my glasses today and have been running around trying to get an alternative - I'm blind without them.  Only sunglasses now for a day or two.  I don't want to put you off, but I do want to try it with a few hundred realistic records to see how it holds up with volume.

Be back to you as soon as I can.
0
 

Author Comment

by:wmgraham
ID: 6474258
OK, the Spanish doesn't make it very easy but I have been able to find the meanings of most of the individual words and am trying to follow the logic.  I will get there.

The bigger current problem is that I need to test your solution with a larger data set (300 rows, 10 columns, 2 columns of up to 50 Bytes and the rest a mixture of integers, dates, currency and text averaging around 10 Bytes).  

My current problem is the way you populate your input table; e.g.,

  tabla.insertaCelda(1,1,new CEnlace(Tipo.TEXTO('fge'));

I think I have an idea for a way to get around this, but first let me detail the problem.

I first need a way to translate my input data into this structure.  I don't think it would be a good idea to do this on the server side since it would turn a file that currently ranges up to 50k into almost 200k.
As I said in

My current data structure looks like this:
  DataArray = new Array(
  new Array("col_1", col_2, "col_3", col_4),
  new Array("col_1", col_2, "col_3", col_4));

This means I add very little overhead to the raw data which makes the download time reasonable.  

This means that to the actual data, I add only 3 bytes per field and 12 bytes per row. If I generated input as you have it, it would add 50+ Bytes per field.  At an average data length of around 12 bytes per field, if we assumed 10 fields per row and 300 rows per table, this would result in almost 200K of data.

It seems to me that the ideal solution would be to have an HTML page that initializes some parameters that describe the table (Col, Type, ColWidth).  E.g., :

ColParams = new Array(
new Array(1,'CEnlace',150),
new Array(2,'CEntero',100));

Then pass the data in my format.

Then on initialization, call a function that populates your input array from my input array.

Does this make sense?

Have you any experience with performance with larger arrays?

I have thought about storing some of the larger arrays that typically do not change in a session in a hidden frame and thus creating a kind of client-side session variables.  Do you see any down side to that?

I have increased the points to 150 because we are adding complexity.
0
 

Author Comment

by:wmgraham
ID: 6474266
It says I do not have enough points to increase the points.  Since this is the only question I have posted so far I am confused.  Could it be because the question got duplicated somehow?  Sorry about that.  I will have to see if I can find another way.
0
How to improve team productivity

Quip adds documents, spreadsheets, and tasklists to your Slack experience
- Elevate ideas to Quip docs
- Share Quip docs in Slack
- Get notified of changes to your docs
- Available on iOS/Android/Desktop/Web
- Online/Offline

 

Author Comment

by:wmgraham
ID: 6474810
It says I do not have enough points to increase the points.  Since this is the only question I have posted so far I am confused.  Could it be because the question got duplicated somehow?  Sorry about that.  I will have to see if I can find another way.
0
 

Author Comment

by:wmgraham
ID: 6475324
It says I do not have enough points to increase the points.  Since this is the only question I have posted so far I am confused.  Could it be because the question got duplicated somehow?  Sorry about that.  I will have to see if I can find another way.
0
 
LVL 2

Expert Comment

by:rabanero
ID: 6475855
Sorry wmgraham, I have been busy...

The world is being crazy...

I have readed your comments. We have a lot of problems with large amount of data, like you. But we have found some fixes to do code more efficiently.

First at all, if you're creating your table dinamically (we're doing with JSP's) you will find optimal to delete external <table>...</table> tags and close each row into <table>...</table> tags (to do this, revise the HTML dump of table structure and do this change). This produces each row will show as soon as it was created, instead of close entire table with a single <table>...</table>, that produces server has to create entire table, and then it will show it only at the finish.

The visual effect of this is client has not to wait so much time to start to see first data. As data is a continuous <table>...</table> <table>...</table> the first data will fill the screen and you will see how the scrollbar handler reduces continuosly while new rows are showing. But the client can see first results, while data is being created outside screen.

In conjuction of this, you can use any king of data pagination. If you have a large amount of data is more efficient to do "pages of data" and limit the number of rows for each page. The inconvenient of this is sort method only sorts the slice of data showed in each page, but is the fastest choice (And you could replace the javascript sort method by a new SQL select with another "order by", and resort data in server side).

Finally, I don't recommend you to encapsulate table generation into arrays with data structures. Javascript is slow, and it already consumes a lot of resources with existent data structures. Think another way to generate the table dinamically. We are coding in JSP's, and we usually do a "for" loop and "tabla.insertaCelda" inside loop, no more.

I hope you find usseful the code. But if you think you can optimize it, please send me your progress. For our work, we need 100% compatibility in NS and IE, don't forget.

Bye.

P.D.: If I am not wrong, you have 200 points in two open questions. It is all that I need :)
0
 
LVL 2

Expert Comment

by:rabanero
ID: 6475858
Any "king of data pagination" :)

I promise you to go to english class as soon as possible...
0
 

Author Comment

by:wmgraham
ID: 6476213
I will try to find the first question and release those 100 points when I get home from work tonight.  We have optimized the heck out of server side code.  We have also found that formating the data on the client side with JavaScript is just as fast as doing it on the server side for as many as 400 rows (and it offloads the burden from the server which is important if you are serving large numbers of clients) and the time to format is partially offset by having a smaller download.  Another benefit is that the queries needed to extract the data does very complex joins of up to 12 tables some of which have very large numbers of rows (millions).

I could use your help in being able to use your solution but being able to drastically reduce the vloume of data sent by sending the raw data in one array and the parameters that describe the data in a second array.  The second thing would be to separate the sort into one js file and the formating of the table into a second (this would make using more complex data formating easier).

I think it would benefit a lot of people if the final solution incorporated this and was available in English.  My thought is that we could collaborate on this if you are interested and then post it as the final answer to this side of the question (or just the sort part at least).

For this purpose, it might be easier to communicate directly by email.  If you are interested, my email is wmgraham@home.com.  If anyone else is interested in this.  Please also feel free to email me.
0
 
LVL 2

Expert Comment

by:rabanero
ID: 6476324
First at all, you can find your opened questions in your "member profile" link, on the top of page.

Javascript solution is great to free work on server side. But nothing is perfect, and it's paid for large amount of data transferred to client. The kind (not king :)) of application must define the final choice.

In my case, we usually make intranet applications. The bandwith is great, and then the target is optimize the work in server side.

Elsewhere, customer often confuses when you show him a large amount of data (more than 100 records), and the application is a "monster" and unneficient. They are happy if, in these cases, you offer any kind of shortcuts between records (numerated pages, indexing, etc...). So, if your problem is that you have a large amount of data to show perhaps you may think how to slice all that information, instead of how to show more quickly. I mean: You can optimize speed, but too many data will be a lost of usability.

And thank for your offer. By now, I am so busy and I can't help you so much, but I have thought to make useful libraries to community (in English, of course. What a pity! :) ). Please take my e-mail: jrbaena@eresmas.com. We probably will be in communication when I can be a bit free.
We can colaborate in doing libraries (YAJL, yet another javascript libaries :) ).

Bye!.
0
 

Author Comment

by:wmgraham
ID: 6478083
I will try to find the first question and release those 100 points when I get home from work tonight.  We have optimized the heck out of server side code.  We have also found that formating the data on the client side with JavaScript is just as fast as doing it on the server side for as many as 400 rows (and it offloads the burden from the server which is important if you are serving large numbers of clients) and the time to format is partially offset by having a smaller download.  Another benefit is that the queries needed to extract the data does very complex joins of up to 12 tables some of which have very large numbers of rows (millions).

I could use your help in being able to use your solution but being able to drastically reduce the vloume of data sent by sending the raw data in one array and the parameters that describe the data in a second array.  The second thing would be to separate the sort into one js file and the formating of the table into a second (this would make using more complex data formating easier).

I think it would benefit a lot of people if the final solution incorporated this and was available in English.  My thought is that we could collaborate on this if you are interested and then post it as the final answer to this side of the question (or just the sort part at least).

For this purpose, it might be easier to communicate directly by email.  If you are interested, my email is wmgraham@home.com.  If anyone else is interested in this.  Please also feel free to email me.
0
 
LVL 2

Expert Comment

by:rabanero
ID: 6481677
Okay, wmgraham. Thank you for your points in previous question. I'd be grateful if you give me this 100 points too, please.

Have you improved the code? Haye you had to rewrite it? I think you have had to do it, because it was a complex code with improvements as synchro frames.

Bye.
0
 
LVL 12

Expert Comment

by:ahosang
ID: 7968014
This question has been abandoned. I will make a recommendation to the moderators on its resolution in a week or so. I appreciate any comments that would help me to make a recommendation.
 
In the absence of responses, I may recommend DELETE unless it is clear to me that it has value as a PAQ. Silence = you don't care
 
ahosang
0
 
LVL 12

Expert Comment

by:ahosang
ID: 8029341
No comment has been added lately, so it's time to clean up this TA.
I will leave a recommendation in the Cleanup topic area that this question is:

points to rabanero
Please leave any comments here within the next seven days.
 
PLEASE DO NOT ACCEPT THIS COMMENT AS AN ANSWER!
 
ahosang
EE Cleanup Volunteer
0
 
LVL 5

Expert Comment

by:Netminder
ID: 8092819
Per recommendation, force-accepted.

Netminder
EE Admin
0

Featured Post

How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

Join & Write a Comment

Suggested Solutions

Introduction HTML checkboxes provide the perfect way for a web developer to receive client input when the client's options might be none, one or many.  But the PHP code for processing the checkboxes can be confusing at first.  What if a checkbox is…
Nothing in an HTTP request can be trusted, including HTTP headers and form data.  A form token is a tool that can be used to guard against request forgeries (CSRF).  This article shows an improved approach to form tokens, making it more difficult to…
The viewer will learn the basics of jQuery, including how to invoke it on a web page. Reference your jQuery libraries: (CODE) Include your new external js/jQuery file: (CODE) Write your first lines of code to setup your site for jQuery.: (CODE)
The viewer will learn the basics of jQuery including how to code hide show and toggles. Reference your jQuery libraries: (CODE) Include your new external js/jQuery file: (CODE) Write your first lines of code to setup your site for jQuery…

762 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

18 Experts available now in Live!

Get 1:1 Help Now