LINUX.ORG.RU

Сумма квадратов двух максимальных чисел

 ,


2

5

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

  def twoMaxSquareSum(a: Int, b: Int, c: Int): Int =
    {
      def min(): Int =
        {
          if (a < b && a < c) {
            return a;
          } else if (b < c) {
            return b;
          } else return c;
        }
      def square(x:Int):Int=
      {
        return x*x;
      }
      
      return List(a,b,c).map (square(_)).foldLeft(0)(_ + _)-square(min)
    }
Гуру программирования, как можно сделать красивее? И по-сути не обязательно на скале, решение на других языках тоже с удовольствием гляну

Добавление: А какой вариант вы бы безоговорочно приняли на собеседовании как оптимальный?



Последнее исправление: by_zero (всего исправлений: 1)
Ответ на: комментарий от bogus_result

Ага, и вычислив три умножения вместо двух. Лоровские алгоритмисты такие алгоритмисты.

anonymous
()
def maxSquare(a:Int, b:Int, c:Int) = List(a,b,c) sortWith(_>_) take(2) map(x=>x*x) sum

так писать нельзя

RedPossum ★★★★★
()
Ответ на: комментарий от anonymous

расскажи лучше, как эта задача «ложится на фп» (что это за бред вообще?) и как ее отмасштабировать для произвольного к-ва аргументов?

1. имеем список (a, b, c, d, e, f…) и sum=0

2. проверяем a<b

3. если да, то b это не минимум, и прибавляем квадрат b к sum; затем копируем a в b.

4. иначе, a это не минимум, и прибавляем квадрат a к sum.

5. первый эл-т списка обработан, переходим ко второму(b), и считаем его как a(соотв. c как b и так далее).

6. переходим к пункту 2, если в списке >1 эл-та

7. в sum у нас искомая сумма, а в списке единственный минимум.

Как видишь, на каждом шаге нам нужен лишь список, и первые два эл-та. Первый эл-т в ФП конечно не нужно копировать во внутрь списка, а передавать функции как параметр. Функция получается рекурсивной и рекурсия на хвосте(TCO срабатывает).

Ну могу, если ты такой глупый, написать тебе PoC на CL, а то скалу мне ставить лень, а CL у меня тут есть. Надо, или сам?

emulek
()
Ответ на: комментарий от bogus_result

Вообще как бы, если вам на собеседовании задали задачу, в которой три числа, и одно нужно исключить, а вы решаете задачу с N числами, M которых надо исключить, то что это?

это жирный плюс соискателю, если конечно общее решение с N и M не хуже какого-то частного.

emulek
()
Ответ на: комментарий от emulek

Напиши) 10К элементов, нужно треть квадратов от них (максимальных) сложить. Но в твоем коде должно быть для произвольных н и м.

anonymous
()
Ответ на: комментарий от emulek

ага, ну так и запишем: жыыыдкий слив. секретарь, внесите в протоколы заседания: др_батти вынесли в корыте помоев.

anonymous
()
Ответ на: комментарий от emulek

это радует. Откуда-же берётся подобный говнокод?..

Когда тебе нужно написать за пять минут прототип или однострочник.

mix_mix ★★★★★
()
Ответ на: комментарий от emulek

А в данном случае решение эффективно и просто обобщается только при увеличении N. При увеличении M мы теряем ясность.

Кроме того, мало кто в том числе и тут сходу скажет как найти M-ую порядковую статистики (так оно по науке называется) с ассимтотически-линейной трудоемкостью.

bogus_result
()
Ответ на: комментарий от anonymous

А вот это жирный минус соискателя. Да хоть десять умножений. Если не доказано, что это вредит производительности, и делает код понятнее, то зачем что-то оптимизировать?

bogus_result
()
Ответ на: комментарий от anonymous

Напиши) 10К элементов, нужно треть квадратов от них (максимальных) сложить. Но в твоем коде должно быть для произвольных н и м.

Напиши

сколько платишь?

Я вам уже и PoC на сишке написал, и алгоритм по пунктам для списка любой длинны, а теперь ты мне про 10К и 3К квадратов рассказываешь. Зачем мне выполнять твои желания? Это к золотой рыбке.

Данное решение пока лучшее по цене-производительности, да ещё и расширяется. Если есть вопросы/критика — пиши. А твои хотелки сам реализуй.

emulek
()
Ответ на: комментарий от anonymous

ага, ну так и запишем: жыыыдкий слив. секретарь, внесите в протоколы заседания: др_батти вынесли в корыте помоев.

только у drBatty есть рабочий PoC, а у тебя только словесный понос.

emulek
()
Ответ на: комментарий от mix_mix

Когда тебе нужно написать за пять минут прототип или однострочник.

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

emulek
()
Ответ на: комментарий от Deleted

специально для тебя напишу завтра, если не придумаю более интересного занятия.

emulek
()
Ответ на: комментарий от bogus_result

А в данном случае решение эффективно и просто обобщается только при увеличении N. При увеличении M мы теряем ясность.

не теряем. Надо просто M (у меня это число минимумов, которые НЕ нужно складывать) хранить в отдельном списке отсортированными. В императивной версии можно в том же списке, проталкивая их как при простых вставках. Да, при этом сложность будет O(N*M).

Кроме того, мало кто в том числе и тут сходу скажет как найти M-ую порядковую статистики (так оно по науке называется) с ассимтотически-линейной трудоемкостью.

а вот этого я не обещал. Я лишь обещал, что данный способ нетрудно обобщить и на случай N>3 и M>1, но никак не обещал, что обобщение будет оптимальным. Да и обобщать не обещал, хотя мне кажется, что это очевидно.

И да, это написано в пику борщеедам, которые пишут sort(a,b,c) и прочий говнокод.

emulek
()
Ответ на: комментарий от emulek

сложность n * m это что, О(N^2)? отлично промасштабировался, балабол.

в то время, как за-такое-должны-умирать-решение имеет сложность порядка O(NlogN): отсортировать и просуммировать квадраты пеовых М элементов.

борщехлебы заовнили владельца «РоС на сишке»!

anonymous
()
Ответ на: комментарий от anonymous

я даже готов сделать так: ты пиши не «РоС на сишке», а нормальную обобщенную версию, а я ее переведу на скалу и забенчу потом со своей тупой реализацией из сортировки и свертки. мне просто интересно, что себя лучше покажет.

anonymous
()
Ответ на: комментарий от anonymous

сложность n * m это что, О(N^2)?

нет, детка. n*m это n*m. В данном случае m равно 1, и сложность O(n). O(n²) будет если у тебя m = n/2.

в то время, как за-такое-должны-умирать-решение имеет сложность порядка O(NlogN): отсортировать и просуммировать квадраты пеовых М элементов.

если у тебя m=17, то сложность таки O(n), что намного лучше O(n*log(n)). Ну и константа пропорциональности у сортировки НАМНОГО больше, т.ч. при малых n будет тормозить из-за константы, а на больших из-за асимптоты.

emulek
()
Ответ на: комментарий от emulek

что ты со своим примитивным примером постоянно? я тебе говорю про твое «обобщение» и то, что я попросил - алгоритм для любого н и м.

ты ерзаешь на жопе, как царь, который орал, что он все может, а когда дело доходило до кода, он высирал однострочник на макросе и умывал руки. way to go, buddy!

anonymous
()
Ответ на: комментарий от anonymous

нормальную обобщенную версию, а я ее переведу на скалу и забенчу потом со своей тупой реализацией из сортировки и свертки

1. ясное дело, что если m линейно зависит от n, то сложность у меня получается O(n²), и мой вариант не подходит, и сливает твоему начиная с некоторого N. Я же рассчитывал на константное m, и при этом моя сложность O(n), и уже твой вариант сольёт моему начиная с некоторого N.

2. знаю я вас борщеедов, как вы переводите. Видел qsort на хаскеле, у которого IRL сложность O(n³) или типа того. Ты вот и сейчас путаешься, не видя разницы между O(n*m) и O(n²).

3. что такой батхерт? Как обычно, какой-то средний руки сишник нагнул целый тред борщеедов? Привыкайте к коленно-локтевой позиции, в жизни пригодится.

emulek
()
Ответ на: комментарий от anonymous

я тебе говорю про твое «обобщение» и то, что я попросил - алгоритм для любого н и м.

«алгоритм для любого n и m» я тебе не обещал.

орал, что он все может

этого я тоже не орал.

emulek
()
Ответ на: комментарий от emulek

во-первых, велосипедить сортировку я не собирался.

во-вторых, сложность для м = n/2 +- некоторая доля размера - квадратичная, а при м = 1 - линейная, в промежутке же таки сложнее => мой вариант, который гарантовано n logn масштабируется-таки лучше, не говоря уж о том, что он удовлетворит то, что принято называть функциональным подходом (т. е. манипуляция исходными данными посредством воздействия на них композицией некоторых функций, а не «этот алгоритм реализуем хоть рекурсией, хоть итеративно», блять), в отличии от твоего пропихивания в массив и т. д. ибо если ты собрался пропихивать в массив, который нужно держать сортированным, добавь еще стоимости к своему овнящему алгоритму.

в-третьих, это не баттхерт, а показательный процесс над местным крикуном (тобой, ага).

если хочешь продолжить дискуссию, иначе как после предоставления тобой масштабируемой функциональной реализации, которая кардинально отличается по ПД от предложенной и рвет ее, я тебе отвечать больше не буду.

anonymous
()
Ответ на: комментарий от anonymous

сложность для м = n/2 +- некоторая доля размера - квадратичная, а при м = 1 - линейная, в промежутке же таки сложнее

facepalm

Нет никакого «в промежутке», есть линейная зависимость m от n, и есть фиксированное m. Промежутка нет. Если m=100500, зависимость всё равно линейная.

мой вариант, который гарантовано n logn масштабируется-таки лучше

нет, не так. Это твоё «гарантированно» может наступить когда угодно, например при Over9000 миллиардах. Да и то, лишь в случае зависимости m от n.

что принято называть функциональным подходом

время исполнения алгоритмов никак не зависит от подхода. Причём это касается и небольших N, и асимптоты.

в-третьих, это не баттхерт, а показательный процесс над местным крикуном (тобой, ага).

детка, в первом посте вполне конкретная задача, её я решил. Всё остальное — твоя выдумка. Обосрать можно любое решение, если самому придумывать условия задачи. Например: вертолёт это говно, на нём в сортир неудобно.

если хочешь продолжить дискуссию, иначе как после предоставления тобой масштабируемой функциональной реализации

что с тобой, лолкой, дискутировать? Ты даже не понимаешь разницу между алгоритмом и реализацией. Я предложил алгоритм, в условиях ОП он хорошо работает. Ещё он масштабируется, причём я указал условия, в которых его можно масштабировать. Да, минет мой алгоритм не делает, извини.

emulek
()
Ответ на: комментарий от emulek

И да, это написано в пику борщеедам, которые пишут sort(a,b,c) и прочий говнокод.

sort(a,b,c) - как раз пример хорошего кода. Он прост, понятен, работает сразу для любых m/n (в отличи от высранного тобой говна, которое обобщается нетривиально и превращается при переписывании в нечитаемую вонючую портянку) эффективно работает, легко (автоматически) распараллеливается.

anonymous
()
Ответ на: комментарий от emulek

Ещё он масштабируется, причём я указал условия, в которых его можно масштабировать.

Когда дпри изменении выходных данных код надо выкинуть и переписать с нуля заново - это не называется «хорошо масштабируется».

anonymous
()
Ответ на: комментарий от emulek

а вот этого я не обещал. Я лишь обещал, что данный способ нетрудно обобщить и на случай N>3 и M>1

Так ты обобщи, не стесняйся

anonymous
()
Ответ на: комментарий от anonymous

sort(a,b,c) - как раз пример хорошего кода. Он прост, понятен

ладно, ок, я всё понял.

emulek
()
Ответ на: комментарий от bogus_result

Кроме того, мало кто в том числе и тут сходу скажет как найти M-ую порядковую статистики (так оно по науке называется) с ассимтотически-линейной трудоемкостью.

Как два пальца =)

Waterlaz ★★★★★
()
Ответ на: комментарий от emulek

не теряем. Надо просто M (у меня это число минимумов, которые НЕ нужно складывать) хранить в отдельном списке отсортированными. В императивной версии можно в том же списке, проталкивая их как при простых вставках. Да, при этом сложность будет O(N*M).

Нормальная версия работает за O(N)

Waterlaz ★★★★★
()
Ответ на: комментарий от Waterlaz

Осторожнее! Прогневите анонимуса, который обязательно скажет что нормальная версия на фп не ложится, даже если она и ложится. И обязательно скажет, что для нормальной версии есть худший случай, при котором она работает за O(n^2). В общем, по-любому прогневите😊

bogus_result
()
Ответ на: комментарий от Waterlaz

Нормальная версия работает за O(N)

да? Ну показывай свою «нормальную». И ещё раз: моя тоже работает O(N), в случае, если M константное. O(M*N) это случай линейной зависимости M от N.

emulek
()
Ответ на: комментарий от emulek

ты не стесняйся уточнять, что твое м может быть равно, например n/2,n/3 n/2-1 и т.д.,что превращает н*м в н в квадрате.

anonymous
()
Ответ на: комментарий от bogus_result

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

// парой постов выше не я писал, но согласен.

anonymous
()
Ответ на: комментарий от anonymous

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

qsort'ом все пользуются, и ничего, не жужжат. Там тоже средний=лучший~ O(N*log(N)), худший O(N²).

И кстати, сложность сортировки qsort для строк длинной M равна O(M*N*log(N)), и чё?

emulek
()
Ответ на: комментарий от anonymous

ты не стесняйся уточнять, что твое м может быть равно

а ты не стесняйся, рассказывай, из какого места ты этот случай высосал.

emulek
()
Ответ на: комментарий от emulek
#define swap(x, y) do{int t = x; x = y; y = t; }while(0)

#define min(a,b) ((a) < (b) ? (a) : (b))

int sum_m_n(int* a, int m, int n){
    if(m<=0) return 0;
    if(m>=n){
        int res=0;
        int i;
        for(i=0; i<n; i++)
            res+=a[i]*a[i];
        return res;
    }
    int l = 0;
    int r = n-1;
    int mid = (r+l)/2;

    if(a[0]<a[mid]) swap(a[0], a[mid]);
    if(a[mid]<a[r]) swap(a[mid], a[r]);
    if(a[0]<a[mid]) swap(a[0], a[mid]);
    int piv = a[mid];
    l++;
    r--;
    mid = l;

    while(mid<=r){
        if(a[mid]>piv){
            swap(a[mid], a[l]);
            l++;
            mid++;
            continue;
        }

        if(a[mid]<piv){
            swap(a[mid], a[r]);
            r--;
            continue;
        }

        mid++;
    }

    return sum_m_n(a, m, l) + sum_m_n(a+l, min(mid-l, m-l), min(mid-l, m-l)) + sum_m_n(a+r+1, m-r-1, n-r-1);
}

Вот эта вот реализация почти всегда работает за O(n) даже при больших m.

Waterlaz ★★★★★
()
Ответ на: комментарий от anonymous

для любых н и м? ого, что это за алгоритм?

Если совсем честно нужно, чтобы теоретическая оценка была O(n), то берем приведенный мною алгоритм и немного модернизируем его с учетом идей вот этого алгоритма http://en.wikipedia.org/wiki/Median_of_medians

ЗЫ но на практике это все не нужно.

Waterlaz ★★★★★
()
Ответ на: комментарий от Waterlaz

Вот иллюстрация на хаскле

sumM :: [Int] -> Int -> Int
sumM (x:xs) m | m<=0       = 0
              | m < nls    = sumM ls m
              | m == nls   = sumLs
              | m == nls+1 = sumLs + (x^2)
              | otherwise  = sumLs + (x^2) + sumM rs (m - nls - 1)
         where
            ls = filter (>x) xs
            rs = filter (<=x) xs
            nls = length ls
            sumLs = sum $ map (^2) ls

Waterlaz ★★★★★
()
Ответ на: комментарий от anonymous

Где ты там O(n) увидел?

Посчитал, епт. n + n/2 + n/4 + n/8 + ... = 2n

Waterlaz ★★★★★
()
Ответ на: комментарий от Waterlaz

Это совершенно другой алгоритм. Никаким боком опять же не O(n) даже близко. И он не работает.

anonymous
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.