wengxufeng – SKET DAN

冒泡排序、快速排序这种基本知识还是要记得。

冒泡排序:

<?php
function bubble($arr) {
    $count = count($arr);
    for ($i = $count - 1; $i > 0; $i--) {
        for ($j = 0; $j < $i; $j++) {
            if ($arr[$j] > $arr[$j+1]) {
                $arr[$j] = $arr[$j] + $arr[$j+1];
                $arr[$j+1] = $arr[$j] - $arr[$j+1];
                $arr[$j] = $arr[$j] - $arr[$j+1];
            }
        }
    }
    return $arr;
}

<?php

function bubble($arr) {

$count = count($arr);

for ($i = $count - 1; $i > 0; $i--) {

for ($j = 0; $j < $i; $j++) {

if ($arr[$j] > $arr[$j+1]) {

$arr[$j] = $arr[$j] + $arr[$j+1];

$arr[$j+1] = $arr[$j] - $arr[$j+1];

$arr[$j] = $arr[$j] - $arr[$j+1];

}

return $arr;

}

快速排序:

<?php
function quicksort($arr) {
    if (count($arr) > 1) {
        $k = $arr[0];
        $a = array();
        $b = array();
        $count = count($arr);
        for ($i = 1; $i < $count; $i++) {
            if ($arr[$i] <= $k) {
                $a[] = $arr[$i];
            } else {
                $b[] = $arr[$i];
            }
        }
        $a = quicksort($a);
        $b = quicksort($b);
        return array_merge($a, array($k), $b);
    } else {
        return $arr;
    }
}

<?php

function quicksort($arr) {

if (count($arr) > 1) {

$k = $arr[0];

$a = array();

$b = array();

$count = count($arr);

for ($i = 1; $i < $count; $i++) {

if ($arr[$i] <= $k) {

$a[] = $arr[$i];

} else {

$b[] = $arr[$i];

}

$a = quicksort($a);

$b = quicksort($b);

return array_merge($a, array($k), $b);

} else {

return $arr;

}

二分法查找$b在递增数组$arr中的位置:

<?php
function a($arr, $search) {
    $start = 0;
    $end = count($arr) - 1;
    while ($start <= $end) {
        $center = intval(($start + $end) / 2);
        if ($arr[$center] == $search) {
            return $center;
        } elseif ($arr[$center] > $search) {
            $end = $center - 1;
        } else {
            $start = $center + 1;
        }
    }
    return -1;
}

<?php

function a($arr, $search) {

$start = 0;

$end = count($arr) - 1;

while ($start <= $end) {

$center = intval(($start + $end) / 2);

if ($arr[$center] == $search) {

return $center;

} elseif ($arr[$center] > $search) {

$end = $center - 1;

} else {

$start = $center + 1;

}

return -1;

}

2012/11/22

OpenVZ VPS内存解读

购买基于OpenVZ的VPS时，一定会注意到两个参数，一个是Guarantee RAM，一个是Burstable RAM，Burstable RAM会高于Guarantee RAM。一般的说明是说Guarantee是可以保证的内存，VPS应保证在大多数情况下内存的使用量要低于保证内存数，如果内存使用超过的保证内存数，也只能是短时间的超过，也不能超过Burstable内存的限制。而且，如果长时间占用过量内存的话，有可能进程会被系统强制杀掉。换句话说，Burstable内存不能长期占用。如果系统在正常使用时的内存需求超过Guarantee RAM的话，就应该考虑升级了。

但在OpenVZ的系统下如果查看当前使用内存是多少，是否超过了Guarantee内存数呢？Linux的free命令看到的是Guarantee内存吗？如果是free下看到内存已经超过了Guarantee RAM值，是否要马上升级VPS内存呢？

查了一下OpenVZ的文档，似乎没有那么简单，free命令看到的是系统当前所申请的内存量，最大即为Burstable内存的限制数。而OpenVZ Guarantee内存控制的是系统真正使用的内存量。在Linux下，申请的内存并不等于真的占用的系统内存，只有真正被使用时才会真正占用内存。如果实际使用的内存没有超过Guarantee内存数，只是申请的内存数超过了Guarantee内存，VPS应该还是可以正常使用的。

可以通过查看 /proc/user_beancounters 文件来查看当前实际内存的使用。文件中：
kmemsize是核心内存的使用量，一般很少
privvmpages是申请的内存量，限制值就是burstable RAM
oomguarpages是实际使用的内存量，限制值就是guarantee RAM

写了一个小脚本，可能帮助查看当前的内存使用情况。

#!/bin/bash
BEAN=`cat /proc/user_beancounters`
GUAR=`echo "$BEAN" | grep vmguar | awk '{ print int($4/256);}'`
PVMB=`echo "$BEAN" | grep privvm | awk '{ print int($2/256);}'`
OOMG=`echo "$BEAN" | grep oomguar | awk '{ print int($2/256);}'`
BURST=`echo "$BEAN" | grep privvm | awk '{ print int($4/256);}'`
KMMB=`echo "$BEAN" | grep kmem | awk '{ print int(($3/1048576)+0.5);}'`

let USED=$KMMB+$OOMG
let ALLOC=$KMMB+$PVMB

echo "VPS Memory:"
echo "GUARANTEE RAM: $GUAR MB"
echo "BURSTABLE RAM: $BURST MB"
echo "ALLOCATE RAM: $ALLOC MB"
echo "USED RAM: $USED MB"

#!/bin/bash

BEAN=`cat /proc/user_beancounters`

GUAR=`echo "$BEAN" | grep vmguar | awk '{ print int($4/256);}'`

PVMB=`echo "$BEAN" | grep privvm | awk '{ print int($2/256);}'`

OOMG=`echo "$BEAN" | grep oomguar | awk '{ print int($2/256);}'`

BURST=`echo "$BEAN" | grep privvm | awk '{ print int($4/256);}'`

KMMB=`echo "$BEAN" | grep kmem | awk '{ print int(($3/1048576)+0.5);}'`

let USED=$KMMB+$OOMG

let ALLOC=$KMMB+$PVMB

echo "VPS Memory:"

echo "GUARANTEE RAM: $GUAR MB"

echo "BURSTABLE RAM: $BURST MB"

echo "ALLOCATE RAM: $ALLOC MB"

echo "USED RAM: $USED MB"

1. VPS下看到的内存是物理系统是RAM+SWAP,不一定是真正的物理内存。
2. 内存用量应包括socketbuf的用量，但一般比较小，前面的脚本统计中没有计算
3. 如果系统出现超售时，有可能实际使用的内存还没有达到保证内存数时就可出现进程被杀掉。
4. 本文是基于自己目前的一些理解，如有差错，还请见谅，也请指正。

================

来源：http://www.linuxfly.org/post/202/
来源：http://www.fallday.org/archives/9

2012/11/012016/03/05