[задачка] Анаграммы

Локаль, но дело не в ней а в том чтоб прогнать алгоритмы под одним стеком.

https://sandbox.onlinephpfunctions.com/
время 0.0084900856018066
всего 29116

 

Не думаю что у всех кардинально разное решение. Судя по всему (в том числе по времени) примерно одинаковое..

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

Вот если у кого то появится результат на порядки быстрее работающего, то вот там скорее всего какое то существенное изменение алгоритма

 

с массивом из 10к номеров меня не ограничивает

 

http://sandbox.onlinephpfunctions.com/code/6518e096d5c5a7d5866b4a70068946d28cf3d160
Fell успешно нарыл natsort, что удешевляет.

 

Мой вариант
https://sandbox.onlinephpfunctions.com/code/b0cb4b25b719807fde79087377e0a9a4f45a402a

9999
29116
0.008296012878418

 

А чё.. если не 10000 элементов, и миллион и больше? Новые if добавлять будете??

 

Код (Text):

1. <?php
2.  
3. function bmark()
4. {
5.     $args = func_get_args();
6.     $len = count($args);
7.  
8.     if ($len < 3) {
9.         trigger_error("At least 3 args expected. Only $len given.", 256);
10.         return false;
11.     }
12.  
13.     $cnt = array_shift($args);
14.     $fun = array_shift($args);
15.  
16.     $start = microtime(true);
17.     $i = 0;
18.     while ($i < $cnt) {
19.         $i++;
20.         $res = call_user_func_array($fun, $args);
21.     }
22.     $end = microtime(true) - $start;
23.     return $end;
24. }
25.  
26. //функция для конвертации времени, принимает значения в секундах
27. function convert_time($time)
28. {
29.     if ($time == 0) {
30.         return 0;
31.     }
32.     $unit = array(-4 => 'ps', -3 => 'ns', -2 => 'mcs', -1 => 'ms', 0 => 's');
33.     $i = min(0, floor(log($time, 1000)));
34.     $t = @round($time / pow(1000, $i), 1);
35.     return $t . $unit[$i];
36. }
37.  
38. ///////////////
39. //////////////
40. /////////////
41.  
42.  
43. /// ПЕРВЫЙ ВАРИАНТ
44. function anagrams($a) {
45.     // count repeated values
46.     $counts = array_count_values(
47.         // make anagram items equal
48.         array_map(function ($item) {
49.             $array = str_split((string) $item);
50.             sort($array);
51.             return join($array);
52.         }, $a)
53.     );
54.  
55.     // sum of pairs
56.     $result = 0;
57.     foreach ($counts as $n) {
58.         if ($n < 2) continue;
59.         $result += pairCount($n);
60.     }
61.     return $result;
62. }
63.  
64. function pairCount($n)
65. {
66.     static $cache = [0, 0];
67.     return $cache[$n] ?? $cache[$n] = pairCount($n - 1) + $n - 1;
68. }  
69.  
70. ////ПЕРВЫЙ КОНЕЦ
71.  
72.  
73. ////ВТОРОЙ ВАРИАНТ
74. function cnt(int $dupli): int{
75.         $c = 0;
76.         for($i = 1; $i < $dupli; ++$i){
77.             $c += $i;
78.         }
79.         return $c;
80. }
81.  
82. function count_anagra(array $a): int{
83.     $res = [];
84.     foreach($a as $e){
85.         $digs = str_split((string)$e);
86.         sort($digs);
87.         $key = implode($digs);
88.         if (isset($res[$key])){
89.             ++$res[$key];
90.         }else{
91.             $res[$key] = 1;
92.         }
93.     }
94.     return array_sum(array_map('cnt', $res));
95. }
96. ///ВТОРОЙ ВАРИАНТ КОНЕЦ
97.  
98. ///ТРЕТИЙ ВАРИАНТ
99. function count_anagra2(array $a): int{
100.     array_walk($a,
101.         function (&$i) {
102.             $a = str_split((string)$i);
103.             sort($a);
104.             $i = implode($a);
105.         }
106.     );
107.    
108.     $a = array_count_values($a);  
109.    
110.     array_walk($a,
111.         function (int &$dupli): void{
112.             $c = 0;
113.             for($i = 1; $i < $dupli; ++$i){
114.                 $c += $i;
115.             }
116.             $dupli = $c;
117.         }      
118.     );
119.    
120.     return array_sum($a);
121. }
122. ///ТРЕТИЙ ВАРИАНТ КОНЕЦ
123.  
124.  
125.  
126.  
127. ////СРАВНЕНИЕ
128. $rounds = 100;
129. $a = array_keys(array_fill(0,1e4,null));
130. echo str_pad("anagrams() dataset \$a result: ", 45) . anagrams($a) . PHP_EOL;
131. echo str_pad("anagrams() dataset \$a: ", 45) . convert_time(bmark($rounds, "anagrams", $a) / $rounds) . PHP_EOL;
132.  
133. echo str_pad("count_anagra() dataset \$a result: ", 45) . count_anagra($a) . PHP_EOL;
134. echo str_pad("count_anagra() dataset \$a: ", 45) . convert_time(bmark($rounds, "count_anagra", $a) / $rounds) . PHP_EOL;
135.  
136. echo str_pad("count_anagra2() dataset \$a result: ", 45) . count_anagra2($a) . PHP_EOL;
137. echo str_pad("count_anagra2() dataset \$a: ", 45) . convert_time(bmark($rounds, "count_anagra2", $a) / $rounds) . PHP_EOL;

Первый вариант - чужой. Второй и третий - мой.

Сразу посмотреть можно тут: http://sandbox.onlinephpfunctions.com/code/891add2f8914f287cbb48a1b9aa40ddf9d55fd1a

 

Код (Text):

1.  
2. function count_anagra3(array $a): int{
3.     array_walk($a,
4.         function (&$i) {
5.             $a = str_split((string)$i);
6.             rsort($a);
7.             $i = (int)implode($a);
8.         }
9.     );
10.    
11.     $a = array_count_values($a);  
12.    
13.     array_walk($a,
14.         function (int &$i): void{
15.             $i = ($i - 1) / 2 * $i;
16.         }      
17.     );
18.    
19.    

 

Подпилил еще немного.

Код (Text):

1. function count_anagra4(array $a): int{
2.     $res = [];
3.     foreach($a as $e){
4.         $digs = str_split((string)$e);
5.         rsort($digs);
6.         $key = (int)implode($digs);
7.         $res[$key] = isset($res[$key]) ? $res[$key] + 1 : 1;
8.     }
9.  
10.     return array_reduce($res,
11.         function (int $carry, int $i): int{
12.             return $carry + ($i - 1) / 2 * $i;
13.         }
14.     , 0);
15. }

 

Ну что ребятишки, вот и мое решение....
отличие - пытался делать максимально понятным и наглядным. чтоб было видно алгоритм, а не всякие ухищрения - насчет поменьше символов или использования всяких супер-функций php (хотя без них тоже не обошлось)

Сравнивая ранее предложенные - все разбивают на цифры через строки, потому что проще видимо....
я работаю с числами - имхо работа с числами должна быть быстрее...

больше сказать нечего )))

PHP:

1. $input = json_decode(file_get_contents('test-1000.json'));
2.  
3. // Выделяем цифры из числа и составляем новое число - в порядке возрастания цифр,
4. // получаем эдакий хеш числа, у анаграмм - он одинаковый
5. function digits($a){
6.     $digits = [];
7.     while ($a>9) {
8.         $digit =  $a % 10;
9.         $a = ($a - $digit)/10;
10.         $digits[] = $digit;  
11.     }
12.     $digits[] = $a;
13.    
14.     sort($digits);
15.    
16.     return implode('',$digits);
17. }
18.  
19. // оптимизированная функция подсчета кол-ва сочетаний из N по 2 без повторений
20. function C_N_2($x){
21.     return $x*($x-1)/2;
22. }
23.  
24. // Начинаем подсчет времени
25. $start = microtime(true);
26.  
27. // заменяем числа в массиве на их "хэш-анаграммы"
28. $output = array_map('digits',$input);
29.  
30. // Тут для каждого хеша анаграммы - количество его повторений в массиве
31. $output = array_count_values($output);
32.  
33. // вычисляем для каждого кол-во сочетаний по 2 из N и суммируем
34. $sum = 0;
35. foreach ($output AS $item) {
36.     $sum += C_N_2($item);
37. }
38.  
39. echo 'Result = '.$sum . '<br/>';
40.  
41. $finish = microtime(true);
42.  
43. $delta = $finish - $start;
44.  
45. echo $delta . ' сек.';

 

Код (Text):

1. function digits($a){
2.     $digits = [];
3.     while ($a>9) {
4.         $digit =  $a % 10;
5.         $a = ($a - $digit)/10;
6.         $digits[] = $digit;
7.     }
8.     $digits[] = $a;
9.  
10.     sort($digits);
11.  
12.     return implode('',$digits);
13. }

Красивый способ. Получилось ли быстрее, чем просто делать str_split()?

 

Не думаю что существенно на этом наборе данных...

Просто вспомнил олимпиадные задачки в школе, когда в задачу добавлялось, что использование преобразователь чисел в строку и обратно запрещено

 

Хороже же ты учился. ) Близко такой х. не было в школе. Тоже люблю такую олимпиадную дребедень. Приколько было бы порешать задачи по ООП. Не представляю только, можно ли такие придумать.