从更大的列表中筛选出无序int的列表

我认为您可以通过重新使用一个更大的数组来节省一些时间,而不是每次分配新的数组都会导致额外的内存流量和垃圾收集。

这将需要自定义排序实现,该实现知道即使数组可以有1000个项,但对于当前运行,只需要对前80个项进行排序(对于散列也是如此)。在ids的子范围上运行quicksort应该可以正常工作。想法的快速示例(尚未进行详细测试)

int[] buffer = new int[1000];
foreach (List<Example> subList in data)
{
    for (int i = 0; i < subList.Count; i++)
    {
        buffer[i] = subList[i].Id;
    }
    var hash = CalcHashEx(buffer, 0, subList.Count - 1);

    var newHash = checkedUnlock.Add(hash);

    if (newHash)
    {
        //do something
    }
}


public static void QuickSort(int[] elements, int left, int right)
{
    int i = left, j = right;
    int pivot = elements[(left + right) / 2];
    while (i <= j)
    {
        while (elements[i] < pivot)
        {
            i++;
        }
        while (elements[j] > pivot)
        {
            j--;
        }
        if (i <= j)
        {
            // Swap
            int tmp = elements[i];
            elements[i] = elements[j];
            elements[j] = tmp;
            i++;
            j--;
        }
    }

    if (left < j)
    {
        QuickSort(elements, left, j);
    }
    if (i < right)
    {
        QuickSort(elements, i, right);
    }
}

static int CalcHashEx(int[] value, int startIndex, int endIndex)
{
    QuickSort(value, startIndex, endIndex);

    int hash;
    unchecked // https://stackoverflow.com/a/263416/40868
    {
        hash = (int)2166136261;
        var i = endIndex + 1;
        while (i-- > 0)
            hash = (hash * 16777619) ^ value[i];
    }

    return hash;
}

因此,数组最多可以包含140个项,所有值都在0到175之间。数组中的所有值都是唯一的,顺序无关紧要。也就是说,数组 [20, 90, 16] 将被视为 [16, 20, 90] 是的。

因此,可以将单个数组表示为175位的集合。更好的方法是,无需对输入数组排序就可以创建集合。

你在c中表示一个集合 BitArray 是的。要计算数组的哈希代码,需要创建集合,然后遍历集合以获取哈希代码。看起来像这样:

private BitArray HashCalcSet = new BitArray(175);
int CalcHash(int[] a, int startIndex)
{
    // construct the set
    HashCalcSet.SetAll(false);

    for (var i = startIndex; i < a.Length; ++i)
    {
        HashCalcSet[a[i]] = true;
    }

    // compute the hash
    hash = (int)2166136261;
    for (var i = 174; i >= 0; --i)
    {
        if (HashCalcSet[i])
        {
            hash = (hash * 16777619) ^ value[i];
        }
    }
    return hash;
}

它消除了排序以及 ToArray 是的。你必须在 BitArray 有几次,但是有三次 位数组 可能比分类快。

我看到你的解决方案的一个问题是你如何使用 HashSet 是的。你有这个密码:

var hash = CalcHash(subList.Select(x => x.Id).ToArray());  // HOTPSOT1

var newHash = checkedUnlock.Add(hash);

if (newHash)
{
    //do something
}

该代码错误地假设,如果两个数组的哈希代码相等,则数组相等。您正在为175位数量生成32位哈希代码。肯定会有散列冲突。你最终会说你的两个数组是相同的,而不是相同的。

如果这是你关心的问题,让我知道,我可以编辑我的答案,以提供解决方案。

允许比较

如果希望能够比较项的相等性,而不是只检查它们的哈希代码是否相同,则需要创建一个具有 Equals 和 GetHashCode 方法。你将把这个对象插入 哈希表 .其中最简单的对象将包含 位数组 我在上面描述了,以及对其进行操作的方法。类似于:

class ArrayObject
{
    private BitArray theBits;
    private int hashCode;
    public override bool Equals(object obj)
    {
        if (object == null || GetType() != obj.GetType())
        {
            return false;
        }
        ArrayObject other = (ArrayObject)obj;
        // compare two BitArray objects
        for (var i = 0; i < theBits.Length; ++i)
        {
            if (theBits[i] != other.theBits[i])
                return false;
        }
        return true;
    }

    public override int GetHashCode()
    {
        return hashCode;
    }

    public ArrayObject(int hash, BitArray bits)
    {
        theBits = bits;
        hashCode = hash;
    }
}

你的想法是 位数组 以及方法中的哈希代码,如上所述(尽管您将不得不分配一个新的 位数组 对于每个调用),然后创建并返回其中一个 ArrayObject 实例。

你的 散列集 变成 HashSet<ArrayObject> 是的。

上面的方法行得通,但这是一个很大的记忆猪。您可以通过创建一个只包含三个 long 整数。而不是使用 位数组 ,直接操作位。映射这些位,以便数字0到63修改第一个数字中的位0到63。从64到127的数字对应第二个数字的0到63位,等等。你不必保存单独的散列代码,因为从这三个长度计算起来很容易,相等比较也变得容易得多。

这个班看起来像这样。明白,我还没有测试过代码,但这个想法应该是正确的。

class ArrayObject2
{
    private long l1;
    private long l2;
    private long l3;

    public ArrayObject2(int[] theArray)
    {
        for (int i = 0; i < theArray.Length; ++i)
        {
            var rem = theArray[i] % 63;
            int bitVal = 1 << rem;
            if (rem < 64) l1 |= bitVal;
            else if (rem < 128) l2 |= bitVal;
            else l3 |= bitVal;
        }
    }

    public override bool Equals(object obj)
    {
        var other = obj as ArrayObject2;
        if (other == null) return false;
        return l1 == other.l1 && l2 == other.l2 && l3 == other.l3;
    }

    public override int GetHashCode()
    {
        // very simple, and not very good hash function.
        return (int)l1;
    }
}

正如我在代码中所评论的,那里的散列函数不太好。它会起作用的,但你可以做得更好一点研究。

这种方法的优点是使用的内存比 位数组 或者 Boolean 阵列。可能会比 bool 是的。它 可以 快于 位数组 代码。但不管是什么情况,它都会使您避免错误地假设相同的哈希码等于相同的数组。

此版本的 CalcHash() 将允许您删除 .ToArray() 并替换 Array.Sort() 有一些不同的东西可以作用于一个序列,而不是需要整个集合…所以这两个都是热点。

static int CalcHash(IEnumerable<int> value)
{
    value = value.OrderByDescending(i => i);

    int hash;
    unchecked // https://stackoverflow.com/a/263416/40868
    {
        hash = (int)2166136261;
        foreach(var item in value)
        {
            hash = (hash * 16777619) ^ item;
        }
    }

    return hash;
}

我不知道怎么做 OrderByDescending() 会比较好。我想它会比 数组排序() ,但仍然是一个全面的胜利,因为消除 ToArray() …但您需要再次运行探查器才能确定。

通过消除或减少分支,您还可以获得一些改进 .GroupBy() ,并在 .First() 每组项目:

var groups = data.GroupBy(sub => CalcHash(sub.Select(x => x.Id)));
foreach(List<Example> subList in groups.Select(g => g.First()))
{
    //do something
}

把这个放在这里,因为把它放在评论里是没有意义的

到目前为止,我所做的是创建一个布尔数组,并将项的索引设置为true(当存在时),然后用替换calchash;

        unchecked
        {
            hash = (int)2166136261;
            var i = theMaxLength;
            while (i-- > 0)
                if(testing[i]) //the array of boolean
                {
                    hash = (hash  * 16777619) ^ i;
                    testing[i] = false;
                }
        }

这样做时,我完全删除了toArray()和array.sort(),这个解决方案是根据dlxeon/jim/joel答案构建的

我把运行时间减少了20-25%,这很好