python - 所有(2 ^ m−2)/2个可能的分区列表方式

Question

每个样本都是一组功能（整数）。我需要通过弄清楚什么是最佳功能以及该功能的最佳分割值，将样本分为两个单独的组。所谓“最佳”，是指这样的分割，它使我在分割前的集合与左侧和右侧的熵值的加权平均值之间具有最大的熵差。我需要尝试所有（2 ^ m−2）/ 2种将这些项目划分为两个非空列表的可能方法（其中m是不同值的数量（该功能具有相同值的所有样本都作为一个组一起移动） ）

以下内容非常慢，因此我需要一种更合理/更快的方法。

sorted_by_feature是（feature_value，0_or_1）元组的列表。

same_vals = {}
            for ele in sorted_by_feature:
                if ele[0] not in same_vals:
                    same_vals[ele[0]] = [ele]
                else:
                    same_vals[ele[0]].append(ele)



            l = same_vals.keys()
            orderings = list(itertools.permutations(l))
            for ordering in orderings:

                list_tups = []
                for dic_key in ordering:
                    list_tups += same_vals[dic_key]

                left_1 = 0 
                left_0 = 0 
                right_1 = num_one
                right_0 = num_zero


                for index, tup in enumerate(list_tups):
                       #0's or #1's on the left +/- 1
                       calculate entropy on left/ right, calculate entropy drop, etc.

琐碎的细节（继续上面的代码）：

                if index == len(sorted_by_feature) -1:
                        break
                    if tup[1] == 1:
                        left_1 += 1
                        right_1 -= 1

                    if tup[1] == 0:
                        left_0 += 1
                        right_0 -= 1


                    #only calculate entropy if values to left and right of split are different


                    if list_tups[index][0] != list_tups[index+1][0]:

Answer 1

tl; dr

您正在寻求奇迹。没有编程语言可以帮助您摆脱这一障碍。使用比您正在考虑做的更好的方法！

您的解决方案具有指数级的时间复杂度

让我们假设一个完美的算法：可以在恒定的O（1）时间内为您提供新分区的算法。换句话说，无论输入什么，都可以在保证的恒定时间内生成新分区。

实际上，让我们更进一步，并假设您的算法仅受CPU限制并且在理想条件下运行。 Under ideal circumstances，高端CPU每秒可处理多达1000亿条指令。由于此算法需要O（1）的时间，因此，我们将说，哦，每个新分区的生成速度都高达千亿分之一秒。到目前为止，一切都很好？

现在，您希望它表现良好。您说您希望它能够处理大小为m的输入。您知道这意味着您需要算法的pow(2,m)次迭代-这是您需要生成的分区数，并且由于生成每种算法都需要有限的时间O（1），所以总时间仅为pow(2,m)乘以O（1）。让我们快速看一下这里的数字：


m = 20表示您花费的时间为pow(2,20) * 10 ^ -11秒= 0.00001秒。不错。
m = 40表示您花费的时间为pow(2,40) 10-11秒= 1万亿亿亿= 10秒。也不错，但请注意m = 40有多小。在庞大的数字泛滥中，40毫无意义。记住，我们假设理想条件。
m = 100表示​​10 ^ 41秒！发生了什么？


您是算法理论的受害者。简而言之，具有指数时间复杂性的解决方案-任何需要2 ^ m的时间才能完成的解决方案-都无法通过更好的编程来加速。生成或产生pow(2,m)输出总是会花费相同的时间比例。

还要注意，1000亿条指令/秒是高端台式计算机的理想选择-您的CPU还必须担心正在运行的程序以外的进程，在这种情况下，内核中断和上下文切换会占用处理时间（尤其是当您正在运行数千个系统进程（毫无疑问）。您的CPU还必须从磁盘进行读取和写入，这是I / O绑定的，并且花费的时间比您想象的要长得多。诸如Python之类的解释性语言也占用了处理时间，因为每一行都被动态转换为字节码，从而迫使额外的资源投入到该过程中。您可以立即对代码进行基准测试，我可以保证您的数字将比我上面提供的简单计算要高得多。更糟糕的是：存储2 ^ 40个排列需要1000 GB的内存。你还有那么多钱吗？ :)

切换到较低级别的语言，使用生成器等都是毫无意义的事情：它们不是主要的瓶颈，而这仅仅是生成所有分区的brute force approach的巨大且不合理的时间复杂性。

您可以做什么


使用更好的算法。生成pow(2,m)分区并对所有分区进行调查是不切实际的雄心。您想考虑使用dynamic programming approach。与其仅遍历可能的分区的整个空间，不如只考虑遍历减少的最佳解决方案的空间。这就是动态编程为您所做的。它在一个类似于以下问题的示例中起作用：unique integer partitioning。
动态编程问题方法在可以表述为线性有向无环图的问题上效果最佳（如果不确定我的意思，请谷歌搜索！）。
如果没有动态方法，请考虑投资parallel processing with a GPU。您的计算机已经具有GPU-这是系统用来渲染图形的GPU-并且GPU能够并行执行大量计算。并行计算是一种计算，其中不同的工作人员可以同时执行同一计算的不同部分-然后可以将最终结果重新合并在一起。如果您能找到一种将其分解为一系列并行计算的方法-我认为有充分的理由建议您这样做-there are good tools for GPU interfacing in Python。


其他技巧


明确说明您的意思是什么。如果您可以提供有关最佳方法的更多信息，那么Stack Overflow的合作伙伴可能会提供更多帮助，并为您编写这样的算法。
在一般情况下，使用裸机编译语言可能有助于减少解决方案占用的实时时间，但是这种情况下的差异将很小。当您必须进行诸如高效搜索数组之类的操作时，编译语言会很有用，因为每次迭代都没有指令编译开销。在生成新分区时，它们并不是那么有用，因为这并不是消除动态字节码生成障碍的真正影响。