小编Eci*_*ana的帖子

最近我看到一篇关于使用SAT解决难题的Reddit文章[1].这让我对这个"SAT"的事情非常好奇.我阅读了维基百科的文章,但我想请你们中的某些人以更多的外行术语为我解释.

什么是SAT,它有什么用？它可以用于遍历树结构吗？用于解析文本？换线[2]？对于垃圾箱包装[3]？这是一种优化技术吗？

在相关的说明中,我读到NP与P是关于选择哪个数字的集合为零而不是检查某些数字是否总和为零 - SAT是否与此相关？

[1] http://www.reddit.com/r/programming/comments/pxpzd/solving_hexiom_really_fast_with_a_sat_solver/

[2] http://en.wikipedia.org/wiki/Line_wrap

[3] http://en.wikipedia.org/wiki/Bin_packing_problem

是对我上一个问题的后续跟踪: ObjC方法类型编码字符串中的数字是什么？

说有一个编码:

v24@0:4:8@12B16@20

这些数字是如何计算的？B是一个字符,所以它应该只占用1个字节(而不是4个字节).它与"对齐"有关吗？大小是void多少？

如下计算数字是否正确？询问sizeof每个项目并将结果四舍五入到4的倍数？第一个数字成为所有其他数字的总和？

我有许多简单的多边形,它们彼此不相交,但有些多边形可能嵌入到其他多边形中.

例如:

+--------------------------------------------+
|                                            |
|   +----------------+          +--------+   |
|   |                |         /         |   |
|   |   +--------+   |        /          |   |
|   |   |        |   |       /  +----(2)-+   |
|   |   |        |   |      /   |            |
|   |   +----(3)-+   |     /    |   +---+    |
|   |                |    +-----+   |   |    |
|   +------------(2)-+              +(2)+    |
|                                            |
+----------------------------------------(1)-+

如何找出所有多边形的"深度"？换句话说,如何找出多边形包含多少个多边形？"深度"是括号中的数字.

我可以计算多边形点在所有其他多边形内部的次数,但这具有二次复杂性.如何更快地计算这些深度？

我有一个文件夹A,其中包含一些Python文件和__init__.py.

如果我将整个文件夹A复制到其他文件夹B并在那里创建一个带有"import A"的文件,它就可以了.但现在我删除文件夹并移动到原始文件夹的符号链接.现在它不起作用,说"没有名为foo的模块".有谁知道如何使用符号链接进行导入？

这是我上一个问题的后续行动.我仍然觉得这是一个非常有趣的问题,因为有一种算法值得我更多关注,我在这里发布它.

来自维基百科:对于每个xi都是正的并且由相同的常数界定的情况,Pisinger找到了线性时间算法.

有一篇不同的论文似乎描述了相同的算法,但对我来说有点难以阅读,所以请 - 有谁知道如何将伪代码从第4页(balsub)转换为工作实现？

以下是我目前收集的几个指针:

http://www.diku.dk/~pisinger/95-6.ps(该文件)
/sf/answers/696693161/
http://www.diku.dk/hjemmesider/ansatte/pisinger /codes.html

PS:我并不是真的坚持这个算法,所以如果你知道任何其他类似的性能算法,请随意建议它.

编辑

这是旧版本发布的代码的Python版本:

class view(object):
    def __init__(self, sequence, start):
        self.sequence, self.start = sequence, start
    def __getitem__(self, index):
        return self.sequence[index + self.start]
    def __setitem__(self, index, value):
        self.sequence[index + self.start] = value

def balsub(w, c):
    '''A balanced algorithm for Subset-sum problem by David Pisinger
    w = weights, c = capacity of the knapsack'''
    n = len(w)
    assert n > 0
    sum_w = 0
    r …

我刚看了Siggraph 2012的一篇非常令人印象深刻的演讲:

http://nvidia.fullviewmedia.com/siggraph2012/ondemand/SS106.html

我的问题是,这是一个专有的Nvidia扩展,在GPU上快速渲染Bezier路径的其他可能性是什么？或者,作为OpenGL标准的一部分,是否有任何希望最终？是否有可能给出任何时间估计最终何时发生？

你知道处理GPU路径渲染的任何其他(最好是开源)项目吗？

编辑:现在原始论文有一个新的"附件":

https://developer.nvidia.com/sites/default/files/akamai/gamedev/files/nvpr_annex.pdf

有许多起始端对的序列.如何找到所有序列中包含的所有范围？开始和结束是整数,它们可能很远,因此制作序列的位域并且&它们是不可行的.如果有帮助,一个"行"(即一个序列)上的范围(即起始端对)不重叠.并且开始和结束都有下限和上限,我认为32位整数就足够了(即0 <=值<= 65535).

让我举一个例子:

|----------|       |---------------------|           |----------|
     |----------------------|                      |-------|
                |---------------------|                 |--|

结果应该是:

                   |--------|                           |--|

上面的例子大致如下:

row1 = (100, 200), (300, 600), (800, 900)
row2 = (140, 450), (780, 860)
row3 = (280, 580), (820, 860)
result = (300, 450), (820, 860)

另外,有没有任何已知的算法？我的意思是,这个问题有名字吗？

整数除法的硬件指令历来非常慢。例如，对于 64 位输入，Skylake 上的 DIVQ 延迟为 42-95 个周期 [1]（吞吐量倒数为 24-90）。

然而，有更新的处理器，其性能要好得多：Goldmont 具有 14-43 延迟，Ryzen 具有 14-47 延迟 [1]，M1 显然具有“每分频 2 个时钟周期的吞吐量”[2]，甚至 Raspberry Pico 也具有“8 -循环有符号/无符号除法/模电路，每个核心”（尽管这似乎适用于 32 位输入）[3]。

我的问题是，发生了什么变化？是否发明了新的算法？无论如何，新处理器采用什么算法进行除法？

[1] https://www.agner.org/optimize/#manuals
[2] https://ridiculousfish.com/blog/posts/benchmarking-libdivide-m1-avx512.html
[3] https://raspberrypi。 github.io/pico-sdk-doxygen/group__hardware__divider.html#details

我试图理解Cocoa中的东西是如何工作的,但我正在努力解决一件事.我看到http://cocoawithlove.com/2010/09/minimalist-cocoa-programming.html和http://casperbhansen.wordpress.com/2010/08/15/dev-tip-nibless-development/我想我有点了解.

现在,我想对"基于文档的应用程序"做同样的事情.请问,有没有人知道类似上面的教程或示例？或者,我需要做些什么来使它工作？我想我需要创建NSDocumentController- 但它与NSApplication有什么关系？我NSDocument从那里创造？坦率地说,我有点失落......

Bairstow的根寻找方法需要对二次因子进行非常好的初始近似以便收敛.

我尝试了各种常数,随机数,尾随系数中的分数(-a1/a2,-a0/a2;林？)无效.

请问,有没有人知道选择这些因素的好方法？

例如:

1*x^8 + 118*x^7 + 1*x^6 + 2*x^5 - 2*x^4 - 3*x^3 + 3*x^2 + 2*x + 1

找到根的初始近似值为0.1,0.2需要3倍,而0.2,2.0.

要么:

1*x^8 - 36*x^7 + 546*x^6 - 4536*x^5 + 22449*x^4 - 67284*x^3 + 118124*x^2 - 109584*x + 40320

0.1,1.2比0.1,0.1略长(~50%)

尝试使用Cauchy的边界进行初始二次近似:

R=0
for i in range(1,n+1):
    R=max(abs(a[i]/a[0]),R)
R=1+R
phi=2*pi*random()
x1=complex(R*cos(phi),R*sin(phi))
x2=complex(x1.real,-x1.imag)
r=-x1.real-x2.real
s=(x1*x2).real

不幸的是,这并没有真正加速融合.