- Home /
What is the quickest way of getting the most common item in a list or array?
I have looked into this using LINQ and using the O(n) algorithm to solve this problem however I can't get anything to port to unity and work optimally for IOS. I was wondering if anyone has found a mobile performance friendly way of finding the most common item in a generic list or array.
Is there an optimal method using .js that compiles on IOS perhaps using sort/group by, or a way to use the for each loop which returns the most common vector3 in an array of vector3s? Any code examples would be much appreciated :)
What you mean most common? - the most repeated item? i.e. the one that occurs the most in a sequence?
I'm really after just the most common duplicate Vector3 in an array or list. However I'm also interested in how I could get the most duplicate sequence of Vector3's and return that sequence however long that may be from an array full of Vector3's.
Answer by dsada · Jun 19, 2014 at 05:18 PM
How about this one?
Dictionary<Item,int> dic
Item mostCommon = items[0]
dic.Add(items[0],1)
for(int i = 1; i < items.Length; ++i)
{
if(dic.ContainsKey(items[i]))
{
dic[items[i]] += 1
if(dic[items[i]] > dic[mostCommon])
{
mostCommon = items[i]
}
}
else
dic.Add(items[i],1)
}
It just the first idea that came into my mind. Please share with me what do you think about it.
Nice thanks for the quick reply. I like this as it uses a dictionary which seems to be the most relevant to finding the most common item. I have tried it out but am not sure how to set the dictionary up at the beginning in terms of mostcommon item. Here is what I have done so far with it, in my case I am dealing with vector3s.
function get$$anonymous$$ostCommon(a : Vector3[]){ var mostCommon = a[0]; var myDic = new Dictionary.(); var currentCount : int = 0; var maxCount = 0;
for (var i : int = 1; i < a.Length; i++) { if(myDic.Contains$$anonymous$$ey(a[i])) { myDic[a[i]] += 1; if (myDic[a[i]] > myDic[mostCommon]) { mostCommon = a[i]; } } else myDic.Add(a[i],i); } return mostCommon; }
At the mo when an array is passed to the function, this produces the error $$anonymous$$eyNotFoundException. The given key was not present in the dictionary. [UnityEngine.Vector3,System.Int32].get_Item(Vector3 key).
I have just rushed over this so Im sure i'm missing a quick fix or check. I could alter this and try contains ins$$anonymous$$d of contains key but then this would not be using the key properly. Could this be done more quickly with a hashtable or is it actually faster using a generic .NET dictionary? Currently I am converting my list to an array using .ToArray and then passing this to the function.
You missed the thing what I did in line 3. You must add the 0th item to the dictionary because of the very first check in the loop. The algorithm cant start the search if the dictionary does not contain any item. So in your case: myDic.Add(a[0],1) before the loop
and another important thing that i realized in your code: else myDic.Add(a[i],i). This should be myDic.Add(a[i],1)
I just tried it out and it works for me. Here is the script that i wrote.
List<Vector3> vectors = new List<Vector3>();
vectors.Add(new Vector3(1,2,3));
vectors.Add(new Vector3(2,2,3));
vectors.Add(new Vector3(1,2,3));
vectors.Add(new Vector3(1,2,4));
vectors.Add(new Vector3(2,3,3));
vectors.Add(new Vector3(1,2,3));
vectors.Add(new Vector3(2,2,3));
vectors.Add(new Vector3(1,2,3));
vectors.Add(new Vector3(3,2,3));
vectors.Add(new Vector3(5,2,3));
vectors.Add(new Vector3(1,2,3));
vectors.Add(new Vector3(6,2,3));
Dictionary<Vector3,int> dic = new Dictionary<Vector3,int>();
Vector3 mostCommon = vectors[0];
dic.Add(vectors[0],1);
for(int i = 1; i < vectors.Count; ++i)
{
if(dic.Contains$$anonymous$$ey(vectors[i]))
{
dic[vectors[i]] += 1;
if(dic[vectors[i]] > dic[mostCommon])
{
mostCommon = vectors[i];
}
}
else
{
dic.Add(vectors[i],1);
}
}
Debug.Log(mostCommon);
This wrote out (1,2,3) for me
Ohh, and I don't think it is faster with hashtable because Dictionary is a hash table.
If you meant "why do we use the Dictionary class ins$$anonymous$$d of the Hashtable class?", then it's an easy answer: Dictionary is a generic type, Hashtable is not. That means you get type safety with Dictionary, because you can't insert any random object into it, and you don't have to cast the values you take out.
man you really shouldn't have named the variable "myDic", that's too funny
Fully missed line 3, thanks for the reply, I should of clearly done a bit more research ins$$anonymous$$d of just glancing at what I thought was important. This worked a charm and was 'quick as' even with a large list when compiled for IOS.