全部问题

面对这样一个事实，即维基百科定义的质量还有很多不足之处。是的，有很多文字，但形式化并不完整和准确。从字面上看，符文的其余部分是空的。也就是说，来自同一个维基百科的数百个复制粘贴站点。搜索有关编程和算法的书籍（特别是）也没有返回任何结果。要么根本没有定义，要么断章取义，要么翻译质量和编辑的工作太离谱，难以把握意思。

我决定自己正式确定它们之间的差异。我意识到我一个人无法应付。我已经做了一些事情，也许在你的帮助下，可以填补定义中的空白，用波浪号表示。

如果您可以更好地制定公式，请给出确定性和非确定性算法的定义（stochastic，已经有最完整的定义，同时不是一个大的但可以理解的定义）。

分支算法包括：

• 行为完全取决于输入数据的算法称为确定性|deterministic|。他走的每一步都是预先确定的。～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～ ~~~~~~~~~~
  因此，处理相同的输入总是会导致相同的结果。

• 无法预测行为（它依赖于什么？）的算法称为非确定性|非确定性|。
  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  _和不同的结果。

有时，问题的解决方案归结为使用随机变量。

• 除输入数据外，其行为由随机（伪随机）数生成器的值确定的算法称为随机| randomized|

除了维基百科之外，真的没有人能够给出这些概念的定义吗？原则上，这些概念是编程的基础？有合适的书吗？总得来说很奇怪，那么多人受过高等教育，教授难道真的不给学生这么基本的定义吗？

是否可以以编程方式禁用 Windows Defender？

我正在尝试创建一个动画六边形菜单。

请看图更好地理解：

六边形形式的汉堡按钮位于中间。
单击它会显示围绕汉堡按钮的三角形。
汉堡图标变成了一个十字，所以当你再次点击它时，一切都会回到原来的位置。
我的解释性图片实际上在一开始就缺少一步。图像的左半部分应该只显示汉堡按钮。

所以我的问题是：

如何使用 HTML、CSS通过jQuery或以其他方式从六边形创建此动画。

你会用什么方法来做到这一点？

_{@Julian Livin 在中国免费翻译CSS 动画六边形菜单问题。}

我遇到了一件有趣的事情——一种字体，你写一个单词而不是一个图标，它显示为一个图标。我不知道它是如何在这里完成的，但我知道的唯一方法是使用字体中的连字。

我对这种方法的跨浏览器兼容性很感兴趣。

.material-icons.material-icons {
  font-size: 10rem;
}

<link href="https://fonts.googleapis.com/icon?family=Material+Icons" rel="stylesheet">
<i class="material-icons">home</i>

我面临着反转 4 个任意字节的 md5 哈希的任务。也就是说，换句话说，我需要从 1 个方法编写服务 - 该方法在输入处接收 16 个字节的散列并在输出处返回 4 个字节。

因为，据我所知，单独反转散列是不可行的，所以我决定另辟蹊径，为所有可能的值生成散列。我已经隔离了一个实体，我们称之为它запись，它由 16 个字节的哈希（我们称之为ключ）和 4 个字节的值组成。由于值是4字节~4mld，那么我得到4mld记录，每20字节大小为80GB数据。

作为第一个近似值，我生成了 80 个 gig，分为排序的段（每个段是一个单独的文件），并根据合并排序原则实现文件的合并。因此，最后，我将得到一个 80 gig 的大文件，其中将有 4 条按 key 排序的 mld 记录。我计划为这么大的文件创建第二个文件 - 一个可以轻松放入 RAM 的索引文件。之后，通过键搜索记录看起来就像在大文件上进行二分搜索，需要一点索引文件的帮助。搜索时间通常应该是对数的，限制为最多 32 跳。

该解决方案的优点：

• 易于部署。我刚刚部署了服务，等待初始化，一切正常。

缺点：

• 生成文件需要很长时间。时间以小时为单位。
• 生成的数据占用大量空间 - 80 gig

基于这些缺点，我提出了一些想法：

• 首先，当然是将数据存储在数据库中。它们立即被索引并在那里压缩。我已经尝试过 MongoDB 和 SQL Server，但是两个插入都很慢，以至于我厌倦了等待，而且它们显然比生成文件要慢。也就是说，我不想为了 1 服务而设置数据库服务，事实证明这对我没有多大帮助。

• 第二个是试图弄清楚如何最好地压缩数据。老实说，哈希压缩在我看来并不是什么基本的东西，它也无法压缩值，因为在那里使用了完整的值集。有一个想法是将一个大文件拆分为类似 trie 的文件 - 然后每个 trie 级别将为我节省大约 4 GB + 省略值中无关紧要的零 \u200b\u200b（但这会使搜索变得非常复杂）

在我的情况下选择最具体的问题对我来说是相当困难的，但我会尝试：是否有更普遍接受的方法来解决这样的问题？我有一种强烈的感觉，我做错了什么。

UPD所以，让我总结一下目前的结果。

已经尝试了几种方法。

1. 我的原始版本是将所有 16 字节的哈希值连同初始 ID 一起生成到一个文件中，然后在文件中查找哈希值。

生成时间：大约3-4小时。搜索速度：未测试。内存 - 80GB

2. 第二种方法是即使前 4 个字节取自 16 字节散列，也很少有冲突。因此，可以生成一个大 ID 文件（按哈希排序）+一个小索引文件。搜索看起来像这样：我们得到传入的哈希，从中取出前 3 个字节，在索引文件中的这个地址（也可以加载到内存中）是大文件中的初始偏移量。使用这个偏移量，我们读取了 400 个 ID——其中一个就是我们正在寻找的那个。我们统计 400 个哈希，找到需要的 id，返回结果。

生成时间：大约 2 小时（还没有做任何优化）。索引文件 - 70mb，ID 文件 - 16gb。搜索速度：大约每秒 75-100 个请求。

3. 第三种方法是生成散列链。该方法的本质是哈希链只能由初始值和最终值表示。对于我的任务，它看起来像这样：

我们取一个 4 字节的 id，从中生成一个散列H（我们取前 4 个字节），我们得到类似id->H. 散列是 4 个字节，这意味着某处有这样的id，所以我可以从散列中获取散列并构建一个像 id->H1->H2->Hn. 只有链的开头和结尾可以写入文件。开始是需要恢复链，结束是通过哈希搜索一个值。

搜索本身看起来像这样：在输入处我们有一个 hash h。我们正在寻找一个有结束的链h- 如果我们找到它，然后我们恢复链，它包含所需的id. 如果没有这样的链，那么我们从我们的 hash 中获取一个 hash h1，并寻找一个带有 end 的链h1。所以我们重复，直到有一条链。

该方法有几个优点 - 似乎您可以将数据表示为一组长链（仅在内存中保留开头和结尾）。第一个问题在于“长”这个词。我将进一步解释。

所以缺点：

• 显然，如果一条链遇到id已经在另一个链中的链，那么这些链将开始复制信息。

它看起来像这样：

id1->H1->H2->H3->H4
id2->H5->H1->H2->H3

如您所见，如果您保持链的长度不变（这将增加文件生成时间），则会出现重复信息。

• 为了消除重复，我在内存中分配了 2 ^ 32 位 (~ 500 mb)，并标记了已处理的 ID。因此，1 个 ID 仅在 1 个链中。然后链条长度的问题浮出水面。底线是，为了使链真正长且有用，其中所有生成的哈希值必须等于那些尚未处理的 ID。当您开始计算这些链条时（我数了链条，直到遇到一个已经处理过的链条id），它们的平均长度为 200 节。但这个数字正在迅速减少。

举个例子：假设10%所有的ID都已经处理完毕，正在生成一条新的链。假设散列函数具有均匀分布，那么第一个散列是id尚未处理的散列的可能性为0,9. 第二个哈希是 -0,9*0,9=0,81的可能性，依此类推，以及链中至少有10应用元素的可能性0.35。这是处理的时候10%。处理后，链80%中至少有2元素（不包括第一个元素id）的机会是0,64. 处理时99%——人们可能会说，长链的机会不存在，典型的链将由初始链id及其散列组成。这也是我学到的。

总共生成时间大约一个小时，文件大小为16GB。我什至没有尝试测试搜索速度。

4. 第四种方法是彩虹表（感谢@AlexanderPetrov 的提示）。

彩虹表本质上是哈希链的一种变体。与链的不同之处在于，这里使用散列函数与使用不同的函数（归约函数）交替使用。我举个例子：

id -> H1=H(id) -> H2=R1(H1) -> H3=H(H2) -> H4=R2(H3) -> H5=H(H4)

该示例显示散列函数与不同的归约函数交错。这种方法的优点是，即使某个值在 2 条链中相同，也只有从链的开头开始值相同时才会出现重复，例如

id1 -> H1=H(id1) -> H2=R1(H1) -> H3=H(H2) -> H4=R2(H3) -> H5=H(H4)
id2 -> H6=H(id2) -> H7=R1(H6) -> H3=H(H7) -> H4=R2(H3) -> H5=H(H4)

但是如果这个值在链的不同位置，那么它会给出不同的结果，因为它会被不同的归约函数处理

id1 -> H1=H(id1) -> H2=R1(H1) -> H3=H(H2) -> H4=R2(H3) -> H5=H(H4)
id2 -> H6=H(id2) -> H7=R1(H6) -> H2=H(H7) -> H8=R2(H2) -> H9=H(H8)

一切似乎都很好，您可以生成任意长度的链。所以我想当我开始生成长度为 3000 个元素的链时。我很快数完了30%所有的值。我数了数可以忍受的时间50%。但是这里的规则与我在前面的例子中描述的概率论相同。想象一下，我计算95%了所有的 ID。因此，一个新的元素链3000将包含150新元素和2850那些已经计数的元素。因此，计算链的速度急剧下降，因此在每个新链中，95%元素都被认为是空的。我等了大约30 个小时，无法忍受，停止了这种疯狂 - 大约98%所有 Id 占用了大约240兆字节。但我对准确性并不满意98%，当然我需要100%。

由于引入了约简功能，id哈希搜索与之前版本的搜索略有不同。如果在之前的版本中我只是从一个哈希中取出一个哈希，那么在这里，我们需要根据传入的哈希来构建一个新的链。示例：假设有一条链

id1 -> H1=H(id1) -> H2=R1(H1) -> H3=H(H2) -> H4=R2(H3) -> H5=H(H4)

我们在入口处得到了一个哈希H1。我们没有以 结尾的链H1，因此我们考虑：

H(H1) - нет совпадений
R2(H(H1)) - нет совпадений
H(R2(H(H1))) - нет совпадений
R1(H(R2(H(H1)))) - на этом этапе результат выражения будет равен H5 элементу цепочки. 

找到链后，我们将其还原并找到所需的id. 从实践中 - 我通过哈希等待至少 1 个 id 大约 10 分钟，我没有等待。但我怀疑这与算法无关，而我只是一个杂工。我完全承认，如果您需要使用某种错误来反转哈希，那么原则上该选项是有效的。

总的来说，生成时间很长，30小时98%，98%被认为是5-6小时，文件大小为240mb。搜索速度不适用。

作为目前的结果，到目前为止，我已经确定了选项 2) - 16 gig 文件 + 索引。我怀疑这个选项将是最快的。但其他选项也一样，我不会注销。

UPD 2 发布了我的磨难的来源。第二种方法完全实现，整个生成耗时 25 分钟，一次搜索 1 个 key - 大约每秒 180 个请求，搜索来自真实程序的一组传入真实数据 - 每秒约 1000 个请求（检查 75千可用哈希）。

谢谢大家的帮助！