/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 получился с простой на первый(да и на
второй) взгляд задачки :) Результаты замеров привел на глаз, по
памяти, сейчас пробовал всю эту радость запускать - получил несколько
другие(но похожие) цифры.