小编Cap*_*nky的帖子

我需要对矢量执行相当复杂的检查,我必须重复数千次.为了提高效率,我将给定的公式转换为C++源代码,并在高度优化的二进制文件中进行编译,我在代码中调用它.公式总是纯粹的布尔值:只有&&,|| 而且!用过的.典型的源代码如下所示:

#include <assert.h>
#include <vector>

using DataType = std::vector<bool>;

static const char T = 1;
static const char F = 0;
const std::size_t maxidx = 300;

extern "C" bool check (const DataType& l);

bool check (const DataType& l) {
  assert (l.size() == maxidx);
  return (l[0] && l[1] && l[2]) || (l[3] && l[4] && l[5]); //etc, very large line with && and || everywhere
}

我编译如下:

g++  -std=c++11 -Ofast -march=native -fpic -c check.cpp

生成的二进制文件的性能至关重要.

它完美地利用了最近的测试用例和大量变量(300,如上所示).在这个测试用例中,g ++消耗超过100 GB的内存并永久冻结.

我的问题非常简单:如何简化编译器的代码？我应该使用一些额外的变量,摆脱矢量或其他东西？

EDIT1:好的,这是top工具的截图. …

免责声明：

所描述的问题看起来像是来自竞赛的任务。我没有参加任何比赛，我不知道任何正在进行的比赛，这可能会涉及到问题。如果有的话，我会结束这个问题以保持公平！

我有一个问题：给定一个数组 A 的值和整数 K，将 A 拆分为恰好 K 个不重叠的连续子数组，这样子数组的最小和子数组最大和之间的差异是最小的。允许在任何方向上将 A 旋转任意数量。

考虑一个例子：

输入：A = [5 1 1 1 3 2]，K = 3

输出：[5][1 1 1][3 2]，最大总和 = 5，最小总和 = 3，结果 = 2

我有部分工作代码（非常丑陋，我的坏，但这并不意味着生产质量）：

#include <climits>
#include <cstdio>
#include <cstring>

const int max_n = 50;
const int max_k = 20;

int deps[max_n];

int max (int x, int y) {
  return x > y ? x : y;
}

int min (int x, int y) {
  return x < y ? …

问题背景

大家好，我正在根据提供的查询在一堆文档中搜索相关文档的项目。由于这是一个小型项目，我有一个典型的内存架构，我假设我没有超过 100 个文档，每个文档包含不超过 1000 个单词（一个单词不超过 10 个字符）。我收到很多查询，我必须尽可能快地处理查询（绝对不超过一秒）。

我的第一种方法（幼稚且不可扩展）：

由于允许用户上传文档，每当我收到文档时，我都会查找“潜在”关键字并将关键字存储为键，将文档存储为值对或存储在 MYSQL 表中。显然，这必须手动完成，看起来不像程序员会做的。

我的第二种方法（稍微好一点）：

我获取每个文档，扫描其中的每个单词并将这个单词添加到 Trie 数据结构中，因此对于 100 个文档，我必须搜索 100 次尝试，如果查询的长度为 l，则这种方法将采用最坏的 O（单词数）跨所有文档*最大单词的长度）以构建特里树并查询 O（查询长度）。这是很合理的。为了实现这一点，我将在每个文档中保留一个 Trie 根节点向量，并迭代每个 trie 节点并在每个 trie 中搜索。如果我得到至少一半的查询词匹配，我就会将该文档存储为潜在结果。结果，我不会提供超过一些截止数量的文件。

我对社区的问题：

我会问你如何看待我的方法？我如何优化它们，我可以在现有方法中做哪些其他改进？通过使用其他算法或数据结构可以更有效地完成这项工作吗？在网上冲浪时，我遇到了像 Boyer-Moore 和 Aho-Corasick 这样的算法，以及一些调整 Lucene Apache 实现的算法等的建议。你在这里有什么建议？