Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Perl: Общие вопросы > Поиск в хеше с его преобразованием?

Автор: Suppir 21.4.2010, 08:21

Есть хеш %all вида: 12 3 = 1 12 4 = 1 1245 = 1 1236 = 1 123 6 8 89 =1 ... Есть строка $a="1   2    3"; Как сделать функцию, которая будет проверять наличие строки $a в хеше %all, не учитывая пробелы в строке и хеше? Однако значения в хеше нельзя менять навсегда, так как он дальше используется с этими пробелами. Проблема в том, что хеш очень большой и строки в нем длинные. Необходимо оптимизировать поиск.

Автор: dva300 21.4.2010, 12:57

Цитата(Suppir @ 21.4.2010,  08:21) Есть хеш %all вида: 12 3 = 1 12 4 = 1 1245 = 1 1236 = 1 123 6 8 89 =1 ... Есть строка $a="1   2    3"; Как сделать функцию, которая будет проверять наличие строки $a в хеше %all, не учитывая пробелы в строке и хеше? Однако значения в хеше нельзя менять навсегда, так как он дальше используется с этими пробелами. Проблема в том, что хеш очень большой и строки в нем длинные. Необходимо оптимизировать поиск. хм.... Код my %all = (             "123" => 1,             "1 23" => 2,             "12 3 43" => 3,             "12 333" => 4,             "1254 3" => 5,             ); my $per='1254 3'; print "$per exist in \%all\n" if (grep($_=~/^$per$/,keys(%all)));

Автор: amg 21.4.2010, 15:05

Код my %all = (             "123" => 1,             "1 23" => 2,             "12 3 43" => 3,             "12 333" => 4,             "1254 3" => 5,             ); my $a="1   2    3"; print "OK\n" if is_string($a, \%all); sub is_string {   my ($a, $all) = @_;   $a = join '\s*', split ' ', $a;   $a = qr($a);   while ((my $key) = each %$all) {     $key =~ $a && print "$key\n"; # For debug     #$key =~ $a && return $key;   }   return undef; }

Автор: Suppir 23.4.2010, 09:23

amg ближе всех оказался к истине!

Автор: amg 23.4.2010, 09:33

Цитата(Suppir @  23.4.2010,  09:23 ) amg ближе всех оказался к истине! А в чем же настоящая истина?

Автор: odmink0 23.4.2010, 11:00

Хочу заметить, что решение amg находит даже те ключи хеша, которые не равны строке $a (с условием, что из неё и из ключа уберут пробелы), а содержат эту строку. То есть если $a='123', то найдутся и ключи, равные '12345' и '555123555'. Чтобы обеспечить равенство, можно использовать: Код $a = qr(^$a$); Кроме того не вижу смысла использовать each(), когда можно использовать keys() - раз уж мы все равно ведём поиск только среди ключей.

Автор: amg 23.4.2010, 12:04

Цитата(odmink0 @  23.4.2010,  11:00 ) Кроме того не вижу смысла использовать each(), когда можно использовать keys() - раз уж мы все равно ведём поиск только среди ключей. Цитата(Suppir @  21.4.2010,  08:21 ) Проблема в том, что хеш очень большой и строки в нем длинные. keys создаст дополнительный массив из ключей хэша, а это лишний расход и памяти, и времени.

Автор: NuINu 24.4.2010, 12:42

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

Автор: amg 24.4.2010, 12:58

Цитата(NuINu @  24.4.2010,  12:42 ) какая глупость А Вы предложите умное решение, а то рекомендация "просто изменить структуру хеша" не очень информативна

Автор: KSURi 24.4.2010, 17:24

Цитата(amg @  23.4.2010,  12:04 ) keys создаст дополнительный массив из ключей хэша, а это лишний расход и памяти, и времени.  Ну создаст он временный массив с указателями на строки. Ничего вы из-за этого не потеряете. А со временем, так вообще фигня какая-то. Мой вариант простой и без выпендрежа) Код sub foo {     my ( $str, $hash ) = @_;     $str =~ s{\s}{}g;     for my $k ( keys %$hash ) {         $k =~ s{\s}{}g;         return 1 if $str eq $k;     }     0; }

Автор: amg 26.4.2010, 07:51

Господа! Ну почему вам так не нравится функция each? ^  Еще раз процитирую кусочек самого первого поста: Цитата(Suppir @  21.4.2010,  08:21 ) Проблема в том, что хеш очень большой и строки в нем длинные. Необходимо оптимизировать поиск. Сейчас потестировал на хэше из 2_500_000 элементов с длиной ключей 70 символов. Функция KSURi на моем компьютере работает 11 с и скрипт требует 630 М памяти. Если в этой функции просто заменить for my $k ( keys %$hash ) { на  while ( (my $k) = each %$hash ) { то будет 9 с и 350 М. Выигрыш по времени действительно невелик, но по памяти существенен. Я, может неправильно, понял топикстартера так, что нужно искать не совпадение строки с ключом (без пробелов), а наличие подстроки в ключе. Пэтому постарался сделать так, чтобы в цикле было только одно регулярное выражение (видимо, подготовительные операции для этого публика и приняла за выпендреж). Чтобы определять наличие подстроки в функции KSURi, туда нужно внести еще одно регулярное выражение, т.е. $str eq $k заменить на $k =~ /$str/, а это даст еще лишние 2 с. Кстати, KSURi, судя по прибавке памяти, получается (перл 5.8), что keys создает все же массив ключей, а не массив ссылок на них. Хотя в данной ситуации ( for (keys %hash) ), казалось бы, можно было ограничиться массивом ссылок. Может, в более новых перлах так?

Автор: Suppir 26.4.2010, 11:59

Ребята, я сделал эту функцию без хеша. Просто перебором по двум массивам и сравнением измененных элементов этих массивов. Вариант с хешем отбирал очень много оперативки.

Автор: NuINu 26.4.2010, 14:13

Цитата(amg @  24.4.2010,  10:58 ) А Вы предложите умное решение, а то рекомендация "просто изменить структуру хеша" не очень информативна smile элементарно Код #!/usr/bin/perl -w use strict; use Data::Dumper; my %all = (     "123" => 1,     "1 23" => 2,     "12 3 43" => 3,     "12 333" => 4,     "1254 3" => 5, ); my $a="1   2    3"; my $b="1   1    3"; my %s_all = make_searh_hash(\%all); #print "Dump search: ", Dumper(\%s_all), "\n"; print "find '$a' OK\n" if has_string($a, \%s_all); print "find '$b' OK\n" if has_string($b, \%s_all); sub make_searh_hash {     my $p_all = shift;     my %all = %$p_all;     my %s;     while ((my $key) = each %all) {         $key = join '', split '\s*', $key;         $s{$key} = 1;     }     return %s; } sub has_string {     my ($a, $all) = @_;     $a = join '', split '\s*', $a;     return exists $all{$a}; }

Автор: amg 26.4.2010, 14:52

Цитата(NuINu @  26.4.2010,  14:13 ) элементарно Как выяснилось, даже один хэш не влазит в память, а Вы предлагаете завести еще один такой же.  Но Вы безусловно правы в том, что нужно было с самого начала менять подход к решению задачи... Тут упрек топикстартеру: прежде чем просить о помощи, нужно было подумать, ведь потребляемую хэшем память можно http://forum.vingrad.ru/forum/topic-219798/anchor-entry1575015/15.html.

Автор: Suppir 27.4.2010, 08:14

Я знал, что хеш много памяти кушает, но не предполагал, что настолько

Автор: mvsgt 27.4.2010, 16:27

когда хэш начинает кушать память, надо использовать Berkeley DB , например DB_File . Некоторое замедление, конечно, будет, но память освободится. Может быть, фрагмент  $a = join '', split '\s*', $a; лучше заменить на  $a =~ s/\s+//go;

Автор: NuINu 27.4.2010, 19:52

Цитата(mvsgt @  27.4.2010,  14:27 ) лучше заменить на  $a =~ s/\s+//go;  наверное лучше    так же согласен на счет базы, а так же можно увеличить память. кстати первый массив можно и не оформлять в виде хеша. как я понял он достаточно бестолковый. у меня нет данных на 2 000 000 строк, а генерить лень.

Автор: amg 28.4.2010, 05:11

Цитата(NuINu @  27.4.2010,  19:52 ) у меня нет данных на 2 000 000 строк, а генерить лень perl -lne "print rand for 1..2e6" > big_file

Автор: NuINu 28.4.2010, 14:29

я не уверен что это будут те самые данные с пробелами

Автор: amg 28.4.2010, 15:30

Цитата(NuINu @  28.4.2010,  14:29 ) я не уверен что это будут те самые данные с пробелами Я бы даже сказал, что почти наверняка пробелов там не будет  .

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)