Question best data structure

[andrews]

Hi,
I have a question concerning the best (fastest) data structure to use for my program.
I give an example.
There are 100000 items to store with key and value.
In my program I have to take the item with the lowest value, change that value and store it again with the new value.
I have to do that many 1000 times.
The number of items and keys are not changed but always the values
So it is very important to do that in a minimum of time.
What should be the most fastest method ?
Thanks for any response

 

[XardozCom]

Are you going through the data set sequentially?
Or searching for a key to change the value?

 

[andrews]

No, I put simply the changed item into the data set and now I want to know (very fast, immediately) what is the smallest now (can be this one or another).
Is this possible ?
I am suspecting that there is now fast way but can be wrong.

 

[IanRyder]

Hi,

I would suggest that LINQ is going to be your best bet if you have 100,000 rows in a DataTable where you need to find the row with the lowest value and make a change to that row. To do this you need to do this in two stages:-

1) Find out what the lowest value is then,
2) Get the row with that lowest value so it can be changed.

i.e:-

Dim SW As New Stopwatch
 
SW.Start()
Dim smallestValue As Integer = dtPostcodes.Rows.Cast(Of DataRow).Min(Function(x) CInt(x(5)))
Dim rowWithSmallestValue As DataRow = dtPostcodes.Rows.Cast(Of DataRow).Where(Function(x) CInt(x(5)) = smallestValue).FirstOrDefault
SW.Stop()
 
MsgBox(rowWithSmallestValue(5).ToString & " - Elapsed Time: " & SW.ElapsedMilliseconds.ToString)

I have use a Stopwatch here on a sample table of 100,000 records where I need to select the row with the lowest value in column 6. In these tests, the elapsed time was between 92 and 98 milliseconds, if that is any good to you?

Hope that helps.

Cheers,

Ian

BTW, NEVER NEST this type of query into a single statement otherwise you will actually do 100,000 * 100,000 searches within the LINQ (or any other SQL type) query to find the answer. If you do this then you might as well set an Alarm Clock for tomorrow morning rather than use a Stopwatch.

 

[andrews]

IanRyder, thanks for your answer.
But as Newbie I do not know LINK but I know (I hope not to be wrong) that LINK is very easy for quering but also it is not the fastest way.
I have search now the internet and I found a priority queue who is working (fortunally ! :=)) and it seems very fast.
Using stopwatch I found 1 millisecond for removing the best and adding another item (= changing the value).
My PC is moderate.
I do not know if there are better (faster) data structures.
Regards

 

[andrews]

IanRyder, may I ask you something ?
It suppose it is not difficult but I do not know.
I have made a class but how can I import it in a program.
Building, making DLL, importing a Reference?
I do not know the method.
Thanks for any response.

 

[IanRyder]

Hi,

I have no experience with a Priority Queue, so I cannot make any comments here, but if this makes things faster for what you are trying to do then go for it. To finish Post #5, I am not sure you are going to get any better than 1 millisecond, so I would not worry about trying to get anything better.

With regards to Post #6, when you have created a class that you want to use in another project, just set the Application Type in the Project Properties to a Class Library and then ReBuild as normal. This will now create a DLL file in your Project\Bin\Debug folder.

You can now add this to other projects by using Add Reference in your Solution Explorer to navigate to your DLL and add the DLL to your current project. You can then add any Import statements to your local classes as you need.

Hope that helps.

Cheers,

Ian

 

[andrews]

Thanks Ian !

 

[XardozCom]

If the above solution does not work, just use an untyped collection
quite simple to setup and useUsing Arrays and Collections in VB.NET