1. JavaScript / Говнокод #26422

    +3

    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
    28. 28
    29. 29
    30. 30
    31. 31
    32. 32
    33. 33
    34. 34
    35. 35
    36. 36
    37. 37
    38. 38
    39. 39
    40. 40
    41. 41
    42. 42
    43. 43
    44. 44
    45. 45
    46. 46
    47. 47
    48. 48
    49. 49
    50. 50
    51. 51
    52. 52
    53. 53
    54. 54
    55. 55
    56. 56
    57. 57
    58. 58
    59. 59
    60. 60
    61. 61
    62. 62
    63. 63
    64. 64
    65. 65
    66. 66
    onst addAdjacencies = (
      nodes,
    ) => (
      nodes
      .map(({
        colorId,
        id,
        x,
        y,
      }) => ({
        color: colors[colorId],
        eastId: (
          getNodeAtLocation({
            nodes,
            x: x + 1,
            y,
          })
        ),
        id,
        northId: (
          getNodeAtLocation({
            nodes,
            x,
            y: y - 1,
          })
        ),
        southId: (
          getNodeAtLocation({
            nodes,
            x,
            y: y + 1,
          })
        ),
        westId: (
          getNodeAtLocation({
            nodes,
            x: x - 1,
            y,
          })
        ),
      }))
      .map(({
        color,
        id,
        eastId,
        northId,
        southId,
        westId,
      }) => ({
        adjacentIds: (
          [
            eastId,
            northId,
            southId,
            westId,
          ]
          .filter((
            adjacentId,
          ) => (
            adjacentId !== undefined
          ))
        ),
        color,
        id,
      }))
    )

    https://medium.com/free-code-camp/bet-you-cant-solve-this-google-interview-question-4a6e5a4dc8ee

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

    Запостил: Fike, 08 Февраля 2020

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

    • показать все, что скрытоvanished
      Ответить
    • показать все, что скрытоvanished
      Ответить
      • Стоп, он перебирает все ноды линейным поиском чтобы найти хуйню с координатами (х, у)?!
        Ответить
        • Какой анскилл )))
          Ответить
        • Ну так ему показали по сути таблицу при описании задания, а он сначала решил, что придётся изображение парсить. Что ты от него хочешь?
          Ответить
    • Нормальный код, любому петуху понятен
      Ответить
    • Переведите этот код на кресты или бидон, тогда поймете, что Java Script язык будущего
      Ответить
    • У меня первая мысль: неужто пару старых-добрых царских for(var i=0;..) не будут проще этой функцианальной дрисни?

      Но автор похоже в курсе что сишный for лучше и быстрее:
      Use a `for` Loop
      
      Since we know our max item count, there’ll be a minor benefit from switching the reduce function to a traditional for loop.
      
      For whatever reason, Array.prototype methods are incredibly slow compared to for loops.


      И тут мы приходим к тому, о чём я уже говорил......
      Ответить
      • Какой багор )))
        Ответить
        • Я же дальше статью читаю. Там ещё смешнее пошло.

          Он на полном серьёзе начал замерять пирформанс своей скриптухи.

          А в конце подытожил, мол вот ещё пару статей как сделать функцианаьную скриптуху быстрее не такой тормознутой:

          >If you wanna read more on JavaScript performance, check out my other articles:
          > Speed Up JavaScript Array Processing
          > Using Transducers to Speed Up JavaScript Arrays
          >>JavaScript
          >>performance
          Ответить
          • показать все, что скрытоvanished
            Ответить
            • Нее, там смысл что js в функцианальном дрисня-стиле, чуть ли не в ДЕСЯТОК раз сливает jsу же в нормальном императивном стиле.

              Transducers aren’t all peaches and cream. When you have a very small number of items, transducers are a lot slower than either solution. It’s beyond the scope of this article to find the trade-off point for most machines, but let’s redo those performance tests with an array of 3 items.
              Array Method: 0.33ms
              For Loop: 0.22ms
              Transducer: 3.06ms

              Скриптух, боролся, боролся, выдумывал питух-структуры, трансдусеры.
              Но Царя не читал и не знает, что лучшая структура данных — массив. А лучший цикл — for.
              Ответить
              • > When you have a very small number of items

                ¿¿¿нахуя мне оптимизировать алгоритм для small number of items???
                Ответить
                • Допустим, алгоритм захотят использовать на каждой итерации алгоритма с big number of items.
                  Ответить
                  • Там скорее всего внешний код будет занимать больше времени, чем этот вызов
                    Ответить
            • >Если она тормозит -- ее параллелят.
              Не поможет. Он же в статье прямо пишет, что его питушарский способ даже в concurrent версиях сливает тупой однопоточной итерации.
              Моча в рожи сектантов.
              Time 	Method
              229.481ms 	Recursive
              272.303ms 	Iterative Random
              323.011ms 	Iterative Sequential
              391.582ms 	Redux-Observable Concurrent
              686.198ms 	Redux-Observable Random
              807.839ms 	Redux-Observable Sequential
              Ответить
            • а потом ты им там рассказываешь про бранч предикшен, весьма специфичные подкапотооптимизации, а они такие не, я же много раз прогнал, мой бенч не может быть недостоверным
              Ответить
            • может говна поесть сразу ?
              Ответить
      • показать все, что скрытоvanished
        Ответить
        • Это признание факта, что он заедушный скриптух, которого любой залётный боярин сольёт 5ю строками императивной сишки с 2мя forами.

          В самом конце статьи анскилябра дала ссылку, на эпопею как она борлоась с царским for.
          https://itnext.io/speed-up-javascript-array-processing-8d601c57bb0d

          Let’s do a simple performance test with 10 million items using Array.prototype.map:

          And then let’s compare that to the native for loop:

          I ran each test 7 times and pulled the averages. On my overclocked Intel Core i7–4770K, our array method averaged 1281ms while our for loop averaged 323ms. Incredible right? What a performance improvement! But for loops are so 10 years ago. They’re difficult to write and harder to reason about when doing complex transformations.
          Ответить
          • показать все, что скрытоvanished
            Ответить
            • >Функциональщина это новый ООП.

              Да. Я ещё 6 лет назад заметил:
              https://govnokod.ru/16298#comment239238
              В начале 00-х когда оно было в зените популярности мне в принципе было очевидно что панацеей оно не является.
              Сейчас же лихорадка прошла, появляются языки без ооп и стало модно пинать ооп.

              Однако лихорадка сменилась другим сумасшествием - чисто функциональные языки. И это пройдет, останутся только идеи, самые удачные из которых запилят в промышленные императивные язычки (как, например, тоже ооп когда еще было модно, добавили в пыху). Собственно мы видим это уже сейчас.
              Ответить
          • > and pulled the averages
            Ебать дебил.
            Ответить
      • > For whatever reason, Array.prototype methods are incredibly slow compared to for loops.

        кто бы мог подумать. Интересно, почему вызовы функций такие медленные?
        Ответить
    • а его и в комментариях отхуесосили https://medium.com/p/4a6e5a4dc8ee/responses/show
      Ответить
      • > This is an example of why I don’t have the skills to work at Google! Very nice solution.

        cyka blyat
        Ответить
    • Высрал немножко говнокода на «C» в олимпиадном стиле.
      inline int isValidCoords(intptr_t i, intptr_t j)
      {
          return (i >= 0) && (i < ROWS) && (j >= 0) && (j < COLS);
      }
       
      size_t visitNode(Node *matrix, intptr_t i, intptr_t j)
      {
          static const int MOVES[][2] = {
              { -1, 0 },
              { +1, 0 },
              { 0, -1 },
              { 0, +1 },
          };
       
          Vec *vec = vec_create();
          if (!vec) {
              goto OOM;
          }
       
          if (!vec_push(vec, i, j)) {
              goto OOM;
          }
       
          size_t blockSize = 0;
          uint32_t targetColor = MATRIX_AT(matrix, i, j).color;
          MATRIX_AT(matrix, i, j).isVisited = 1;
          while (vec->curSize > 0) {
              Coords *coords = vec_pop(vec);
              i = coords->i;
              j = coords->j;
       
              blockSize++;
       
              for (size_t moveIdx = 0; moveIdx < sizeof(MOVES) / sizeof(MOVES[0]); moveIdx++) {
                  intptr_t movedI = i + MOVES[moveIdx][0], movedJ = j + MOVES[moveIdx][1];
                  if (isValidCoords(movedI, movedJ)) {
                      Node *adjNode = &MATRIX_AT(matrix, movedI, movedJ);
                      if (adjNode->color == targetColor && !adjNode->isVisited) {
                          MATRIX_AT(matrix, movedI, movedJ).isVisited = 1;
                          if (!vec_push(vec, movedI, movedJ)) {
                              goto OOM;
                          }
                      }
                  }
              }
          }
       
          vec_delete(vec);
          return blockSize;
       
      OOM:
          perror("OOM");
          vec_delete(vec);
          exit(EXIT_FAILURE);
      }
      
      // 2000 символов :(
      size_t maxAdjNodes = 0;
      for (intptr_t i = 0; i < ROWS; i++) {
          for (intptr_t j = 0; j < COLS; j++) {
              if (!MATRIX_AT(matrix, i, j).isVisited) {
                  size_t adjNodes = visitNode(matrix, i, j);
                  if (maxAdjNodes < adjNodes) {
                      maxAdjNodes = adjNodes;
                  }
              }
          }
      }
      
      printf("Max block size: %zd\n", maxAdjNodes);

      https://ideone.com/e7dSAC
      Ответить
      • Самое смешное, что это тупое наивное говно безо всяких оптимизаций, в котором половину кода занимает реализация вектора (лол), на моём всратом «ай-пятом» работает 3 миллисекунды. Против «the fastest» 230 у анскиллябры из статьи.
        Какой пиздец )))
        Ответить
        • Включил релизную сборку, получил 2 мс для 100*100 и 5991 мс для 10000*10000.
          Ответить
        • И тут мы приходим к тому, о чём я уже говорил...
          Ответить
        • >тупое наивное говно

          Хахаха. Минут 40 втыкал в код, искал где же «говно».
          >    uint32_t targetColor = MATRIX_AT(matrix, i, j).color;
          >    MATRIX_AT(matrix, i, j).isVisited = 1;

          Ну можно столько MATRIX_AT и не делать.
          >        let currentNode = matrixAt(matrix, i, j);
          +        if (currentNode.visited) return 0;

          И сразу early-exit вписать. Нет смысла продолжать, если уже посещали.
          Ответить
          • > Ну можно столько MATRIX_AT и не делать.
            Да, точно.

            > И сразу early-exit вписать. Нет смысла продолжать, если уже посещали.
            У меня в visitNode() идут только непосещённые ноды, там в главном цикле проверка.

            На «C» основное говно в неоптимизированности и самописном векторе, ИМХО. Для теста заменил в коде вектора «calloc» на «malloc», увеличил начальную ёмкость до 100, в visitNode сделал vec статическим (с заменой vector_delete на vector_clear) — получил x3 прирост, с 6 секунд до 2 для матрицы 10000*10000. Думаю, если в профилировщике посидеть — можно ещё пару-тройку раз прироста выжать.
            Ответить
            • >У меня в visitNode() идут только непосещённые ноды, там в главном цикле проверка.
              Ну да.
              Я имел ввиду перенести её в цикл, а лишний MATRIX_AT выкинуть.
              Или просто передавать curr аргументом.
              size_t blockSize = 0;
                  Node *curr = &MATRIX_AT(matrix, i, j);
                  uint32_t targetColor = curr->color;
                  if (curr->isVisited) {
                  	return blockSize;
                  }


              Ну и тут
              >                Node *adjNode = &MATRIX_AT(matrix, movedI, movedJ);
              >                if (adjNode->color == targetColor && !adjNode->isVisited) {
              -                    MATRIX_AT(matrix, movedI, movedJ).isVisited = 1;
              +                    adjNode->isVisited = 1;


              Edit: Я пытался замерять пирфоманс, но код настолько быстрый, даже на 5000x5000, что пирфоманс колеблется в пределах погрешности таймера.
              Ответить
          • > искал где же говно

            Вот же оно: LCGRand() % COLOR_NUM
            Ответить
      • >> олимпиадном стиле
        > vec_delete
        > EXIT_FAILURE

        Ну ты понел )
        Ответить
        • Ну это я про «#define ROWS». Олимпиадники за собой не чистят, это да.
          Ответить
          • А ещё вот это:
            >putchar(MATRIX_AT(matrix, i, j).color + '0');
            >putchar('\n');

            Только настоящий олд-сишник держит в уме что printf тормозной.
            И на тысячах итераций putchar чуток быстрее.

            * притом что шланг вроде оптимизирует односимвольные printfы в putchar
            Ответить
          • https://godbolt.org/z/Syz4Ej
            И gcc тоже
            #include <stdio.h>
            void charFormat(void)
            {
              printf("%c",'0');
            }
            
            void single(void)
            {
              printf("\n");
            }
            
            charFormat:
                    subq    $8, %rsp
                    movl    $48, %edi
                    call    putchar
                    addq    $8, %rsp
                    ret
            single:
                    subq    $8, %rsp
                    movl    $10, %edi
                    call    putchar
                    addq    $8, %rsp
                    ret


            А вот MSVC — глупая лалка.
            Ответить
        • показать все, что скрытоvanished
          Ответить
        • >goto OOM;
          >perror("OOM");
          >size_t вместо inta

          Попытался прикинуться олимпиадником, но руки-то помнят!

          Ответить
          • Сразу видно, что он анскильный олимпиадник.
            Ответить
            • Ага.

              Это как маленькая девочка заходит и сообщает: «приффетик ))) я люблю кукол и розофых пони».

              А потом пишет обфусцированную программу на Си, которая помимо прочего возвращает ненулевой код ответа в случае ошибочного ввода.
              Ответить
            • Я вот об этом если что:
              https://govnokod.ru/21037#comment349170

              Для удобного чтения треда, введите в консоль регистрационный ключ:
              jQuery(".ajax").click()
              Ответить
              • Хм. Хастехбка - это гост был?
                Ответить
                • Сомневаюсь.
                  > printf("%c", love [bormand % HACTEHbKA]);
                  Всё-таки девочки в сишке не очень сильны. gost бы кошерно putchar поставил.

                  Да и какая разница? Лулзы же.
                  Ответить
                • Отрицаю.
                  Ответить
                • Я Настенька
                  Ответить
                  • Привет, Настенька!
                    Бормондяша так мощно кодил на крестах, что пробудил тебя ото сна?
                    Ответить
                    • Да я почуствовала мощные электрамагнитные импульсы это был мой вайфай соабщал скрипт что бормондяша кодил один заодним падряд
                      Ответить
                    • Ну вот, дооптимизировались, опять пробудили древнее зло ;(
                      Ответить
      • Я в лёгком неудомении. Как эта программа очутилась на сайте «Говнокод»?
        Ответить
      • Дословно перевёл на «JavaScript». Получил ~10 миллисекунд в консольке браузера.
        function visitNode(matrix, i, j) {
            const MOVES = [
                [ -1, 0 ],
                [ +1, 0 ],
                [ 0, -1 ],
                [ 0, +1 ],
            ];
            
            let vec = [[i, j]];
            let blockSize = 0;
            let currentNode = matrixAt(matrix, i, j);
            const targetColor = currentNode.color;
            currentNode.visited = true;
            while (vec.length > 0) {
                [i, j] = vec.pop();
                blockSize++;
                
                for (let move of MOVES) {
                    let movedI = i + move[0], movedJ = j + move[1];
                    if (isValidCoords(movedI, movedJ)) {
                        let node = matrixAt(matrix, movedI, movedJ);
                        if (node.color === targetColor && !node.visited) {
                            node.visited = true;
                            vec.push([movedI, movedJ]);
                        }
                    }
                }
            }
            return blockSize;
        }

        https://pastebin.com/yHXjpAg2

        Просто пиздец, насколько же чувак из статьи — анскилльный питух.
        Ответить
        • > Time: 15ms
          > 229.481ms Recursive
          > 391.582ms Redux-Observable Concurrent

          >js в функцианальном дрисня-стиле, чуть ли не в ДЕСЯТОК раз сливает jsу же в нормальном императивном стиле.

          Хм. Перехвалил я скриптуха, откровенно перехвалил. 10x slowdown нужно ещё заслужить.
          Ответить
          • Я думаю если линейный поиск ноды по координатам из getNode выкинуть, то и Rx-косичка не так уж позорно сливается.
            Ответить
        • Так шо, тебя в Гугл взяли-то?
          Ответить
          • Жду, когда перезвонят.
            Ответить
            • А меня возьмёте в гугол?

              https://ideone.com/UEJlLe
              struct Block {
                  uint32_t color;
                  size_t size;
              };
              
              using BlockPtr = std::shared_ptr<Block>;
              
              struct Proxy {
                  BlockPtr block;
              };
              
              using ProxyPtr = std::shared_ptr<Proxy>;
              
              int main()
              {
                  std::vector<ProxyPtr> up_row(COLS);
                  size_t max_size = 0;
              	
                  for (size_t row = 0; row < ROWS; row++) {
                      ProxyPtr left;
                  	
                      for (size_t col = 0; col < COLS; col++) {
                          uint32_t color = LCGRand() % COLORS_NUM;
                  		
                          ProxyPtr &up = up_row[col];
                  		
                          ProxyPtr cur;
                          if (left && (left->block->color == color)) {
                              cur = left;
                  			
                              if (up && (up->block->color == color) && (up->block != left->block)) {
                                  left->block->size += up->block->size;
                                  up->block = left->block;
                              }
                          } else if (up && (up->block->color == color)) {
                              cur = up;
                          } else {
                              BlockPtr block = std::make_shared<Block>(Block{color, 0});
                              cur = std::make_shared<Proxy>(Proxy{block});
                          }
                  		
                          ++cur->block->size;
                          if (cur->block->size > max_size)
                              max_size = cur->block->size;
                  			
                          left = up = cur;
                      }
                  }
              	
                  std::cout << "Max block size: " << max_size << std::endl;
                  return 0;
              }
              З.Ы. Не особо оптимально, но если на пулы пересадить, то будет за O(COLS) по памяти.
              Ответить
              • Хуйня получилась. В некоторых хитрых ситуациях криво мёржит блоки.
                Ответить
              • Красиво, но иногда выдаёт неправильный результат (на 10000*10000 со стандартным сидом; кстати, 9 секунд работает). Написал простую фаззилку наивной и твоей версий, получил реальный пример: при ROWS = 3, COLS = 23, SEED = 3735928572ull получается матрица:
                10111121200121100111102
                22112011211021011121121
                02101000120120111022110

                Крестовая версия выдаёт 12, наивная — 14, ручной подсчёт присуждает победу наивной.
                10111121200121100111102
                22112011211021011121121
                02101000120120111022110


                Именно для этого, кстати, я и запилил самописный рандом.
                Ответить
                • Ещё более реальный пример: ROWS = 3, COLS = 5, SEED = 3735807571ull:
                  11222
                  02202
                  22202

                  9 у крестовой, 10 у наивной.

                  Не учитывается самый левый столбец блока, у которого есть только один элемент нужного цвета, находящийся в самой нижней строке?
                  Ответить
                  • Да не, там косяк во время слияния с блоком, который уже был слит.
                    Ответить
                • Вроде пофиксил: https://ideone.com/kKEyGB
                  Ответить
                  • Проверил, фаззилка ошибок не нашла.
                    По сравнению с немного оптимизированной версией на «C» (https://ideone.com/bd4g1I) производительность снижена примерно в 1.5—2.5 раза: https://ideone.com/mhPokq (на моём компе — ~6500 мс против ~2400).

                    Подозреваю, что в основном это из-за «шаред_поинтеров».
                    Ответить
                    • Скорее из-за аллокаций на каждый чих. Пул надо прикручивать...
                      Ответить
                      • Точно, из-за них: https://i.imgur.com/FkGfv2x.png.
                        Ответить
                        • Обмазал в пул со смартпоинтером, проверь: https://ideone.com/8RBwIS
                          Ответить
                          • Проверил, ~1500 мс, x1.6 быстрее сишной. Охуенно!

                            Кстати, оптимизированный код на «C++» оказался гораздо больше похож на «C», чем код на «C». Какой багор )))
                            Ответить
                            • Больше похож в какой метрике?
                              Ответить
                              • По количествам уко-ко-ко-козателей и стрелочных разыменований.
                                Ответить
                            • А моё проверишь?

                              У меня сначала была мысль сделать что-то похожее на борманда.

                              Но я стремился к царскому решению: побольше массивов, поменьше структур.

                              Потому я взял за основу твой одномерный массив и заполняшку.
                              Ответить
                              • > побольше массивов

                                Зато у меня даже входной матрицы нет, можно генерить её на ходу или стримить с диска.
                                Ответить
                                • Да у меня срань вышла.
                                  На больших и хитрых матрицах ломается. Плюс второй цикл непонятно как убрать.
                                  Ответить
                                  • А я, кажется, придумал новый царский алгоритм, который должен разъебать всё, что здесь было...
                                    Ответить
                                    • >я, кажется, придумал новый царский алгоритм

                                      Я не смотрел в крестоверсию.
                                      Пока свою не сделал. У меня вышло очень похоже.

                                      Но блин, никак не выходит без третьего вложенного цикла, который топы апдейтит:
                                      while (up && up->redir)
                                      up = up->redir;


                                      >который должен разъебать всё
                                      Слить в хламину же.
                                      Ответить
                                  • Это на каких параметрах ломается?
                                    Ответить
                                    • >Это на каких параметрах ломается?
                                      Да взять исходный 0xDEADBEAF 100х100.
                                      Недосчитывает.

                                      Я merge заинлайнил, но всё-равно надо вверх идти и топы обновлять.
                                      http://govnokod.ru/26422#comment525770
                                      Ответить
                              • Проверил, ~5.5 мс, фаззилка до 50*100 проёбов не нашла.
                                Фаззилка на «C++»: https://ideone.com/4JphF7;
                                Фаззилка на «JavaScript»: https://pastebin.com/QD8nBSA2.
                                Ответить
                                • Тогда я не пойму где ошибка в фаззилке или у меня.
                                  Ответить
                                  • Наверное, просто не сгенерировалось таких матриц, фаззилка же, а не полный перебор.
                                    Ответить
                            • Блин, на ideone оказывается boost завезли. А я руками хуячил эти intrusive_ptr и object_pool ;(
                              Ответить
                            • Новый рекорд - 894мс, проверяй, а я спать ;)

                              З.Ы. Код внизу треда.
                              Ответить
              • Какой царь )))
                Ответить
      • Кстати, а на крестах с RxCpp нет желания побенчить? Просто интересно, справится ли крестооптимизатор с говном из топика.
        Ответить
        • Хм, можно попробовать. Надо только перевести на «C++», а у меня от кода анскиллябры уши в трубочку сворачиваются.
          Ответить
    • Переведите на "1С"
      Ответить
    • Хм. А вот интересно: каково матожидание размера этого самого максимального contiguous блока? Эмпирически, при увеличении размеров матрицы оно растёт как что-то логарифмоподобное.
      Ответить
      • Это вореции?
        Ответить
      • >каково матожидание размера этого самого максимального contiguous блока?

        > Эмпирически, при увеличении размеров матрицы оно растёт как что-то логарифмоподобное.
        Думаю вопрос очень сложный. Формулы будут зависеть от числа цветов.

        Не факт что при их увеличении, размер больших областей будет расти пропорицонально размерам карты. Вспомним проблему 4х цветов.

        5000х5000 Max block size: 106
        10kх10k Max block size: 93
        Ответить
        • Хотя нет. Не факт что мат. ожидание среднего размера областей будет расти при увеличении карты.

          А вот МО одноцветной области максимального размера на бесконечной случайной карте явно будет бесконечным.
          Ответить
          • Ты всех заебал уже, кому это блять интересно, мы тут на скриптовых языках пишем, иди нахуй со своими матожиданиями, хуяк хуяк и в продакшн
            Ответить
        • Можно попробовать упростить: отрезок из N цветных блоков, всего цветов K.
          Возьмём простенькую модельку:
          float getEmaxAvg(size_t sequenceLen, size_t sequencesCount = 30)
          {
              size_t sum = 0;
              for (size_t tries = 0; tries < sequencesCount; tries++) {
                  uint32_t lastColor = LCGRand();
                  size_t currentSequence = 1;
                  size_t maxSequence = 0;
                  for (size_t i = 1; i < sequenceLen; i++) {
                      uint32_t color = LCGRand() % COLORS_NUM;
                      if (color != lastColor) {
                          maxSequence = std::max(maxSequence, currentSequence);
                          currentSequence = 1;
                      } else {
                          ++currentSequence;
                      }
                      lastColor = color;
                  }
                  sum += maxSequence;
              }
              return (float)sum / sequencesCount;
          }

          https://ideone.com/dGYGm7
          Джва цвета:
          10,2.93333
          100,6.6
          1000,10
          10000,14.0667
          100000,16.7
          1000000,20.3
          10000000,23.8667
          100000000,26.7333

          Три:
          10,2.66667
          100,4.96667
          1000,6.83333
          10000,8.7
          100000,11.3333
          1000000,13.0667
          10000000,15.4
          100000000,17.5333

          Четыре:
          10,1.96667
          100,4.13333
          1000,5.86667
          10000,7.63333
          100000,8.86667
          1000000,10.9333
          10000000,12.3333
          100000000,14.0333

          Пять:
          10,2.1
          100,3.73333
          1000,4.8
          10000,6.26667
          100000,7.9
          1000000,9.5
          10000000,11.0667
          100000000,12.0667

          Эта ебола очень похожа на какой-то логарифм.
          Ответить
    • function generateMatrix(size) {
              let matrix = [];
              for (let i = 0; i < size; i++) {
                  matrix.push({
                      color: Number(LCGRand()) % COLORS_NUM
                      ,area: {
                          pos: i
                      }
                  });
              }
              return matrix;
          }
       
          function matrixAt(matrix, i, j) {
              return matrix[i * COLS + j];
          }
             
          function main() 
          {
              var len  = ROWS * COLS;
              let matrix  = generateMatrix(len);
              let startTime = performance.now();
              
              for (var i = 0; i < ROWS; i++) {
                  var prev=null;
                  for (var j = 0; j < COLS; j++) 
                  {
                      var curr = matrixAt(matrix, i, j);
                      if (prev && curr.color == prev.color){
                          curr.area = prev.area;
                      }
                      if (i>0){
                          var top = matrixAt(matrix, i-1, j);
                          if (top.color == curr.color){
                              if (top.area.pos!=curr.area.pos)
                                  merge(top, curr);
                          }
                      }
                      prev=curr;
                  }
              }
      
              var area = new Array(len).fill(0);
              var maxArea = 0;
              for (var i = 0; i < len; i++) {
                  var pos=matrix[i].area.pos;
                  area[pos]+=1;
                  if (area[pos] > maxArea) {
                      maxArea = area[pos];
                  }
              }
              console.log('Max block size: ' + maxArea);
              console.log('Time: ' + (performance.now() - startTime));
          }
          function merge(a,b)
          {
      //     a.area.size += b.area.size;
      //     b.area.size =  a.area.size;
              a.area.pos  =  Math.min(a.area.pos, b.area.pos)|0 ;
              b.area.pos  =  a.area.pos;
          }
      
             
              main();
      Ответить
      • 
        -                    if (top.color == curr.color){
        -                        if (top.area.pos!=curr.area.pos)
        -                            merge(top, curr);
        
        +    if (top.color == curr.color){
        +        if (top.area.pos  >= curr.area.pos){
        +            top.area.pos  = curr.area.pos;
        +            top.area      = curr.area;
        +        }else {
        +            curr.area.pos = top.area.pos;
        +            curr.area     = top.area;
        +        }
        +    }

        Но всё-равно херня. Никак не выходит без третьего вложенного цикла, который upы обновляет.
        Ответить
    • O(1) на обработку каждого элемента, O(COLS) по памяти.

      https://ideone.com/k37NrX
      struct Node {
          uint32_t color;
          size_t size;
          Node *next;
          Node *prev;
      	
          Node() : color(COLORS_NUM), size(0), next(this), prev(this) { }
      	
          void PushOut(size_t& max_size) {
              if (next == this) {
                  max_size = std::max(max_size, size);
                  return;
              }
              next->size += size;
              next->prev = prev;
              prev->next = next;
              next = prev = this;
          }
      	
          void LinkTo(Node &other) {
              other.prev->next = next;
              next->prev = other.prev;
              next = &other;
              other.prev = this;
          }
      };
      
      int main()
      {
          std::vector<Node> scanline(COLS);
      	
          size_t max_size = 0;
      	
          clock_t start = clock();
      	
          for (size_t row = 0; row < ROWS; row++) {
              for (size_t col = 0; col < COLS; col++) {
                  uint32_t color = LCGRand() % COLORS_NUM;
          		
                  if (scanline[col].color != color) {
                      scanline[col].PushOut(max_size);
                      scanline[col].color = color;
                      scanline[col].size = 1;
                  } else {
                      scanline[col].size++;
                  }
          		
                  if ((col > 0) && (scanline[col - 1].color == color))
                      scanline[col].LinkTo(scanline[col - 1]);
              }
          }
          
          for (size_t col = 0; col < COLS; col++)
              scanline[col].PushOut(max_size);
      	
          std::cout << "Max block size: " << max_size << std::endl;
          std::cout << "Time: " << (clock() - start) / (CLOCKS_PER_SEC / 1000) << " ms" << std::endl;
          return 0;
      }
      З.Ы. Ну теперь то мне позвонят из гугла? UwU
      Ответить
      • Годно!

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

        PS
        >next = prev = this;
        А это зачем? Для чистки памяти?
        Ответить
        • Чтобы инвариант списка не разрушить и следующая нода без if'ов прицеплялась.
          Ответить
          • > if (next == this) {
            > max_size = std::max(max_size, size);

            Ага. Вкурил, теперь. Мощно.
            Ответить
        • К слову, у меня есть подозрение, что существуют такие картинки, которые заставят линковать список сам к себе. Код не крашнется, но список порвётся пополам и максимум будет проёбан.
          Ответить
          • ?

            У меня на ломалось на областях в форме буквы Ш, из-за того что данные в верхних объектах не обновлялись. Линкед-лист очевидно решает эту проблему.

            Вот пара тестовых матриц.
            000111101
            001100101
            011000001
            010100111
            010100100
            011111100


            000111101
            001100110
            011000011
            010100111
            010100100
            011111100
            Ответить
            • В общем походу я случайно избежал ошибку...

              На любой картинке с кольцом LinkTo начинает линковать список сам с собой. Но так вышло, что LinkTo ничего не делает если ноды в правильном порядке, а порядок всегда сохраняется.
              Ответить
      • Браво, 938 мс на эталонном корыте!
        Ну вот, это теперь практически идиоматический код на «C». Именно поэтому…

        Судя по тому, что после прошлогоднего обновления веб-интерфейса их почты он стал жрать одно ядро и отрисовываться с ~10-15 фпс (просто тупой список тем сообщений с парой иконок!) — нет, не возьмут.
        Ответить
        • > идиоматичненький код на С

          К сожалению, я не осилил circular_list_algorithms из буста, чувствую себя мартышкой с очками ;(
          Ответить
        • Кстати, а мы ведь почти догнали redux-observable sequential на массиве, который в 10к раз меньше...
          Ответить
        • >Судя по тому, что после прошлогоднего обновления веб-интерфейса их почты он стал жрать одно ядро и отрисовываться с ~10-15 фпс

          А чего ещё ждать от доски объявлений-то?

          govno jopa barebuh suka, pidor gopa ⓒ

          https://ebanoe.it/2019/07/05/govno-jopa-google/

          The video is just great! 
          I would like to learn more about the new JavaScript syntax elements like "govno jopa barebuh suka" and "pidor gopa" at lines 33 and 36 at 0:16 in your new video. 
          I am very excited about bringing the elements of slavic languages into JavaScript!
          Ответить
          • Ага, на ГК тред был: https://govnokod.ru/25696. Там же я оригинал в «1080p» схоронил.
            Ответить

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