За последние 24 часа нас посетили 10843 программиста и 693 робота. Сейчас ищут 447 программистов ...

[задачка] Сумма конкатенаций

Тема в разделе "Прочие вопросы по PHP", создана пользователем artoodetoo, 23 дек 2020.

Метки:
  1. artoodetoo

    artoodetoo Суперстар
    Команда форума Модератор

    С нами с:
    11 июн 2010
    Сообщения:
    10.780
    Симпатии:
    1.160
    Адрес:
    там-сям
    Есть массив положительных целых a, надо расчитать сумму всех возможных ai ∘ aj , то есть конкатенаций строкового представления ai и aj.

    Пример:
    Для a = [10, 2], сумма = 1344
    a[0] ∘ a[0] = 10 ∘ 10 = 1010,
    a[0] ∘ a[1] = 10 ∘ 2 = 102,
    a[1] ∘ a[0] = 2 ∘ 10 = 210,
    a[1] ∘ a[1] = 2 ∘ 2 = 22.
    Сумма будет равна 1010 + 102 + 210 + 22 = 1344.

    Для a = [8], сумма = 88.
    Для a = [1, 2, 3], сумма = 198.

    Вот такое решение "в лоб" считает верно, но медленно:
    PHP:
    1. function mysum($a) {
    2.   $sum = 0;
    3.   foreach ($a as $ai) {
    4.     foreach ($a as $aj) {
    5.       $sum += $ai.$aj;
    6.     }
    7.   }
    8.   return $sum;
    9. }
    Я сделал заготовку с тестовыми данными
    http://sandbox.onlinephpfunctions.com/code/9072eec3fe81efd7a07e0888756cb22f48d0f126
    Она тратит примерно 0.095 сек на массив из 1000 элементов. Это очень много, надо не больше 0.0003 сек

    Кто сумеет оптимизировать?

    (обновил пример на 1000 элементов)
     
    #1 artoodetoo, 23 дек 2020
    Последнее редактирование: 23 дек 2020
  2. Chushkin

    Chushkin Активный пользователь

    С нами с:
    17 дек 2010
    Сообщения:
    1.060
    Симпатии:
    89
    Адрес:
    Мещёра, Центр, Болото N3
    Никто.
    Это пересечение массивов. Т.е. на 1000 будет 1 млн итераций, что и должно давать порядка 0.1 сек в ПХП.
    Нужно быстрее - используй распараллеливание или пиши на ассемблере.

    п.с. Кстати, 0.1 сек для строк это очень неплохая скорость, особенно в ПХП.
     
    [vs] нравится это.
  3. [vs]

    [vs] Суперстар
    Команда форума Модератор

    С нами с:
    27 сен 2007
    Сообщения:
    10.533
    Симпатии:
    623
    Я сделал алгоритм с одним циклом на миллион итераций, вместо тысячи вложенных циклов по 1000 итераций, результат ещё хуже. Можно число итераций уменьшить сколь угодно, если внутрь засунуть больше арифметики, но это не помогает.
    Надо суммировать 1 млн чисел, пхп не может это сделать быстрее.
    --- Добавлено ---
    Хотя есть ещё идея которую надо проверить...
     
  4. Fell-x27

    Fell-x27 Суперстар
    Команда форума Модератор

    С нами с:
    25 июл 2013
    Сообщения:
    12.162
    Симпатии:
    1.770
    Адрес:
    :сердА
    Я решил.
    0.000060s в сендбоксе.

    Скинул в личку.
    --- Добавлено ---
    Так суть задачи в оптимизации, а не в ускорении пересечения массивов. Это немного разные вещи.
     
    #4 Fell-x27, 24 дек 2020
    Последнее редактирование: 24 дек 2020
  5. [vs]

    [vs] Суперстар
    Команда форума Модератор

    С нами с:
    27 сен 2007
    Сообщения:
    10.533
    Симпатии:
    623
    У меня пока получилось 0.000030s если числа в наборе от 1 до 9 :D но в сете @artoodetoo проскакивают десятки...
     
  6. [vs]

    [vs] Суперстар
    Команда форума Модератор

    С нами с:
    27 сен 2007
    Сообщения:
    10.533
    Симпатии:
    623
    Код (Text):
    1. 2.8848648071289E-5
    2. Result: 60059300
    3. Check sum: 60059300
    Скинул в личку

    Сначала тоже было 0.00005 но потом вспомнил про одну встроенную функцию ))
     
    #6 [vs], 24 дек 2020
    Последнее редактирование: 24 дек 2020
  7. Chushkin

    Chushkin Активный пользователь

    С нами с:
    17 дек 2010
    Сообщения:
    1.060
    Симпатии:
    89
    Адрес:
    Мещёра, Центр, Болото N3
    Куда податься бедному крестьянину ... кругом партизаны. :)
     
  8. Fell-x27

    Fell-x27 Суперстар
    Команда форума Модератор

    С нами с:
    25 июл 2013
    Сообщения:
    12.162
    Симпатии:
    1.770
    Адрес:
    :сердА
    Я вот сейчас дико загнался, но ниже 0.00004 не могу выйти в сендбоксе. Не то, чтобы оно было принципиально, конечно...
    Количество итераций свел до 64 всего.
     
  9. artoodetoo

    artoodetoo Суперстар
    Команда форума Модератор

    С нами с:
    11 июн 2010
    Сообщения:
    10.780
    Симпатии:
    1.160
    Адрес:
    там-сям
    Народ, давайте вскрываться :)

    60059300
    0.000155

    http://sandbox.onlinephpfunctions.com/code/623a0d5cd02b3facf86d922485fb792f8acc5f6b
    PHP:
    1. function mysum($a) {
    2.     foreach ($a as $ai) {
    3.         $len = strlen($ai);
    4.         if (isset($dict[$len])) $dict[$len]++;
    5.         else $dict[$len] = 1;
    6.     }
    7.     $result = 0;
    8.     $count = count($a);
    9.     foreach ($a as $ai) {
    10.         foreach ($dict as $len => $n) {
    11.             $result += $ai * $n * 10 ** $len;
    12.         }
    13.         $result += $ai * $count;
    14.     }
    15.     return $result;
    16. }
    --- Добавлено ---
    я недоволен, но всё равно это был прорыв. потому что когда я получил на сайте отлуп по таймауту, первая реакция была как у Чушкина "тут нечего ускорять, n**2 переборов и баста".
     
  10. Fell-x27

    Fell-x27 Суперстар
    Команда форума Модератор

    С нами с:
    25 июл 2013
    Сообщения:
    12.162
    Симпатии:
    1.770
    Адрес:
    :сердА
    artoodetoo нравится это.
  11. artoodetoo

    artoodetoo Суперстар
    Команда форума Модератор

    С нами с:
    11 июн 2010
    Сообщения:
    10.780
    Симпатии:
    1.160
    Адрес:
    там-сям
  12. Fell-x27

    Fell-x27 Суперстар
    Команда форума Модератор

    С нами с:
    25 июл 2013
    Сообщения:
    12.162
    Симпатии:
    1.770
    Адрес:
    :сердА
    Я почти два часа голову ломал и кучу вариантов перебрал, прежде чем дошел до этой реализации, которая выглядит почти как анекдот в плане простоты...

    Но, что круто, в процессе открыл для себя некоторые оч интересные техники, которые могут быть полезны в продакшене. В этом и прелесть таких задачек.
     
  13. [vs]

    [vs] Суперстар
    Команда форума Модератор

    С нами с:
    27 сен 2007
    Сообщения:
    10.533
    Симпатии:
    623
    PHP:
    1. <?php
    2.  
    3. $m = microtime(1);
    4. $sum = 0;
    5. $len = count($a);
    6. $val_c = array_count_values($a);
    7. foreach ($val_c as $v => $c1) {
    8.     $sum += $v * $c1 * $len;
    9.     foreach ($val_c as $vv => $c2) {
    10.         $sum += $c2 * $vv * (10 ** strlen($v)) * $c1;
    11.     }
    12. }
    13. echo microtime(1) - $m;
    14. echo "\r\n";
    15. echo "Result: $sum";
    Тест: https://sandbox.onlinephpfunctions.com/code/e173724e0e85d427797d979d08269842ffdde3d0
    Примерно каждый пятый запуск 0.00003 а иногда и ниже. Вместо конкатенации чисел здесь возведение в степень по числу разрядов. Типа одно число идёт как есть, а другое смещено на число разрядов в первом числе. Логично? Вообще задачка оказалась больше на умение выводить арифметические теоремы. Я часто делаю разные статистики с по большому числу строк, и стараюсь обходится минимальными ресурсами с помощью подобных оптимизаций. Там где у кого-то фоновый процесс на пол часа, у меня загрузка в браузере за 15 сек. Минус в том, что через месяц сам ногу сломишь пытаясь понять, как оно работает.
     
    johovich нравится это.
  14. johovich

    johovich Активный пользователь

    С нами с:
    24 авг 2016
    Сообщения:
    146
    Симпатии:
    17
    Мое решение.

    Код (Text):
    1. function mysum3($a) {
    2.     $size = count($a); //array size
    3.     $s = array_sum($a) * $size; //result
    4.     $ranks = [
    5.         1=> 0,
    6.         2=> 0,
    7.         3=> 0,
    8.         4=> 0,
    9.         5=> 0,
    10.         6=> 0,
    11.         7=> 0,
    12.         8=> 0,
    13.         9=> 0,
    14.     ]; //this array to store and count value rank
    15.     array_walk($a,
    16.         function(&$n) use (&$ranks)
    17.         {
    18.             $rank = round(log10($n) + 0.5, 0);
    19.             ++$ranks[$rank];
    20.         }
    21.     );
    22.     $ranks = array_filter($ranks);
    23.    
    24.     foreach($ranks as $i=>$rank){
    25.         $pow = pow(10, $i);
    26.         array_walk($a,
    27.             function (&$n) use($pow, $rank, &$s) {$s += $n * $pow * $rank;}
    28.         );
    29.     }
    30.    
    31.     return  $s;
    32. }
    --- Добавлено ---

    Поэлегантнее получилось.
    --- Добавлено ---
    хитроумно, только у тебя на датасетах без повторений плохо работать будет.
    --- Добавлено ---
    Ты эту х. придумал в голове или листочек там какой с ручкой использовал?
     
  15. [vs]

    [vs] Суперстар
    Команда форума Модератор

    С нами с:
    27 сен 2007
    Сообщения:
    10.533
    Симпатии:
    623
    @johovich я печатал строку простым перебором для чисел 1,2,3 и искал закономерности. Понял что каждый раз одна цифра прибавляет себя к сумме x10 раз, потому что становится первой в двухзначном числе, а другая всего 1 раз. Поэтому написал что нашёл решение для чисел от 1 до 9. Потом допер про разряды, к решению с конкатенацией не приходил.
     
  16. johovich

    johovich Активный пользователь

    С нами с:
    24 авг 2016
    Сообщения:
    146
    Симпатии:
    17
  17. johovich

    johovich Активный пользователь

    С нами с:
    24 авг 2016
    Сообщения:
    146
    Симпатии:
    17
    Больше не буду клевать на задачи. Проебался весь день с этим. Стыдно сказать родным что я на таких умных щах весь день занимался утешением своего ЧСВ.
     
  18. ADSoft

    ADSoft Старожил

    С нами с:
    12 мар 2007
    Сообщения:
    3.511
    Симпатии:
    672
    Адрес:
    Татарстан
    Круто.... молодцы.

    Жаль что у меня не получилось ...

    Перво-напрево попробовал оптимизировать циклы, получилось вот что
    PHP:
    1. function get_line($start,$arr) {
    2.     $sum = 0;
    3.     for($i=$start+1;$i<count($arr);$i++) {      
    4.         $sum += intval($arr[$start] . $arr[$i]) + intval($arr[$i] . $arr[$start]);
    5.     }
    6.     return $sum;
    7. }
    8.  
    9. for($i=0;$i<count($input);$i++) {
    10.    
    11.     $sum += ($input[$i] . $input[$i]);
    12.     $sum += get_line($i,$input);
    13. }
    14.  
    15. echo 'Test = '.$sum .'<br>';
    16.  
    17. $sum = 0;
    Да работает, да операций меньше... но время... плачевно... никакой разницы с оригинальным не оптимизированным решением (+/- 0,1с)

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

    PHP:
    1. // Сумма цифр/чисел в массиве
    2. for($i=0;$i<count($input);$i++) {
    3.  $sum += $input[$i];
    4. }
    5.  
    6. $n = count($input);
    7.  
    8. echo 11 * $n * $sum;
    И да - это работает.... формула выводится чисто математически,

    Печально что не работает - если есть двузначные и более числа.... хотя там тоже математически выводится
    только формула вычисления суммы цифр немного видоизменяется (добавляются степени 10 для чисел)
    точно так-же выносится коэф = но не 11, а другой .. .какой недопер, а вот чему равен второй коэф. я так и не смог найти зависимость, но она точно есть

    Там получается что то типа $k0*$sum*$k1 + $k2; но ни времени ни желания, да и мозгов сейчас уже на это не хватает
     
  19. Chushkin

    Chushkin Активный пользователь

    С нами с:
    17 дек 2010
    Сообщения:
    1.060
    Симпатии:
    89
    Адрес:
    Мещёра, Центр, Болото N3
    На моём локальном компе получилось так:
    Код (Text):
    1.  
    2. mysum     | Time: 0.113124, Iterations: 1000000, Sum: 454594950000
    3. sum_jo1   | Time: 0.186695, Iterations: 1000000, Sum: 454589955000
    4. sum_jo2   | Time: 0.000678, Iterations:    5000, Sum: 454590454500
    5. sum_jo3   | Time: 0.000678, Iterations:    5000, Sum: 454590454500
    6. sum_vs    | Time: 0.088474, Iterations: 1000000, Sum: 454594950000
    7. sum_arte  | Time: 0.000263, Iterations:    4000, Sum: 454594950000
    8. sum_fel   | Time: 0.133820, Iterations: 1000000, Sum: 454594950000
     
  20. ADSoft

    ADSoft Старожил

    С нами с:
    12 мар 2007
    Сообщения:
    3.511
    Симпатии:
    672
    Адрес:
    Татарстан
    а чего результаты разные?
     
  21. johovich

    johovich Активный пользователь

    С нами с:
    24 авг 2016
    Сообщения:
    146
    Симпатии:
    17
    Баг какой-то в работе измерителя кол-ва разрядов в числе. strlen($n) правильно показывает, а round(log10($n) + 0.5, 0) иногда дает неправильный результат.

    Нашел причину.

    strlen(0) дает 0, а round(log10(0) + 0.5, 0) дает 1.
     
    #21 johovich, 25 дек 2020
    Последнее редактирование: 25 дек 2020
  22. artoodetoo

    artoodetoo Суперстар
    Команда форума Модератор

    С нами с:
    11 июн 2010
    Сообщения:
    10.780
    Симпатии:
    1.160
    Адрес:
    там-сям
    ты в курсе, что round возвращает вещественное число?
    --- Добавлено ---
    и непонятно почему ты в своей сводке игнорируешь типовой набор, на котором все сравнивали результаты. а зачем-то хитровыделанным способом генеришь числа по порядку.
    ( мог бы range() взять )
     
  23. johovich

    johovich Активный пользователь

    С нами с:
    24 авг 2016
    Сообщения:
    146
    Симпатии:
    17
    а
    А че ты делаешь benchmark? Кол-во итераций автоматом делает?
    --- Добавлено ---
    Типовой набор я тоже испытывал. Он с недостатком, поэтому я взял другой.
    Range или не что-то еще, какая разница?

    То что round выдает float это пох. там все приводится нормально.
     
    #23 johovich, 25 дек 2020
    Последнее редактирование: 25 дек 2020
  24. artoodetoo

    artoodetoo Суперстар
    Команда форума Модератор

    С нами с:
    11 июн 2010
    Сообщения:
    10.780
    Симпатии:
    1.160
    Адрес:
    там-сям
    штош. пох так пох.
     
  25. johovich

    johovich Активный пользователь

    С нами с:
    24 авг 2016
    Сообщения:
    146
    Симпатии:
    17
    Ты прав, типы лучше приводить руками.