Int64 的自定义 IComparer

Question

我有大约 5000 个 Int64 排序 List。

我想做一个List.BinarySearch但是只基于左边的39位。我将信息打包到 39 右边的位中。基本上左边的 39 位是密钥，我在右边的 12 位中打包一个值。

对于 class 你只是 MyClass : IComparer

如何为 Int64 添加自定义 IComparer？

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

我知道我可以只使用字典，但我想保存一些 space 以及我使用它的方式我需要打包的数据。我收到它有打包数据。

我想我可以写一个自定义的二进制搜索。

有人问我举个例子。例如将使用具有 8 位的字节。每个条目由 4 个左位标识。我将一些数据存储在右 4 位中。基本上左边的 4 位是键，右边的 4 位是值。

我希望能够搜索 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

我明白了。如何为 IComparer 编写语法让我感到害怕。有些人认为我必须扩展 Byte。

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

Answer 2

您的比较器只需要通过掩码进行比较，然后比较结果即可。（移位也有效——它们在这里基本上是等价的，尽管屏蔽允许您的密钥是输入中的 any 位集，而不一定是最重要的位。）使用您的示例- 但作为最小的完整控制台应用程序：

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

Int64 的自定义 IComparer

Custom IComparer for Int64

.net

list

binary-search