Linq2sql:获取具有权重的随机元素的有效方法?

我的第一个想法和Ron Klein的一样——创建一个加权列表并从中随机选择。

这里有一个LINQ扩展方法,可以从普通列表创建加权列表,给定一个lambda函数,该函数知道对象的权重属性。

如果你没有马上得到所有的泛型,别担心。。。下面的用法应该更清楚:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
    public class Item
    {
        public int Weight { get; set; }
        public string Name { get; set; }
    }

    public static class Extensions
    {
        public static IEnumerable<T> Weighted<T>(this IEnumerable<T> list, Func<T, int> weight)
        {
            foreach (T t in list)
                for (int i = 0; i < weight(t); i++)
                    yield return t;
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            List<Item> list = new List<Item>();
            list.Add(new Item { Name = "one", Weight = 5 });
            list.Add(new Item { Name = "two", Weight = 1 });

            Random rand = new Random(0);

            list = list.Weighted<Item>(x => x.Weight).ToList();

            for (int i = 0; i < 20; i++)
            {
                int index = rand.Next(list.Count());
                Console.WriteLine(list.ElementAt(index).Name);
            }

            Console.ReadLine();
        }
    }
}

我假设权重是一个整数。这里有一种方法,它连接到一个虚拟表,以增加每个权重的行数;首先,让我们在TSQL上证明一下:

SET NOCOUNT ON
--DROP TABLE [index]
--DROP TABLE seo
CREATE TABLE [index] ([key] int not null) -- names for fun ;-p
CREATE TABLE seo (url varchar(10) not null, [weight] int not null)

INSERT [index] values(1) INSERT [index] values(2)
INSERT [index] values(3) INSERT [index] values(4)
INSERT [index] values(5) INSERT [index] values(6)
INSERT [index] values(7) INSERT [index] values(8)
INSERT [index] values(9) INSERT [index] values(10)

INSERT [seo] VALUES ('abc',1)  INSERT [seo] VALUES ('def',2)
INSERT [seo] VALUES ('ghi',1)  INSERT [seo] VALUES ('jkl',3)
INSERT [seo] VALUES ('mno',1)  INSERT [seo] VALUES ('mno',1)
INSERT [seo] VALUES ('pqr',2)

DECLARE @count int, @url varchar(10)
SET @count = 0
DECLARE @check_rand TABLE (url varchar(10) not null)

-- test it lots of times to check distribution roughly matches weights
WHILE @count < 11000
BEGIN
    SET @count = @count + 1

    SELECT TOP 1 @url = [seo].[url]
    FROM [seo]
    INNER JOIN [index] ON [index].[key] <= [seo].[weight]
    ORDER BY NEWID()

    -- this to check distribution
    INSERT @check_rand VALUES (@url)
END

SELECT ISNULL(url, '(total)') AS [url], COUNT(1) AS [hits]
FROM @check_rand
GROUP BY url WITH ROLLUP
ORDER BY url

这将输出如下内容:

url        hits
---------- -----------
(total)    11000
abc        1030
def        1970
ghi        1027
jkl        2972
mno        2014
pqr        1987

[index] 表来执行此操作)-我的DBML:

  <Table Name="dbo.[index]" Member="indexes">
    <Type Name="index">
      <Column Name="[key]" Member="key" Type="System.Int32" DbType="Int NOT NULL" CanBeNull="false" />
    </Type>
  </Table>
  <Table Name="dbo.seo" Member="seos">
    <Type Name="seo">
      <Column Name="url" Type="System.String" DbType="VarChar(10) NOT NULL" CanBeNull="false" />
      <Column Name="weight" Type="System.Int32" DbType="Int NOT NULL" CanBeNull="false" />
    </Type>
  </Table>

现在我们将消耗这些;在 partial class 对于数据上下文,在 附加 Random 方法:

partial class MyDataContextDataContext
{
    [Function(Name = "NEWID", IsComposable = true)]
    public Guid Random()
    {
        throw new NotImplementedException();
    }
    public string GetRandomUrl()
    {
        return randomUrl(this);
    }
    static readonly Func<MyDataContextDataContext, string>
        randomUrl = CompiledQuery.Compile(
        (MyDataContextDataContext ctx) =>
                 (from s in ctx.seos
                 from i in ctx.indexes
                 where i.key <= s.weight
                 orderby ctx.Random()
                 select s.url).First());
}

这个LINQ到SQL查询与我们编写的TSQL的关键部分非常相似;让我们测试一下:

using (var ctx = CreateContext()) {
    // show sample query
    ctx.Log = Console.Out;
    Console.WriteLine(ctx.GetRandomUrl());
    ctx.Log = null;

    // check distribution
    var counts = new Dictionary<string, int>();
    for (int i = 0; i < 11000; i++) // obviously a bit slower than inside db
    {
        if (i % 100 == 1) Console.WriteLine(i); // show progress
        string s = ctx.GetRandomUrl();
        int count;
        if (counts.TryGetValue(s, out count)) {
            counts[s] = count + 1;
        } else {
            counts[s] = 1;
        }
    }
    Console.WriteLine("(total)\t{0}", counts.Sum(p => p.Value));
    foreach (var pair in counts.OrderBy(p => p.Key)) {
        Console.WriteLine("{0}\t{1}", pair.Key, pair.Value);
    }
}

SELECT TOP (1) [t0].[url]
FROM [dbo].[seo] AS [t0], [dbo].[index] AS [t1]
WHERE [t1].[key] <= [t0].[weight]
ORDER BY NEWID()
-- Context: SqlProvider(Sql2008) Model: AttributedMetaModel Build: 3.5.30729.4926

这看起来一点也不糟糕——它有两个表和范围条件,以及 TOP 1 ,所以它正在做一些非常相似的事情;数据:

(total) 11000
abc     939
def     1893
ghi     1003
jkl     3104
mno     2048
pqr     2013

同样,我们得到了正确的发行版,从LINQ到SQL。分类?

从问题中可以看出,您建议的解决方案绑定到Linq/Linq2Sql。

如果我理解正确,您的主要目标是从数据库中最多获取X条记录,这些记录的权重大于0。如果数据库包含X条以上的记录,您希望使用记录的权重从中进行选择,并得到一个随机结果。

然而,克隆这些记录会造成复制。所以你不能只取X条记录,你应该取越来越多的记录,直到你有X条不同的记录。

我认为使用

如果总数 是 巨大的,我建议您随机(通过Linq2Sql)选择100000条(或更少)记录,并按上述方式应用实现。我相信这已经够随机的了。

尝试使用RAND()sql函数-它将给您一个0到1的浮点值。

缺点是,我不确定这是否会导致sql server端的完整表扫描,也就是说,sql上的查询+执行是否会以这样一种方式进行优化,即一旦您拥有前n条记录,它就会忽略表的其余部分。

var rand = new Random();

var ws = db.WorkTypes
.Where(e => e.HumanId != null && e.SeoPriority != 0)
.OrderByDescending(e => rand.Next() * e.SeoPriority)
.Select(e => new
{
   DescriptionText = e.DescriptionText,
   HumanId = e.HumanId
})
.Take(take).ToArray();

在您正在查看的SQL示例中使用GUID(NEWID)函数的原因很简单,SQL Server RAND函数只对每条语句计算一次。所以在随机选择中是无用的。

var ws=db.WorkTypes .OrderByDescending(e=>rand.Next(10)*e.SeoPriority) .拿(拿)去排队;

它不是100%的准确度,但很接近,调整下一个值可以调整它。