1. C++ / Говнокод #19588

    +2

    1. 01
    2. 02
    3. 03
    4. 04
    5. 05
    6. 06
    7. 07
    8. 08
    9. 09
    10. 10
    11. 11
    12. 12
    13. 13
    14. 14
    15. 15
    16. 16
    17. 17
    18. 18
    19. 19
    20. 20
    21. 21
    22. 22
    23. 23
    24. 24
    25. 25
    26. 26
    27. 27
    switch (a) {
    	case 12345:
    		return 0;
    	case 14523:
    		return 1;
    	case 102543:
    		return 2;
    	case 104325:
    		return 3;
    	case 243051:
    		return 4;
    	case 245130:
    		return 5;
    	case 350214:
    		return 6;
    	case 351402:
    		return 7;
    	case 423150:
    		return 8;
    	case 425031:
    		return 9;
    	case 530412:
    		return 10;
    	case 531204:
    		return 11;
    	}
    	return -1;

    Запостил: Ekke, 07 Марта 2016

    Комментарии (51) RSS

    • Error 404 C++ not found.
      Ответить
    • Лучше чем
      (a/10000)*2 + (((a/1000)%10) == 1 ||((a/1000)%10) >3)?1:0;
      Ответить
    • На самом деле, не понятно, где ГК: свитч для этого придумывался и, казалось бы, даёт лучшее решение по времени/памяти из возможных.
      Ответить
      • На таком малом количестве - не дает, а вообще O(n)
        Ответить
        • Не O(n), а O(log N), что в данном случае даст прирост в скорости выполнения в 12/(log2(12) + 1), то есть больше, чем в два раза.
          Круче по операциям только лукап в таблице по n / 1000, но не факт, что исполнится лучше -- один джамп по указателю из памяти в непредсказуемое место и два обычных джампа или всё-таки пять обычных джампов.
          Ответить
          • O(количество кейсов), или цпп как-то по-другому свич обрабатывает?
            Ответить
            • Компилятор может обработать свич как хочет. На таком тесте, скорее всего, будет решающее дерево типа бинпоиска.
              Ответить
              • Ух ты. Что, правда (не сарказм)?
                Ответить
                • Да
                  http://goo.gl/Yim0ZY
                  Ответить
                  • Ух ты! А в старых версиях (или вообще не в gcc) была табличка пар {значение, адрес перехода} и тупой перебор. Или даже табличка адресов перехода, если значения забиты плотно.
                    Ответить
              • >Компилятор может обработать свич как хочет.
                То есть, гарантий никаких не дается и по сути это столь любимое бормондом UB?
                Ответить
                • не UB, а implementation defined
                  ещё блять не хватало, чтобы в стандарте навязывалась реализация свича или ограничивалась работа duff device
                  Ответить
                  • UB и ID это в принципе не про это. Стандарт никогда не говорит, как что-то должно быть реализовано, он говорит, как должна себя вести какая-то конструкция языка. Про свитч будет сказано что-то вроде "при наличии метки, равной значению выражения, будет джамп на эту метку, в противном случае при наличии метки default -- на неё, в противном случае -- за тело свитча". А как будет осуществлён джамп -- через бинпоиск, через таблицу, через последовательное сравнение или ещё как-то -- остаётся на совести компилятора, главное, чтобы наблюдаемое поведение программы не изменялось.

                    Например, для какого-нибудь switch (a) { case 1: return 2; case 2: return 3; case 3: return 4; default: return -1; } вполне соответствовать стандарту будет превращение в return 1 <= a && a <= 3 ? a+1 : -1;
                    Ответить
                    • Алгоритмическая сложность тоже иногда строго указана же. Например для всяких контейнеров из STL.
                      Ответить
                      • Да, согласен. Но обычно не строго, а в формулировке "Не больше, чем". Но, опять же, без указания на способ реализации.
                        Ответить
                        • Есть такое указание для свича?
                          Ответить
                          • Нету. Там про свитч меньше странички, ISO 14882 пункт 6.4.2.
                            И даже про вычислительную сложность сложения, умножения и деления там нет ни слова.
                            Ответить
                            • Ну а что, на брейнфак-процессоре сложность сложения лучше линейной не сделать. А умножение вообще квадратично.
                              Ответить
                              • Ну это уж совсем экзотика, а вот деление, например, на некоторых МК компилятору приходится эмулировать программно.
                                Ответить
                              • Машина Тьюринга используется для теоретической доказуемости вычисляемости, выч. сложность значения не имеет. А брейнфак юзают те... кто хотят факать брейн.
                                Ответить
                            • И как его тогда юзать, котаны?
                              Ответить
                              • Так же, как питонисты юзают спискомассив -- не задумываясь
                                Ответить
                                • Но питонисты же знают O(). Или ты про васянов, которые не знают зачем set - ведь у списка тоже есть in.
                                  Ответить
                                  • Питонисты не знают про О. Ну что-то может слышали, но не считают это нужным.

                                    Например, знаю кучу людей, у которых был первым языком питон, и которые второй минимум в массиве ищут сортировкой. И даже не задумываются, что что-то тут не так.
                                    Ответить
                                    • >Питонисты
                                      >у которых был первым языком питон
                                      Зачем ты так...

                                      >и которые второй минимум в массиве ищут сортировкой
                                      А чо такое? O(n*logn ) же
                                      Ответить
                              • 1) Альтернатив-то нет. Медленнее if-else-if-else-if все равно не будет.
                                2) Про студию/гцц/шланг доподлинно известно, что они свитч оптимизируют. А это 99,99% платформ. ICC, у которого вся писечка в оптимизациях, тоже наверняка делает настолько быстрый свитч, насколько возможно.
                                3) Нужно верить в свой компилятор. Это один из столпов с++.
                                Ответить
                                • > Нужно верить в свой компилятор. Это один из столпов с++.
                                  Нужно верить в Штольмана и трухвальца - это один из столпов прыщей.
                                  Ответить
                  • >ещё блять не хватало, чтобы в стандарте навязывалась вычислительная сложность свича.
                    Ответить
                    • Надо было зеленым выделить? Для справки - в жавке все однозначно.
                      Ответить
          • В варианте с таблицей никакого джампа не надо, просто берем из нее значение и возвращаем.
            Ответить
            • Перед заходом в таблицу нам надо проверить, что n / 1000 меньше размера таблицы, после -- проверить, что значение равно запрошенному.
              Ответить
              • И который из них "джамп по указателю из памяти в непредсказуемое место"?
                Ответить
      • Разброс слишком большой, скорее всего таблицу компилятор генерить не будет. В лучшем случае двоичный поиск воткнёт.
        Ответить
    • Я уж было заподозрил, что тут строки кастуют к инту.
      Ответить

    Добавить комментарий