1. Куча / Говнокод #13711

    +135

    1. 1
    2. 2
    3. 3
    4. 4
    5. 5
    BoxOfIndex =[0,0,0,1,1,1,2,2,2,0,0,0,1,1,1,2,2,2,0,0,0,1,1,1,2,2,2,
                       3,3,3,4,4,4,5,5,5,3,3,3,4,4,4,5,5,5,3,3,3,4,4,4,5,5,5,
                       6,6,6,7,7,7,8,8,8,6,6,6,7,7,7,8,8,8,6,6,6,7,7,7,8,8,8]

Box = BoxOfIndex[i*9 +j]

    Определение индекса малого квадрата в судоку

    Вместо
    Box = (i/3)*3 +j/3

    Запостил: kegdan, 01 Сентября 2013

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

    • ava 1024-- 01.09.2013 11:36 # +4

      Как же можно, где перфоманс? Хоть так бы:
      BoxOfIndex =[
  0,0,0,1,1,1,2,2,2, 0,0,0,0,0,0,0,
  0,0,0,1,1,1,2,2,2, 0,0,0,0,0,0,0,
  0,0,0,1,1,1,2,2,2, 0,0,0,0,0,0,0,
  3,3,3,4,4,4,5,5,5, 0,0,0,0,0,0,0,
  3,3,3,4,4,4,5,5,5, 0,0,0,0,0,0,0,
  3,3,3,4,4,4,5,5,5, 0,0,0,0,0,0,0,
  6,6,6,7,7,7,8,8,8, 0,0,0,0,0,0,0,
  6,6,6,7,7,7,8,8,8, 0,0,0,0,0,0,0,
  6,6,6,7,7,7,8,8,8, 0,0,0,0,0,0,0
]

Box = BoxOfIndex[i<<4 | j]
      Ответить

      • ava bormand 01.09.2013 15:28 # 0

        > где перфоманс
        На месте он ;) На x86 это скомпилится в че-то типа:
        mov eax, i
lea eax, [eax*8 + eax + offset BoxOfIndex]
add eax, j
        Настоящего умножения на 9 там точно не будет.
        Ответить

        • ava 1024-- 01.09.2013 15:39 # +1

          Ещё немного, и я бы своими заклинаниями царя случайно вызвал.
          Ответить

      • ava bormand 01.09.2013 15:56 # +3 

        Box = (i * 86 >> 8) * 3 + (j * 86 >> 8)
        Всяко не быстрее, зато смотрится таинственней.
        Ответить

        • ava kegdan 01.09.2013 16:05 # +1

          если не секрет как это вывелось
          (i * 86 >> 8) ==i/3
          ?
          Ответить

          • ava 1024-- 01.09.2013 16:11 # +1

            +1, действительно, как.

            Это явно какая-то примерная магия. Оно на i=128 даёт 43, а надо 42, а для i=0..127 работает.
            Кстати, можно использовать от 86 до 96, чтобы работало от 0 до 8
            Ответить

            • ava bormand 01.09.2013 16:16 # +1

              > Это явно какая-то примерная магия.
              Ну оно так и есть, но для небольших чисел обычно работает.

              Проще всего представить это как вычисление floor(1/3 * x) через fixed point с 8 знаками после точки. 86 это приближенная запись 1/3, а сдвиг вправо - это floor.
              Ответить

          • ava bormand 01.09.2013 16:11 # +1

            ceil(256/3)
            Ответить

            • ava kegdan 01.09.2013 16:21 # +1

              а 8 вестимо логарифм. угу.

              получается (i/3)*2^8>>8 = i/3 для малых чисел
              Ответить

              • ava bormand 01.09.2013 16:35 # +1

                > получается (i/3)*2^8>>8 = i/3 для малых чисел
                Да.

                (i * (256/3)) / 256 наверное будет самой наглядной записью.
                Ответить

                • ava kegdan 01.09.2013 16:43 # 0

                  та же фигня, только в профиль
                  Ответить

                • ava 1024-- 01.09.2013 16:56 # 0

                  > (i * (256/3)) / 256 наверное будет самой наглядной записью.
                  ceil(256/3) была самой краткой и наглядной (для меня)

                  Я же в своих размышлениях отклонился от истины. Поделил 86/2, получил 43 - простое и не 3 - удивился, думал, что дело в старших битах, раз был сдвиг. Но 1010110 не похоже на 3, оно похоже на 5. Потом осознал, что старшие биты помогли бы с умножением. Скажем, i*86>>8 было бы умножением на 5 для малых чисел. В итоге всё больше укреплялась в голове мысль, что это магия, а 86 - это в честь x86 :)
                  Оставался лишь вопрос: 256 (?) 86..90 = 3.
                  Ответить

    • ava bormand 01.09.2013 15:24 # 0

      > Определение индекса малого квадрата в судоку
      Алгоритмами будешь решать или брутом?
      Ответить

      • ava kegdan 01.09.2013 16:00 # 0

        я не буду решать, просто смотрел пример кода, там алгоритмом было.
        Ответить

    • ava Dummy00001 01.09.2013 16:24 # 0

      > Определение индекса малого квадрата в судоку

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

      во-вторых, а зачем изгалятся и не сделать просто вложеные массивы?
      Ответить

      • ava kegdan 01.09.2013 16:27 # 0

        это ruby

        предложите реализацию
        Ответить

        • ava bormand 01.09.2013 16:33 # +2

          >> и не сделать просто вложеные массивы
          > предложите реализацию
          Видимо вот это имеется в виду:
          BoxOfIndex = [
    [0,0,0,1,1,1,2,2,2],
    [0,0,0,1,1,1,2,2,2],
    [0,0,0,1,1,1,2,2,2],
    [3,3,3,4,4,4,5,5,5],
    [3,3,3,4,4,4,5,5,5],
    [3,3,3,4,4,4,5,5,5],
    [6,6,6,7,7,7,8,8,8],
    [6,6,6,7,7,7,8,8,8],
    [6,6,6,7,7,7,8,8,8]]
Box = BoxOfIndex[i][j]
          Ответить

          • ava Dummy00001 01.09.2013 16:42 # 0

            да.
            Ответить

          • ava kegdan 01.09.2013 16:45 # 0

            тоже не айс руками писать. если только сгенерить статичным конструктором в классе GameField... Их есть в ruby?
            Ответить

            • ava Dummy00001 01.09.2013 17:08 # 0

              я буду очень сильно удивлен если нет.
              Ответить

              • ava kegdan 01.09.2013 17:12 # +1

                я тоже, но мало ли.

                Я буквально сегодня начал читать "Язык программирования Ruby" от отца-основателя и у меня уже передозировка сахаром)
                Ответить

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