C＃尋找更有效的方法來存儲和比較真/假值列表

Question

我有數據集的真/假值列表。這些列表可以是任意長度，但在大多數情況下，通常會在5到40個項目之間變化。在每個數據集中，所有列表將具有相同的長度。爲了這個過程的目的，列表中的元素一旦被創建，將始終以相同的順序（即，一旦列表被設置爲true，false，false，true，它將始終爲真，假，假，真正）。

我還需要能夠快速比較任何兩個這些不等長度的列表（即相同的值以相同的順序）。通過這種情況下的不等式，我的意思是，對於一個數據集而言，真正的插槽在另一個數據集中的相同插槽中不能具有任何匹配的真值。錯誤的值是無關緊要的。例如：

• 10010和10001是「相等」，因爲在這兩個值的第一個時隙是 真
• 00100和00001是「不等於」，因爲沒有真正值的 秋天在相同時隙
• 00000和00000也「不等於」因爲 既沒有任何真正的價值

的比較是遍地做一次需要儘可能以最快和最有效的記憶方式來完成。對於給定的數據集，最初的創建過程將只運行一次，因此效率在比較過程中是次要的。

我已經嘗試過使用位置布爾比較以及字符串（「100101」格式）做循環位置char值比較的布爾值數組和排序列表。但似乎應該有更多的處理器和內存有效的方式來存儲和比較這些值列表。

字符串比較版本的示例。數組和列表進行比較遵循相同的模式：

private bool DoListsConflict(string activeValuesA, string activeValuesB) 
{ 
    var lengths = new int[3] {10000, activeValuesA.Length, activeValuesB.Length}; 

    var a = activeValuesA.ToCharArray(); 
    var b = activeValuesB.ToCharArray(); 

    for (var x = 0; x < lengths.Min(); x++) 
    { 
     if (a[x] == '1' && b[x] == '1') return true; 
    } 
    return false; 
} 

我已經看了this question其答案表明BitArrays，但建議的答覆還指出，它不一定是有效的，我不知道這會比我已經做的更好。是否有更高效的結構可以用來加速整個過程？

Answer 1

按位與，並檢查您是否得到零或非零值。

Answer 2

這樣做的最好和有效的方法是使用位。有一點是計算機中較小的數據大小，並且它也是最高效的，因爲您可以使用ULA在少於一個機器時鐘週期內處理它（當CPU流水線工作時）。

爲此，我創建了一個簡單的類，我稱之爲BooleanSet。它可以存儲使用的存儲器量最小可能的任何數量的布爾值的和的CPU的最小時間量：

public class BooleanSet 
{ 
    private List<ulong> values = new List<ulong>(); 
    private int count = 0; 
    /* 0x8000000000000000UL is the same as the binary number 1000000000000000000000000000000000000000000000000000000000000000 */ 
    private const ulong MsbFilterMask = 0x8000000000000000UL; 
    /* 0xfffffffffffffffeUL is the same as the binary number 1111111111111111111111111111111111111111111111111111111111111110 */ 
    private const ulong LsbEraserMask = 0xfffffffffffffffeUL; 
    public BooleanSet() 
    { 
     /* the set mut be initialized with a 0 value */ 
     values.Add(0); 
    } 

    /// <summary> 
    /// Append a new boolean value to the list 
    /// </summary> 
    /// <param name="newValue">New value to append</param> 
    public void Append(bool newValue) 
    { 
     /* Each element in list can store up to 64 boolean values. 
     * If is number is going to be overcome, the set must grow up. 
     */ 
     if (count % 64 == 63) 
     { 
      values.Add(0); 
     } 
     count++; 
     /* now we just have to shift the whole thing left, but we have 
     * to preserve the MSB for lower elements: 
     * 
     * We have to initialize the last MSB (Most Significant Bit) with the new value. 
     */ 
     ulong lastMsb = newValue ? 0x1UL : 0x0UL; 

     for (int position = 0; position < values.Count; position++) 
     { 
      /* & is the bitwhise operator AND 
      * It is used as a mask to zero fill anything, except the MSB; 
      * After get the MSB isolated, we just have to shift it to right edge (shift right 63 times) 
      */ 
      ulong currentMsb = (values[position] & MsbFilterMask) >> 63; 
      /* Now we have discart MSB and append a new LSB (Less Significant Bit) to the current value. 
      * The | operator is the bitwise OR 
      */ 
      values[position] = ((values[position] << 1) & LsbEraserMask) | lastMsb; 
      lastMsb = currentMsb; 
     } 
     /* We don't have to take care of the last value, because we have did this already (3 1sf lines of this methid) */ 
    } 

    public override string ToString() 
    { 
     /* Now we have to write the set as a string */ 
     StringBuilder sb = new StringBuilder(); 
     /* We have to keep track of the total item count */ 
     int totalCount = count; 
     string separator = ""; 
     foreach (ulong value in this.values) 
     { 
      /* for each value in the internal list, we have to create a new bit mask */ 
      ulong bitMask = 1; 
      /* We have to get all bits of all values, except the last one, because it may not be full. 
      * the totalCount will let us to know where we reach the end of the list. 
      */ 
      for (int pos = 0; pos < 64 && totalCount > 0; pos++, totalCount--) 
      { 
       /* We have to write the string in reverse order, because the first item is in the end of our list */ 
       sb.Insert(0, separator); 
       sb.Insert(0, (value & bitMask) > 0); 
       separator = ", "; 
       bitMask = bitMask << 1; 
      } 
     } 
     return sb.ToString(); 
    } 
} 

此類只有2種方法： 1：追加（），用於將新值提供給組。 2：ToString（），用於按照添加的順序列出所有存儲的值。

爲了測試本實施例中，只需要建立一個像這樣的控制檯應用程序：

 static void Main(string[] args) 
    { 
     BooleanSet set = new BooleanSet(); 
     set.Append(false); 
     set.Append(false); 
     set.Append(true); 
     set.Append(false); 
     set.Append(true); 
     set.Append(false); 
     set.Append(true); 

     Console.WriteLine("Checking the stored values:"); 
     Console.WriteLine(set.ToString()); 
     Console.WriteLine(); 
     Console.WriteLine("Checking the stored values again:"); 
     Console.WriteLine(set.ToString()); 
     Console.WriteLine(); 
     Console.WriteLine("Press any key to continue..."); 
     Console.ReadKey(); 
    } 

的輸出將是這樣的：

---

檢查所存儲的值：
FALSE，FALSE ，真，假，真，假，真

再次檢查存儲值：
假，假，真，假，真，假，真

按任意鍵繼續......

---

用於比較兩個組，你只需要比較內錫爾值內在列出你想要的方式。