ЙажаСценарий / Говнокод #26422 Ссылка на оригинал

0

  1. 1
  2. 2
  3. 3
  4. 4
  5. 5
  6. 6
  7. 7
  8. 8
  9. 9
  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 Fike, (Updated )

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

  • ava guest # 0

    Это сыр-косичка, а не код. Читать его физически больно
    Ответить

  • ava guest # 0

    >I wrote a helper function for that piece of the logic:

    const getNodeAtLocation = ({
  nodes,
  x: requiredX,
  y: requiredY,
}) => (
  (
    nodes
    .find(({
      x,
      y,
    }) => (
      x === requiredX
      && y === requiredY
    ))
    || {}
  )
  .id
)


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

    • ava bormand # Ссылка на оригинал 0 ⇈

      Стоп, он перебирает все ноды линейным поиском чтобы найти хуйню с координатами (х, у)?!
      Ответить

      • ava Desktop # Ссылка на оригинал 0 ⇈

        Ну так ему показали по сути таблицу при описании задания, а он сначала решил, что придётся изображение парсить. Что ты от него хочешь?
        Ответить

  • ava phpBidlokoder2 # Ссылка на оригинал 0

    Переведите этот код на кресты или бидон, тогда поймете, что Java Script язык будущего
    Ответить

  • ava 3.14159265 # Ссылка на оригинал 0

    У меня первая мысль: неужто пару старых-добрых царских 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.


    И тут мы приходим к тому, о чём я уже говорил......
    Ответить

      • ava 3.14159265 # Ссылка на оригинал 0 ⇈

        Я же дальше статью читаю. Там ещё смешнее пошло.

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

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

        >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
        Ответить

        • ava guest # 0 ⇈

          Всегда охуевал с этих скриптоотимизаций.

          Скриптушню берут ровно для того, чтобы не думать. Если она тормозит -- ее параллелят.

          Если ты закопался настолько, что измеряешь какой способ обхода массива быстрее (на твоем конкртетном движке) то может надо на сишечку переписать?
          Ответить

          • ava 3.14159265 # Ссылка на оригинал 0 ⇈

            Нее, там смысл что 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.
            Ответить

            • ava Fike # Ссылка на оригинал 0 ⇈

              > When you have a very small number of items

              ¿¿¿нахуя мне оптимизировать алгоритм для small number of items???
              Ответить

              • ava 1024-- # Ссылка на оригинал 0 ⇈

                Допустим, алгоритм захотят использовать на каждой итерации алгоритма с big number of items.
                Ответить

                • ava Fike # Ссылка на оригинал 0 ⇈

                  Там скорее всего внешний код будет занимать больше времени, чем этот вызов
                  Ответить

          • ava 3.14159265 # Ссылка на оригинал 0 ⇈

            >Если она тормозит -- ее параллелят.
            Не поможет. Он же в статье прямо пишет, что его питушарский способ даже в 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
            Ответить

            • ava guest # 0 ⇈

              Вот он сейчас про это напишет, и все хомячки узнают, что "функционалщина томрозит" и будут вручную итерироваться по массиву из двух элементов.
              Ответить

          • ava Fike # Ссылка на оригинал 0 ⇈

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

    • ava guest # 0 ⇈

      Это из TODO чтоли? Он сначала сделал "функционально", а потом решил переделать?
      Ответить

      • ava 3.14159265 # Ссылка на оригинал 0 ⇈

        Это признание факта, что он заедушный скриптух, которого любой залётный боярин сольёт 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.
        Ответить

        • ava guest # 0 ⇈

          > But for loops are so 10 years ago.
          а? чо?
          >They’re difficult to write
          чо? а?

          > and harder to reason about when doing complex transformations.
          Согласен.

          Зато с мапами все чисто и наглядно, как в коде для примера.



          Функциональщина это новый ООП. Теперь нельзя признаться, что ты использовал "for". Тебя хипстеры обоссут сразу
          Ответить

          • ava 3.14159265 # Ссылка на оригинал 0 ⇈

            >Функциональщина это новый ООП.

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

            Однако лихорадка сменилась другим сумасшествием - чисто функциональные языки. И это пройдет, останутся только идеи, самые удачные из которых запилят в промышленные императивные язычки (как, например, тоже ооп когда еще было модно, добавили в пыху). Собственно мы видим это уже сейчас.
            Ответить

            • ava guest # 0 ⇈

              лол, Пи немножко пророк конечно:)

              Макаки просто не могут ничего взять в меру. Если ООП, то значит нужны языки где вообще нету процедур: только классы и методы.

              Если функц, но надо вообще отказаться от императивщины и кишку длинную писать.

              Если XML, то значит надо всё сразу делать на XML, включая key-value конфиг.

              Если XML уже не моден, то надо все переделывать на JSON, даже шаблонизаторы

              итл
              Ответить

              • ava 1024-- # Ссылка на оригинал 0 ⇈

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

    • ava Fike # Ссылка на оригинал 0 ⇈

      > For whatever reason, Array.prototype methods are incredibly slow compared to for loops.

      кто бы мог подумать. Интересно, почему вызовы функций такие медленные?
      Ответить

    • ava Fike # Ссылка на оригинал 0 ⇈

      > This is an example of why I don’t have the skills to work at Google! Very nice solution.

      cyka blyat
      Ответить

  • ava gost # Ссылка на оригинал 0

    Высрал немножко говнокода на «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
    Ответить

    • ava gost # Ссылка на оригинал 0 ⇈

      Самое смешное, что это тупое наивное говно безо всяких оптимизаций, в котором половину кода занимает реализация вектора (лол), на моём всратом «ай-пятом» работает 3 миллисекунды. Против «the fastest» 230 у анскиллябры из статьи.
      Какой пиздец )))
      Ответить

      • ava gost # Ссылка на оригинал 0 ⇈

        Включил релизную сборку, получил 2 мс для 100*100 и 5991 мс для 10000*10000.
        Ответить

      • ava 3.14159265 # Ссылка на оригинал 0 ⇈

        >тупое наивное говно

        Хахаха. Минут 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 вписать. Нет смысла продолжать, если уже посещали.
        Ответить

        • ava gost # Ссылка на оригинал 0 ⇈

          > Ну можно столько MATRIX_AT и не делать.
          Да, точно.

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

          На «C» основное говно в неоптимизированности и самописном векторе, ИМХО. Для теста заменил в коде вектора «calloc» на «malloc», увеличил начальную ёмкость до 100, в visitNode сделал vec статическим (с заменой vector_delete на vector_clear) — получил x3 прирост, с 6 секунд до 2 для матрицы 10000*10000. Думаю, если в профилировщике посидеть — можно ещё пару-тройку раз прироста выжать.
          Ответить

          • ava 3.14159265 # Ссылка на оригинал 0 ⇈

            >У меня в 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, что пирфоманс колеблется в пределах погрешности таймера.
            Ответить

    • admin admin # 0 ⇈

      >> олимпиадном стиле
      > vec_delete
      > EXIT_FAILURE

      Ну ты понел )
      Ответить

      • ava gost # Ссылка на оригинал 0 ⇈

        Ну это я про «#define ROWS». Олимпиадники за собой не чистят, это да.
        Ответить

        • ava 3.14159265 # Ссылка на оригинал 0 ⇈

          А ещё вот это:
          >putchar(MATRIX_AT(matrix, i, j).color + '0');
          >putchar('\n');

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

          * притом что шланг вроде оптимизирует односимвольные printfы в putchar
          Ответить

        • ava 3.14159265 # Ссылка на оригинал 0 ⇈

          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 — глупая лалка.
          Ответить

      • ava 3.14159265 # Ссылка на оригинал 0 ⇈

        >goto OOM;
        >perror("OOM");
        >size_t вместо inta

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

        • admin admin # 0 ⇈

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

          • ava 3.14159265 # Ссылка на оригинал 0 ⇈

            Ага.

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

            А потом пишет обфусцированную программу на Си, которая помимо прочего возвращает ненулевой код ответа в случае ошибочного ввода.
            Ответить

              • ava 3.14159265 # Ссылка на оригинал 0 ⇈

                Сомневаюсь.
                > printf("%c", love [bormand % HACTEHbKA]);
                Всё-таки девочки в сишке не очень сильны. gost бы кошерно putchar поставил.

                Да и какая разница? Лулзы же.
                Ответить

                • ava gost # Ссылка на оригинал 0 ⇈

                  Привет, Настенька!
                  Бормондяша так мощно кодил на крестах, что пробудил тебя ото сна?
                  Ответить

                  • ava HACTEHbKA # Ссылка на оригинал 0 ⇈

                    Да я почуствовала мощные электрамагнитные импульсы это был мой вайфай соабщал скрипт что бормондяша кодил один заодним падряд
                    Ответить

                  • ava bormand # Ссылка на оригинал 0 ⇈

                    Ну вот, дооптимизировались, опять пробудили древнее зло ;(
                    Ответить

    • ava 3.14159265 # Ссылка на оригинал 0 ⇈

      Я в лёгком неудомении. Как эта программа очутилась на сайте «Говнокод»?
      Ответить

    • ava gost # Ссылка на оригинал 0 ⇈

      Дословно перевёл на «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

      Просто пиздец, насколько же чувак из статьи — анскилльный питух.
      Ответить

      • ava 3.14159265 # Ссылка на оригинал 0 ⇈

        > Time: 15ms
        > 229.481ms Recursive
        > 391.582ms Redux-Observable Concurrent

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

        Хм. Перехвалил я скриптуха, откровенно перехвалил. 10x slowdown нужно ещё заслужить.
        Ответить

        • ava bormand # Ссылка на оригинал 0 ⇈

          Я думаю если линейный поиск ноды по координатам из getNode выкинуть, то и Rx-косичка не так уж позорно сливается.
          Ответить

          • ava bormand # Ссылка на оригинал 0 ⇈

            А меня возьмёте в гугол?

            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) по памяти.
            Ответить

            • ava bormand # Ссылка на оригинал 0 ⇈

              Хуйня получилась. В некоторых хитрых ситуациях криво мёржит блоки.
              Ответить

            • ava gost # Ссылка на оригинал 0 ⇈

              Красиво, но иногда выдаёт неправильный результат (на 10000*10000 со стандартным сидом; кстати, 9 секунд работает). Написал простую фаззилку наивной и твоей версий, получил реальный пример: при ROWS = 3, COLS = 23, SEED = 3735928572ull получается матрица:
              10111121200121100111102
22112011211021011121121
02101000120120111022110

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


              Именно для этого, кстати, я и запилил самописный рандом.
              Ответить

              • ava gost # Ссылка на оригинал 0 ⇈

                Ещё более реальный пример: ROWS = 3, COLS = 5, SEED = 3735807571ull:
                11222
02202
22202

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

                Не учитывается самый левый столбец блока, у которого есть только один элемент нужного цвета, находящийся в самой нижней строке?
                Ответить

                • ava bormand # Ссылка на оригинал 0 ⇈

                  Да не, там косяк во время слияния с блоком, который уже был слит.
                  Ответить

                • ava gost # Ссылка на оригинал 0 ⇈

                  Проверил, фаззилка ошибок не нашла.
                  По сравнению с немного оптимизированной версией на «C» (https://ideone.com/bd4g1I) производительность снижена примерно в 1.5—2.5 раза: https://ideone.com/mhPokq (на моём компе — ~6500 мс против ~2400).

                  Подозреваю, что в основном это из-за «шаред_поинтеров».
                  Ответить

                  • ava bormand # Ссылка на оригинал 0 ⇈

                    Скорее из-за аллокаций на каждый чих. Пул надо прикручивать...
                    Ответить

                        • ava gost # Ссылка на оригинал 0 ⇈

                          Проверил, ~1500 мс, x1.6 быстрее сишной. Охуенно!

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

                            • ava gost # Ссылка на оригинал 0 ⇈

                              По количествам уко-ко-ко-козателей и стрелочных разыменований.
                              Ответить

                          • ava 3.14159265 # Ссылка на оригинал 0 ⇈

                            А моё проверишь?

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

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

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

                            • ava bormand # Ссылка на оригинал 0 ⇈

                              > побольше массивов

                              Зато у меня даже входной матрицы нет, можно генерить её на ходу или стримить с диска.
                              Ответить

                              • ava 3.14159265 # Ссылка на оригинал 0 ⇈

                                Да у меня срань вышла.
                                На больших и хитрых матрицах ломается. Плюс второй цикл непонятно как убрать.
                                Ответить

                                • ava bormand # Ссылка на оригинал 0 ⇈

                                  А я, кажется, придумал новый царский алгоритм, который должен разъебать всё, что здесь было...
                                  Ответить

                                  • ava 3.14159265 # Ссылка на оригинал 0 ⇈

                                    >я, кажется, придумал новый царский алгоритм

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

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


                                    >который должен разъебать всё
                                    Слить в хламину же.
                                    Ответить

                                  • ava 3.14159265 # Ссылка на оригинал 0 ⇈

                                    >Это на каких параметрах ломается?
                                    Да взять исходный 0xDEADBEAF 100х100.
                                    Недосчитывает.

                                    Я merge заинлайнил, но всё-равно надо вверх идти и топы обновлять.
                                    http://govnokod.ru/26422#comment525770
                                    Ответить

                                • ava gost # Ссылка на оригинал 0 ⇈

                                  Наверное, просто не сгенерировалось таких матриц, фаззилка же, а не полный перебор.
                                  Ответить

                          • ava bormand # Ссылка на оригинал 0 ⇈

                            Блин, на ideone оказывается boost завезли. А я руками хуячил эти intrusive_ptr и object_pool ;(
                            Ответить

                          • ava bormand # Ссылка на оригинал 0 ⇈

                            Новый рекорд - 894мс, проверяй, а я спать 😉

                            З.Ы. Код внизу треда.
                            Ответить

    • ava bormand # Ссылка на оригинал 0 ⇈

      Кстати, а на крестах с RxCpp нет желания побенчить? Просто интересно, справится ли крестооптимизатор с говном из топика.
      Ответить

      • ava gost # Ссылка на оригинал 0 ⇈

        Хм, можно попробовать. Надо только перевести на «C++», а у меня от кода анскиллябры уши в трубочку сворачиваются.
        Ответить

  • ava gost # Ссылка на оригинал 0

    Хм. А вот интересно: каково матожидание размера этого самого максимального contiguous блока? Эмпирически, при увеличении размеров матрицы оно растёт как что-то логарифмоподобное.
    Ответить

    • ava 3.14159265 # Ссылка на оригинал 0 ⇈

      >каково матожидание размера этого самого максимального contiguous блока?

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

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

      5000х5000 Max block size: 106
      10kх10k Max block size: 93
      Ответить

      • ava 3.14159265 # Ссылка на оригинал 0 ⇈

        Хотя нет. Не факт что мат. ожидание среднего размера областей будет расти при увеличении карты.

        А вот МО одноцветной области максимального размера на бесконечной случайной карте явно будет бесконечным.
        Ответить

        • ava phpBidlokoder2 # Ссылка на оригинал 0 ⇈

          Ты всех заебал уже, кому это блять интересно, мы тут на скриптовых языках пишем, иди нахуй со своими матожиданиями, хуяк хуяк и в продакшн
          Ответить

      • ava gost # Ссылка на оригинал 0 ⇈

        Можно попробовать упростить: отрезок из 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

        Эта ебола очень похожа на какой-то логарифм.
        Ответить

  • ava 3.14159265 # Ссылка на оригинал 0 

    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();
    Ответить

    • ava 3.14159265 # Ссылка на оригинал 0 ⇈ 

      
-                    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ы обновляет.
      Ответить

  • ava bormand # Ссылка на оригинал 0

    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
    Ответить

    • ava 3.14159265 # Ссылка на оригинал 0 ⇈

      Годно!

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

      PS
      >next = prev = this;
      А это зачем? Для чистки памяти?
      Ответить

      • ava bormand # Ссылка на оригинал 0 ⇈

        Чтобы инвариант списка не разрушить и следующая нода без if'ов прицеплялась.
        Ответить

        • ava 3.14159265 # Ссылка на оригинал 0 ⇈

          > if (next == this) {
          > max_size = std::max(max_size, size);

          Ага. Вкурил, теперь. Мощно.
          Ответить

      • ava bormand # Ссылка на оригинал 0 ⇈

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

        • ava 3.14159265 # Ссылка на оригинал 0 ⇈

          ፀ ?

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

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


          000111101
          001100110
          011000011
          010100111
          010100100
          011111100
          Ответить

          • ava bormand # Ссылка на оригинал 0 ⇈

            В общем походу я случайно избежал ошибку...

            На любой картинке с кольцом LinkTo начинает линковать список сам с собой. Но так вышло, что LinkTo ничего не делает если ноды в правильном порядке, а порядок всегда сохраняется.
            Ответить

    • ava gost # Ссылка на оригинал 0 ⇈

      Браво, 938 мс на эталонном корыте!
      Ну вот, это теперь практически идиоматический код на «C». Именно поэтому…

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

      • ava bormand # Ссылка на оригинал 0 ⇈

        > идиоматичненький код на С

        К сожалению, я не осилил circular_list_algorithms из буста, чувствую себя мартышкой с очками ;(
        Ответить

      • ava bormand # Ссылка на оригинал 0 ⇈

        Кстати, а мы ведь почти догнали redux-observable sequential на массиве, который в 10к раз меньше...
        Ответить

      • ava 3.14159265 # Ссылка на оригинал 0 ⇈

        >Судя по тому, что после прошлогоднего обновления веб-интерфейса их почты он стал жрать одно ядро и отрисовываться с ~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!
        Ответить

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

Где здесь C++, guest?!

    А не использовать ли нам bbcode?

    ↑
    8
    ↓