Re: Insert Obejct to sorted list [modified] - C# Discussion Boards

Re: Insert Obejct to sorted list [modified]

26-Jul-09 2:44

How can i insert to list/array an object to the right place by some comparison function and in the end of the process to get back the best 100 object?

for example if i have this code:

<br />
 class Example : IComparable<br />
    {<br />
        //Var's and Prop's of class<br />
        public double num1;<br />
        public double num2;<br />
        public double GetIt<br />
        {<br />
            get<br />
            {<br />
                return num1 * num2;<br />
            }<br />
        }<br />
<br />
        //Some function the return value based on var's of class<br />
        public double SomeValue()<br />
        {<br />
            double result = this.num1 * this.num2 - this.num1 / (this.num2 + 1);<br />
            return result;<br />
        }<br />
<br />
        //Compare function between 2 Example's<br />
        #region IComparable Members<br />
<br />
        public int CompareTo(object obj)<br />
        {<br />
            Example e1 = (Example)obj;<br />
            int res = (this.SomeValue() - e1.SomeValue()) > 0 ? 1 : -1;<br />
            return res;<br />
        }<br />
<br />
<br />
        #endregion<br />
    }<br />
<br />
    //Class that want to find the best 100 Examples<br />
    class UsingExample<br />
    {<br />
        public List<Example> m_List;<br />
<br />
        public UsingExample()<br />
        {<br />
            m_List = new List<Example>();<br />
            for (int num1 = 1; num1 <= 100; num1++)<br />
                for (int num2 = 1; num2 <= 100; num2++)<br />
                {<br />
                    //Create the current Example<br />
                    Example e1 = new Example();<br />
                    e1.num1 = num1;<br />
                    e1.num2 = num2;<br />
                    //Insert into list and then sort (By Example.CompareTo)<br />
                    m_List.Add(e1);<br />
                    m_List.Sort();<br />
<br />
                    //I want just 100 result on the list and not 10,000^2<br />
                    if (m_List.Count > 100)<br />
                        m_List.RemoveAt(100);<br />
                }<br />
<br />
            //In the end i will have the best result 100 result<br />
<br />
        }<br />
        public Example this[int num]<br />
        {<br />
            get { return this.m_List[num]; }<br />
        }<br />
<br />
<br />
    }<br />
<br />

The problem is that every time i need to sort all the list. What is the best way to do it in C# by this process:
1. Insert an object to Sorted Array/List in the right place.
2. If the Current Instance of an object is Smaller then the biggest object in the 100 small object list (by Some IComparable functions):
2.1 Remove the biggest object from the list.

by This process i want to remaine with the smallest object in 100 list.
what is the best way to do it because i don't want to sort the Array every iteration if the Array/List is allready sorted.

PIEBALDconsult26-Jul-09 4:39

26-Jul-09 4:39

How about a System.Collections.Generic.SortedList<T> ?

See here[^]

(But it seems to say that it can't contain duplicate keys. Might you have duplicates?)

Also, you wouldn't need to sort after each insert, only before retrieving.

modified on Sunday, July 26, 2009 10:48 AM

bonzaiholding26-Jul-09 6:15

26-Jul-09 6:15

Yes , i don't have key as the value of the function. It can be the same value and this is the reason that i can't Use SortedList<>, Is there another way?

PIEBALDconsult26-Jul-09 6:26

Re: Insert Obejct to sorted list [modified]

26-Jul-09 6:26

There's always another way. Big Grin | :-D

If there's a duplicate for highest value, which would you remove? Or contain both?

Do you want 100 items or all the items with the bottom 100 values? Or would it matter?

bonzaiholding26-Jul-09 6:31

26-Jul-09 6:31

I want to have all the 100 items with the best result even if all of them have the same value. (Its very big range of data , more then 10^50 Items) And i want the best 100 items.

What should i do?

modified on Sunday, July 26, 2009 12:39 PM

PIEBALDconsult26-Jul-09 6:51

26-Jul-09 6:51

But what if items 95 - 105 all have the same value? Does it matter which ones you discard?

bonzaiholding26-Jul-09 20:39

26-Jul-09 20:39

In This case i does not matter, You can just save the first one : (Example of the result)

1. 0.212132
2. 0.23
3. 0.23
4. 0.3
.
.
.
96. 2.299
97. 2.299
98. 2.3
99. 2.3
100. 2.3

Luc Pattyn26-Jul-09 11:32

Luc Pattyn

26-Jul-09 11:32

bonzaiholding wrote:
more then 10^50 Items

Stop right there, no need to optimize anything, there isn't enough life in your PC to ever finish such a job, provided you would be willing to pay for the energy it will take.

Smile | :)

Luc Pattyn [Forum Guidelines] [My Articles]

The quality and detail of your question reflects on the effectiveness of the help you are likely to get.
Show formatted code inside PRE tags, and give clear symptoms when describing a problem.

PIEBALDconsult26-Jul-09 14:49

26-Jul-09 14:49

But they're very small items. Waffer thin.

Martijn Boeker26-Jul-09 21:55

Martijn Boeker

26-Jul-09 21:55

I think you can do it this way.

In the loop, first collect the values (without sorting) in a list up to a certain number, say 1000 values. When it reaches 1000 values, re-sort the list and keep only the top 100 using GetRange(). Then continue adding to the list. This will prevent the algorithm from sorting all the time while keeping memory usage limited. The number 1000 should be a variable and you should experiment with it to find a value that gives you the best performance.

In your example:

int maxSize = 1000;

for (int num1 = 1; num1 <= 100; num1++)
for (int num2 = 1; num2 <= 100; num2++)
{
  //Create the current Example
  Example e1 = new Example();
  e1.num1 = num1;
  e1.num2 = num2;

  //Insert into list 
  m_List.Add(e1);

  // Sort only after certain treshold.
  if (m_List.Count >= maxSize)
  {
    // sort
    m_List.Sort();

    // Get top 100.
    m_List = m_List.GetRange(0, 100);
  }
}

// Sort and select top 100 after loop, because the list may be between 100 and maxSize.

// sort
m_List.Sort();

if (m_List.Count > 100)
{
  // Get top 100.
  m_List = m_List.GetRange(0, 100);
}

I must agree though, doing this 10^50 times is impossible. Your computer does something in the order of 10^9 processor instructions per second, per day say 10^14, per year say 10^16, in a hundred years 10^18... (I may be a bit off, but you get the idea..) Or are there any mice involved? Big Grin | :-D

bonzaiholding26-Jul-09 22:40

26-Jul-09 22:40

This is what i did, The problem is that every iteration i need to sort the list that is allready sorted.
The Only thing that i need is to Insert the object into the right place in the sorted list and then Remove the last object on the list.

Do you have any idea what can i do?

modified on Monday, July 27, 2009 7:27 AM

How do I add the floating Toolbar with TabPage like "Might and Magic V Map Editor"

Martijn Boeker27-Jul-09 9:19

Martijn Boeker

27-Jul-09 9:19

With the solution I propose, this is not the case. You would only sort every so often, not with every iteration. Now I think about it, this may still be slow, because you would have to sort a larger list.

I suppose you could also use a LinkedList (for fast insert/remove) and implement some kind of binary search to find the index to insert at. LinkedList doesn't seem to have a BinarySearch() method, but I'm sure you can find an example of binary search somewhere. I think that would give you the best performance.

reality check

Luc Pattyn27-Jul-09 10:47

Luc Pattyn

27-Jul-09 10:47

You still don't get it, do you?

assuming a fantastic CPU that does everything your algorithm needs for one iteration in a single instruction (waw), and runs at 1000GHz (waw), so it does 1 of your zillion things per picosecond, or 3E19 per year (as there are 3E7 seconds in a year); now assume it started when the universe started (some 14E9 years ago?), then it would now have finished some 4E29 thereof, way less than 1E50 (you're twenty zeroes short).

so sorting isn't relevant, your algorithm stinks, it is just undoable that many times.

Smile | :)

Luc Pattyn [Forum Guidelines] [My Articles]

The quality and detail of your question reflects on the effectiveness of the help you are likely to get.
Show formatted code inside PRE tags, and give clear symptoms when describing a problem.

akira3225-Jul-09 22:46

akira32

25-Jul-09 22:46

The Might and Magic V Map Editor's floating Toolbar with TabPage as below:
http://cid-fbeb6373d9321a7f.skydrive.live.com/self.aspx/Questions/Visual%20C%7C3/MapEditor%7C_Might%20and%20Magic%20V%20Map%20Editor.JPG
How do I design the same toolbar in Visual C# 2008?

Re: How do I add the floating Toolbar with TabPage like "Might and Magic V Map Editor"

Abhijit Jana26-Jul-09 3:12

Abhijit Jana

26-Jul-09 3:12

Here is an Nice Example of Floating Toolbar. You have to design the internal content of Toolbar.
Floating Toolbar

Abhijit Jana | Codeproject MVP
Web Site : abhijitjana.net
Don't forget to click "Good Answer" on the post(s) that helped you.
View My Latest Article

modified on Sunday, July 26, 2009 12:44 PM

Re: How do I add the floating Toolbar with TabPage like "Might and Magic V Map Editor"

akira3227-Jul-09 6:45

akira32

27-Jul-09 6:45

Thank you,Abhijit Jana!

Insert object to a sort list in the most efficient way

bonzaiholding25-Jul-09 22:39

Re: Insert object to a sort list in the most efficient way

25-Jul-09 22:39

I have a list of specific class.
Im doing some simulation and i want to receive in the end the 100 best result.
Lets say i have this class :

class A<br />
{<br />
int j;<br />
int t;<br />
<br />
}

and i want to save in some range of j and t the best 100 "A" elements that give me the low math.pow(j/t,2) (100 result of the lowest A that i have).

Right now im insert the result to the list and then sort the list with the Compare method. each time a take the smallest result of the list and then if the current result is more small then then the small one on this. If its is smallest then i insert it into the the array , sort it and then remove the last object and continue.

What is the best way to take a List/Array of sort element and just insert the Current element to it's place in the sorted List/Array and remove that biggest element of the list ? (In C# )

modified on Sunday, July 26, 2009 7:46 AM

PIEBALDconsult26-Jul-09 4:53