python - 每层放置 pow(N,levels) 个元素

Question

给定一个列表L = [6,3,87,90,90,90,43,21,1]

我正在创建一个类似树的结构，其中每个级别都将 pow(2,level) 元素存储在数组中

这是我尝试过的代码

from collections import defaultdict

def slotify(L):
    level = defaultdict(dict)
    ptr = 0
    try:
        for ref in xrange(len(L)):
            #print ref
            for count in xrange(pow(2,ref)):
                level[ref].update({ptr:L[ptr]})
                ptr += 1
    except (IndexError) as e:
        return level


slotify(L)
Out[297]: defaultdict(<type 'dict'>, {0: {0: 6}, 1: {1: 3, 2: 87}, 2: {3: 90, 4: 90, 5: 90, 6: 43}, 3: {8: 1, 7: 21}})

输出正确。

我想知道更好的逻辑实现，更好的代码。谢谢。

Answer 1

这是我的做法:

def slotify(L):
    level = []
    counter = 1
    while counter*2 <= len(L):
        level.append(L[counter-1:counter*2-1])
        counter = counter * 2
    level.append(L[counter-1:])
    return level

这将循环遍历各个级别并将它们插入到“级别”中，除了最后一个级别之外，它只添加剩余的几个级别，因为它可能不一定是完整的级别。

您甚至可以更进一步，缓存计数器*2 值以节省乘法(改编自 user2290820 的建议)

def slotify(L):
    level = []
    counter = 1
    counter_n2 = 2
    while counter_n2 <= len(L):
        level.append(L[counter-1:counter_n2-1])
        counter = counter_n2
        counter_n2 = counter_n2 * 2
    level.append(L[counter-1:])
    return level

您甚至可以更进一步进行更改

counter_n2 = counter_n2 * 2

至

counter_n2 += counter_n2

因为 python 处理事物的方式。

为了获得更好的性能，您可以用 += [] 替换附加(请参阅评论，user2290820 的另一条评论)

如果您缓存 len(L) 的返回值，速度会更快，因为您只需要计算一次，然后就不必再次担心全局查找。

这是现在的代码:

def slotify(L):
  level=[]
  counter=1
  counter2=2
  val=len(L)
  while counter2<=val:
    level+=[L[counter-1:counter2-1]]
    counter=counter2
    counter2+=counter2
level+=[L[counter-1:]]
return level

你不会比这更快了。

程序流程与第一个流程相同，只是进行了优化。

但我必须相信rickhg12hs。我的代码比他的要快(仅仅目前，我确信他可以再次推送他过去的我的代码;))使用我的设置(Linux 2.7.5)，但他的代码比我的更好。 (我现在看起来有点像c程序)