需要优化计数正负值 [英] Need to optimise counting positive and negative values
问题描述
我需要优化code计数正/负价值与按时间删除非限定值。
我有值与时间戳连接队列。
我需要放弃这是1ms的旧值和计数正值和负值。这里是伪code
列表＆LT; VAL＆GT;升;
V = q.dequeue（）;
deleteold（升，v.time）;
l.add（五）;
negcount = l.count（ⅰ=＆GT; i.value℃下）;
poscount = l.count（ⅰ=＆GT; i.value＆GT; = 0）;
如果（negcount == 10）返回-1;
如果（poscount == 10）返回1;
我需要这个code在C＃中，最大速度工作。没有必要坚持到列表中。在隔了负和POS值实际上数组是值得欢迎的。
编辑：可能不安全的阵列将是最好的。任何提示？
编辑：感谢您的抬起头.. 我赶紧阵列测试版VS列表（我已经有）和列表是速度快：35比16毫秒1万次迭代...
下面是code为公平起见：
类节目
{
静态INT LEN = 10;
静态INT LEN1 = 9;
静态无效的主要（字串[] args）
{
var []的数据= GenerateData（）;
秒表SW =新的秒表（）;
的for（int i = 0;我小于30;我++）
{
sw.Reset（）;
ArraysMethod（数据，SW）;
Console.Write（数组：{0：0.0000}毫秒，sw.ElapsedTicks / 10000.0）;
sw.Reset（）;
ListMethod（数据，SW）;
Console.WriteLine（列表：{0：0.0000}毫秒，sw.ElapsedTicks / 10000.0）;
}
到Console.ReadLine（）;
}
私有静态无效ArraysMethod（var []的数据，秒表SW）
{
INT信号= 0;
INT NI = 0，PI = 0;
var []的N =新变种[LEN]
瓦尔[] P =新变种[LEN]
的for（int i = 0; I＆LT; LEN;我++）
{
N [i] =新的VAR（）;
P [i] =新的VAR（）;
}
sw.Start（）;
的for（int i = 0; I＆LT; DATALEN;我++）
{
瓦尔V =数据[I]
如果（v.val℃，）
{
INT X = 0;
NI = 0;
//时间不连续的
对于（INT J = 0; J＆LT; LEN; J ++）
{
长差异= v.time - N [J]。时间;
如果（DIFF＆LT; 0）
的diff = 0;
// 太老
如果（DIFF＆GT; 10000）
X = D];
其他
妮++;
}
N [X] = V;
如果（NI＆GT; = LEN1）
信号= -1;
}
其他
{
INT X = 0;
圆周率= 0;
//时间不连续的
对于（INT J = 0; J＆LT; LEN; J ++）
{
长差异= v.time - P [J]。时间;
如果（DIFF＆LT; 0）
的diff = 0;
// 太老
如果（DIFF＆GT; 10000）
X = D];
其他
PI ++;
}
P [X] = V;
如果（PI＆GT; = LEN1）
信号= 1;
}
}
sw.Stop（）;
}
私有静态无效ListMethod（var []的数据，秒表SW）
{
INT信号= 0;
名单＆LT;无功＆GT; D =新的名单，其中，无功＆GT;（）;
sw.Start（）;
的for（int i = 0; I＆LT; DATALEN;我++）
{
瓦尔V =数据[I]
d.Add（新功（）{时间= v.time，VAL = v.val℃，-1：θ1}）;
//删除过期
对于（INT J = 0; J＆LT; d.Count; J ++）
{
如果（v.time - D [J]。时间＆LT; 10000）
d.RemoveAt（j--）;
其他
打破;
}
INT CNT = 0;
INT K = d.Count;
对于（INT J = 0; J＆LT; k; J ++）
{
CNT + = D [J] .VAL;
}
如果（（CNT＆GT; = 0 CNT：-cnt）＆GT; = LEN？）
信号= 9;
}
sw.Stop（）;
}
静态INT DATALEN = 1000000;
私有静态无功[] GenerateData（）
{
随机R =新的随机（DateTime.Now.Millisecond）;
var []的数据=新变种[DATALEN]
瓦尔preV =新的VAR（）{VAL = 0，时间= DateTime.Now.TimeOfDay.Ticks};
的for（int i = 0; I＆LT; DATALEN;我++）
{
INT X = r.Next（20）;
数据[i] =新的VAR（）{VAL = X - 10，时间= prev.time + X * 1000};
}
返回的数据;
}
类瓦尔
{
公众诠释VAL;
众长的时间;
}
}
一些想法：
- 只有计数，直到
MAX（negcount，poscount）变成10，然后退出（无需算上休息）。只有当10为最大数。 - 伯爵在1去消极和积极的项目。
- 计算仅
negcount和计数negcount这是很容易，指望他们俩做推断poscount。
有没有人比你现在有什么更快，这是最快的，要看在其他事情上有什么数据通常如下所示。它是多久？短？
一些更多关于3：
您可以使用诡计，以避免树枝这里。你不必测试项目是否是负的，你可以添加其消极到柜台。假设该项目是 X ，它是一个 INT ，计数器 - = X＆GT;＆GT; 31 会给 negcount 。
编辑：不安全阵列可以更快，但不应该是在此情况下，因为循环将是以下形式
的for（int i = 0; I＆LT; array.Length;我++）
做一些与数组[我]
这是由JIT编译器优化
I need to optimise code that counts pos/neg values and remove non-qualified values by time.
I have queue of values with time-stamp attached.
I need to discard values which are 1ms old and count negative and positive values. here is pseudo code
list<val> l;
v = q.dequeue();
deleteold(l, v.time);
l.add(v);
negcount = l.count(i => i.value < 0);
poscount = l.count(i => i.value >= 0);
if(negcount == 10) return -1;
if(poscount == 10) return 1;
I need this code in c# working with max speed. No need to stick to the List. In fact arrays separated for neg and pos values are welcome.
edit: probably unsafe arrays will be the best. any hints?
EDIT: thanks for the heads up.. i quickly tested array version vs list (which i already have) and the list is faster: 35 vs 16 ms for 1 mil iterations...
Here is the code for fairness sake:
class Program
{
static int LEN = 10;
static int LEN1 = 9;
static void Main(string[] args)
{
Var[] data = GenerateData();
Stopwatch sw = new Stopwatch();
for (int i = 0; i < 30; i++)
{
sw.Reset();
ArraysMethod(data, sw);
Console.Write("Array: {0:0.0000}ms ", sw.ElapsedTicks / 10000.0);
sw.Reset();
ListMethod(data, sw);
Console.WriteLine("List: {0:0.0000}ms", sw.ElapsedTicks / 10000.0);
}
Console.ReadLine();
}
private static void ArraysMethod(Var[] data, Stopwatch sw)
{
int signal = 0;
int ni = 0, pi = 0;
Var[] n = new Var[LEN];
Var[] p = new Var[LEN];
for (int i = 0; i < LEN; i++)
{
n[i] = new Var();
p[i] = new Var();
}
sw.Start();
for (int i = 0; i < DATALEN; i++)
{
Var v = data[i];
if (v.val < 0)
{
int x = 0;
ni = 0;
// time is not sequential
for (int j = 0; j < LEN; j++)
{
long diff = v.time - n[j].time;
if (diff < 0)
diff = 0;
// too old
if (diff > 10000)
x = j;
else
ni++;
}
n[x] = v;
if (ni >= LEN1)
signal = -1;
}
else
{
int x = 0;
pi = 0;
// time is not sequential
for (int j = 0; j < LEN; j++)
{
long diff = v.time - p[j].time;
if (diff < 0)
diff = 0;
// too old
if (diff > 10000)
x = j;
else
pi++;
}
p[x] = v;
if (pi >= LEN1)
signal = 1;
}
}
sw.Stop();
}
private static void ListMethod(Var[] data, Stopwatch sw)
{
int signal = 0;
List<Var> d = new List<Var>();
sw.Start();
for (int i = 0; i < DATALEN; i++)
{
Var v = data[i];
d.Add(new Var() { time = v.time, val = v.val < 0 ? -1 : 1 });
// delete expired
for (int j = 0; j < d.Count; j++)
{
if (v.time - d[j].time < 10000)
d.RemoveAt(j--);
else
break;
}
int cnt = 0;
int k = d.Count;
for (int j = 0; j < k; j++)
{
cnt += d[j].val;
}
if ((cnt >= 0 ? cnt : -cnt) >= LEN)
signal = 9;
}
sw.Stop();
}
static int DATALEN = 1000000;
private static Var[] GenerateData()
{
Random r = new Random(DateTime.Now.Millisecond);
Var[] data = new Var[DATALEN];
Var prev = new Var() { val = 0, time = DateTime.Now.TimeOfDay.Ticks};
for (int i = 0; i < DATALEN; i++)
{
int x = r.Next(20);
data[i] = new Var() { val = x - 10, time = prev.time + x * 1000 };
}
return data;
}
class Var
{
public int val;
public long time;
}
}
Some ideas:
- Only count until
max(negcount,poscount)becomes 10, then quit (no need to count the rest). Only works if 10 is the maximum count. - Count negative and positive items in 1 go.
- Calculate only
negcountand infer poscount from count-negcount which is easier to do than counting them both.
Whether any of them are faster than what you have now, and which is fastest, depends among other things on what the data typically looks like. Is it long? Short?
Some more about 3:
You can use trickery to avoid branches here. You don't have to test whether the item is negative, you can add its negativity to a counter. Supposing the item is x and it is an int, x >> 31 is 0 for positive x and -1 for negative x. So counter -= x >> 31 will give negcount.
Edit: unsafe arrays can be faster, but shouldn't be in this case, because the loop would be of the form
for (int i = 0; i < array.Length; i++)
do something with array[i];
Which is optimized by the JIT compiler.
这篇关于需要优化计数正负值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
