gpt4 book ai didi

c++ - 如何生成具有预定义*唯一性*的整数序列?

转载 作者:塔克拉玛干 更新时间:2023-11-03 06:21:15 26 4
gpt4 key购买 nike

对于某些测试,我需要生成一个可能很长的非随机整数序列,该序列具有预定义的唯一性。我将唯一性定义为一个 float ,等于“序列中唯一 数的数量”除以“序列总长度”。这个数字应该在(0, 1]半开区间内。

我可能需要这些长度不同的序列,这事先是未知的 - 所以我需要一种算法来生成这样一个序列,它的 any 前缀序列具有唯一性,接近于预定义的序列.例如,序列 1,2,...,m,1,2,...,n 具有唯一性 max(m,n)/(m+n) 对我不好。

问题看起来很简单,因为该算法应该只生成一个序列 - 但我编写的函数 next()(见下文)看起来出乎意料地复杂,而且它还使用了核心内存 a很多:

typedef std::set<uint64_t> USet;
typedef std::map<unsigned, USet> CMap;

const double uniq = 0.25; // --- the predefined uniqueness
uint64_t totalSize = 0; // --- current sequence length
uint64_t uniqSize = 0; // --- current number of unique integers
uint64_t last = 0; // --- last added integer
CMap m; // --- all numbers, grouped by their cardinality

uint64_t next()
{
if (totalSize > 0)
{
const double uniqCurrent = static_cast<double>(uniqSize) / totalSize;
if (uniqCurrent <= uniq)
{
// ------ increase uniqueness by adding a new number to the sequence
const uint64_t k = ++last;
m[1].insert(k);
++totalSize;
++uniqSize;
return k;
}
else
{
// ------ decrease uniqueness by repeating an already used number
CMap::iterator mIt = m.begin();
while (true)
{
assert(mIt != m.cend());
if (mIt->second.size() > 0) break;
++mIt;
}
USet& s = mIt->second;
const USet::iterator sIt = s.cbegin();
const uint64_t k = *sIt;
m[mIt->first + 1].insert(k);
s.erase(sIt);
++totalSize;
return k;
}
}
else
{
m[1].insert(0);
++totalSize;
++uniqSize;
return 0;
}
}

有什么想法可以更简单地做到这一点吗?

最佳答案

您没有说要让每个数字具有相同的基数。下面的代码大致做到了这一点,但在某些情况下它选择了一个“不按顺序”的数字(主要是在序列的早期)。希望简单性和持续的空间使用可以弥补这一点。

#include <cassert>
#include <cstdio>

class Generator {
public:
explicit Generator(double uniqueness)
: uniqueness_(uniqueness), count_(0), unique_count_(0),
previous_non_unique_(0) {
assert(uniqueness_ > 0.0);
}

int Next() {
++count_;
if (static_cast<double>(unique_count_) / static_cast<double>(count_) <
uniqueness_) {
++unique_count_;
previous_non_unique_ = 1;
return unique_count_;
} else {
--previous_non_unique_;
if (previous_non_unique_ <= 0) {
previous_non_unique_ = unique_count_;
}
return previous_non_unique_;
}
}

private:
const double uniqueness_;
int count_;
int unique_count_;
int previous_non_unique_;
};

int main(void) {
Generator generator(0.25);
while (true) {
std::printf("%d\n", generator.Next());
}
}

关于c++ - 如何生成具有预定义*唯一性*的整数序列?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/33638006/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com