Очередная задачка для наработки скиллов. Написать функцию подсчета количества цифровых анаграмм. На входе функции массив целых положительных чисел, на выходе число. Цифровой анаграммой будем считать такую пару чисел (x, y), где все цифры из x присуствуют в y и наоборот. Порядок цифр неважен. А вот повторы важны. 72 и 27 это пара, а 72 и 227 нет. Про незначащие нули в начале числа думать не надо. Так, например, в массиве Код (Text): $a = [ 0 => 25, 1 => 35, 2 => 872, 3 => 228, 4 => 53, 5 => 278, 6 => 872 ]; есть 4 анаграммы: (a[1], a[4]), (a[2], a[5]), (a[2], a[6]), (a[5], a[6]) ещё пара примеров для самопроверки: [30, 72, 3, 227] → 0 [1, 1, 1, 1, 1] → 10 Надо оптимизировать функцию так, чтобы она могла работать с тысячами элементов за пару секунд. Файл из 10 тыс элементов во вложении. Update: давайте смотреть время выполнения на https://sandbox.onlinephpfunctions.com/ и PHP 7.4.13
Позвольте пару уточнений? 1. Считать ли анограммой то же самое число? в условии не задано что x!=y 2. Судя по примеру с [1, 1, 1, 1, 1] все-же само с собой - считается 3. Но тогда неверный подсчет для самого первого примера $a.... там число анаграмм = 6 должно быть
1. нет. равное ему — да (ai, aj), но не то же самое (ai, ai). 2. нет. попробуй с ручкой и бумажкой решить, прям номера позиций вписывай в пары, станет понятней. (a0, a1), (a0, a2),... 3. нет. в описании нет противоречий. оно есть в твоем ошибочном предположении 1-2 --- Добавлено --- можно только дополнить: если есть пара (ai, aj), то НЕ надо считать её дважды — как (ai, aj) и (aj, ai) ! считаем её как одну пару. скажем пусть будет i < j
время то скажи ) это с сайта сертификации. смысл в проверке умений. --- Добавлено --- если щелкаешь такие задачи, то и тест на собесе пройдёшь.
Time: 0.0088839530944824 29116 --- Добавлено --- Но это в онлайн сэндбоксе. Локально мб будет быстрее, но лень ребутиться на линь. Ну и сложность 2n получается. Мб, если посидеть, можно сделать и n.
Дабы не смущать, https://sandbox.onlinephpfunctions.com/ выполнил так (php 7.4.13) 29116 0.0083651542663574 Да, годнота наконец
Это на phponline ? Локальные замеры на своей тачке не интересны, мы все тут можем взять продовые серваки и выполнить за 0.0001 сек
В конечном счёте надо прогнать все варианты на одной машине, конечно, чтобы было сравнимо. https://sandbox.onlinephpfunctions.com/ хороший вариант Давайте до утра 23 декабря подождем и будем показывать код. --- Добавлено --- Замерять надо время выполнения функции, никакие дополнительные шаги роли не играют. Временем исполнения echo можно пренебречь PHP: $time = microtime(true); echo anagrams($a)."\n"; printf("%.9f\n", microtime(true) - $time);
Ну...оч смешной "оптимизацией" сбил время в сендбоксе до 0.0072 в среднем. Но, сдается мне, там ужиматься уже физически некуда. Быстрее только вынесение в расширение на сях, имхо. В любом случае, рубеж в "пару секунд" очень далеко за горизонтом. Код на 90% такой же как у Миши. И, скорее всего, у всех +- тот же самый принцип, судя по времени исполнения.