将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处理事情的方式。

为了获得更高的性能，您可以用+= See comments, another one by 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。我的代码比他的要快(我确信他现在还能再推一次我的)，但是他的代码比我的好。(我的看起来有点像c程序了)

Answer 2

如果如评论中提到的那样，列表是可以的，下面是我首先尝试的方法。下面是高得多的性能答案。

In [1]:  from math import *

In [2]:  L = [6,3,87,90,90,90,43,21,1]

In [3]: a=L[:]   # make a copy that gets trashed

In [4]: [[a.pop(0) for k in range(min(len(a),2**k1))] for k1 in range(int(log(len(a),2))+1)]
Out[4]: [[6], [3, 87], [90, 90, 90, 43], [21, 1]]

为了获得更多的性能(速度超过3倍)：

In [2]: L = [6,3,87,90,90,90,43,21,1]

In [3]: def slotify(L):
    return [L[(1<<k)-1:(1<<(k+1))-1] for k in range(len(L).bit_length())]

In [4]: slotify(L)
Out[4]: [[6], [3, 87], [90, 90, 90, 43], [21, 1]]