二进制文件中的二进制搜索数据包

Question

我的二进制文件由许多 24 字节的数据包组成，其中每个数据包的前 8 个字节代表 DateTime 类型的序列化时间戳。数据包都按时间戳以升序排列。我想开发一种二进制搜索算法，它选择前 8 个字节，反序列化时间戳，并将其与所需的时间戳进行比较。

目标是在二进制文件中找到表示与所需时间戳相匹配的序列化时间戳起始位置的位置。

编辑数据在二进制文件中而不是在数据结构中，因此 List<T>.BinarySearch() 对我不起作用。但是否可以在 Stream 上使用 BinarySearch 和 CustomComparer?

该文件包含数以千万计的此类数据包，因此对文件进行简单的迭代将非常低效。我考虑使用二进制搜索方法。

Answer 1

还没有测试过，但重点是读取文件中间的 8 个字节，然后移动到右侧或左侧中间并重复，具体取决于读取时间戳。（不是最干净的代码）。复杂度为 Log(N)

public class BinaryFinder
{
    private readonly long _packagesCount;
    private readonly FileStream _reader;

    public BinaryFinder(FileStream reader, int packageSize)
    {
        _reader = reader;
        _packagesCount = reader.Length / packageSize;
    }


    public long Find(DateTime dateToSearch)
    {
        return Find(0, _packagesCount, dateToSearch);
    }

    private long Find(long minPosition, long maxPosition, DateTime dateToSearch)
    {
        while (minPosition<=maxPosition) {
            var newPosition = (minPosition + maxPosition) / 2;
            var readDate = ReadDateAt(newPosition);

            if (readDate == dateToSearch) {
                return newPosition;
            }

            if (dateToSearch < readDate){
                maxPosition = newPosition-1;
            }
            else {
                minPosition = newPosition+1;
            }
        }

        return -1;
    }

    private DateTime ReadDateAt(long middlePosition)
    {
        var buffer = new byte[8];

        _reader.Seek(middlePosition, SeekOrigin.Begin);
        _reader.Read(buffer, 0, buffer.Length);

        var currentDate = ConvertBytesToDate(buffer);
        return currentDate;
    }

    private static DateTime ConvertBytesToDate(byte[] dateBytes)
    {
        throw new NotImplementedException();
    }
}

Answer 2

好的，这是代码中的疯狂想法，检查它，它将 return 您正在寻找的时间戳的结构索引。

只需实例化一个 FileStructList(fileName) 然后执行 list.BinarySearchIndexOf(theTimeStamp);

你甚至可以传递你自己的比较器:)

这包括对代码的二进制搜索，但由于它是一个 IList，您可以使用任何可用于集合的搜索方法。

public class FileStructList : IList<long>
{

    Stream baseStream;
    BinaryReader reader;
    int length;
    int headerSize;

    public FileStructList(string FileName, int HeaderSize)
    {
        baseStream = File.OpenRead(FileName);
        reader = new BinaryReader(baseStream);
        length = (int)((baseStream.Length - HeaderSize) / 24);
        headerSize = HeaderSize;
    }

    public long this[int index]
    {
        get
        {
            baseStream.Seek(24 * index + headerSize, SeekOrigin.Begin);
            return reader.ReadInt64();
        }

        set
        {
            throw new NotImplementedException();
        }
    }

    public int Count
    {
        get
        {
            return length;
        }
    }

    public bool IsReadOnly
    {
        get
        {
            return true;
        }
    }

    public void Add(long item)
    {
        throw new NotImplementedException();
    }

    public void Clear()
    {
        throw new NotImplementedException();
    }

    public bool Contains(long item)
    {
        return BinarySearchIndexOf(item) != -1;
    }

    public void CopyTo(long[] array, int arrayIndex)
    {
        throw new NotImplementedException();
    }

    public IEnumerator<long> GetEnumerator()
    {
        throw new NotImplementedException();
    }

    public int IndexOf(long item)
    {
        return BinarySearchIndexOf(item);
    }

    public void Insert(int index, long item)
    {
        throw new NotImplementedException();
    }

    public bool Remove(long item)
    {
        throw new NotImplementedException();
    }

    public void RemoveAt(int index)
    {
        throw new NotImplementedException();
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        throw new NotImplementedException();
    }

    public Int32 BinarySearchIndexOf(long value, IComparer<long> comparer = null)
    {
        comparer = comparer ?? Comparer<long>.Default;

        Int32 lower = 0;
        Int32 upper = length - 1;

        while (lower <= upper)
        {
            Int32 middle = lower + (upper - lower) / 2;
            Int32 comparisonResult = comparer.Compare(value, this[middle]);
            if (comparisonResult == 0)
                return middle;
            else if (comparisonResult < 0)
                upper = middle - 1;
            else
                lower = middle + 1;
        }

        return -1;
    }
}

二进制文件中的二进制搜索数据包

Binary Search packet in binary file

c#

search

serialization

binary-search