SamCash
asked on
Fast access to array, using indexes, smart iterative search
I had 26 DataTable(s) (some were smaller subsets in an effort to speed thing up). Once built they are never rebuilt, no Rows or Columns are added to or removed, the data (cells) are accessed millions of times only to update or compare. It is taking up to 200 minutes. I have converted about half of them to arrays and cut the time in about half. So I think I am on the right track. I am using a single dimension int[] idxArray (no duplicate values) as an indexer to all the other arrays. My research indicates this array should be a specific kind for speed. i.e. sorted once when built and then when searched for a value, a "smart search" should be available because the elements are in numerical order - instead of iterating over each of the elements. I believe
Ultimate solution: would be an array of unique int[] sorted numerically, then the ability to get the "index by element value" where some fast technique is used like checking the element at length/2 and then dependent on the result being > or < divide by 2 the remaining length until the length becomes so short that the "compare, branch and half" is taking longer than just checking all of the remaining elements until found. C# must have this already??
I have looked at HashSet, HashTable, List, SortedList, Dictionary... I have not found anything on point, a fast way to get index by element value in an array. I am concerned the overhead on some of these may slow things back down, and I want to use best practices and something that is readily available and debugged.
Thanks for sharing your experience.
Sam
int index = Array.IndexOf(array, value)
is checking element by element until the first one is found. Ultimate solution: would be an array of unique int[] sorted numerically, then the ability to get the "index by element value" where some fast technique is used like checking the element at length/2 and then dependent on the result being > or < divide by 2 the remaining length until the length becomes so short that the "compare, branch and half" is taking longer than just checking all of the remaining elements until found. C# must have this already??
I have looked at HashSet, HashTable, List, SortedList, Dictionary... I have not found anything on point, a fast way to get index by element value in an array. I am concerned the overhead on some of these may slow things back down, and I want to use best practices and something that is readily available and debugged.
Thanks for sharing your experience.
Sam
using System;
using System.Collections.Generic;
using System.Linq;
using System.Web;
using System.Web.UI;
using System.Web.UI.WebControls;
using WebApplication1.myUtilities;
namespace WebApplication1.Debug
{
public partial class Scratch_IndexToArray : System.Web.UI.Page
{
protected void Page_Load(object sender, EventArgs e)
{
Utilities Utilities = new Utilities();
// in actual use these are passed parameters along with the appropriate arrays
int SeasonWeeks = 22;
int GamesPerWeekLimit = 3;
int idxWeekCurrent = 4;
int TeamID = 1234;
int[] TeamArrayIndex = new int[gvTeams.Rows.Count];//this array holds the index of teams in the TeamWeekCounters and TeamDayCounters array
int idxTeamArray = 0;
GridViewRow gvr_idx = gvTeams.Rows[0]; // get a row from gridview for lookup column index next line
int ChildTeamID = Utilities.GridViewColumnIndexByName(gvr_idx, "ChildTeamID");
// this array provides an index into all the other arrays, never rebulit, added to or removed from.
foreach (GridViewRow gvr in gvTeams.Rows) // 8 - 10,000 items, other arrays used for lookup are larger up to about 500,000 items
{
TeamArrayIndex[idxTeamArray] = int.Parse(gvr.Cells[ChildTeamID].Text);
idxTeamArray++;
}
// the cells in this array are incremented or compared ONLY, never rebulit, added to or removed from.
int[,] TeamWeekCounters = new int[TeamArrayIndex.Length, SeasonWeeks];
//Access, these are called millions of times and is taking about 200 minutes using all DataTables,
//I have already cut this in half by converting some of the DataTables to arrays and indexing as shown,
//I am continuing to do the rest of the DataTables, but would like to use a faster access technique
DoSomething(TeamID, GamesPerWeekLimit, idxWeekCurrent, TeamArrayIndex, TeamWeekCounters);
}
//private static void DoSomething(int TeamID, int GamesPerWeekLimit, int idxWeekCurrent, int[] TeamArrayIndex, int[,] TeamWeekCounters)
private void DoSomething(int TeamID, int GamesPerWeekLimit, int idxWeekCurrent, int[] TeamArrayIndex, int[,] TeamWeekCounters)
{
int idxTeam = Array.IndexOf(TeamArrayIndex, TeamID);
bool b = TeamWeekCounters[idxTeam, idxWeekCurrent] < GamesPerWeekLimit; // normally in an if(
TeamWeekCounters[idxTeam, idxWeekCurrent]++; //
}
}
}
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER
Thanks Much
Sam