我现在有一亿个正整数,平均存储在100个文本里面,每行一个数字; 每个文件里面数字的顺序是随机的,给定一个数字,如果快速确定它在特定文件的哪一行?

leeyi 发布于 2018/12/14 14:11
阅读 625
收藏 1
PHP

我现在有一亿个正整数,平均存储在100个文本里面,每行一个数字; 每个文件里面数字的顺序是随机的,给定一个数字,如果快速确定它在特定文件的哪一行?

加载中
0
leeyi
leeyi

我用下面的Python3代码生成文件(每个文件随机一千万行数字,打乱顺序),PHP代码去读文,之后保存到数据库,问题解决了

 

PHP代码去读文,之后保存到数据库

/**
 * 获取邀请码
 * @param int $uid 用户编号
 * @param int $len 编码长度
 * @return string   邀请码
 */
function invitation_code($uid)
{
    $path = EXTEND_PATH.'icode/';
    if ($uid > 0) {
        // $hashids = new \Hashids\Hashids(config('hashids_salt'), $len, config('hashids_alphabet'));
        // return $hashids->encodeHex($uid);
        $fname = '';
        $uid2 = $uid;
        if ($uid<=10000000) {
            $fname = '100000_10100000.txt';
        } else if(10000000<$uid && $uid<=20000000) {
            $uid2 = $uid-10000000;
            $fname = '10100000_20100000.txt';
        } else if(20000000<$uid && $uid<=30000000) {
            $uid2 = $uid-20000000;
            $fname = '20100000_30100000.txt';
        } else if(30000000<$uid && $uid<=40000000) {
            $uid2 = $uid-30000000;
            $fname = '30100000_40100000.txt';
        } else if(40000000<$uid && $uid<=50000000) {
            $uid2 = $uid-40000000;
            $fname = '40100000_50100000.txt';
        } else if(50000000<$uid && $uid<=60000000) {
            $uid2 = $uid-50000000;
            $fname = '50100000_60100000.txt';
        } else if(60000000<$uid && $uid<=70000000) {
            $uid2 = $uid-60000000;
            $fname = '60100000_70100000.txt';
        } else if(70000000<$uid && $uid<=80000000) {
            $uid2 = $uid-70000000;
            $fname = '70100000_80100000.txt';
        } else if(80000000<$uid && $uid<=90000000) {
            $uid2 = $uid-80000000;
            $fname = '80100000_90100000.txt';
        }
        // var_dump($uid2);
        if ($fname) {
            $file = "{$path}{$fname}";
            $fp = new SplFileObject($file, 'r');
            //转到第二行, seek方法参数从0开始计数
            $fp->seek($uid2-1);
            $code = $fp->current();
            $code = $code ? trim($code) : '';
            $data = [
                'uid'=>$uid,
                'code'=>$code,
            ];
            if ($code) {
                \think\Db::name('user_invitation_code')->insert($data, true);
            }
            return $code;
        }
    }
    return '';
}

python3 生成文件 

#!/usr/bin/env python3
# encoding: utf-8
import os
import sys
import time
import random
import threading


min_code = 100000
max_code = 99999999

def create_code(start_id, end_id):
    starttime = time.time()
    end_id = end_id if end_id else max_code-min_code+1
    fname = '%d_%d.txt' % (start_id, end_id)
    f = open(fname,'w')
    for code in range(start_id, end_id):
        f.write("%s\n" % (str(code), ))
    f.close()
    endtime = time.time()
    print('starttime %f; endtime %f; use %f' % (starttime, endtime, (endtime-starttime),))

def shuffle_code(start_id, end_id):
    starttime = time.time()
    end_id = end_id if end_id else max_code-min_code+1
    fname = '%d_%d.txt' % (start_id, end_id)
    # fname = '/Users/leeyi/workspace/test_script/start_100000_end_100100.txt'
    with open(fname, 'r+') as f:
        li = f.readlines()
        random.shuffle(li)
        # print(type(li), li)
        with open(fname, 'r+') as f2:
            for l in li:
                f2.write(l)
    endtime = time.time()
    print('starttime %f; endtime %f; use %f' % (starttime, endtime, (endtime-starttime),))

# 10099999
# 20099999
if __name__=="__main__":
    try:
        length = 10000000
        for i in range(0, 9):
            sid = min_code+length*i
            eid = min_code+length*(i+1)
            create_code(sid, eid)
            shuffle_code(sid, eid)
    except KeyboardInterrupt:
        sys.exit(0)
    except Exception as e:
        print(e)

 

0
召唤兽01
召唤兽01

做。。。 做个索引?

leeyi
leeyi
如何做索引?
0
A
ATM.z

入数据库建索引

0
银杏卡卡
银杏卡卡

搜索二叉树?B树?Hash?

0
0
UchihaRyuuzaki
UchihaRyuuzaki

(这1亿个数不一定是连续的,假设没有超过int型最大值)100个长度100万数组,读文件的时候下标是数字,元素值是行号,就已经排序了。然后最坏情况100次二分查找(或者归并到一个大数组后二分查找)。消耗内存大概381m,如果直接用哈希,确实更快但内存可能要翻20倍以上。

0
南粤石头
南粤石头

hadoop mapreduce

0
leeyi
leeyi

我的实际需求是这样的,把系统用户uid 做“hashids”处理(https://hashids.org/ 这里有很好的方法),但是,老板要求 经过处理之后的 数据不能够包含字母(必须是纯数字的),数据的长度 在 6-9位数 (预计不久将来,我们的用户可以亿级别的),我的想法就是“把一亿uid先生成,把每100万UID存储在一个文件,每行一个UID,让后打乱文件每行的顺序,行号就对应的用户UID,【实际UID】就是转码后的code”,现在的问题,是如何快速通过code查找 【行号】?  @UchihaRyuuzaki 或者有其他更好的方式(把uid,code 存储在数据库里面,数据量有点大,我跑了一天一夜,才两百多万数据,有点慢了)

leeyi
leeyi
回复 @志田未来 : 思路不错,key=code value=uid 但是,不小心把 这个Redis删除了,就麻烦了
志田未来
志田未来
根据uid找行号,只存在于已注册用户,只要把已注册用户uid和行号对应关系写入数据库or redis hash 就很快啊
0
阿影
阿影

redis 有 bitcount, bitfield, bitop, bitpos 一系列命令可以解决;

java 有 java.util.BitSet,需要写一些代码,保存 BitSet 的数据(实际上就是索引)

0
学科带头人
学科带头人

既然是提前生成了,你为什么不从1排到一亿,再找个合适的计算啊规则,打乱文件或者存储顺序。

返回顶部
顶部