VPF::быстрый поиск по нескольким ключам

zyxerr

Дата 31.7.2008, 16:56 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 66
Регистрация: 17.7.2008

Репутация: 2
Всего: 2

возникла такая задача:

нужно из txt-файла размером 1 гигабайт удалить все номера абонентов, которые есть в массиве @a.
(который я подгружаю из другого файла). Каждый номер состоит из 32 буквенно-цифровых символов,
всего в массиве @a 500 тыс. номеров.
.
Получается для каждой строки нужно производить 500 тыс. поисков по шаблону. А если этих
строк - несколько миллионов..
.
пробовал склеить весь массив @a в общий шаблон $a="первый номер|второй номер|...|"
и потом регепс s/$a//g - зависает просто.
.
кто сталкивался с такой задачей?

ginnie

Дата 31.7.2008, 17:39 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 1287
Регистрация: 6.1.2008
Где: Москва

Репутация: 38
Всего: 49

Уважаемый zyxerr, как вариант, могу предложить разбить массив на хэши помельче по нескольким первым символам номера.

Почему Вы написали про поиск по шаблону, разве у Вас не простое сравнение номеров?

--------------------

Написать код, понятный компьютеру, может каждый, но только хорошие программисты пишут код, понятный людям. (Мартин Фаулер. Рефакторинг)

tolkien

Дата 31.7.2008, 17:43 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 277
Регистрация: 5.4.2008

Репутация: 4
Всего: 4

1. Данные из файла загружайте кусками. Т.е не 1 Гб. А Где нибдуь по 1 Мб но так чтобы последний символ загружаемого куска был пробле или \n.

2. Воспользуйтесь index и substr вместо рег выраж.

И у вас будет все летать.

sir_nuf_nuf

Дата 31.7.2008, 21:04 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 920
Регистрация: 6.1.2008

Репутация: 14
Всего: 31

хм.. продолжая идею ginnie:

а почему бы не поместить все 500 000 в один perl хэш ?
а потом читать по по одному номеру из большого файла и проверять есть ли он в хеше.
должно быть быстро..

если у вас не 500 000, а очень много, то возможно лучше экономить память - писать на С.
если совсем много - читать Кнута про внешнюю сортировку и реализовывать нечто похожее..

--------------------

amg

Дата 1.8.2008, 07:25 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1145
Регистрация: 3.8.2006
Где: Новосибирск

Репутация: 38
Всего: 50

Цитата(zyxerr @ 31.7.2008, 16:56

)

пробовал склеить весь массив @a в общий шаблон $a="первый номер|второй номер|...|" и потом регепс s/$a//g - зависает просто.

Неудивительно. Известно, что подобные решения приводят к изрядным тормозам.

Код


# Медленно, если @a большой
my $regexp = join '|', @a;
$string =~ /$regexp/;
# То же самое, но существенно быстрее
foreach my $regexp (@a) {
   last if $string =~ /$regexp/;
}

Но все равно это будет медленно (перебирать большой массив на каждую строку гигового файла).

Цитата(sir_nuf_nuf @ 31.7.2008, 21:04

)

а почему бы не поместить все 500 000 в один perl хэш ?

По моему тоже, так и надо сделать. Такой хэш займет, по моим подсчетам, всего 63 мега оперативки. Вот примерный код:

Код

%a = map {$_=>undef} @a;
while (<>) {
  chomp; # Предполагаю, что в каждой строке файла номер и больше ничего.
  print if ! exists $a{$_};
}

Думаю, что скорость работы такого скрипта будет определяться скоростью чтения/записи на диск.

zyxerr

Дата 1.8.2008, 10:17 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 66
Регистрация: 17.7.2008

Репутация: 2
Всего: 2

спасибо, я попробую и отпишусь позже

korob2001

Дата 1.8.2008, 16:50 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 2871
Регистрация: 29.12.2002

Репутация: 31
Всего: 61

Если не трудно напишите формат обоих файлов.

Вот как-то человеку хотел помочь, а потом выяснилось, что тема была в мусорке, собственно всё это время она там и была.

Код


#!/usr/bin/perl
use locale;

# Если не получили 2 параметра, выводим сообщение об ошибке и завершаем программу
if ( @ARGV < 2 ) {
     print "Start this program with two parameters.\n";
     print "Forexample so: C:\\>perl this_file.pl dir/file1.txt dir/file2.txt";
     exit 0;
}

my(%dbm1, %dbm2) = ();
my($file1,$file2) = @ARGV;

# Указываем, что будем читать файлы по словам, а не по строкам.
$/ = " ";

# Открываем DBM файл, будем имитировать хеш на жёстком диске,
# так как файлы могут быть и очень большими.
dbmopen(%dbm1, "tempdb1", 0644) or die "Can't open DBM file './tempdb1': $!\n";
dbmopen(%dbm2, "tempdb2", 0644) or die "Can't open DBM file './tempdb2': $!\n";

# Открываем первый файл и читаем его по словам
open my $fh, "<", "$file1" or die "Can't open file '$file1': $!\n";
     while (my $word = <$fh>) {
            # Удаляем символ перевода строки, если он есть
            chomp $word;
            # Пропускаем пустые строки, а так же строки с пробелами
            next if $word =~ /^\s*$/;
            # Обрежем пробелы вначале и конце слова, если они есть
            $word =~ s/^\s+//;
            $word =~ s/\s+$//;
            # опускаем слова в нижний регистр и заносим их
            # в DBM файл, так же инкрементируем значение.
            $dbm1{lc($word)}++;
     }
# Закрываем первый файл
close $fh;

# Открываем второй файл
open $fh, "<", "$file2" or die "Can't open file: $!\n";
      while (my $word = <$fh>) {
             chomp $word;
             next if $word =~ /^\s*$/;
             $word =~ s/^\s+//;
             $word =~ s/\s+$//;
             $dbm2{lc($word)}++;
      }
close $fh;

# Открываем файл, куда будем выводить результат
open $fh, ">", "result.txt" or die "Can't open file 'result.txt': $!\n";

# Теперь проходим по первому dbm файлу и сравниваем его со вторым
while (my($key,$val) = each %dbm1) {
       # Проверяем, есть ли такое слово во втором файле?
       if (exists $dbm2{$key}) {
           print $fh "Слово \"$key\" пересекается.\n";
           print $fh "Кол-во пересечений в файле '$file1': $val\n";
           print $fh "Кол-во пересечений в файле '$file2': $dbm2{$key}\n";
           print $fh "=" x 80, "\n";
       }
}

# Закрываем файлы
close $fh or die "Can't close file 'result.txt': $!\n";
dbmclose %dbm1 or die "Can't close DBM file: $!\n";
dbmclose %dbm2 or die "Can't close DBM file: $!\n";

# Удаляем DBM файлы
unlink "tempdb1.dir", "tempdb2.dir", "tempdb2.pag", "tempdb1.pag";

Пример получился немного длинный, но зато он никогда не убьёт оперативную помять, даже если файлы будут >= 50 Gb каждый, лишь бы хватило места на винте. ;)))))
Запускать его нужно из командной строки и при запуске передать ему 2 параметра:
1. имя первого файла
2. имя второго файла

Допустим мы назвали его parser.pl, значит вызываем его так:
C:\>perl parser.pl ./file1.txt ./file2.txt
Результат будет сохранён в файл с именем result.txt в том же каталоге, где и сам файл parser.pl
Выглядеть он будет примерно так:

Код


Слово "стране," пересекается.
Кол-во пересечений в файле 'file1.txt': 1
Кол-во пересечений в файле 'file2.txt': 1
================================================================================
Слово "об" пересекается.
Кол-во пересечений в файле 'file1.txt': 2
Кол-во пересечений в файле 'file2.txt': 2
================================================================================
Слово "этом" пересекается.
Кол-во пересечений в файле 'file1.txt': 1
Кол-во пересечений в файле 'file2.txt': 4
================================================================================
Слово "на" пересекается.
Кол-во пересечений в файле 'file1.txt': 11
Кол-во пересечений в файле 'file2.txt': 45
================================================================================
Слово "что" пересекается.
Кол-во пересечений в файле 'file1.txt': 5
Кол-во пересечений в файле 'file2.txt': 24
================================================================================
Слово "платьях" пересекается.
Кол-во пересечений в файле 'file1.txt': 1
Кол-во пересечений в файле 'file2.txt': 1
================================================================================
Слово "им" пересекается.
Кол-во пересечений в файле 'file1.txt': 1
Кол-во пересечений в файле 'file2.txt': 3
================================================================================

Правда здесь идёт подсчёт пересечений, но впринцип тот же, что и в поставленной задаче.

Это сообщение отредактировал(а) korob2001 - 1.8.2008, 17:20

--------------------

"Время проходит", - привыкли говорить вы по неверному пониманию.
"Время стоит - проходите вы".

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Perl: Общие вопросы \| Следующая тема »