汉明重量/人口数量在T-SQL。

时间:2021-12-06 07:31:56

I'm looking for a fast way to calculate the hamming weight/population count/"the number of 1 bits" of a BINARY(1024) field. MySQL has a BIT_COUNT function that does something like that. I couldn't find a similar function in T-SQL?

我正在寻找一种快速的方法来计算二进制(1024)字段的汉明权值/总体计数/“1比特数”。MySQL有一个BIT_COUNT函数。我在T-SQL中找不到类似的函数?

Or would you suggest storing the binary data in a field of another type?

或者您建议将二进制数据存储在另一个类型的字段中?

If you don't know what I'm talking about, here's a Wikipedia article about the hamming weight.

如果你不知道我在说什么,这里有一篇关于汉明重量的*文章。

4 个解决方案

#1


4  

You could use a helper table with precalculated Hamming weights for small numbers, like bytes, then split the value accordingly, join to the helper table and get the sum of partial Hamming weights as the value's Hamming weight:

您可以使用一个帮助表,对小数字(如字节)使用预先计算的汉明权值进行汉明权值,然后相应地分割值,加入到帮助表中,得到部分汉明权值的和作为值的汉明权值:

-- define Hamming weight helper table
DECLARE @hwtally TABLE (byte tinyint, hw int);
INSERT INTO @hwtally (byte, hw) VALUES (0, 0);
INSERT INTO @hwtally (byte, hw) SELECT   1 - byte, 1 - hw FROM @hwtally;
INSERT INTO @hwtally (byte, hw) SELECT   3 - byte, 2 - hw FROM @hwtally;
INSERT INTO @hwtally (byte, hw) SELECT   7 - byte, 3 - hw FROM @hwtally;
INSERT INTO @hwtally (byte, hw) SELECT  15 - byte, 4 - hw FROM @hwtally;
INSERT INTO @hwtally (byte, hw) SELECT  31 - byte, 5 - hw FROM @hwtally;
INSERT INTO @hwtally (byte, hw) SELECT  63 - byte, 6 - hw FROM @hwtally;
INSERT INTO @hwtally (byte, hw) SELECT 127 - byte, 7 - hw FROM @hwtally;
INSERT INTO @hwtally (byte, hw) SELECT 255 - byte, 8 - hw FROM @hwtally;

-- calculate
WITH split AS (
  SELECT SUBSTRING(@value, number, 1) AS byte
  FROM master.dbo.spt_values
  WHERE type = 'P' AND number BETWEEN 1 AND LEN(@value)
)
SELECT
  Value = @value,
  HammingWeight = SUM(t.hw)
FROM split s
  INNER JOIN @hwtally t ON s.byte = t.byte

#2


1  

When you are playing with smaller value (something like 16 bit max), The most efficient way to do it with SQL Server is using an Table with all result calculated and using a join.

当您使用更小的值(比如16位最大值)时,使用SQL Server进行处理的最有效方法是使用一个表,并使用一个连接计算所有结果。

I have speed up a query from 30 sec to 0 sec by doing this kind of thing on a query which should calculate Hamming Weight of a 4 bit value on 17'000 rows .

我已经通过在查询上执行这种操作将查询从30秒加速到0秒,该查询应该计算在17000行上4位值的汉明权值。

WITH HammingWeightHelper AS (
        SELECT  x, Fx 
        FROM (VALUES(0,0),(1,1),(2,1),(3,2),
                    (4,1),(5,2),(6,2),(7,3),
                    (8,1),(9,2),(10,2),(11,3),
                    (12,2),(13,3),(14,3),(15,4)) AS HammingWeight(x, Fx)
    )
SELECT HammingWeight.Fx As HammingWeight, SomeTable.Value As bitField
FROM   SomeTable INNER JOIN
       HammingWeightHelper ON HammingWeightHelper.x = SomeTable.Value 

Of course it is an ugly solution and it probably won't suit well for long bit field.

当然,这是一个丑陋的解决方案,它可能不适合长期的位域。

#3


0  

Didn't find anything specifically about hamming weight, but here's one for hamming distance:

没有发现任何关于汉明体重的具体信息,但这里有一个关于汉明距离的信息:

create function HamDist(@value1 char(8000), @value2 char(8000))
returns int
as
begin
    declare @distance int
    declare @i int
    declare @len int

    select @distance = 0,
           @i =1,
           @len = case when len(@value1) > len(@value2)
                       then len(@value1)
                       else len(@value2) end

    if (@value1 is null) or (@value2 is null)
        return null

    while (@i <= @len)
        select @distance = @distance +
                           case when substring(@value1,@i,1) != substring(@value2,@i,1)
                                then 1
                                else 0 end,
               @i = @i +1

    return @distance
end

This computes the hamming distance between two values. The hamming weight of a single value would be the hamming distance between that value and an array of zero-values.

计算两个值之间的汉明距离。单个值的汉明权值将是该值与一个零值数组之间的汉明距离。

#4


0  

I couldn't find a good way to do it. In the end I calculated the hamming weight in Java and periodically update the bit counts in the database.

我找不到一个好办法。最后,我计算了Java中的汉明权值,并定期更新数据库中的位计数。

#1


4  

You could use a helper table with precalculated Hamming weights for small numbers, like bytes, then split the value accordingly, join to the helper table and get the sum of partial Hamming weights as the value's Hamming weight:

您可以使用一个帮助表,对小数字(如字节)使用预先计算的汉明权值进行汉明权值,然后相应地分割值,加入到帮助表中,得到部分汉明权值的和作为值的汉明权值:

-- define Hamming weight helper table
DECLARE @hwtally TABLE (byte tinyint, hw int);
INSERT INTO @hwtally (byte, hw) VALUES (0, 0);
INSERT INTO @hwtally (byte, hw) SELECT   1 - byte, 1 - hw FROM @hwtally;
INSERT INTO @hwtally (byte, hw) SELECT   3 - byte, 2 - hw FROM @hwtally;
INSERT INTO @hwtally (byte, hw) SELECT   7 - byte, 3 - hw FROM @hwtally;
INSERT INTO @hwtally (byte, hw) SELECT  15 - byte, 4 - hw FROM @hwtally;
INSERT INTO @hwtally (byte, hw) SELECT  31 - byte, 5 - hw FROM @hwtally;
INSERT INTO @hwtally (byte, hw) SELECT  63 - byte, 6 - hw FROM @hwtally;
INSERT INTO @hwtally (byte, hw) SELECT 127 - byte, 7 - hw FROM @hwtally;
INSERT INTO @hwtally (byte, hw) SELECT 255 - byte, 8 - hw FROM @hwtally;

-- calculate
WITH split AS (
  SELECT SUBSTRING(@value, number, 1) AS byte
  FROM master.dbo.spt_values
  WHERE type = 'P' AND number BETWEEN 1 AND LEN(@value)
)
SELECT
  Value = @value,
  HammingWeight = SUM(t.hw)
FROM split s
  INNER JOIN @hwtally t ON s.byte = t.byte

#2


1  

When you are playing with smaller value (something like 16 bit max), The most efficient way to do it with SQL Server is using an Table with all result calculated and using a join.

当您使用更小的值(比如16位最大值)时,使用SQL Server进行处理的最有效方法是使用一个表,并使用一个连接计算所有结果。

I have speed up a query from 30 sec to 0 sec by doing this kind of thing on a query which should calculate Hamming Weight of a 4 bit value on 17'000 rows .

我已经通过在查询上执行这种操作将查询从30秒加速到0秒,该查询应该计算在17000行上4位值的汉明权值。

WITH HammingWeightHelper AS (
        SELECT  x, Fx 
        FROM (VALUES(0,0),(1,1),(2,1),(3,2),
                    (4,1),(5,2),(6,2),(7,3),
                    (8,1),(9,2),(10,2),(11,3),
                    (12,2),(13,3),(14,3),(15,4)) AS HammingWeight(x, Fx)
    )
SELECT HammingWeight.Fx As HammingWeight, SomeTable.Value As bitField
FROM   SomeTable INNER JOIN
       HammingWeightHelper ON HammingWeightHelper.x = SomeTable.Value 

Of course it is an ugly solution and it probably won't suit well for long bit field.

当然,这是一个丑陋的解决方案,它可能不适合长期的位域。

#3


0  

Didn't find anything specifically about hamming weight, but here's one for hamming distance:

没有发现任何关于汉明体重的具体信息,但这里有一个关于汉明距离的信息:

create function HamDist(@value1 char(8000), @value2 char(8000))
returns int
as
begin
    declare @distance int
    declare @i int
    declare @len int

    select @distance = 0,
           @i =1,
           @len = case when len(@value1) > len(@value2)
                       then len(@value1)
                       else len(@value2) end

    if (@value1 is null) or (@value2 is null)
        return null

    while (@i <= @len)
        select @distance = @distance +
                           case when substring(@value1,@i,1) != substring(@value2,@i,1)
                                then 1
                                else 0 end,
               @i = @i +1

    return @distance
end

This computes the hamming distance between two values. The hamming weight of a single value would be the hamming distance between that value and an array of zero-values.

计算两个值之间的汉明距离。单个值的汉明权值将是该值与一个零值数组之间的汉明距离。

#4


0  

I couldn't find a good way to do it. In the end I calculated the hamming weight in Java and periodically update the bit counts in the database.

我找不到一个好办法。最后,我计算了Java中的汉明权值,并定期更新数据库中的位计数。