小编use*_*575的帖子

我正在尝试压缩长向量（它们的大小范围从 1 到 1 亿个元素）。向量具有正整数，其值范围从 0 到 1 或 1 亿（取决于向量大小）。因此，我使用 32 位整数来包含大数字，但这会消耗太多存储空间。这些向量具有以下特征：

1. 所有值都是正整数。它们的范围随着向量大小的增长而增长。
2. 值在增加，但较小的数字确实经常干预（见下图）。
3. 特定索引之前的值都不大于该索引（索引从零开始）。例如，索引 6 之前出现的值都不大于 6。但是，较小的值可能会在该索引之后重复。这适用于整个阵列。
4. 我通常处理很长的数组。因此，当数组长度超过 100 万个元素时，即将出现的数字大多是与先前重复出现的数字混合的大数字。较短的数字通常比较大的数字更频繁地重新出现。当您通过数组时，新的更大的数字会添加到数组中。

以下是数组中的值示例：{initial padding..., 0, 1, 2, 3, 4, 5, 6, 4, 7, 4, 8, 9, 1, 10, ... later ..., 1110, 11, 1597, 1545, 1392, 326, 1371, 1788, 541,...}

这是向量的一部分的图：

我想要什么？：因为我使用的是 32 位整数，这会浪费大量内存，因为可以用小于 32 位表示的较小数字也会重复。我想最大限度地压缩这个向量以节省内存（理想情况下，减少 3 倍，因为只有减少这个数量或更多才能满足我们的需求！）。实现这一目标的最佳压缩算法是什么？或者是否可以利用上述数组的特征将该数组中的数字可逆地转换为 8 位整数？

我尝试过或考虑过的事情：

1. Delta 编码：这在这里不起作用，因为矢量并不总是增加。
2. 霍夫曼编码：这里似乎没有帮助，因为数组中唯一数字的范围非常大，因此，编码表将是一个很大的开销。
3. 使用变量 Int 编码。即对较小的数字使用 8 位整数，对较大的数字使用 16 位......等等。这将向量大小减小到 size*0.7（不令人满意，因为它没有利用上述特定特性）
4. 我不太确定以下链接中描述的这种方法是否适用于我的数据：http: //ygdes.com/ddj-3r/ddj-3r_compact.html 我不太了解该方法，但它给了我鼓励尝试类似的事情，因为我认为可以利用数据中的某些顺序来发挥它的优势。例如，我尝试将任何大于 255 的数字（n）重新分配给 n-255，以便我可以将整数保留在 …

最近,我对Julia-lang很感兴趣,因为它声称是一种具有接近C性能的动态语言.但是,到目前为止我对它的体验并不好(至少表现明智).我正在编写的应用程序需要随机访问特定的数组索引,然后将它们的值与其他特定的数组索引进行比较(通过多次迭代).以下代码模拟了我对程序的需求:我的Julia代码在大约8秒内完成执行,而java脚本代码在chrome环境中需要不到1秒!我是否在使用Julia代码做错了什么？非常感谢提前.

朱莉娅代码在这里:

n=5000;
x=rand(n)
y=rand(n)
mn=ones(n)*1000;
tic();
for i in 1:n;
    for j in 1:n;
        c=abs(x[j]-y[i]);
        if(c<mn[i])
            mn[i]=c;
        end
    end
end
toc();

Javascript代码:(>比上面的julia代码快8倍!)

n=5000; x=[]; y=[]; mn=[];
for(var i=0; i<n; i++){x.push(Math.random(1))}
for(var i=0; i<n; i++){y.push(Math.random(1))}
for(var i=0; i<n; i++){mn.push(1000)}
console.time('test');
for(var i=0; i<n; i++){
    for(var j=0; j<n; j++){
        c=Math.abs(x[j]-y[i]);
        if(c<mn[i]){
            mn[i]=c;
        }       
    }
} 
console.timeEnd('test');

鉴于未排序的矢量{6.0,3.02,4.2,5.3}以及给定的0.1的阈值,我怎样才能有效地找到C++中的给定阈值内的所述第一匹配的值3(例如)？我目前的实现如下,但它的复杂度为O(n).如果可能的话,我想将其改进为O(log n).非常感谢提前

std::vector<double> array = {6.0, 3.02, 4.2, 5.3};  
double val = 3 // the to be found value within the array above
double thresh = 0.1; // max threshold of the matching value
double found; // the matching value
for (int i = 0; i < array.size(); i++){
    if ( abs(array[i] - val) < thresh){
        found = array[i];
    }
}

输出应为3.02,因为它是允许阈值0.1内给定数组中与3的第一个最接近的匹配

编辑:如果我能负担得起预先对矢量进行排序,我如何重新实现上述搜索为O(log n)？谢谢

我在 C++ 中使用一组对象来获取插入和查找的 log(n) 次。在下面的代码中，我可以插入元素并使它们按 x 属性排序，但是，我无法使用 lower_bound 来查找基于相同属性的下限。我不知道如何解决这个问题。任何帮助将不胜感激。

我能找到的大多数关于集合的例子都不是关于一组对象的

struct MyObject {
float x = 0;
float y = 0;    
const bool operator < ( const MyObject &r ) const{
    return ( x< r.x);
}
};

set<MyObject> nset;

int main(){

MyObject n1;
n1.x=5;
n1.y=1;

MyObject n2;
n2.x=3;
n2.y=2;

nset.insert(n1);
nset.insert(n2);

// this works, the elementes are sorted according to x
for(auto elem: nset){
    cout << elem.x << endl; 
}

// this doesn't work
set<MyObject>::iterator it = lower_bound(nset.begin(), nset.end(), 1.2); …