如何优化这个答案以使用给定的256字节作为示例
示例字节为：
bytez = [197 215 20 156 94 67 20 100 27 208 186 248 71 48 128 75 7 165 148 223 94 163 233 15 161 104 246 66 242 142 118 165 204 0 252 22 233 28 136 197 113 122 72 229 11 91 133 142 20 204 119 211 170 104 63 39 46 68 150 123 148 95 96 95 17 133 243 35 45 66 76 19 41 200 141 120 110 215 140 230 252 182 42 166 59 249 171 97 124 8 138 59 112 191 87 170 218 31 51 74 112 23 37 13 63 96 61 200 110 189 59 18 11 99 94 63 245 107 31 11 217 51 133 35 113 36 154 179 223 92 31 239 20 51 200 102 133 183 240 88 104 29 81 122 28 246 161 90 89 6 241 241 19 40 43 248 78 6 234 40 171 23 143 70 122 246 180 148 183 67 158 198 212 41 0 98 171 81 122 114 229 193 213 212 65 72 120 191 228 32 132 172 88 100 104 119 253 166 159 242 246 6 66 190 31 57 175 105 161 1 109 8 1 50 97 60 101 25 131 93 51 243 203 41 11 140 231 59 131 68 177 58 80 142 9 21 20 106 132 161 187 21 253 234 222 190 91 106 192 149 4 70 77 139 170 172]
distinct = 156
我希望item_at和item_index这两个方法都能处理256字节的列表，而不是字符串或整数。
详细信息：
对于item_at，将提供一个256字节的列表l256b作为index，对于distinct(所提供的l256b中存在不同字节的数量(，该方法的用户将提供值0<=x<256
不需要参数alphabet和length，因为它们始终是常数，并且对于alphabet是字节0<=x<256，对于length是字节256item_at必须返回一个256字节的列表，这是所提供索引的排列。
对于item_index，将提供256个字节的列表l256b作为item(排列(，并且对于distinct(所提供的l256b中存在不同字节的数量(，方法的用户将提供0<=d<256之间的值
不需要参数alphabet和length，因为它们始终是常数，并且对于alphabet是字节0<=x<256，对于length是字节256item_index必须返回一个256字节的列表，这是所提供排列的索引。
1-处理列表
有两个细节，一个是该解决方案是为处理字符串而设计的，但它可以很容易地修改为处理列表
2-仅跟踪前缀的计数
该代码正在使用构造整个前缀，从而在每次调用时对其进行扩展，这将导致重要的复制。在函数item_index中，该前缀仅用于知道是否使用了给定符号。相反，可以做的是有一个字典，每个符号的前缀都有数字。然后使用prefixCount[d] != 0而不是检查d in prefix。
3-调整缓存大小
您可以看到，该解决方案使用LRU缓存，默认情况下，这种类型的缓存将只存储128个最新的元素。如果您知道输入的最大长度是256，那么使用lru_cache(maxsize=256**2)就足够了，您可以用lru_cache(maxsize=None)或简单的cache()来装饰函数。
@lru_cache(maxsize=256**2)
def count_seq(n_symbols, length, distinct, used=0):
if distinct < 0:
return 0
if length == 0:
return 1 if distinct == 0 else 0
else:
return
count_seq(n_symbols, length-1, distinct-0, used+0) * used +
count_seq(n_symbols, length-1, distinct-1, used+1) * (n_symbols - used)
def item_at(idx, alphabet, length, distinct, used=0, prefix=None):
if prefix is None:
prefix = [];
if distinct < 0:
return
if length == 0:
return prefix
else:
for d in alphabet:
if d in prefix:
branch_count = count_seq(len(alphabet),
length-1, distinct, used)
if branch_count <= idx:
idx -= branch_count
else:
prefix.append(d);
return item_at(idx, alphabet,
length-1, distinct, used, prefix)
else:
branch_count = count_seq(len(alphabet),
length-1, distinct-1, used+1)
if branch_count <= idx:
idx -= branch_count
else:
prefix.append(d);
return item_at(idx, alphabet,
length-1, distinct-1, used+1, prefix)
def item_index(item, alphabet, length, distinct, used=0, prefixCount=None, idx=0):
if prefixCount is None:
prefixCount = {a: 0 for a in alphabet}
if distinct < 0:
return 0
if length == 0:
return 0
else:
offset = 0
for d in alphabet:
if prefixCount[d] != 0:
if d == item[idx]:
prefixCount[d] += 1
return offset + item_index(item, alphabet,
length-1, distinct, used, prefixCount, idx+1)
else:
offset += count_seq(len(alphabet),
length-1, distinct, used)
else:
if d == item[idx]:
prefixCount[d] += 1;
return offset + item_index(item, alphabet,
length-1, distinct-1, used+1, prefixCount, idx+1)
else:
offset += count_seq(len(alphabet),
length-1, distinct-1, used+1)
然后它将在现代计算机中运行几毫秒
迭代实施
我正在写一个类，你将实例化它，给出你想要的字母表和不同符号的数量，在这种情况下，distinct + used在所有递归中都是不变的。在矩阵CCD_ 35中预先计算了CCD_。方法CCD_ 36和CCD_ 37是基于CCD_。
在我看来，这变得不那么可读了，因为在递归实现中，一切都是用具有明确概念关联的函数调用来表示的。
class SequenceLookup:
def __init__(self, alphabet, length, distinct):
self.alphabet = list(alphabet)
self.distinct = distinct
n_symbols = len(alphabet)
c = [0] * distinct + [1, 0]
C = [c]
for l in range(2,length+1):
c = [
c[d] * d + c[d+1] * (n_symbols - d)
for d in range(distinct+1)
] + [0]
C.append(c)
self.C = C
def item_index(self, item):
length = len(item)
offset = 0
seen = set()
for i,di in enumerate(item):
for d in self.alphabet:
if d == di:
break;
if d in seen:
offset += self.C[length-1-i][len(seen)]
else:
offset += self.C[length-1-i][len(seen)+1]
seen.add(di)
return offset
def item_at(self, idx, length):
seen = set()
prefix = []
for i in range(length):
for d in self.alphabet:
if d in prefix:
branch_count = self.C[length-1-i][len(seen)]
else:
branch_count = self.C[length-1-i][len(seen)+1]
if branch_count <= idx:
idx -= branch_count
else:
prefix.append(d)
seen.add(d)
break
return prefix
bytez=[197, 215, 20, 156, 94, 67, 20, 100, 27, 208, 186, 248,
71, 48, 128, 75, 7, 165, 148, 223, 94, 163, 233, 15,
161, 104, 246, 66, 242, 142, 118, 165, 204, 0, 252,
22, 233, 28, 136, 197, 113, 122, 72, 229, 11, 91, 133,
142, 20, 204, 119, 211, 170, 104, 63, 39, 46, 68, 150,
123, 148, 95, 96, 95, 17, 133, 243, 35, 45, 66, 76, 19,
41, 200, 141, 120, 110, 215, 140, 230, 252, 182, 42,
166, 59, 249, 171, 97, 124, 8, 138, 59, 112, 191, 87,
170, 218, 31, 51, 74, 112, 23, 37, 13, 63, 96, 61, 200,
110, 189, 59, 18, 11, 99, 94, 63, 245, 107, 31, 11,
217, 51, 133, 35, 113, 36, 154, 179, 223, 92, 31, 239,
20, 51, 200, 102, 133, 183, 240, 88, 104, 29, 81, 122,
28, 246, 161, 90, 89, 6, 241, 241, 19, 40, 43, 248, 78,
6, 234, 40, 171, 23, 143, 70, 122, 246, 180, 148, 183,
67, 158, 198, 212, 41, 0, 98, 171, 81, 122, 114, 229,
193, 213, 212, 65, 72, 120, 191, 228, 32, 132, 172, 88,
100, 104, 119, 253, 166, 159, 242, 246, 6, 66, 190, 31,
57, 175, 105, 161, 1, 109, 8, 1, 50, 97, 60, 101, 25,
131, 93, 51, 243, 203, 41, 11, 140, 231, 59, 131, 68,
177, 58, 80, 142, 9, 21, 20, 106, 132, 161, 187, 21, 253,
234, 222, 190, 91, 106, 192, 149, 4, 70, 77, 139, 170, 172]
v = SequenceLookup(range(256), len(bytez), len(set(bytez)))
%%timeit
v = SequenceLookup(range(256), len(bytez), len(set(bytez)))
11.4 ms ± 229 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
#%%timeit
v.item_index(bytez)
7.57 ms ± 132 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
#%%timeit
v.item_at(t, 256)
33.6 ms ± 598 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
专用于字节
一种使用固定字母[0,..255]的实现
class SequenceLookup:
def __init__(self, length, distinct):
self.distinct = distinct
c = [0] * distinct + [1, 0]
C = [c]
for l in range(2,length+1):
c = [
c[d] * d + c[d+1] * (256 - d)
for d in range(distinct+1)
] + [0]
C.append(c)
self.C = C
def item_index(self, item):
length = len(item)
offset = 0
seen = set()
for i,di in enumerate(item):
for d in range(256):
if d == di:
break;
if d in seen:
offset += self.C[length-1-i][len(seen)]
else:
offset += self.C[length-1-i][len(seen)+1]
seen.add(di)
return offset
def item_at(self, idx, length):
seen = [0] * 256
prefix = [0] * length
used = 0
for i in range(length):
for d in range(256):
if seen[d] != 0:
branch_count = self.C[length-1-i][used]
else:
branch_count = self.C[length-1-i][used+1]
if branch_count <= idx:
idx -= branch_count
else:
prefix[i] = d;
if seen[d] == 0:
used += 1;
seen[d] = 1
break
return prefix
使用这种实现结构和item_index基本上需要相同的时间，但item_at在我的测试中运行得更快
6.32 ms ± 91.7 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
这当然会有所不同，所以你可能想自己用不同的数据结构尝试相同的算法。