压缩正弦波表

Question

我有一个很大的数组，里面有1024个条目，每个条目的值在range(14, 86)这个范围内，也就是每个值都是14到85之间的数字。

这意味着在这个数组中，有很多索引位置的值是相同的。

举个例子，

consider the index range 741 to 795. It maps to 14
consider the index range 721 to 740. It maps to 15
consider the index range 796 to 815. It maps to 15

我想把这个数组传给一个Python程序，然后它会输出以下内容：

if((index >= 741) and (index <= 795)) return 14;
if((index >= 721) and (index <= 740)) return 15;
if((index >= 796) and (index <= 815)) return 15;

我已经准备好了一些代码，可以用来groupby这些映射的值，但我在用pairwise写表达式时遇到了一些困难。

有没有人之前做过类似的事情？

我已经把数据集上传成两种形式：

常规形式，按索引排序。

按映射值分组。

Answer 1

如果你不介意因为四舍五入而导致的稍微不同的数值，我可以帮你把这个压缩得非常好。

from math import pi, sin
interval=2*pi/1024
sinval=lambda i:int(round(sin(i*interval)*36))+50

这里有一段代码可以实现你想要的功能；它适用于

vals = sorted((sinval(i), i) for i in range(1024))

作为测试数据。如果你的索引在第一列，你需要在这里的for循环中交换val和index的顺序。

ranges, oldval, oldidx = [[0, 0]], 0, 0
for val, index in vals:
    if not (val == oldval and index == oldidx + 1):
        ranges[-1].append(oldidx)
        ranges.append([val, index])
    oldval, oldidx = val, index
ranges[-1].append(oldidx)
ranges.pop(0)
ifs = ('if((index >= {1}) and (index <= {2})) return {0};\n'.format(val, start, end)
            for val, start, end in ranges)
print ''.join(ifs)

编辑：哎呀，我漏掉了一行。已经修好了。另外，你的乘数其实是36而不是35，我可能在脑子里把(14, 86)四舍五入成了(15, 85)。

编辑2：接下来我会告诉你如何只存储表格的四分之一。

from math import pi, sin

full = 1024
half = 512
quarter = 256
mag = 72
offset = 50

interval = 2 * pi / full

def sinval(i):
    return int(round(sin(i * interval) * (mag // 2))) + offset

vals = [sinval(i) for i in range(quarter)]

def sintable(i):
    if  i >= half + quarter:
        return 2 * offset - vals[full - i - 1]
    elif  i >= half:
        return 2 * offset - vals[i - half]
    elif i >= quarter:
        return vals[half - i - 1]
    else:
        return vals[i]

for i in range(full):
    assert -1 <= sinval(i) - sintable(i) <= 1

如果你想从表格中减去偏移量，只需把前两个-vals[...]改成这样就可以了。

另外，底部的比较有点模糊，因为我在这方面有72个越界错误。这是因为你的数值被四舍五入成了整数；它们都是在两个值之间的中间位置，所以准确度几乎没有下降。

Answer 2

在我关闭这个问题后，我才发现了这个解决方案，链接是“用什么方法在列表中识别连续重复项最符合Python风格？”。

---

注意：对于像正弦这样的周期性函数，你只需要存储四分之一（也就是256个值）或一半的表格，然后在查找时对索引进行一些简单的（定点）运算。正如我所评论的，如果你进一步不存储偏移量+50，你就可以少用一位，但在查找后需要多加一个整数。因此，79%的压缩是很容易实现的。使用RLE（游程编码）可以得到更多的压缩。即使函数有噪声，你仍然可以通过这种通用方法获得不错的压缩效果。

正如agf指出的，你的f(n) = 50 + 36*sin(72*pi*n/1024)可以写成50 + g(n)。

所以只需要为范围n=0到255计算g(n) = 36*sin(72*pi*n/1024)的256个值。

然后可以很容易地计算出f(n)：

if 0 <= n < 256, f(n) = 50 + g(n)
if 256 <= n < 512, f(n) = 50 + g(511-n)
if 512 <= n < 768, f(n) = 50 - g(n-512)
if 768 <= n < 1024, f(n) = 50 - g(1023-n)

---

总之，这里有一个通用的表格压缩解决方案，可以生成(istart,iend,value)三元组。

我花了很多时间想怎么用列表推导和itertools.takewhile()更符合Python风格地实现这个；还需要进一步打磨。

#import itertools

table_="""
    0       50
    1       50
    ...
    1021    49
    1022    50
    1023    50""".split()

# Convert values to int. Throw away the indices - will recover them with enumerate()
table = [int(x) for x in table_[1::2]]

compressed_table = []
istart = 0
for i,v in enumerate(table):
    if v != table[i-1]:
        iend = i-1
        compressed_table.append((istart,iend,table[i-1]))
        istart = i
    else:
        continue # skip identical values
# Slightly ugly: append the last value, when the iterator was exhausted
compressed_table.append((istart,i,table[i]))

（注意，我在agf改变他的方法之前就开始了表格压缩的尝试……当时想用itertools或列表推导来解决这个问题）