代码之家  ›  专栏  ›  技术社区  ›  Fredou

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

  •  3
  • Fredou  · 技术社区  · 6 年前

    我有一个 无序列表 在80到140个项目之间,每个项目的值在0到175之间。

    我正在生成一个列表,其中大约有500万到1000万个。

    我需要尽快处理所有 唯一有序序列 (不包括副本)。

    我现在做的方法是创建一个列表所有值的散列并将其插入到散列集中。

    分析时的两个热点是toarray() 热点1 和array.sort() 热点2

    有没有更好的方法来完成这项任务或者更好的方法来修复这两个热点?速度很重要。

    小演示,我试着尽可能多地复制

    using System;
    using System.Collections.Generic;
    using System.Linq;
    
    namespace ConsoleApp1
    {
    
        class Example
        {
            //some other properties
    
            public int Id { get; set; }
        }
    
        class Program
        {
            static void Main(string[] args)
            {
                var checkedUnlock = new HashSet<int>();
                var data = FakeData();
    
                foreach (List<Example> subList in data)
                {
                    var hash = CalcHash(subList.Select(x => x.Id).ToArray());  // HOTPSOT1
    
                    var newHash = checkedUnlock.Add(hash);
    
                    if (newHash)
                    {
                        //do something
                    }
                }
            }
    
            static int CalcHash(int[] value)
            {
                Array.Sort(value); // HOTPSOT2
    
                int hash;
                unchecked // https://stackoverflow.com/a/263416/40868
                {
                    hash = (int)2166136261;
                    var i = value.Length;
                    while (i-- > 0)
                        hash = (hash * 16777619) ^ value[i];
                }
    
                return hash;
            }
    
            //don't look at this, this is just to fake data
            static List<List<Example>> FakeData()
            {
                var data = new List<List<Example>>();
    
                var jMax = 10; //normally between 80 and 140
                var idMax = 25; //normally between 0 and 175
                var rnd = new Random(42);
                var ids = Enumerable.Range(0, idMax).ToArray();
    
                for (int i = 0; i < 500000; ++i)
                {
                    //force duplicate
                    if(i % 50000 == 0)
                    {
                        ids = Enumerable.Range(0, idMax).ToArray();
                        rnd = new Random(42);
                    }
    
                    for (int r = 0; r < idMax; ++r)
                    {
                        int randomIndex = rnd.Next(idMax);
                        int temp = ids[randomIndex];
                        ids[randomIndex] = ids[r];
                        ids[r] = temp;
                    }
    
                    var subList = new List<Example>();
                    data.Add(subList);
    
                    for (int j = 0; j < jMax; ++j)
                    {
                        subList.Add(new Example() { Id = ids[j] });                    
                    }
                }
    
                return data;
            }
        }
    }
    
    4 回复  |  直到 6 年前
        1
  •  1
  •   dlxeon    6 年前

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

    这将需要自定义排序实现,该实现知道即使数组可以有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;
    }
    
        2
  •  3
  •   Jim Mischel    6 年前

    因此,数组最多可以包含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 是的。它 可以 快于 位数组 代码。但不管是什么情况,它都会使您避免错误地假设相同的哈希码等于相同的数组。

        3
  •  1
  •   Joel Coehoorn    6 年前

    此版本的 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
    }
    
        4
  •  0
  •   Fredou    6 年前

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

    到目前为止,我所做的是创建一个布尔数组,并将项的索引设置为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%,这很好