Кресты / Говнокод #27536 Ссылка на оригинал

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
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 grillow1337, (Updated )

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

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

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

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

      Не уверен, что pointer - всегда value_type* (std::vector<bool> или что-нибудь такое)
      Ответить

  • ava [email protected] # Ссылка на оригинал 0

    Параметры компилятора в студию. Но вообще это ожидаемо. Нелинейное и непредсказуемое прыганье по структуре против стандартного divide & conquer на линейном участке памяти. Десятки вызовов sort на крохотных блоках ланных, каждый со своими накладными расходами против одного.
    Ответить

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

      Не знаю, что на серверах литкода делается (на их тестах разница в три раза)
      У себя компилировал с разной оптимизацией (gcc 10.2.1):
      Результаты для матрицы 10 000 x 1000:

      iter-O0 5606 ms
      iter-O3 360 ms

      vec-O0 267 ms
      vec-O3 45 ms
      Ответить

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

    але шеф? а как оператор "дереференса может возвращать референс"?
    reference operator*() const { return (*base)[i][j]; }
    а вот это что за багор?
    using reference = typename std::conditional<isConst, const T&, T&>::type;
    Ответить

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

    если делать рефы то лучше писать так (как пример)
    reference at (size_type n);
    const_reference at (size_type n) const;
    Ответить

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

    вот тут нужно возвращать конс_реф

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

    а не реф
    Ответить

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

      Для итераторов reference = T&
      Для конст_итераторов reference = const T&
      Поскольку reference = typename std::conditional<isConst, const T&, T&>::type
      Ответить

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

Семь раз отмерь — один отрежь, guest!

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

    ↑
    8
    ↓