经典面试题目——250M内存处理10G大小的log文件

时间：2024-03-21 14:36:20

前言

周末逛知乎的时候，看到的一个经典面试题目：http://www.zhihu.com/question/26435483。非常经典的一道分而治之的题目。

题目描写叙述例如以下：

有次面试遇到一个问题，10G的log里面每一行都保存着一个url，内存仅仅有250M，当输入一个url时，假设高速查出日志里是否有这条记录，假设有，有多少条？要求不能使用数据库，仅仅能使用文本处理。

思路

之前我的研究生导师已经从project角度分析了这个问题。这里我是简单的记录思想，并写出完整的演示样例来解决问题。
这是一道很典型的使用分治法来解决这个问题的题目。思路例如以下：
  1. 首先。考虑将10G的log文件划分为多个小于250M的文件，这样每一个小文件就能够一次性加载内存了。
  2. 当小文件能够一次性加载内存后，能够直接grep搜索，也能够对文件内容排序后，然后二分查找。
疑问：怎样避免在切分文件的过程中。误操作切断url？
解答：能够使用split按行来切分文件（注意：这里按行是依照“\n”切割，和你用vim编译器打开看到的行是不一样地）。因此，我们如果一个记录几乎相同是480byte（已经不少了），那么依照-l 500000 切割文件。那事实上每一个文件存储500000行也才240M。全然能够加载内存，也不存在url被截断的问题了。

演示样例

1. 通过一个4k大小的日志文件。构造一个1G大小的測试log文件。并添加特殊的url为“www.wangzhengyi.com”，这也是我们要查询的特殊url。
思路：cat 4k大小的日志文件256000次，每次结束时添加这个特殊的url:"www.wangzhengyi.com“。演示样例代码例如以下：
#!/bin/bash

BASE_LOG_PATH=/tmp/test/access.log.1

RES_LOG_PATH=/tmp/test/big.log

if [ -f $RES_LOG_PATH ]; then

    rm -rf $RES_LOG_PATH

fi

touch $RES_LOG_PATH

for i in `seq 1 256000`; do

    cat $BASE_LOG_PATH >> $RES_LOG_PATH

    echo "www.example.com|10.32.185.95|-[28/Oct/2014:12:34:39 +0800]|" >> $RES_LOG_PATH

done

建成之后，我们du -sh看一下文件大小确实是1G多。

经典面试题目——250M内存处理10G大小的log文件

watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvd3p5XzE5ODg=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center" alt="">



2. 我们更苛刻一些，如果最多能用的内存是5k，那我们能够依照1000行来对1G的文件进行分割，然后bash shell for循环遍历分割后的文件，通过grep将特殊的url查找出来，存储到特定的文件里。演示样例脚本例如以下：
#!/bin/bash

LOAD_DIR_PATH="/tmp/test/children"

SOURCE_PATH="/tmp/test/big.log"

if [ ! -d $LOAD_DIR_PATH ];then

    mkdir -p $LOAD_DIR_PATH

fi

cp $SOURCE_PATH $LOAD_DIR_PATH

#1.split依照1000行来进行切分

NUMBER=1000

cd $LOAD_DIR_PATH

split -l $NUMBER $LOAD_DIR_PATH/big.log

#2.for循环遍历查找

TARGET_URL="www.wangzhengyi.com"

TARGET_PATH="/tmp/test/res.txt"

for file in `ls $LOAD_DIR_PATH`; do

    if [[ $file != "big.log" ]]; then

        grep -i $TARGET_URL $file >> $TARGET_PATH

    fi

done

#3.统计行数(前提：总结果数不超过规定的内存限制)

echo `cat $TARGET_PATH | wc -l`

相关文章