代码之家  ›  专栏  ›  技术社区  ›  Remi.b

C++:用普通基数将整数分组以节省内存

  •  -1
  • Remi.b  · 技术社区  · 6 年前

    考虑一个无符号整数值的(排序)向量。

    std::vector<unsigned int> data = {1234,1254,1264,1265,1267,1268,1271,1819,1832,1856,
                                      1867,1892,3210,3214,3256,3289};
    

    假设每个无符号int是4个字节,这个16个元素的向量将占用至少64个字节的RAM。

    我认为可以通过按公共基数对这些值进行分组来减少内存使用。例如,考虑一种

    data =
    {
       {12..
          ..34, ..54, ..64, ..65, ..67, ..68, ..71
       },
       {18..
          ..19, ..32, ..56, ..67, ..92
       }
       {32..
          ..10, ..14, ..56, ..89
       }
    };
    

    在上面的例子中,我将值按块100分组。按2^8=256或2^16=65536的组对数据进行分组更符合逻辑。

    是否有一种数据类型(在std::或boost::或其他格式中)可以为我完成这种任务,或者我必须为此编写自己类型的容器代码?听起来像是个潜在的好主意吗?

    1 回复  |  直到 6 年前
        1
  •  1
  •   Captain Giraffe    6 年前

    对于非常受限的场景中的特定输入,这是一个可行的想法。唉,std::没有提供这种结构。你的建议可以合理地以树状的方式实现。

    请注意一般的基数感知排序,因为它们通常使用大列表,因此使用的内存比常规向量要多。