需要優化計數的正負值

Question

我需要優化對pos/neg值進行計數並按時間刪除非限定值的代碼。

我有附加時間戳的價值隊列。
我需要丟棄1ms的值，並計算負值和正值。這裏是僞代碼

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; 

我需要這個代碼在C＃工作與最大速度。無需堅持列表。實際上，爲負數和正數值分隔的數組是值得歡迎的。

編輯：可能不安全的陣列將是最好的。任何提示？

編輯：謝謝你的頭了..我快速測試陣列版本VS列表（我已經有）和列表是速度快：35比16毫秒1萬次迭代...

這是爲了公平起見，此代碼：

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; 
    } 

} 

Answer 1

一些想法：

1. 只有計數，直到max(negcount,poscount)變爲10，然後退出（無需算上休息）。只有當10是最大數量時纔有效。
2. 計算1次去的負面和正面項目。
3. 只計算negcount並從count-negcount推斷poscount比計算它們更容易做到。

它們中的任何一個是否比現在快以及哪個最快都取決於數據的典型外觀。它很長嗎？短？

更多約3：
你可以使用欺騙來避免在這裏分支。您不必測試該項目是否消極，您可以將其消極性添加到櫃檯。假設物品是x並且它是int,x >> 31對於正x是0，對於負x是-1。所以counter -= x >> 31會給negcount。

編輯：不安全陣列可以更快，更不應該在這種情況下，因爲環路將是這是由JIT編譯器優化的形式

for (int i = 0; i < array.Length; i++) 
    do something with array[i]; 

的。

Answer 2

要獲得negcount和poscount，你兩次遍歷整個列表。 而是遍歷它一次（計算negcount），然後poscount = l.Count - negcount。