我试图解决以下问题:正在将数字插入容器中.每次插入一个数字时,我都需要知道容器中有多少元素大于或等于当前插入的数字.我相信这两个操作都可以以对数复杂度完成.
我的问题:
C++库中是否有可以解决问题的标准容器？我知道std::multiset可以在对数时间插入元素,但是如何查询呢？或者我应该实现一个数据结构(从二叉搜索树)来解决它？
用于插入和搜索的trie数据结构的最佳/最差/平均情况复杂度(以Big-O表示法)是多少？
我认为这适用O(K)于所有情况,其中K是插入或搜索的任意字符串的长度.有人会证实吗？
我有一个工作正则表达式来解析PinYin,它匹配每个有效的PinYin并且与无效的PinYin不匹配.我想知道如何优化它.
^(?P<initial>ch|zh|sh|r|c|b|d|g|f|h|k|j|m|l|n|q|p|s|t|w|y|x|z|)
(?P<final>
(?:(?<=ch)uang|(?<=ch)ang|(?<=ch)eng|(?<=ch)ong|(?<=ch)uai|(?<=ch)uan|(?<=ch)ai|(?<=ch)an|(?<=ch)ao|(?<=ch)en|(?<=ch)ou|(?<=ch)ua|(?<=ch)ui|(?<=ch)un|(?<=ch)uo|(?<=ch)a|(?<=ch)e|(?<=ch)i|(?<=ch)u)
|(?:(?<=zh)uang|(?<=zh)ang|(?<=zh)eng|(?<=zh)ong|(?<=zh)uai|(?<=zh)uan|(?<=zh)ai|(?<=zh)an|(?<=zh)ao|(?<=zh)ei|(?<=zh)en|(?<=zh)ou|(?<=zh)ua|(?<=zh)ui|(?<=zh)un|(?<=zh)uo|(?<=zh)a|(?<=zh)e|(?<=zh)i|(?<=zh)u)
|(?:(?<=sh)uang|(?<=sh)ang|(?<=sh)eng|(?<=sh)uai|(?<=sh)uan|(?<=sh)ai|(?<=sh)an|(?<=sh)ao|(?<=sh)ei|(?<=sh)en|(?<=sh)ou|(?<=sh)ua|(?<=sh)ui|(?<=sh)un|(?<=sh)uo|(?<=sh)a|(?<=sh)e|(?<=sh)i|(?<=sh)u)
|(?:(?<=c)ang|(?<=c)eng|(?<=c)ong|(?<=c)uan|(?<=c)ai|(?<=c)an|(?<=c)ao|(?<=c)en|(?<=c)ou|(?<=c)ui|(?<=c)un|(?<=c)uo|(?<=c)a|(?<=c)e|(?<=c)i|(?<=c)u)
|(?:(?<=b)ang|(?<=b)eng|(?<=b)ian|(?<=b)iao|(?<=b)ing|(?<=b)ai|(?<=b)an|(?<=b)ao|(?<=b)ei|(?<=b)en|(?<=b)ie|(?<=b)in|(?<=b)a|(?<=b)i|(?<=b)o|(?<=b)u)
|(?:(?<=d)ang|(?<=d)eng|(?<=d)ian|(?<=d)iao|(?<=d)ing|(?<=d)ong|(?<=d)uan|(?<=d)ai|(?<=d)an|(?<=d)ao|(?<=d)ei|(?<=d)en|(?<=d)ia|(?<=d)ie|(?<=d)iu|(?<=d)ou|(?<=d)ui|(?<=d)un|(?<=d)uo|(?<=d)a|(?<=d)e|(?<=d)i|(?<=d)u)
|(?:(?<!r|c|b|d|g|f|h|k|j|m|l|n|q|p|s|t|w|y|x|z)a|(?<!r|c|b|d|g|f|h|k|j|m|l|n|q|p|s|t|w|y|x|z)ai
|(?<!r|c|b|d|g|f|h|k|j|m|l|n|q|p|s|t|w|y|x|z)an|(?<!r|c|b|d|g|f|h|k|j|m|l|n|q|p|s|t|w|y|x|z)ang
|(?<!r|c|b|d|g|f|h|k|j|m|l|n|q|p|s|t|w|y|x|z)ao|(?<!r|c|b|d|g|f|h|k|j|m|l|n|q|p|s|t|w|y|x|z)e
以上是为了便于阅读的缩写版本.整个表达可以在这篇文章的最后找到.
我特别想知道是否将两个或多个前缀传递给结束匹配器可以提高性能:
(<=ch|zh|sh)uang|(<=ch|zh|sh)ang...
感谢您的时间和建议.
整个正则表达式:
^(?P<initial>ch|zh|sh|r|c|b|d|g|f|h|k|j|m|l|n|q|p|s|t|w|y|x|z|)(?P<final>(?:(?<=ch)uang|(?<=ch)ang|(?<=ch)eng|(?<=ch)ong|(?<=ch)uai|(?<=ch)uan|(?<=ch)ai|(?<=ch)an|(?<=ch)ao|(?<=ch)en|(?<=ch)ou|(?<=ch)ua|(?<=ch)ui|(?<=ch)un|(?<=ch)uo|(?<=ch)a|(?<=ch)e|(?<=ch)i|(?<=ch)u)|(?:(?<=zh)uang|(?<=zh)ang|(?<=zh)eng|(?<=zh)ong|(?<=zh)uai|(?<=zh)uan|(?<=zh)ai|(?<=zh)an|(?<=zh)ao|(?<=zh)ei|(?<=zh)en|(?<=zh)ou|(?<=zh)ua|(?<=zh)ui|(?<=zh)un|(?<=zh)uo|(?<=zh)a|(?<=zh)e|(?<=zh)i|(?<=zh)u)|(?:(?<=sh)uang|(?<=sh)ang|(?<=sh)eng|(?<=sh)uai|(?<=sh)uan|(?<=sh)ai|(?<=sh)an|(?<=sh)ao|(?<=sh)ei|(?<=sh)en|(?<=sh)ou|(?<=sh)ua|(?<=sh)ui|(?<=sh)un|(?<=sh)uo|(?<=sh)a|(?<=sh)e|(?<=sh)i|(?<=sh)u)|(?:(?<=c)ang|(?<=c)eng|(?<=c)ong|(?<=c)uan|(?<=c)ai|(?<=c)an|(?<=c)ao|(?<=c)en|(?<=c)ou|(?<=c)ui|(?<=c)un|(?<=c)uo|(?<=c)a|(?<=c)e|(?<=c)i|(?<=c)u)|(?:(?<=b)ang|(?<=b)eng|(?<=b)ian|(?<=b)iao|(?<=b)ing|(?<=b)ai|(?<=b)an|(?<=b)ao|(?<=b)ei|(?<=b)en|(?<=b)ie|(?<=b)in|(?<=b)a|(?<=b)i|(?<=b)o|(?<=b)u)|(?:(?<=d)ang|(?<=d)eng|(?<=d)ian|(?<=d)iao|(?<=d)ing|(?<=d)ong|(?<=d)uan|(?<=d)ai|(?<=d)an|(?<=d)ao|(?<=d)ei|(?<=d)en|(?<=d)ia|(?<=d)ie|(?<=d)iu|(?<=d)ou|(?<=d)ui|(?<=d)un|(?<=d)uo|(?<=d)a|(?<=d)e|(?<=d)i|(?<=d)u)|(?:(?<=g)uang|(?<=g)ang|(?<=g)eng|(?<=g)ong|(?<=g)uai|(?<=g)uan|(?<=g)ai|(?<=g)an|(?<=g)ao|(?<=g)ei|(?<=g)en|(?<=g)ou|(?<=g)ua|(?<=g)ui|(?<=g)un|(?<=g)uo|(?<=g)a|(?<=g)e|(?<=g)u)|(?:(?<=f)ang|(?<=f)eng|(?<=f)iao|(?<=f)an|(?<=f)ei|(?<=f)en|(?<=f)ou|(?<=f)a|(?<=f)o|(?<=f)u)|(?:(?<!sh|ch|zh)(?<=h)uang|(?<!sh|ch|zh)(?<=h)ang|(?<!sh|ch|zh)(?<=h)eng|(?<!sh|ch|zh)(?<=h)ong|(?<!sh|ch|zh)(?<=h)uai|(?<!sh|ch|zh)(?<=h)uan|(?<!sh|ch|zh)(?<=h)ai|(?<!sh|ch|zh)(?<=h)an|(?<!sh|ch|zh)(?<=h)ao|(?<!sh|ch|zh)(?<=h)ei|(?<!sh|ch|zh)(?<=h)en|(?<!sh|ch|zh)(?<=h)ou|(?<!sh|ch|zh)(?<=h)ua|(?<!sh|ch|zh)(?<=h)ui|(?<!sh|ch|zh)(?<=h)un|(?<!sh|ch|zh)(?<=h)uo|(?<!sh|ch|zh)(?<=h)a|(?<!sh|ch|zh)(?<=h)e|(?<!sh|ch|zh)(?<=h)u)|(?:(?<=k)uang|(?<=k)ang|(?<=k)eng|(?<=k)ong|(?<=k)uai|(?<=k)uan|(?<=k)ai|(?<=k)an|(?<=k)ao|(?<=k)en|(?<=k)ou|(?<=k)ua|(?<=k)ui|(?<=k)un|(?<=k)uo|(?<=k)a|(?<=k)e|(?<=k)u)|(?:(?<=j)iang|(?<=j)iong|(?<=j)ian|(?<=j)iao|(?<=j)ing|(?<=j)üan|(?<=j)ia|(?<=j)ie|(?<=j)in|(?<=j)iu|(?<=j)üe|(?<=j)ün|(?<=j)i|(?<=j)ü)|(?:(?<=m)ang|(?<=m)eng|(?<=m)ian|(?<=m)iao|(?<=m)ing|(?<=m)ai|(?<=m)an|(?<=m)ao|(?<=m)ei|(?<=m)en|(?<=m)ie|(?<=m)in|(?<=m)iu|(?<=m)ou|(?<=m)a|(?<=m)e|(?<=m)i|(?<=m)o|(?<=m)u)|(?:(?<=l)iang|(?<=l)ang|(?<=l)eng|(?<=l)ian|(?<=l)iao|(?<=l)ing|(?<=l)ong|(?<=l)uan|(?<=l)ai|(?<=l)an|(?<=l)ao|(?<=l)ei|(?<=l)ia|(?<=l)ie|(?<=l)in|(?<=l)iu|(?<=l)ou|(?<=l)un|(?<=l)uo|(?<=l)üe|(?<=l)a|(?<=l)e|(?<=l)i|(?<=l)o|(?<=l)u|(?<=l)ü)|(?:(?<=n)iang|(?<=n)ang|(?<=n)eng|(?<=n)ian|(?<=n)iao|(?<=n)ing|(?<=n)ong|(?<=n)uan|(?<=n)ai|(?<=n)an|(?<=n)ao|(?<=n)ei|(?<=n)en|(?<=n)ie|(?<=n)in|(?<=n)iu|(?<=n)ou|(?<=n)un|(?<=n)uo|(?<=n)üe|(?<=n)a|(?<=n)e|(?<=n)i|(?<=n)u|(?<=n)ü)|(?:(?<=q)iang|(?<=q)iong|(?<=q)ian|(?<=q)iao|(?<=q)ing|(?<=q)üan|(?<=q)ia|(?<=q)ie|(?<=q)in|(?<=q)iu|(?<=q)üe|(?<=q)ün|(?<=q)i|(?<=q)ü)|(?:(?<=p)ang|(?<=p)eng|(?<=p)ian|(?<=p)iao|(?<=p)ing|(?<=p)ai|(?<=p)an|(?<=p)ao|(?<=p)ei|(?<=p)en|(?<=p)ie|(?<=p)in|(?<=p)ou|(?<=p)a|(?<=p)i|(?<=p)o|(?<=p)u)|(?:(?<=s)ang|(?<=s)eng|(?<=s)ong|(?<=s)uan|(?<=s)ai|(?<=s)an|(?<=s)ao|(?<=s)en|(?<=s)ou|(?<=s)ui|(?<=s)un|(?<=s)uo|(?<=s)a|(?<=s)e|(?<=s)i|(?<=s)u)|(?:(?<=r)ang|(?<=r)eng|(?<=r)ong|(?<=r)uan|(?<=r)an|(?<=r)ao|(?<=r)en|(?<=r)ou|(?<=r)ua|(?<=r)ui|(?<=r)un|(?<=r)uo|(?<=r)e|(?<=r)i|(?<=r)u)|(?:(?<=t)ang|(?<=t)eng|(?<=t)ian|(?<=t)iao|(?<=t)ing|(?<=t)ong|(?<=t)uan|(?<=t)ai|(?<=t)an|(?<=t)ao|(?<=t)ei|(?<=t)ie|(?<=t)ou|(?<=t)ui|(?<=t)un|(?<=t)uo|(?<=t)a|(?<=t)e|(?<=t)i|(?<=t)u)|(?:(?<=w)ang|(?<=w)eng|(?<=w)ai|(?<=w)an|(?<=w)ei|(?<=w)en|(?<=w)a|(?<=w)o|(?<=w)u)|(?:(?<=y)ang|(?<=y)ing|(?<=y)ong|(?<=y)uan|(?<=y)ai|(?<=y)an|(?<=y)ao|(?<=y)in|(?<=y)ou|(?<=y)ue|(?<=y)un|(?<=y)a|(?<=y)e|(?<=y)e|(?<=y)i|(?<=y)o|(?<=y)u)|(?:(?<=x)iang|(?<=x)iong|(?<=x)ian|(?<=x)iao|(?<=x)ing|(?<=x)üan|(?<=x)ia|(?<=x)ie|(?<=x)in|(?<=x)iu|(?<=x)üe|(?<=x)ün|(?<=x)i|(?<=x)ü)|(?:(?<=z)ang|(?<=z)eng|(?<=z)ong|(?<=z)uan|(?<=z)ai|(?<=z)an|(?<=z)ao|(?<=z)ei|(?<=z)en|(?<=z)ou|(?<=z)ui|(?<=z)un|(?<=z)uo|(?<=z)a|(?<=z)e|(?<=z)i|(?<=z)u)|(?:(?<!r|c|b|d|g|f|h|k|j|m|l|n|q|p|s|t|w|y|x|z)a|(?<!r|c|b|d|g|f|h|k|j|m|l|n|q|p|s|t|w|y|x|z)ai|(?<!r|c|b|d|g|f|h|k|j|m|l|n|q|p|s|t|w|y|x|z)an|(?<!r|c|b|d|g|f|h|k|j|m|l|n|q|p|s|t|w|y|x|z)ang|(?<!r|c|b|d|g|f|h|k|j|m|l|n|q|p|s|t|w|y|x|z)ao|(?<!r|c|b|d|g|f|h|k|j|m|l|n|q|p|s|t|w|y|x|z)e|(?<!r|c|b|d|g|f|h|k|j|m|l|n|q|p|s|t|w|y|x|z)ei|(?<!r|c|b|d|g|f|h|k|j|m|l|n|q|p|s|t|w|y|x|z)en|(?<!r|c|b|d|g|f|h|k|j|m|l|n|q|p|s|t|w|y|x|z)eng|(?<!r|c|b|d|g|f|h|k|j|m|l|n|q|p|s|t|w|y|x|z)er|(?<!r|c|b|d|g|f|h|k|j|m|l|n|q|p|s|t|w|y|x|z)o|(?<!r|c|b|d|g|f|h|k|j|m|l|n|q|p|s|t|w|y|x|z)ou))$
我有MPICH 3.0.4我的机器(Ubuntu的12.04)上安装.我正在尝试安装一个名为Qthreads的库,我已经使用过并成功安装过(除了安装了MPICH2软件包).配置工作正常:
./configure --prefix=/usr/local/qthreads --enable-multinode --with-multinode-runtime=mpi --with-portals4=/usr/local/portals4 --with-hwloc=/usr/local/hwloc:
...
...
...
System Characteristics:
Target Style: unix
Multi-node: yes, mpi
Topology API: hwloc
Qtimer type: clock_gettime
Aligned_t size: 8 (aligned on 8 byte boundaries)
Default Stack size: 4kB
Safety/Debugging:
Sanity assert()s: no
Check alignment: no
Profiling: none
Debugging Output: no
Guard Pages: no
Speed:
Scheduler: sherwood (multiworker shepherds)
Sinc Style: donecount
Barrier Style: feb
Dictionary Style: simple
Lazy Thread IDs: yes
Pools/caches: memory, spawns
RCRTool: no …假设我们有这样的功能
void test() {return;}
这是正确的C代码吗？我只是在mingw中测试它,编译器什么也没说,同样的
void test() {return 1;}
所以我想我的编译器已经过时了.
在C/C++的特定情况下会发生什么？
编辑:
该return 1;给我一个警告.这return;是否正确？
为什么我在下面的转换之间丢失数据,即使两种类型占用相同的空间量？如果按位完成转换,x = z除非在转换过程中剥离数据,否则应该是正确的,对吗？有没有办法在不丢失数据的情况下进行两次转换(即这样x = z)？
main.cpp中:
#include <stdio.h>
#include <stdint.h>
int main() {
double x = 5.5;
uint64_t y = static_cast<uint64_t>(x);
double z = static_cast<double>(y) // Desire : z = 5.5;
printf("Size of double: %lu\nSize of uint64_t: %lu\n", sizeof(double), sizeof(uint64_t));
printf("%f\n%lu\n%f\n", x, y, z);
}
结果:
Size of double: 8
Size of uint64_t: 8
5.500000
5
5.000000
为什么我在以下代码中遇到分段错误？
struct Cell
{
cellMode mode;
bool visited;
//bool scanned;
int rowIndex;
int colIndex;
Cell *neighbours;//if using Cell neighbours[3] i am getting a compilation error
Cell()
{
neighbours = new Cell[3];//seg fault here
}
};
当我使用静态数组时,我收到以下错误
neighbours has incomplete type
我刚刚编写了一个算法,该算法在输入整数数组中找到具有最大/最小出现次数的值.我的想法是对数组进行排序(所有出现的顺序都是按顺序排列)并使用一<value:occurrences>对来为每个值存储相应的出现次数.
它应该是O(nlogn)复杂的,但我认为有一些常数乘数.我该怎么做才能提高性能？
#include <stdio.h>
#include <stdlib.h>
#include "e7_8.h"
#define N 20
/*Structure for <value, frequencies_count> pair*/
typedef struct {
int value;
int freq;
} VAL_FREQ;
void get_freq(int *v, int n, int *most_freq, int *less_freq) {
int v_i, vf_i, current_value, current_freq;
VAL_FREQ* sp = malloc(n*sizeof(VAL_FREQ));
if(sp == NULL) exit(EXIT_FAILURE);
mergesort(v,n);
vf_i = 0;
current_value = v[0];
current_freq = 1;
for(v_i=1; v_i<n+1; v_i++) {
if(v[v_i] == current_value) current_freq++;
else{
sp[vf_i].value = current_value;
sp[vf_i++].freq = current_freq;
current_value = v[v_i]; …我有以下代码:
(do
(prn "sleeping for 60 seconds")
(Thread/sleep 6000)
(prn "kicking off calendar downloads @ " (new java.util.Date))
(let [links (map #(clojure.string/split % #",") (clojure.string/split (clojure.string/replace (slurp "calendars.csv") #"\r" "") #"\n"))]
(map download links))
我注意到let评估必须是最后的,否则它不会被评估.这对我来说很困惑.尽管如此,当我在循环中实现它时,let永远不会进行评估,因为我认为recur最终会被推断出来.
(while
(do
(prn "sleeping for 60 seconds")
(Thread/sleep 60000)
(prn "kicking off calendar downloads @ " (new java.util.Date))
(let [links (map #(clojure.string/split % #",") (clojure.string/split (clojure.string/replace (slurp "calendars.csv") #"\r" "") #"\n"))]
(map download links))
))
我也希望sleep在本do节末尾,但这真的没有实际意义.
我怎样才能 …
我有以下代码:
#include <stdio.h>
typedef struct {
int* arg1;
int arg2;
} data;
int main(int argc, char** argv) {
data d;
printf("arg1: %p | arg2: %d\n", d.arg1, d.arg2);
}
输出最终d.arg1是不是NULL而且d.arg2是0.例如:
arg1: 0x7fff84b3d660 | arg2: 0
当我添加一个指向main的指针时,没有任何变化.但是,当我打印指针时:
#include <stdio.h>
typedef struct {
int* arg1;
int arg2;
} data;
int main(int argc, char** argv) {
data d;
int* test;
printf("arg1: %p | arg2: %d | test: %p\n", d.arg1, d.arg2, test);
}
输出总是导致:
arg1: (nil) | arg2: 4195264 …我有一个类似于以下内容的包装函数：
template<typename Func, typename ... Args>
void func(Func f, Args ... args) {
...
f(args...);
...
}
Func是否可以在编译时从类型中提取返回类型？
例如，用户拥有代码并按func以下方式调用：
template<typename T>
T add(const T& l, const T& r) {
return l + r;
}
int main(int argc, char** argv) {
double a = 4.5, b = 5.5;
func(add<double>, a, b);
return 0;
}
我们可以在调用中推断出func一个函数被传递给它并返回一个 吗double？我想将返回类型信息用于内部的其他内容func。
在函数或构造函数的头中分配变量的优点(如果存在的话)是什么？换句话说,以下两组代码之间的区别是什么？为什么我更喜欢一个代码？
例1:
class A {
private:
char* b;
public:
A(size_t var = 8*1024*1024) {
...
b = new char[var];
...
}
...
};
例2:
class A {
private:
char* b;
public:
A() {
const size_t var = 8*1024*1024;
...
b = new char[var];
...
}
...
};
我感谢任何建设性的意见.