草庐IT

c - 求和，数组构造和寻址的简洁二叉树

coder 2024-07-07 原文

使用“sum”作为捷径进行任意计算。我有一个通过递归求和值对来从值列表中计算单个和的过程。未配对的值将被不变地提升到树上，直到可以配对为止。

在进行了这种计算之后，我正在寻找平衡计算的最佳方法(即访问数组元素/节点所需的操作数)以及一维数组中所有节点的最简洁的编码(即无间隙，零值) (或重复值)，并且最好没有额外的索引数组，该数组不能从简洁编码中轻松得出，因此必须将其与数组一起保存。

尽管以下是简单的示例，但实际上，初始列表中的值数量可能非常大(2 ^ 47或更多)。

例如，给定列表[1、2、3、4]，该数组是微不足道的:[10、3、7、1、2、3、4]，并很好地拆分为易于按节点寻址的行，或作为对整个行的引用。

但是对于5项列表，树看起来像这样:

树1

         15
        /  \
       /    \
      /      \
     /        \
    10          5
  /   \       /   \
 3     7     5     -
/ \   / \   / \   / \
1  2  3  4 5   - -   -

标准映射left = i*2+1，right = i*2+2为我们提供了以下数组:

阵列1
[ 15, 10,  5,  3,   7,   5,  nil,   1,   2,   3,   4,   5,   nil,   nil, nil]

该数组具有4个nil值，列表“5”中的最后一个元素重复2次。

为了改善这一点，我们可以暗示重复5，并删除nil值:

阵列2
[15, 10, 3, 7, 1, 2, 3, 4, 5]

这更紧凑。这棵树是相同的，但从概念上看有点像:

树2
       15
      / \
     /   \
    10    \
  /   \    \
 3     7    \
/ \   / \    \
1  2  3  4    5

在数组2 编码中，我有4行:
1. [1, 2, 3, 4]
2. [3, 7]
3. [10, 5]
4. [15]

行1，行2和行4可以简单地引用到数组2 中，这使我可以“就地”计算结果，而无需分配或复制。非常快。但是，第3行包含两个不连续单元格中的值。我必须打破用于其他行的简单逻辑，并可能为 map 添加副本，索引或存储。

我可以构造完整/平衡的子树(例如索引1-7、1、2、3、4的树)，但是当奇数个项目出现在不同的行时，它们似乎并不会总是很好地对齐取决于输入长度。例如，考虑具有6个元素的初始列表的树。

最佳答案

假设您的树在最后(最多)行上具有N节点。

如果确实存储仅向上传播的节点，则树的总数在2*N-1和2*N-1+log2(N)节点之间。节点的确切总数由OEIS A120511给出。其中，最多floor(2 + log2(N-1))是复制/传播的节点。

树上有floor(2 + log2(N-1))行。作为N的函数的行数(最后一行的元素数)是OEIS A070941。

这样的树中的行数非常低。例如，如果最后一行有240≈1,000,000,000,000个节点，则树中只有42行。对于264个节点，您只有66个。因此，如果您需要每行进行一些操作，则开销不会很高。

给定最后一行N中的节点数，一个简单的对数时间函数可以计算行数和节点总数。

# Account for the root node
rows = 1
total = 1

curr_left = N
While (curr_left > 1):
    rows = rows + 1
    total = total + curr_left
    curr_left = (curr_left + 1) / 2
End While

其中/表示整数除法，即任何小数部分都被丢弃/截断/舍入为零。同样，对于最后一行中的264个节点，以上仅循环65次。

当我们知道树中的节点总数和行数时，我们可以使用另一个对数时间循环来计算树的每一行上第一个元素的偏移量以及该行上的节点数:
first_offset = []
nodes = []

curr_row = rows - 1
curr_offset = total - N
curr_left = N

While (curr_left > 1):
    nodes[curr_row] = curr_left
    first_offset[curr_row] = curr_offset
    curr_row = curr_row - 1
    curr_left = (curr_left + 1) / 2
    curr_offset = curr_offset - curr_left
}

first_offset[0] = 0
nodes[0] = 1

与之前一样，对于最后一行中的264个节点，以上仅循环65次。

行中的所有元素在内存中都是连续的，如果我们使用从零开始的索引，并且N是最后一行中的节点数，则应用上面的内容，然后
  • rows是树
    • 中的行数
  • total是树
    • 中的节点总数
  • 如果nodes[r]和r
    • ，则在r >= 0行上有r < rows节点
  • 行r上的节点的数组索引，列c是first_offset[r] + c
  • 行r上的节点，列c上，带有r > 0，在行r-1上，列c/2上有一个父节点，数组索引为first_offset[r-1] + c/2
  • 行r(列c)上的节点(带有r < rows - 1)，在行r+1(列2*c)上具有左子节点，数组索引为first_offset[r+1] + 2*c
  • 第r行，第c列上的节点(带有r < rows - 1和c < nodes[r] - 1)在第r+1行，第2*c+1列上有一个正确的子节点，在数组索引first_offset[r+1] + 2*c + 1上
  • 行r，列c上的节点(带有r < rows - 1和c < nodes[r] - 1)具有左右两个子

    • 该阵列非常紧凑，除了向上传播的节点(对于一个TB级的数据集，可能只有几十个节点)之外，它不会浪费存储空间。

    如果最后一行中的节点数与数组一起存储(例如，作为数组数据后的额外uint64_t)，则所有阅读器都可以恢复total，rows，first_offset[]和nodes[]，并轻松导航树。 (但是，请注意，您不仅可以使用数组索引，还可以使用“column”和“row”，并使用它们来派生数组索引。)

    由于first_offset[]和nodes[]数组最多具有几十个条目，因此它们应在高速缓存中保持高温，并且使用它们不应损害性能。

    请注意，并非所有树大小都适用于以上第二段所述的规则。例如，具有两个节点的树没有意义:为什么要复制根节点？

    如果您确实知道树的大小(total)有效，则可以使用二进制搜索以N时间复杂度为基础，根据total查找O(log2(total)*log2log2(total))，如果使用简单循环，则可以以O((log2(total))²)为基础。请记住，total在2*N-1和2*N-1+log2(N)之间。相反，N不能大于(N + 1)/2或小于(N + 1)/2 - log2(total)，因为total大于N，因此log2(N)小于log2(total)。因此，二进制搜索可以实现为
    Function Find_N(total):
    Nmax = (total + 1) / 2
    Nmin = Nmax - log2(total)

    t = Total(Nmin)
    If t == total:
        Return Nmin
    Else if t < total:
        Return "Bug!"
    End if

    t = Total(Nmax)
    if t == total:
        Return Nmax
    Else if t > total:
        Return "Bug!"
    End if

    Loop:

        N = (Nmin + Nmax) / 2
        If N == Nmin:
            Return "Invalid tree size!"
        End If

        t = Total(N)
        If t > total:
            Nmax = N
        Else if t < total:
            Nmin = N
        Else:
            return N
        End If            
    End Loop
End Function

    请记住，即使树中有264个节点，上述函数也最多对1 + log2(64)进行Total = 6调用，该函数实现了此答案中的第一个伪代码段。由于通常每个程序调用仅需要一次，因此开销实际上是不相关的。

    自C99起，您就可以使用log2(x)来计算log(x)/log(2)，并使用log2()中的<math.h>函数(但是由于double的精度不及uint64_t，我会在结果中添加+1，或者使用ceil()将其四舍五入为正无穷大)，甚至使用一个简单的循环:
    Function ulog2(value):
    result = 0
    While (value > 0):
        result = result + 1
        value = value / 2
    End While
    Return result
End Function

    其中/再次表示整数除法。

    关于c - 求和，数组构造和寻址的简洁二叉树，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/44895747/

    求和简洁codebrtotalcarraysalgorithmgotree

    有关c - 求和，数组构造和寻址的简洁二叉树的更多相关文章

    1. ruby-on-rails - 在 Ruby 中循环遍历多个数组 - 2

      我有多个ActiveRecord子类Item的实例数组，我需要根据最早的事件循环打印。在这种情况下，我需要打印付款和维护日期，如下所示:ItemAmaintenancerequiredin5daysItemBpaymentrequiredin6daysItemApaymentrequiredin7daysItemBmaintenancerequiredin8days我目前有两个查询，用于查找maintenance和payment项目(非排他性查询)，并输出如下内容:paymentrequiredin...maintenancerequiredin...有什么方法可以改善上述(丑陋的)代

    2. ruby - 多次弹出/移动 ruby​​ 数组 - 2

      我的代码目前看起来像这样numbers=[1,2,3,4,5]defpop_threepop=[]3.times{pop有没有办法在一行中完成pop_three方法中的内容？我基本上想做类似numbers.slice(0,3)的事情，但要删除切片中的数组项。嗯...嗯，我想我刚刚意识到我可以试试slice! 最佳答案 是numbers.pop(3)或者numbers.shift(3)如果你想要另一边。 关于ruby-多次弹出/移动ruby​​数组，我们在StackOverflow上找到一

    3. ruby - 将数组的内容转换为 int - 2

      我需要读入一个包含数字列表的文件。此代码读取文件并将其放入二维数组中。现在我需要获取数组中所有数字的平均值，但我需要将数组的内容更改为int。有什么想法可以将to_i方法放在哪里吗？ClassTerraindefinitializefile_name@input=IO.readlines(file_name)#readinfile@size=@input[0].to_i@land=[@size]x=1whilex 最佳答案 只需将数组映射为整数:@land边注如果你想得到一条线的平均值，你可以这样做:values=@input[x]

    4. ruby - 通过 erb 模板输出 ruby​​ 数组 - 2

      我正在使用puppet为ruby​​程序提供一组常量。我需要提供一组主机名，我的程序将对其进行迭代。在我之前使用的bash脚本中，我只是将它作为一个puppet变量hosts=>"host1,host2"我将其提供给bash脚本作为HOSTS=显然这对ruby​​不太适用——我需要它的格式hosts=["host1","host2"]自从phosts和putsmy_array.inspect提供输出["host1","host2"]我希望使用其中之一。不幸的是，我终其一生都无法弄清楚如何让它发挥作用。我尝试了以下各项:我发现某处他们指出我需要在函数调用前放置“function_”……这

    5. ruby - 检查数组是否在增加 - 2

      这个问题在这里已经有了答案:Checktoseeifanarrayisalreadysorted?(8个答案)关闭9年前。我只是想知道是否有办法检查数组是否在增加？这是我的解决方案，但我正在寻找更漂亮的方法:n=-1@arr.flatten.each{|e|returnfalseife

    6. ruby - 如果指定键的值在数组中相同，如何合并哈希 - 2

      我有一个这样的哈希数组:[{:foo=>2,:date=>Sat,01Sep2014},{:foo2=>2,:date=>Sat,02Sep2014},{:foo3=>3,:date=>Sat,01Sep2014},{:foo4=>4,:date=>Sat,03Sep2014},{:foo5=>5,:date=>Sat,02Sep2014}]如果:date相同，我想合并哈希值。我对上面数组的期望是:[{:foo=>2,:foo3=>3,:date=>Sat,01Sep2014},{:foo2=>2,:foo5=>5:date=>Sat,02Sep2014},{:foo4=>4,:dat

    7. ruby - 在 Ruby 中用键盘诅咒数组浏览 - 2

      我正在尝试在Ruby中制作一个cli应用程序，它接受一个给定的数组，然后将其显示为一个列表，我可以使用箭头键浏览它。我觉得我已经在Ruby中看到一个库已经这样做了，但我记不起它的名字了。我正在尝试对soundcloud2000中的代码进行逆向工程做类似的事情，但他的代码与SoundcloudAPI的使用紧密耦合。我知道cursesgem，我正在考虑更抽象的东西。广告有没有人见过可以做到这一点的库或一些概念证明的Ruby代码可以做到这一点？ 最佳答案 我不知道这是否是您正在寻找的，但也许您可以使用我的想法。由于我没有关于您要完成的工作

    8. ruby - 如何在 Grape 中定义哈希数组？ - 2

      我使用Ember作为我的前端和GrapeAPI来为我的API提供服务。前端发送类似:{"service"=>{"name"=>"Name","duration"=>"30","user"=>nil,"organization"=>"org","category"=>nil,"description"=>"description","disabled"=>true,"color"=>nil,"availabilities"=>[{"day"=>"Saturday","enabled"=>false,"timeSlots"=>[{"startAt"=>"09:00AM","endAt"=>

    9. ruby - 使用多个数组创建计数 - 2

      我正在尝试按0-9和a-z的顺序创建数字和字母列表。我有一组值value_array=['0','1','2','3','4','5','6','7','8','9','a','b'，'光盘'，'e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','','u','v','w','x','y','z']和一个组合列表的数组，按顺序，这些数字可以产生x个字符，比方说三个list_array=[]和一个当前字母和数字组合的数组(在将它插入列表数组之前我会把它变成一个字符串，]current_combo['0','0','0']

    10. ruby - 在哈希的键数组中追加元素 - 2

      查看我的Ruby代码:h=Hash.new([])h[0]=:word1h[1]=h[1]输出是:Hash={0=>:word1,1=>[:word2,:word3],2=>[:word2,:word3]}我希望有Hash={0=>:word1,1=>[:word2],2=>[:word3]}为什么要附加第二个哈希元素(数组)？如何将新数组元素附加到第三个哈希元素？ 最佳答案 如果您提供单个值作为Hash.new的参数(例如Hash.new([])，完全相同的对象将用作每个缺失键的默认值。这就是您所拥有的，那是你不想要的。您可以改用

    随机推荐