C#遍历数组效率问题。
一个存有大量数据的数组,里边数据有不少重复的。而且不确定重复次数,怎么检索才能高效率的查找到重复的内容和次数。。。
其实也是一个算法问题,请教专家拉。。请专家指点下啊。 --------------------编程问答-------------------- mark --------------------编程问答-------------------- e...你的问题是两个问题...
1. C#下高效遍历数组
2. 查找重复值
对于第一个, 如果确实性能要求高的, 直接用指针..
int[] arr=new int[]{...};
int* p=&arr[0];
然后用p[index]存取值.
对于第二个 ,经典方法是在stack上开一个辅助大数组int* asstArr=stackalloc int[256];, 用原数组的值作为辅助数组的下标.
遍历原数组,asstArr[p[index]]++; 最后这个值就是p[index]出现的次数.
--------------------编程问答-------------------- c#有指针吗??? 不是说没有么.
感觉放Sql里 然后用sql查询读出来在放数组里 比较好实现 直接分组找一个就行了
具体操作 搜下 sql保留一条重复数据 就可以了 --------------------编程问答-------------------- c# 没有指针了 。 --------------------编程问答-------------------- 安全代码没有...不安全代码(用unsafe声明)有... --------------------编程问答-------------------- I have got a possible solution to solve this problme.
I use a Hashtable,like this following.
// Create a new hashtable object:
Hashtable ht = new Hashtable();
I assume a simple an array.
// Declare and set array element values
int[] array2 = new int[] { 1, 3,5,5, 5, 7,7,9,9,9,9,9,9, 9 };
I need to iterate through the collection array2 to count the times of each element which appears in the collection.
So the computing time is O(n).
when I increase the value,it is easy to find if there is a key that has existed in the Hashtable now.
Then I can get the final ht.
ht[1] = 1
ht[3] = 1
ht[5] = 2
ht[7] = 2
ht[9] = 7
After we build the final ht,we can search the content and its repeated times very easily.
--------------------编程问答-------------------- hashtable? hashtable还有效率可言吗?我觉得2楼的方法已经很快了...唯一不足就是不安全代码...可是我也想不到更好的办法了... --------------------编程问答-------------------- jf --------------------编程问答-------------------- C#使用指针:
usafe
{
int[] arr = new int[]{...};
int* p = &arr[0];
}
仅供参考... --------------------编程问答-------------------- ^o^ 手误...
unsafe
usafe
{
int[] arr = new int[]{...};
int* p = &arr[0];
}
然后(右键)项目.属性->生成, 把"允许不安全代码"勾上后重新编译就可... --------------------编程问答-------------------- -_-!!! 又打多一个"usafe"... --------------------编程问答-------------------- 世界上没有任何东西是完美的.
完美的是怎么样寻找一个平衡点.
性能?安全?开发难度?
而且, 要考虑性能, 如果不需要排序的话, 这个东西最开始就不该用数组, 而是应该用一个稍微变体的hashtable.
--------------------编程问答-------------------- 以前做过试验,数据量大于1000时Dictionary明显占优。明天补充具体试验结果。 --------------------编程问答-------------------- 我补充下。开始的数据是存储在其他地方的,具体读进什么里边,数组也好,HashTable也好,关键是一个检索效率。生成的结果应该带有重复记录的内容+重复次数。另一个可以结果也可以是当重复记录小于多少条,如果重复次数少于10次的记录。显示其内容和重复次数。。。请大家在研究下 --------------------编程问答-------------------- 对了,数据不是数字。而是一条一条的记录,是文本性的东西。
而且数据量巨大。比如有个几百万条的。 --------------------编程问答-------------------- up --------------------编程问答-------------------- 数字的话,肯定要先排序,然后就好处理了
要是字符串的话,我就不知道怎么就效率高了 --------------------编程问答-------------------- 根据LZ的说法可以推测,数据一定是从数据库中得来的,那么完全可以使用sql来实现要求,无需另行考虑了。 --------------------编程问答-------------------- 没有好的建议!mark下下! --------------------编程问答-------------------- 其实可以参考 位图排序,用空间换时间,也就是shrinerain提到的"用原数组的值作为辅助数组的下标" --------------------编程问答-------------------- 2楼的,用元素值做index的tip要求元素值有个上限,这种方式寻址会比较快但内存的占用就得看数组里的最大元素值了,类似位图排序,用hashtable做起来比较通用,不仅局限于数字类型 --------------------编程问答-------------------- 比如你的数组是: int[] data = new int[]{1,20,5,7,7,20,8,9,1,5};
那么你用数组中最大的一个数来实例化一个新的int数组
int[] result = new [20];
并初始化result所有元素都为0
然后遍历一次data
foreach(int i in data)
{
result[i] += 1;
}
之后,比如你想知道5这个数是否在数组data里存在,那么只要判断result[5]是否大于0,那么result[5]的值就是5在数组data里重复出现的次数.
上面是大概算法的描述
至于要执行速度最快,那么就是用point,以及在Stack上(而不是heap上)开空间操作,那就需要使用unsafe代码,或者你用c++写代码. --------------------编程问答-------------------- hashtable检索速度差太远,特别是在数据量很大的时候.
所以至于是要牺牲空间还是要牺牲时间,还是要楼主根据具体需求来定了. --------------------编程问答-------------------- unsafe在单机上运行没有问题,效率的提升也非常明显
如果是asp.net程序中
建议使用托管代码 --------------------编程问答-------------------- 这个你看一下数据结构c语言版的里面有这样的demo --------------------编程问答-------------------- 每条数据是很长的文本的话 先去他们的 HashCode 储存为一个 int 的 数组
然后就好办了. --------------------编程问答-------------------- 楼上前半部分人不少都白说了, 我看题目就说是数据没说数据类型一定就是Int32了..如果这样C#是不允许对拖管引用类型使用指针的吧...就别奢望C#了.
还有楼上的shinaterry的unsafe写法...显然是不正确的...
对于非stackalloc的, 用指针首先固定长度初始化应该是Int32[] arr = {1,2,3}; 并且不可以直接取地址操作.Int32 *ip = &arr[0]; 需要fixed吧..如果只是单个的Int32变量写成Int32 *ip = &某个变量是没问题的.
如果是从数据库取出来的..尽量通过T-SQL解决吧..
如果是已经存在的非数据库媒体存储的...我觉的还是用散列..用Dictionary<string, uint>
Contains的时候..后面++值 ..在使用Dictionary时最后先初始化它的capacity..为你的数组的length * 2..因为它的实现应该是平方探测.
--------------------编程问答-------------------- public class SolidPoint
{
public SolidPoint()
{
//
// TODO: 在此处添加构造函数逻辑
//
}
private byte _height = 1;
/// <summary>
/// 高度,放电个数
/// </summary>
public byte height
{
get
{
return this._height;
}
set
{
this._height = value;
}
}
private Point _Coordinate;
/// <summary>
/// 坐标点
/// </summary>
public Point Coordinate
{
get
{
return this._Coordinate;
}
set
{
this._Coordinate = new Point(value.X,value.Y);
}
}
}
List<SolidPoint> ls = new List<SolidPoint>();
for (int i = 0; i < ls.Count - 1;i++ )
{
for (int j = i + 1; j < ls.Count; j++)
{
if (ls[i].Coordinate == ls[j].Coordinate)
{
ls[i].height += 1;
ls.RemoveAt(j);
}
}
} --------------------编程问答-------------------- 很难,非常难,有待数据结构高手来讲课。 --------------------编程问答-------------------- 3楼大大的解决方法很有实用性.... --------------------编程问答-------------------- 我觉得应该从算法方面研究,数据库有效率可言吗?
指针虽然能快,也有限,而且还是不安全代码。
Hash表存在不同对象Hash值相同的可能性。
用数据内容做下标的,数组占内存太大了,说不定就报异常。
要我说,如果数据是整数这样的小数据,优化也没什么效果,真想快,就应该从一开始就进行排序,例如使用SortedList。那样统计重复数量的时候直接报结果行了。如果数据是大数据,譬如长字符串或者是Datatable的一个Row,就有了优化算法的必要了。可以把单个大数据分成几部分分层比较,每层比较都筛掉大多数的候选数据。越往后,比较次数越少,省略了很多不必要的比较。
--------------------编程问答-------------------- 思路:用哈希链表是很通用的方法,适用于各种数据类型。
实现:c# Hashtable,或者unsafe c++自己写一个Hash List。 --------------------编程问答--------------------
data数组里如果有个成员值很大,内存会爆的,如果数组本身长度却很小,就更划不来了。。 --------------------编程问答-------------------- 学习数据结构中,有待高手出现,接分! --------------------编程问答-------------------- up.... --------------------编程问答-------------------- Friendly Up!
补充:.NET技术 , C#