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

    +1

    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
    class Solution {
    public:
        std::vector<std::vector<int>> diagonalSort(std::vector<std::vector<int>> & mat) {
            if (!mat.size()) return mat;
            
            const size_t rl = mat[0].size();
            const size_t cl = mat.size();
            
            sort(mat, rl, cl, 0, 0);
            for (size_t i = 1; i < rl; ++i) {
                sort(mat, rl, cl, 0, i);
            }
            for (size_t i = 1; i < cl; ++i) {
                sort(mat, rl, cl, i, 0);
            }
            
            return mat;
        }
    private:
        void sort(std::vector<std::vector<int>> & mat, size_t rl, size_t cl, size_t i, size_t j) {
            const size_t len = std::min(rl - j, cl - i);
            const size_t endj = j + len;
            const size_t endi = i + len;
            std::sort(diag_iter<false>{&mat, i, j}, diag_iter<false>{&mat, endi, endj});
        }
        
        template <bool isConst>
        class diag_iter {
            std::vector<std::vector<int>> *base;
            size_t i, j;
            using T = int;
        public:
            using iterator_category = std::forward_iterator_tag;
            using difference_type   = std::ptrdiff_t;
            using value_type        = T;
            using pointer           = T*;
            using reference         = typename std::conditional<isConst, const T&, T&>::type;
            diag_iter(std::vector<std::vector<int>> *base, size_t i, size_t j) : base(base), i(i), j(j) { }
            diag_iter(const diag_iter&) = default;
            diag_iter& operator=(const diag_iter&) = default;
            ~diag_iter() = default;
            reference operator*() const { return (*base)[i][j]; }
            diag_iter& operator++() { i++; j++; return *this; }
            friend bool operator== (const diag_iter& a, const diag_iter& b) { return a.i == b.i && a.j == b.j; };
            friend bool operator!= (const diag_iter& a, const diag_iter& b) { return !(a == b); };
            pointer operator->() const { return &(this->operator*()); }
            diag_iter operator++(int) { diag_iter tmp = *this; ++(*this); return tmp; }
            diag_iter() = default;
            diag_iter& operator--() { i--; j--; return *this; }
            diag_iter operator--(int) { diag_iter tmp = *this; --(*this); return tmp; }
            diag_iter& operator+=(difference_type n) { i += n; j += n; return *this; }
            friend diag_iter operator+(diag_iter it, difference_type n) { return it += n; }
            diag_iter& operator-=(difference_type n) { i -= n; j -= n; return *this; }
            diag_iter operator-(difference_type n) const { return diag_iter(*this) -= n; }
            friend difference_type operator-(const diag_iter& a, const diag_iter& b) { return (b.j * b.base->size() + b.i) - (a.j * a.base->size() + a.i); }
            reference operator[](difference_type n) const { return *(*this + n); }
            friend bool operator<(const diag_iter& a, const diag_iter& b) { return b - a > 0; }
            friend bool operator>(const diag_iter& a, const diag_iter& b) { return b < a; }
            friend bool operator>=(const diag_iter& a, const diag_iter& b) { return !(a < b); }
            friend bool operator<=(const diag_iter& a, const diag_iter& b) { return !(a > b); }
        };
    };

    https://leetcode.com/problems/sort-the-matrix-diagonally/

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

    Запостил: grillow1337, 25 Июля 2021

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

    • using pointer = value_type*;
      Ответить
      • Чем это лучше?
        Ответить
        • тем что поинтер всегда указывает на "валью" тип
          Ответить
          • И что?
            Ответить
            • ничего... почему вы не пишите "using pointer = void*"? верно. что бы провалидировать <value>. кто знает что такое "Т" в темплейте? никто ... а "value_type" уже прошел логическое валидирование типа.
              Ответить
              • > почему вы не пишите

                Я не знал что так можно писать.
                Ответить
      • Не уверен, что pointer - всегда value_type* (std::vector<bool> или что-нибудь такое)
        Ответить
    • Параметры компилятора в студию. Но вообще это ожидаемо. Нелинейное и непредсказуемое прыганье по структуре против стандартного divide & conquer на линейном участке памяти. Десятки вызовов sort на крохотных блоках ланных, каждый со своими накладными расходами против одного.
      Ответить
      • Не знаю, что на серверах литкода делается (на их тестах разница в три раза)
        У себя компилировал с разной оптимизацией (gcc 10.2.1):
        Результаты для матрицы 10 000 x 1000:

        iter-O0 5606 ms
        iter-O3 360 ms

        vec-O0 267 ms
        vec-O3 45 ms
        Ответить
    • але шеф? а как оператор "дереференса может возвращать референс"?
      reference operator*() const { return (*base)[i][j]; }
      а вот это что за багор?
      using reference = typename std::conditional<isConst, const T&, T&>::type;
      Ответить
      • все под чутким руководством cppreference
        https://en.cppreference.com/w/cpp/named_req/InputIterator
        *i returns reference, convertible to value_type
        Ответить
      • > как оператор "дереференса может возвращать референс"

        Без этого не будет работать *foo = 42.
        Ответить
    • если делать рефы то лучше писать так (как пример)
      reference at (size_type n);
      const_reference at (size_type n) const;
      Ответить
    • вот тут нужно возвращать конс_реф

      reference operator[](difference_type n) const { return *(*this + n); }

      а не реф
      Ответить
      • Для итераторов reference = T&
        Для конст_итераторов reference = const T&
        Поскольку reference = typename std::conditional<isConst, const T&, T&>::type
        Ответить
    • В итераторе много лишней работы.
      Ответить
      • Решение с сортировкой напрямую попробуй погонять. Там есть место для оптимизаций.
        https://coliru.stacked-crooked.com/a/4e5c0e21de62f769
        Ответить

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