Есть массив положительных целых 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: function mysum($a) { $sum = 0; foreach ($a as $ai) { foreach ($a as $aj) { $sum += $ai.$aj; } } return $sum; } Я сделал заготовку с тестовыми данными http://sandbox.onlinephpfunctions.com/code/9072eec3fe81efd7a07e0888756cb22f48d0f126 Она тратит примерно 0.095 сек на массив из 1000 элементов. Это очень много, надо не больше 0.0003 сек Кто сумеет оптимизировать? (обновил пример на 1000 элементов)
Никто. Это пересечение массивов. Т.е. на 1000 будет 1 млн итераций, что и должно давать порядка 0.1 сек в ПХП. Нужно быстрее - используй распараллеливание или пиши на ассемблере. п.с. Кстати, 0.1 сек для строк это очень неплохая скорость, особенно в ПХП.
Я сделал алгоритм с одним циклом на миллион итераций, вместо тысячи вложенных циклов по 1000 итераций, результат ещё хуже. Можно число итераций уменьшить сколь угодно, если внутрь засунуть больше арифметики, но это не помогает. Надо суммировать 1 млн чисел, пхп не может это сделать быстрее. --- Добавлено --- Хотя есть ещё идея которую надо проверить...
Я решил. 0.000060s в сендбоксе. Скинул в личку. --- Добавлено --- Так суть задачи в оптимизации, а не в ускорении пересечения массивов. Это немного разные вещи.
У меня пока получилось 0.000030s если числа в наборе от 1 до 9 но в сете @artoodetoo проскакивают десятки...
Код (Text): 2.8848648071289E-5 Result: 60059300 Check sum: 60059300 Скинул в личку Сначала тоже было 0.00005 но потом вспомнил про одну встроенную функцию ))
Я вот сейчас дико загнался, но ниже 0.00004 не могу выйти в сендбоксе. Не то, чтобы оно было принципиально, конечно... Количество итераций свел до 64 всего.
Народ, давайте вскрываться 60059300 0.000155 http://sandbox.onlinephpfunctions.com/code/623a0d5cd02b3facf86d922485fb792f8acc5f6b PHP: function mysum($a) { foreach ($a as $ai) { $len = strlen($ai); if (isset($dict[$len])) $dict[$len]++; else $dict[$len] = 1; } $result = 0; $count = count($a); foreach ($a as $ai) { foreach ($dict as $len => $n) { $result += $ai * $n * 10 ** $len; } $result += $ai * $count; } return $result; } --- Добавлено --- я недоволен, но всё равно это был прорыв. потому что когда я получил на сайте отлуп по таймауту, первая реакция была как у Чушкина "тут нечего ускорять, n**2 переборов и баста".
60059300 ~0.00005 https://sandbox.onlinephpfunctions.com/code/0e29fcd8b71ba5d5478b974c54851637ecfc2993 PHP: <?php function mysum($a) { $sum = 0; $uniq_values = array_count_values($a); foreach ($uniq_values as $val1 => $cnt1) { foreach ($uniq_values as $val2 => $cnt2) { $sum += $cnt1 * $cnt2 * ($val1.$val2); } } return $sum; }
Я почти два часа голову ломал и кучу вариантов перебрал, прежде чем дошел до этой реализации, которая выглядит почти как анекдот в плане простоты... Но, что круто, в процессе открыл для себя некоторые оч интересные техники, которые могут быть полезны в продакшене. В этом и прелесть таких задачек.
PHP: <?php $m = microtime(1); $sum = 0; $len = count($a); $val_c = array_count_values($a); foreach ($val_c as $v => $c1) { $sum += $v * $c1 * $len; foreach ($val_c as $vv => $c2) { $sum += $c2 * $vv * (10 ** strlen($v)) * $c1; } } echo microtime(1) - $m; echo "\r\n"; echo "Result: $sum"; Тест: https://sandbox.onlinephpfunctions.com/code/e173724e0e85d427797d979d08269842ffdde3d0 Примерно каждый пятый запуск 0.00003 а иногда и ниже. Вместо конкатенации чисел здесь возведение в степень по числу разрядов. Типа одно число идёт как есть, а другое смещено на число разрядов в первом числе. Логично? Вообще задачка оказалась больше на умение выводить арифметические теоремы. Я часто делаю разные статистики с по большому числу строк, и стараюсь обходится минимальными ресурсами с помощью подобных оптимизаций. Там где у кого-то фоновый процесс на пол часа, у меня загрузка в браузере за 15 сек. Минус в том, что через месяц сам ногу сломишь пытаясь понять, как оно работает.
Мое решение. Код (Text): function mysum3($a) { $size = count($a); //array size $s = array_sum($a) * $size; //result $ranks = [ 1=> 0, 2=> 0, 3=> 0, 4=> 0, 5=> 0, 6=> 0, 7=> 0, 8=> 0, 9=> 0, ]; //this array to store and count value rank array_walk($a, function(&$n) use (&$ranks) { $rank = round(log10($n) + 0.5, 0); ++$ranks[$rank]; } ); $ranks = array_filter($ranks); foreach($ranks as $i=>$rank){ $pow = pow(10, $i); array_walk($a, function (&$n) use($pow, $rank, &$s) {$s += $n * $pow * $rank;} ); } return $s; } --- Добавлено --- Поэлегантнее получилось. --- Добавлено --- хитроумно, только у тебя на датасетах без повторений плохо работать будет. --- Добавлено --- Ты эту х. придумал в голове или листочек там какой с ручкой использовал?
@johovich я печатал строку простым перебором для чисел 1,2,3 и искал закономерности. Понял что каждый раз одна цифра прибавляет себя к сумме x10 раз, потому что становится первой в двухзначном числе, а другая всего 1 раз. Поэтому написал что нашёл решение для чисел от 1 до 9. Потом допер про разряды, к решению с конкатенацией не приходил.
Запилил всех в 1 файл для бенчмарка. http://sandbox.onlinephpfunctions.com/code/adfc0555ba8f363941be92f139476361a2511109
Больше не буду клевать на задачи. Проебался весь день с этим. Стыдно сказать родным что я на таких умных щах весь день занимался утешением своего ЧСВ.
Круто.... молодцы. Жаль что у меня не получилось ... Перво-напрево попробовал оптимизировать циклы, получилось вот что PHP: function get_line($start,$arr) { $sum = 0; for($i=$start+1;$i<count($arr);$i++) { $sum += intval($arr[$start] . $arr[$i]) + intval($arr[$i] . $arr[$start]); } return $sum; } for($i=0;$i<count($input);$i++) { $sum += ($input[$i] . $input[$i]); $sum += get_line($i,$input); } echo 'Test = '.$sum .'<br>'; $sum = 0; Да работает, да операций меньше... но время... плачевно... никакой разницы с оригинальным не оптимизированным решением (+/- 0,1с) Потом ударился в теорию чисел - да там и завяз... вернее нащупал путь.. но не до конца. Смог сделать - но только для однозначных чисел.... зато там - всего один цикл на вычисление суммы цифр! PHP: // Сумма цифр/чисел в массиве for($i=0;$i<count($input);$i++) { $sum += $input[$i]; } $n = count($input); echo 11 * $n * $sum; И да - это работает.... формула выводится чисто математически, Печально что не работает - если есть двузначные и более числа.... хотя там тоже математически выводится только формула вычисления суммы цифр немного видоизменяется (добавляются степени 10 для чисел) точно так-же выносится коэф = но не 11, а другой .. .какой недопер, а вот чему равен второй коэф. я так и не смог найти зависимость, но она точно есть Там получается что то типа $k0*$sum*$k1 + $k2; но ни времени ни желания, да и мозгов сейчас уже на это не хватает
На моём локальном компе получилось так: Код (Text): mysum | Time: 0.113124, Iterations: 1000000, Sum: 454594950000 sum_jo1 | Time: 0.186695, Iterations: 1000000, Sum: 454589955000 sum_jo2 | Time: 0.000678, Iterations: 5000, Sum: 454590454500 sum_jo3 | Time: 0.000678, Iterations: 5000, Sum: 454590454500 sum_vs | Time: 0.088474, Iterations: 1000000, Sum: 454594950000 sum_arte | Time: 0.000263, Iterations: 4000, Sum: 454594950000 sum_fel | Time: 0.133820, Iterations: 1000000, Sum: 454594950000
Баг какой-то в работе измерителя кол-ва разрядов в числе. strlen($n) правильно показывает, а round(log10($n) + 0.5, 0) иногда дает неправильный результат. Нашел причину. strlen(0) дает 0, а round(log10(0) + 0.5, 0) дает 1.
ты в курсе, что round возвращает вещественное число? --- Добавлено --- и непонятно почему ты в своей сводке игнорируешь типовой набор, на котором все сравнивали результаты. а зачем-то хитровыделанным способом генеришь числа по порядку. ( мог бы range() взять )
а А че ты делаешь benchmark? Кол-во итераций автоматом делает? --- Добавлено --- Типовой набор я тоже испытывал. Он с недостатком, поэтому я взял другой. Range или не что-то еще, какая разница? То что round выдает float это пох. там все приводится нормально.