求随机数字算法

Chinazdj

｛202.205.0.0/28;205.12.0.0/26｝;
这是关于求随机数的问题。
首先这是一段网络段，现在可以将他解析出来202.205.0.0就是IP地址后面的28其实就是32-28=4，2的4次方=16，那么这段IP地址就是202.205.0.0-202.205.0.16.
所以｛202.205.0.0/28;205.12.0.0/26｝中应该是有16+64=80个IP地址。
现在要在这80个IP地址中随机取20个IP。（我只是举个列子，之前用容器做的，我把所有IP都放到容器中内存不足了，其实正常数据一个段里有上万个IP，有上万个段，所以有几亿数据）
16，64是我都能知道的，我还能知道就是首IP地址，比如202.205.0.0和205.12.0.0。
现在想获得一个随机数，比如72，72在80以内，其实它的地址应该是72-16=56，那应该就是205.12.0.0+52也就是205.12.0.52，这样想我能想明白
while(iplist!=it->second.end())
{
        unsigned long int ip_num=imask-iplist->mask;

        for(unsigned long int i=iplist->net_id+firstend;i<iplist->net_id+everyip_num-firstend;i++)
        {
                v.push_back(i);
        }
        iplist++;
        everyip_num+=ip_num;       
}
上述代码中while循环就是循环｛202.205.0.0/28;205.12.0.0/26｝2组数据，ip_num=imask-iplist->mask;就是每组的IP数，16和64，everyip_num就是总IP数80；
for(unsigned long int i=iplist->net_id;i<iplist->net_id+everyip_num;i++)
        {
                v.push_back(i);
        }
按照这种插入数据的办法肯定有问题，数据过多会把容器爆掉，现在就随机插入20个，其中iplist->net_id就是IP地址，之前是循环一组就把IP都放到容器里，现在是要随机放20个，如果随机数是76的话，代码要怎么写？

cokeboL

楼主，我看不懂你的 语文描述。。。

cokeboL

应该是有16+64=80个IP地址。

这个64是哪里来的。。。再描述详细点吧。。

先不管其他的，看上去随机应该是某个范围内，或者是几个范围内的，何必使用容器。。

windoze

嗯，lz的这个问题我还真的想了想，发现还是需要写点代码的

https://gist.github.com/windoze/ ... #file-gistfile1-txt

1. 
   
2. #include <cstdint>
   
3. #include <array>
   
4. #include <vector>
   
5. #include <iostream>
   
6. #include <random>
   
7. 
   
8. inline constexpr uint32_t subnet_mask(int len) {
   
9.     return 0xFFFFFFFF >> (32-len) << (32-len);
   
10. }
    
11. 
    
12. inline uint8_t read_segment(const std::string &s, size_t start_pos) {
    
13.     return 0;
    
14. }
    
15. 
    
16. struct IP_addr {
    
17.     uint32_t data;
    
18.    
    
19.     // NOTE: Hardcoded little endian u32
    
20.     uint8_t &operator[](size_t index)
    
21.     { return reinterpret_cast<uint8_t *>(&data)[3-index]; }
    
22.    
    
23.     // NOTE: Hardcoded little endian u32
    
24.     const uint8_t &operator[](size_t index) const
    
25.     { return reinterpret_cast<const uint8_t *>(&data)[3-index]; }
    
26.    
    
27.     IP_addr mask(int len) const { return IP_addr{data & subnet_mask(len)}; }
    
28.     template<typename Iterator>
    
29.     static IP_addr parse(Iterator begin, Iterator end) {
    
30.         IP_addr ret{0};
    
31.         size_t index = 0;
    
32.         while (begin!=end) {
    
33.             if (isdigit((unsigned char)*begin)) {
    
34.                 ret[index] *= 10;
    
35.                 ret[index] += *begin - '0';
    
36.             } else {
    
37.                 ++index;
    
38.             }
    
39.             ++begin;
    
40.         }
    
41.         return ret;
    
42.     }
    
43. };
    
44. 
    
45. inline std::ostream &operator << (std::ostream &os, const IP_addr &addr) {
    
46.     os << int(addr[0]) << '.' << int(addr[1]) << '.' << int(addr[2]) << '.' << int(addr[3]);
    
47.     return os;
    
48. }
    
49. 
    
50. struct IP_subnet {
    
51.     IP_addr subnet_base;
    
52.     int mask_len;
    
53.    
    
54.     size_t size() const {
    
55.         // .0 and .255 are not valid IP address unless it's a single address subnet
    
56.         if (mask_len==32) {
    
57.             return 1;
    
58.         }
    
59.         return (~subnet_mask(mask_len)) + 1 - 2;
    
60.     }
    
61.    
    
62.     IP_addr operator[](size_t index) {
    
63.         if(mask_len==32)
    
64.             return IP_addr{static_cast<uint32_t>(subnet_base.data+index)};
    
65.         return IP_addr{static_cast<uint32_t>(subnet_base.data+index+1)};
    
66.     }
    
67.    
    
68.     template<typename Iterator>
    
69.     static IP_subnet parse(Iterator begin, Iterator end) {
    
70.         IP_subnet ret{0, 0};
    
71.         Iterator slash=std::find(begin, end, '/');
    
72.         ret.subnet_base=IP_addr::parse(begin, slash);
    
73.         ret.mask_len=0;
    
74.         ++slash;
    
75.         while(slash!=end) {
    
76.             ret.mask_len *= 10;
    
77.             ret.mask_len += *slash - '0';
    
78.             ++slash;
    
79.         }
    
80.         ret.subnet_base=ret.subnet_base.mask(ret.mask_len);
    
81.         return ret;
    
82.     }
    
83. };
    
84. 
    
85. template<typename InputContainer, typename OutputContainer>
    
86. size_t random_pick(InputContainer input, OutputContainer &output) {
    
87.     size_t n=input.size();
    
88.     size_t k=output.size();
    
89.     k=std::min(n, k);
    
90.     for (size_t i=0; i<k; i++) {
    
91.         output[i]=input[i];
    
92.     }
    
93.     std::random_device rd;
    
94.     std::default_random_engine e(rd());
    
95.    
    
96.     for (size_t i=k; i<n; i++) {
    
97.         size_t j=std::uniform_int_distribution<size_t>(0, i+1)(e);
    
98.         if(j<k)
    
99.             output[j]=input[i];
    
100.     }
     
101.     return k;
     
102. }
     
103. 
     
104. inline std::ostream &operator << (std::ostream &os, const IP_subnet &subnet) {
     
105.     os << subnet.subnet_base << '/' << subnet.mask_len;
     
106.     return os;
     
107. }
     
108. 
     
109. int main(int argc, const char * argv[]) {
     
110.     std::string ip("192.168.2.234");
     
111.     IP_addr addr=IP_addr::parse(ip.begin(), ip.end());
     
112.     std::cout << addr << std::endl;
     
113.     std::string ip_subnet("192.168.2.58/24");
     
114.     // parse会自动将这个子网修正为192.168.2.0/24
     
115.     IP_subnet sn=IP_subnet::parse(ip_subnet.begin(), ip_subnet.end());
     
116.     std::cout <<sn << std::endl;
     
117.     std::cout <<sn[0] << std::endl;
     
118.     std::vector<IP_addr> out(20);
     
119.     random_pick(sn, out);
     
120.     std::cout << "---------------------\n";
     
121.     for(auto &&e: out) {
     
122.         std::cout << e << std::endl;
     
123.     }
     
124.     return 0;
     
125. }
     

复制代码

windoze

如果需要在多个网段中随机挑选，用下面这段：

1. 
   
2. struct IP_subnet_set {
   
3.     std::vector<IP_subnet> data;
   
4.    
   
5.     size_t size() const {
   
6.         size_t ret=0;
   
7.         for(auto && sn : data) {
   
8.             ret += sn.size();
   
9.         }
   
10.         return ret;
    
11.     }
    
12.    
    
13.     void add_subnet(const IP_subnet &sn) {
    
14.         data.push_back(sn);
    
15.     }
    
16.    
    
17.     struct const_iterator {
    
18.         const IP_subnet_set *owner=nullptr;
    
19.         size_t sn_index=0;
    
20.         size_t ip_index=0;
    
21.         const_iterator(const IP_subnet_set *p)
    
22.         : owner(p)
    
23.         , sn_index(0)
    
24.         , ip_index(0)
    
25.         {}
    
26.         
    
27.         const_iterator(const IP_subnet_set *p, size_t sni, size_t ipi)
    
28.         : owner(p)
    
29.         , sn_index(sni)
    
30.         , ip_index(ipi)
    
31.         {}
    
32.         
    
33.         void next() {
    
34.             if(sn_index>=owner->data.size()) { owner=nullptr; return; }
    
35.             ip_index++;
    
36.             if(ip_index==owner->data[sn_index].size()) {
    
37.                 ip_index=0;
    
38.                 sn_index++;
    
39.             }
    
40.         }
    
41.         
    
42.         bool ended() const {
    
43.             return (!owner)
    
44.             || (sn_index>=owner->data.size())
    
45.             || ((sn_index==owner->data.size()-1) && (ip_index==owner->data[sn_index].size()));
    
46.         }
    
47.         
    
48.         const_iterator operator++() {
    
49.             next();
    
50.             return *this;
    
51.         }
    
52.         
    
53.         IP_addr operator*() const {
    
54.             return owner->data[sn_index][ip_index];
    
55.         }
    
56.         
    
57.         bool operator==(const const_iterator &other) const {
    
58.             return (ended()&&other.ended())
    
59.             || (owner==other.owner && sn_index==other.sn_index && ip_index==other.ip_index);
    
60.         }
    
61.         
    
62.         bool operator!=(const const_iterator &other) const {
    
63.             return !operator==(other);
    
64.         }
    
65.     };
    
66.    
    
67.     const_iterator begin() const {
    
68.         return const_iterator(this);
    
69.     }
    
70.    
    
71.     const_iterator end() const {
    
72.         return const_iterator(nullptr);
    
73.     }
    
74.    
    
75.     template<typename OutputContainer>
    
76.     size_t random_pick(OutputContainer &output) {
    
77.         size_t n=size();
    
78.         size_t k=output.size();
    
79.         k=std::min(n, k);
    
80.         const_iterator it=begin();
    
81.         for (size_t i=0; i<k; i++, ++it) {
    
82.             output[i]=*it;
    
83.         }
    
84.         std::random_device rd;
    
85.         std::default_random_engine e(rd());
    
86.         
    
87.         for (size_t i=k; i<n; i++, ++it) {
    
88.             size_t j=std::uniform_int_distribution<size_t>(0, i+1)(e);
    
89.             if(j<k) output[j]=*it;
    
90.         }
    
91.         return k;
    
92.     }
    
93. };
    

复制代码

使用方法：

1. 
   
2.     IP_subnet_set sns;
   
3.     sns.add_subnet(IP_subnet::parse("192.168.2.58/24"));
   
4.     sns.add_subnet(IP_subnet::parse("192.168.18.58/24"));
   
5.     sns.add_subnet(IP_subnet::parse("10.0.0.0/16"));
   
6.     std::vector<IP_addr> out(200);
   
7.     sns.random_pick(out);
   

复制代码