среда, 26 ноября 2008 г.

/etc/passwd: удаляем неугодных :)

Долго ничего писал в блог, не смотря на то что вроде бы и
накопилось достаточно всего что хотелось бы рассказать, да и время
есть - на работе относительно тихо и спокойно, и утром/вечером есть
время подумать. Но как-то все руки не доходят. Попробуем немного
исправить эту странную ситуацию.


Не так давно на работе подкинули задачку - есть у нас, скажем,
достаточно большой файл паролей: /etc/passwd, на 500.000+
пользователей,и есть список пользователей - штук 100.000, которые надо
из этого файлика убрать, за разумный период времени и скромно расходуя
ресурсы. Что делать, и как дальше жить?


Вообще строки из файлов удалять - ума много не надо: sed -e
'//d' filename и вперед. Но, ежели и строк много и файл не
маленький, то растянуться удовольствие в стиле cat users | while read
i; do sed -ie '/^'$i':/d' "$i"; done может очень надолго. Более
быстрый вариант - это когда за один раз удалять, скажем не одну
строку, а несколько тысяч:



n=0;
cat test_passwd_list |
while read i ; do
echo -n "${i}|" ;
let n =1 ;
if [ "${n}" -gt 2000 ] ; then
echo ;
n=0 ;
fi ;
done |
while read users ; do
sed -i -r -e "/^${users}:/d" test_passwd ;
done

Вот такой вариант был предложен одним из людей с которыми я
работаю. Так работает значительно быстрее, чем если это делать
построчно, если не ошибаюсь - около минуты. Единственная проблема
- эта конструкция жрет достаточно много памяти, да и две минуты, как
оказалось потом - это долго.


Впрочем, первое что пришло в голову мне, работало тоже около двух
минут. Идея заключалась в том, чтобы сравнивать не "все со всем
файлом", а как-то сравниваемое ограничить. Скажем, если мы поместим в
перловый хэш первые пару букв каждого логина, а потом будем сравнивать
каждую строчку /etc/passwd только с теми юзернеймами у которых первые
буквы такие же - должно получиться быстрее. Получилось примерно вот
так:




#!/usr/bin/perl

use strict;
use warnings;
my $in = 2;
my $off = 0;
my %hash;
while(<>){
chomp;
my $s = $_;
push(@{$hash{substr($s,$off,$in)}}, $s);
}

open(FILE,"/Users/diesel/scripts/passwdsplit/test_passwd");
while(<FILE>){
my $s = $_;
my $t = 0;
my ($sub,undef) = split(/:/,$s);
foreach my $item ( @{$hash{substr($s,$off,$in)}}){
if ($item eq $sub){
$t = 1;
last;
}
}
print $s unless $t == 1;
}


Собственно эта штука написанная не думая отработала свои 2 минуты,
сделала то что требовалось и проблема была решена. Но я не успокоился
:)


Играясь с значением переменных $in и $off уже на тестовых файлах, я
понял что чем больше строку мы кладем в хэш, тем быстрее все
работает, при этом все это дело не так уж много памяти жрет. Поэтому
возникло желание засунуть в хэш весь файл с юзернеймами, которые надо
удалить - с самого начала это в голову не пришло - боялся что перлу
поплохеет. Оказывается не плохеет и вот такой вариант:




diesel@indie:~/scripts/passwdsplit$ cat noregexp1.pl
#!/usr/bin/perl

use strict;
use warnings;

my %hash;
open(FILE1,$ARGV[0]);
while(<FILE1>){
chomp;
# my $s = $_;
$hash{$_} = "1";
}

open(FILE2,$ARGV[1]);
while(<FILE2>){
my ($sub,undef) = split(/:/);
print $_ unless $hash{$sub};
}


отработал всего за две секунды. Под конец, решил прикола ради
попробовать сделать тоже самое на ruby, попытки разобраться с которым
до сих пор не оставил. Получилась вот такая штука:



diesel@indie:~/scripts/passwdsplit$ cat noregexp.rb
#!/usr/bin/ruby

hash = Hash.new;
File.open(ARGV[0]) do |file|
while ! file.eof? do
hash[file.readline.chomp] = 1;
end
end
File.open(ARGV[1]) do |file|
while ! file.eof? do
s=file.readline;
unless hash[s.split(":")[0]]
print s
end
end
end

которой на выполнение той же задачи понадобилось секунд
пять. Другой человек, с которым я работаю решил попытать счастье с
С++'ным STL, и binary search в vector(да простят меня гуру, если я
сказал что-то не так). Его binary search занял примерно те же пять секунд
что и ruby-скрипт, равно как и моя переделка с использованием map:




#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <algorithm>
#include <map>
using namespace std;

int main(int argc, char *argv[]) {
string buff;
map<string,char> hash;

ifstream ex(argv[1]);
if (ex.is_open()){
while(!ex.eof()) {
getline(ex, buff);
hash[buff] = '1';
}
ex.close();
}

ifstream in(argv[2]);
if (in.is_open()){
while(!in.eof()) {
getline(in, buff);
string usr(buff.substr(0, buff.find(":", 0)));
if ( hash.find(usr) == hash.end() ){
cout<<buff<<endl;
}
}
}
in.close();
return 0;
}



Что вобщем-то не плохо, но несколько странно. Я расчитывал что оно
догонит и перегонит перл :). Чтобы догнать и перегнать перл оказалось
нужно заменить cout<<buff<<endl на банальный
printf("%s,\n",buff.c_str()).

Вот такой вот странный fun получился с простой на первый(да и на
второй) взгляд задачки :) Результаты замеров привел на глаз, по
памяти, сейчас пробовал всю эту радость запускать - получил несколько
другие(но похожие) цифры.

8 комментариев:

gemelen комментирует...

Из интереса, сравните работу этих костылей (без обид :)) с работой userdel? =)

diesel комментирует...

"прождал 5 минут и выключил". я думаю userdel работает по времени где-то так же как sed, удаляющий по одному домену, если не медленнее - оно ведь еще кучу проверок делает.

diesel комментирует...

Вы кстати сами можете оценить время, даже если прогнать на обычном файле паролей, в котором у мну 38 пользователей(то есть реально ничего не удаляется, а usedel выбрасывает на этапе "нет такого пользователя":

debian:/home/diesel/passwdsplit# time seq 1 10000 | while read i; do userdel user$i; done 2> /dev/null

real 0m24.550s
user 0m11.461s
sys 0m14.305s

debian:/home/diesel/passwdsplit# time seq 1 100000 | while read i; do userdel user$i; done 2> /dev/null

real 4m34.146s
user 2m21.253s
sys 2m35.302s

Dr.AKULAvich комментирует...

Не знал, что cout из iostream настолько "медленный". Выходит, вывод через stdio предпочтительнее. Какая между этими вариантами временная разница получилась?

diesel комментирует...

Примерно вот такая.

diesel@indie:~/scripts/passwdsplit$ time ./a.out test_passwd_list test_passwd > result

real 0m2.241s
user 0m1.645s
sys 0m0.213s
diesel@indie:~/scripts/passwdsplit$ g++ passwd5.cpp
diesel@indie:~/scripts/passwdsplit$ time ./a.out test_passwd_list test_passwd > result

real 0m4.485s
user 0m2.459s
sys 0m1.717s

diesel@indie:~/scripts/passwdsplit$ time ./noregexp.pl test_passwd_list test_passwd >result

real 0m3.940s
user 0m3.172s
sys 0m0.347s
diesel@indie:~/scripts/passwdsplit$ time ./noregexp.rb test_passwd_list test_passwd >result

real 0m5.432s
user 0m4.873s
sys 0m0.180s


я не берусь оценивать скорость чего-бы то ни было на основании подобных измерений. или утверждать что надо использовать b вместо a. Это просто то, что получалось у меня.

Анонимный комментирует...

Попробуйте ради интереса в Си++ поменять map на hash_map и cout << buf << endl; на cout << buf << "\n", т. к. endl отключает буферизацию.

Assaron комментирует...

ну дак это известный факт про принтф и стримы, что начиная с файликов размером от метра стримы сильно проигрывают

Assaron комментирует...

хотя нет, я погоречился