Int64的自定義IComparer

Question

我在排序的List中有大約5000個Int64。

我想做一個List.BinarySearch但只基於左邊的39位。 我打包信息的位數在39的右邊。 基本上左邊的39位是Key，我在右邊的12位打包一個值。

對於一個類你只是MyClass的：IComparer

如何添加自定義的IComparer爲Int64的？

我知道如何使用掩碼來有效地提取39位。

我知道我可以使用字典，但我想節省一些空間和使用它的方式我需要打包的數據。我收到它已包裝數據。

我想我可以只寫一個自定義二進制搜索。

我被要求舉個例子。例如將使用具有8位的字節。每個條目由剩下的4位標識。我正在將一些數據存儲在正確的4位中。基本上左邊的4位是密鑰，右邊的4位是值。

0000 1010 
0001 1010 
0010 1010 
0011 1010 
0100 1011 
0101 1011 
0110 1011 
0111 1011 

我想能夠搜索0011並獲得第4行（3）的索引。 當我搜索時，我不知道右邊的4位是什麼。 是的，左邊的4位是唯一的。我可以對字節進行排序，因爲左側的位將決定正確的排序。

如果有更好的方法，那麼很好。我有一個打包的Int64，其中的關鍵是左邊的39位。我想要基於該密鑰進行快速搜索。

簡化代碼示例

public void ListBinaryLeft() 
{ 
    List<byte> fourLeftFourRight = new List<byte>(); 
    for(int i = 0; i < 16; i+= 2) 
    { 
     byte newRow = (byte)((i << 4) | 1); 
     fourLeftFourRight.Add(newRow); 
     Debug.WriteLine("Hexadecimal value of {0} is {1} {2} i {3}", newRow, String.Format("{0:X}", newRow), Convert.ToString(newRow, 2).PadLeft(8, '0'), i); 
    } 
    Debug.WriteLine(""); 
    fourLeftFourRight.Sort(); //actuall not necessary 
    for (int i = 0; i < 16; i += 2) 
    { 
     int findRow = fourLeftFourRight.BinarySearch((byte)(i << 4)); 
     Debug.WriteLine("key index of {0} is {1} ", i, findRow); //strange getting a negative and off by 1 
     findRow = fourLeftFourRight.BinarySearch((byte)((i << 4) | 1)); 
     Debug.WriteLine("cheat index of {0} is {1} ", i, findRow); //works but this is not what I need 
    }   
    Debug.WriteLine(""); 
} 

Answer 1

您的比較器只需通過掩蔽並比較結果進行比較。 （移位也是如此 - 它們在這裏基本相當，儘管掩碼允許您的密鑰在輸入中是任何位集合，而不一定是最重要的位。）要使用您的示例 - 但作爲最小的完整控制檯應用程序：

using System; 
using System.Collections.Generic; 

class Test 
{ 
    static void Main() 
    { 
     List<byte> list = new List<byte>(); 
     for(int i = 0; i < 16; i+= 2) 
     { 
      byte newRow = (byte)((i << 4) | 1); 
      list.Add(newRow); 
     } 

     var comparer = new MaskingComparer(0xf0); 
     // Only needed if the values aren't added in order to start with 
     list.Sort(comparer); 

     for (int i = 0; i < 16; i += 2) 
     { 
      int index = list.BinarySearch((byte)(i << 4), comparer); 
      Console.WriteLine($"Key index of {i} is {index}"); 
      if (index >= 0) 
      { 
       byte value = (byte) (list[index] & 0xf); 
       Console.WriteLine($"Associated value: {value}"); 
      } 
     }   
    } 
} 

class MaskingComparer : IComparer<byte> 
{ 
    private readonly byte mask; 

    public MaskingComparer(byte mask) 
    { 
     this.mask = mask; 
    } 

    public int Compare(byte lhs, byte rhs) => 
     (lhs & mask).CompareTo(rhs & mask); 
} 

Answer 2

我計算出來。如何做IComparer的語法讓我感到震驚。有些人認爲我不得不延長字節。

public void ListBinaryLeft() 
{ 
    List<byte> fourLeftFourRight = new List<byte>(); 
    ByteLeftFourKey byteLeftFourKey = new ByteLeftFourKey(); 
    for (int i = 0; i < 16; i+= 2) 
    { 
     byte newRow = (byte)((i << 4) | 1); 
     fourLeftFourRight.Add(newRow); 
     Debug.WriteLine("Hexadecimal value of {0} is {1} {2} i {3}", newRow, String.Format("{0:X}", newRow), Convert.ToString(newRow, 2).PadLeft(8, '0'), i); 
    } 
    Debug.WriteLine(""); 
    fourLeftFourRight.Sort(byteLeftFourKey); //actuall not necessary 

    for (int i = 0; i < 16; i += 2) 
    { 
     int findRow = fourLeftFourRight.BinarySearch((byte)(i << 4), byteLeftFourKey); 
     Debug.WriteLine("key index of {0} is {1} ", i, findRow); 
     findRow = fourLeftFourRight.BinarySearch((byte)((i << 4) | 1)); 
     Debug.WriteLine("cheat index of {0} is {1} ", i, findRow); //works but this is not what I need 
    }   
    Debug.WriteLine(""); 
} 
public class ByteLeftFourKey : IComparer<byte> 
{ 
    // Compares by 4 left most bits 
    public int Compare(Byte x, Byte y) 
    { 
     return (x >> 4).CompareTo(y >> 4); 
    } 
}