0 / 0 / 0
Регистрация: 18.10.2020
Сообщений: 4
1

Оптимизация кода по поиску анаграмм

14.04.2021, 19:16. Показов 1092. Ответов 7

Суть состоит в том, что нужно из списка слов выбрать анаграммы. В ключ записывается первое слово, а в значение массив с анаграммами. Причем, если в значении всего одно слово, этот ключ не должен попасть в результат. Проблема состоит в том, что при большом количестве слов, программа работает слишком долго. Есть какие-нибудь рекомендации по оптимизации кода?
Perl
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
use 5.016;
use warnings;
use utf8;
use open qw(:std :utf8);
 
sub anagram {
    my $words_list = shift; #ссылка на массив со словами
    my %result; #хеш с анаграммами
    my $i = 0;
    my $count;
    my $countuniq;
    my $let1;
    my $let2;
        my $word;
    for (@$words_list){
        $count = 0;
                $word = lc($words_list->[$i]);
        for (keys %result) { 
            if (length $_ == length $word){ 
                $let1 = join "", sort split "", $_; #разделить по буквенно, отсортировать и соединить
                $let2 = join "", sort split "",$word);
                if ($let1 eq $let2) {
                    $count++;
                    $countuniq = 0;
                    for my $uniq (@{$result{$_}}){# проверка есть ли уже данное слово в значениях
                        $countuniq++ if ($uniq eq $word);
                        }
                    if ($countuniq == 0){ #если слова нет в значениях ключа
                        push(@{$result{$_}},$word);
                    }
                }
            }
        }
        if ($count ==0){ #если слово не совпало ни с одним ключом
            push(@{$result{$word}},$word);
        }
        $i++;
    }
    for (keys %result){
        if (scalar(@{$result{$_}}) == 1){ #удаление ключа если в значении ключа только одно слово
            delete($result{$_});
        }
                else {@{$result{$_}} = sort @{$result{$_}};}#сортировка массива значений
    }
    return \%result;
 
}
 
1;
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
14.04.2021, 19:16
Ответы с готовыми решениями:

Создать hash-функцию по поиску анаграмм
Разработать функции хеширования со свойствами h(a,b,c)= h(c,b,a)= h(b,с,a)= h(a,c,b) = h(b,a,c)=...

Оптимизация методом Ньютона (нахождение точки минимума). Оптимизация кода
MATLAB только начал осваивать. Попытался реализовать нахождение точки минимума методом Ньютона...

Оптимизация кода. Замер времени выполнения части кода.
Доброе утро. Есть желание посмотреть сколько времени занимает выполнение какого-то блока...

Типы оптимизация: черная оптимизация, серая оптимизация и белая оптимизация
Много много лет назад, на заре становления профессии "оптимизатора" в какой то умной книжке был...

7
Невнимательный
2197 / 594 / 203
Регистрация: 08.02.2013
Сообщений: 4,464
Записей в блоге: 2
15.04.2021, 11:27 2
Цитата Сообщение от n7arti Посмотреть сообщение
#ссылка на массив со словами
IMHO должно быть чуть шустрее , если делать без массива со словами... например построчно чтением файла
типа как сравнить два варианта
Perl
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
use 5.016;
use warnings;
use utf8;
use open qw(:std :utf8);
 
# 1 ==================================
my $pos = tell DATA;
my @L = map { chomp; $_ } <DATA>;
# say for @L;
 
my %RES = ();
sub xxxx {
    my $k= join "", sort split("", lc);
    $RES{$k} = [] unless exists $RES{$k};
    push @{$RES{$k}}, $_;
}
map xxxx, @L;
 
for (keys %RES){ # удаление лишнего
   delete $RES{$_} if 2 > @{$RES{$_}};
}
use Data::Dumper;
say Dumper \%RES;
 
# 2 ==================================
%RES = ();
seek DATA,$pos,0;
xxxx for <DATA>;
 
for (keys %RES){ # удаление лишнего
   delete $RES{$_} if 2 > @{$RES{$_}};
}
use Data::Dumper;
say Dumper \%RES;
 
__DATA__
ток
Кот
том
Тор
мор
ром
... теоретически )
Не проверял на каких-то больших данных... но чем меньше грузить в память тем обычно лучше
... Уменьшить расход памяти/Ускорить наверно только с циклом по заранее отсортированными по длинне данным

Добавлено через 3 часа 42 минуты
Цитата Сообщение от x_lab Посмотреть сообщение
Perl
28
xxxx for <DATA>;
точнее
Perl
28
chomp, xxxx for <DATA>;
0
0 / 0 / 0
Регистрация: 18.10.2020
Сообщений: 4
16.04.2021, 20:18  [ТС] 3
x_lab, На вход в функцию прилетает именно массив со словами, а не файл, который я бы могла читать построчно. Попробую с помощью заранее отсортированных данных. Спасибо
0
4510 / 1625 / 281
Регистрация: 10.12.2013
Сообщений: 5,721
16.04.2021, 22:16 4
Perl
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
use strict;
my @words_list = (
 
        "ene","bene","raba","angle",
        "neal","lena","lane","galen",
        "elan","trace","crate","cater","large",
        "lager","black","and","blue","angel",
        "caret","regal","able","abel","lange",
        "bela","personal","jesus","glean","vile","veil",
        "someone","nothing","live","levi","glare","more","or",
        "less","alger","lean","carte","bale","elba","evil","Words",
        "like","violence","Break","the","silence","Come","crashing",
        "in","Into","my","little","world","Painful","to","me","Pierce","right","through","me"
);
 
sub anagram($) {
    my $words_list = shift;
    my %result;
    for ( @$words_list ) {
        push @{ $result{ join '', sort split'' }}, $_;
    }
    return \%result;
}
 
use Data::Printer;
 
for ( values %{anagram(\@words_list)} ) {
    p $_ if @$_>1;
}
0
ft4l
17.04.2021, 03:20
  #5

Не по теме:

Цитата Сообщение от volodin661 Посмотреть сообщение
@words_list = (
Хак по получению слов из __DATA__ .)
Perl
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
use strict;
use utf8;
use 5.016;
use open qw(:std :utf8);
 
my @words_list = do { local $/; eval 'qw/'. <DATA> .'/' };
 
sub anagram($) {
    my $words_list = shift;
    my %result;
    for ( @$words_list ) {
        $_ = lc;
        push @{ $result{ join '', sort split'' }}, $_;
    }
    grep {1<@$_} values %result;
}
 
use Data::Printer;
p $_ for anagram(\@words_list);
 
__DATA__
ром мор Тор том Кот ток Суть состоит нужно из списка слов выбрать анаграммы
В записывается первое слово а значение массив с анаграммами Причем
если значении всего одно этот ключ не должен попасть  результат Проблема
что при большом количестве программа работает слишком долго Есть какие нибудь
рекомендации по оптимизации кода
ene  bene  raba  angle neal  lena  lane  galen
elan  trace  crate  cater  large lager  black  and  blue  angel
caret  regal  able  abel  lange bela  personal  jesus  glean  vile  veil
someone  nothing  live  levi  glare  more  or less  alger  lean  carte  bale
elba  evil  Words like  violence  Break  the  silence  Come  crashing
in  Into  my  little  world  Painful  to  me  Pierce  right  through

0
4510 / 1625 / 281
Регистрация: 10.12.2013
Сообщений: 5,721
17.04.2021, 13:11 6
да, хак поражает неокрепшую психику )



код на PERL должен вызывать мистический ужос,
иначе ты потратил время впустую.

Perl
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#!/usr/bin/env perl -w
use strict;
 
sub anagram($) {
 
    map     { push @{ $::-> { join '', sort split '', lc }}, $_ }
    shift   ->@*;
 
    return  grep 1<@$_, values %$::
}
 
print "@$_", v10
    for
        anagram [split/\s+/,<<''];
ene       bene      raba      angle     Neal      Lena      lane      galen
elan      trace     crate     cater     large     lager     black     and
blue      angel     caret     regal     able      abel      lange     bela
personal  jesus     glean     vile      veil      someone   nothing   live
levi      glare     more      or        less      alger     lean      carte
bale      elba      evil      Words     like      violence  Break     the
silence   Come      crashing  in        Into      my        little    world
Painful   to        me        Pierce    right     through
0
47 / 33 / 8
Регистрация: 13.06.2019
Сообщений: 194
18.04.2021, 04:55 7
но чёрт побери, Холмс!..
0
4510 / 1625 / 281
Регистрация: 10.12.2013
Сообщений: 5,721
19.04.2021, 16:54 8
всё-таки желательно, гражданин артист, чтобы вы незамедлительно разоблачили перед публикой технику ваших фокусов.

Кликните здесь для просмотра всего текста
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
19.04.2021, 16:54
Помогаю со студенческими работами здесь

Оптимизация кода
var a:array of integer; i,n,r,k,j:integer; begin readln(n); for i:=1 to n do read(a);...

Оптимизация кода на C#
Здравствуйте уважаемые господа. Использую WinForms, webbrowser. Написал программу, всё...

Оптимизация кода
Подскажите, можно как нибудь более компактно реализовать данный участок кода: if ((buf=31) or...

Оптимизация кода
Доброго времени суток. Имеется такой код: #include &lt;iostream&gt; #include &lt;string&gt; using...

оптимизация кода
Всем Добрый день. Никогда раньше не писал на vba, однако появилась рабочая необходимость написать...

Оптимизация кода
Помогите пожалуйста оптимизировать код. Особо смысла в этом коде нет, просто вычисляет результат...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
8
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru