假设您有一系列元素,如何选择具有重复元素的元素并将它们放入每组中并进行最少量的比较？最好是在C++中,但算法比语言更重要.对于给出{E1,E2,E3,E4,E4,E2,E6,E4,E3}的示例,我希望提取出{E2,E2},{E3,E3},{E4,E4,E4}.您将选择哪种数据结构和算法？还请包括设置数据结构的成本,例如,它是否是像std :: multimap这样的预先排序的数据结构
根据建议使事情更清楚.有一个约束:元素必须自己进行比较,以确定它们是重复的.
所以哈希不适用,因为实际上他们将比较从重元素(例如数据块)转移到轻元素(整数),并减少一些比较,但不要废除它们,最后,我们又回到了我们原来的问题,什么时候在一个碰撞桶内.
假装你有一堆潜在的GB重复文件,它们与人类所知的每个哈希算法具有相同的哈希值.现在你要发现真正的重复.
不,它不能成为现实生活中的问题(即使MD5足以为现实生活中的文件生成唯一的哈希值).但只是假装我们可以专注于寻找涉及最少量比较的数据结构+算法.
我正在做的是
代表一个STL std :: list数据结构(在那个1中)它的元素删除比例如矢量2便宜,它的插入更便宜,不需要排序.)
弹出一个元素并将其与其余元素进行比较,如果找到重复元素,则将其从列表中拉出.一旦到达列表的末尾,就会找到一组重复,如果有的话.
重复上述两个步骤,直到列表为空.
在最好的情况下它需要N-1,但是(N-1)!在更糟糕的情况下.
有什么更好的选择？
我的代码使用上面解释的方法:
// algorithm to consume the std::list container,
// supports: list<path_type>,list< pair<std::string, paths_type::const_iterater>>
template<class T>
struct consume_list
{
groups_type operator()(list<T>& l)
{
// remove spurious identicals and group the rest
// algorithm:
// 1. compare the first element with the remaining elements,
// pick out all duplicated files including the first element itself.
// 2. start over again with …我创建了一个系统,它根据全局实例的构造函数自动将函数对象(仿函数)注册到映射中.
在定义仿函数的每个cpp文件中,有一个注册器类实例的全局实例,用于将仿函数注册到单个std::map<int, std::function<...> >对象.
这是注册商类的定义:
template
<
typename map_type,
typename handler_type
>
struct registrar
{
registrar
(
map_type& map_object,
boost::uint16_t cmd_code,
const handler_type& handler
)
{
map_object.insert(std::pair<boost::uint16_t, handler_type>(cmd_code, handler));
}
};
在每个.cpp文件中.全局实例定义如下:
namespace one_way
{
static registrar <in_out_map_type, handler>
post_receiver(in_out_map_type::instance(), command, handlers());
}
如果我将所有cpp与main.cpp一起编译,那么一切正常.但是如果我将cpp文件编译成静态库并将其链接到main.cpp,则注册不起作用.
我在Windows和Ubuntu 11.10上使用VC10和GCC4.61进行了测试.两者都失败了
我发现一个线程有同样的问题,但OP没有说是否解决了.
我错过了什么吗？
编辑
感谢所有回复,包括评论.
每一个回复确实帮助我更多地思考并深入研究这种方法.经过所有的研究和试验,我终于放弃了依赖全局/静态变量进行二元边界自注册的想法,因为没有可靠的方法来保证它能够正常工作.
我最后的方法是将注册保持在一个二进制文件中.
c++ initialization global-variables static-libraries static-linking
我正在编写一个例程来使用内存映射文件比较两个文件.如果文件太大而无法一次映射.我拆分文件并逐个映射它们.例如,要映射1049MB文件,我将其分为512MB + 512MB + 25MB.
除了一件事之外,每件事情都运行良好:比较剩余部分(本例中为25MB)总是花费更多,更长的时间,尽管代码逻辑完全相同.3观察:
std::_Equal(),但这个函数主要是(分析器说100%)等待I/O和其他线程.我试过了
结果非常一致:在剩余部分和用户模式中需要花费更多时间.
我怀疑它与映射大小不是映射对齐的倍数(在我的系统上为64K)这一事实有关,但不确定如何.
下面是例程的完整代码和3G文件的时序.
谁能解释一下,谢谢？
// using memory-mapped file
template <size_t VIEW_SIZE_FACTOR>
struct is_equal_by_mmapT
{
public:
bool operator()(const path_type& p1, const path_type& p2)
{
using boost::filesystem::exists;
using boost::filesystem::file_size;
try
{
if(!(exists(p1) && exists(p2))) return false;
const size_t segment_size = mapped_file_source::alignment() * VIEW_SIZE_FACTOR;
// lanmbda
boost::function<bool(size_t, size_t)> segment_compare =
[&](size_t seg_size, size_t offset)->bool
{
using boost::iostreams::mapped_file_source;
boost::chrono::run_timer t;
mapped_file_source mf1, mf2; …我记得在某地读过一个套接字可以看作是两个独立的半双工通道.这是否意味着recv()和send()同一插座,实际上无关紧要？
谢谢.
我有一个模板课
template<class U, class V, class W>
class S
{
//... implementations
};
和类型的一些股票类型实现U,V和W:
typedef boost::mpl::vector<U0, U1> u_types;
typedef boost::mpl::vector<V0, V1, V2, V3, V4> u_types;
typedef boost::mpl::vector<W0, W1, W2, W3, W4> w_types;
我想用模板参数的所有可能组合测试类S,
typedef boost::mpl::vector<
S<U0,V0,W0>,
S<U0,V0,W1>,
// ...
S<U1,V4,W4>,
> s_types;
像这样:
boost::mpl::for_each<s_types>(test_func).
唯一的问题是有2**5**5 = 50种组合,我不希望逐个输入.
有没有办法s_types用Boost :: mpl或Boost.Preprocessor 生成所有组合()？
谢谢.
添加了我最初的失败尝试:
我试图诉诸索引(因此定义u_types等)和部分模板专业化这样
namespace wrapper
{
template <int Uidx, int Vidx, int Widx>
struct S_Wrapper
{
typedef S<Uidx, Vidx, Widx> type; …我读到它们在概念上是平等的.在实践中,是否有任何场合
foo(T t)
比...更受欢迎
foo(const T& t)
？为什么？
到目前为止,感谢您的答案,请注意我并不是在询问by-ref和by-val之间的区别.
实际上我对by-const-ref和by-val之间的区别很感兴趣.
我曾经认为by-const-ref可以在调用案例中替换值,因为即使Herb Sutter和Bjarne说它们在概念上是相等的,并且"by ref"(是const)意味着更快.直到最近,我在某处读到了在某些情况下可以更好地优化by-val.
那么何时以及如何？
假设我已经实现了一个这样的模板类：
template <size_t N> class C
{
void f()
{
// print out N here?
}
};
我希望当编译器编译一个子句时
C<20> c;
它会打印出一条消息
“C 类以 N = 20 为模板”
我试过 #pragma 和 static_assert 都是徒劳的。
问题是
有没有办法或没有办法？
谢谢。
以下函数的递归版本是什么样的:
void tri_loop(size_t i, size_t j, size_t k)
{
for(size_t x = 0; x < i; ++x)
for(size_t y = 0; y < j; ++y)
for(size_t z = 0; z < k; ++z)
{
cout << x <<y << z;
}
}
只是为了精神钻探.(编辑:强调这一行)