fork(2) download
copy 
  1. #include <iostream>
  2. #include <memory>
  3. #include <vector>
  4. #include <ctime>
  5.  
  6. static const uint64_t SEED = 0xDEADBEEFull;
  7. static const size_t ROWS = 10000;
  8. static const size_t COLS = 10000;
  9. static const uint32_t COLORS_NUM = 3;
  10.  
  11. uint32_t LCGRand()
  12. {
  13.     static uint64_t seed = SEED;
  14.     seed = seed * 6364136223846793005 + 1442695040888963407;
  15.     return seed >> 32;
  16. }
  17.  
  18. template <typename T>
  19. class IntrusivePtr
  20. {
  21. public:
  22. 	IntrusivePtr() : ptr(nullptr) { }
  23. 	IntrusivePtr(T *raw) : ptr(raw) {
  24. 		if (ptr) ptr->AddRef();
  25. 	}
  26. 	IntrusivePtr(const IntrusivePtr& other) : ptr(other.ptr) {
  27. 		if (ptr) ptr->AddRef();
  28. 	}
  29. 	~IntrusivePtr() {
  30. 		if (ptr) ptr->Release();
  31. 	}
  32. 	IntrusivePtr & operator = (const IntrusivePtr& other) {
  33. 		T *old = ptr;
  34. 		ptr = other.ptr;
  35. 		if (ptr) ptr->AddRef();
  36. 		if (old) old->Release();
  37. 		return *this;
  38. 	}
  39.  
  40. 	T *operator -> () {
  41. 		return ptr;
  42. 	}
  43.  
  44.     operator T*() {
  45. 		return ptr;
  46. 	}
  47.  
  48.  
  49. private:
  50. 	T* ptr;
  51. };
  52.  
  53. struct Block {
  54. 	typedef IntrusivePtr<Block> Ptr;
  55.  
  56. 	uint32_t color;
  57. 	size_t size;
  58. 	Ptr redir;
  59.  
  60. 	size_t ref_count;
  61. 	Block *next_free;
  62.  
  63. 	Block() : color(0), size(0), redir(), ref_count(0), next_free(nullptr) { }
  64.  
  65. 	static Ptr Allocate() {
  66. 		Block *item = pool;
  67. 		if (item)
  68. 			pool = item->next_free;
  69. 		else
  70. 			item = new Block();
  71. 		*item = Block();
  72. 		return item;
  73. 	}
  74.  
  75. 	void AddRef() {
  76. 		++ref_count;
  77. 	}
  78.  
  79. 	void Release() {
  80. 		if (!--ref_count) {
  81. 			next_free = pool;
  82. 			pool = this;
  83. 		}
  84. 	}
  85.  
  86. 	static Block *pool;
  87. };
  88.  
  89. Block *Block::pool = nullptr;
  90.  
  91. int main()
  92. {
  93. 	std::vector<Block::Ptr> up_row(COLS);
  94. 	size_t max_size = 0;
  95.  
  96. 	clock_t start = clock();
  97.  
  98.     for (size_t row = 0; row < ROWS; row++) {
  99.     	Block::Ptr left;
  100.  
  101.     	for (size_t col = 0; col < COLS; col++) {
  102.     		uint32_t color = LCGRand() % COLORS_NUM;
  103.  
  104.     		Block::Ptr &up = up_row[col];
  105.     		while (up && up->redir)
  106.     			up = up->redir;
  107.  
  108.     		Block::Ptr cur;
  109.     		if (left && (left->color == color)) {
  110.     			cur = left;
  111.  
  112.     			if (up && (up->color == color) && (up != left)) {
  113.     				left->size += up->size;
  114.     				up->redir = left;
  115.     			}
  116.     		} else if (up && (up->color == color)) {
  117.     			cur = up;
  118.     		} else {
  119.     			cur = Block::Allocate();
  120.     			cur->color = color;
  121.     		}
  122.  
  123.     		max_size = std::max(max_size, ++cur->size);
  124.     		left = up = cur;
  125.     	}
  126.     }
  127.  
  128.     std::cout << "Max block size: " << max_size << std::endl;
  129.     std::cout << "Time: " << (clock() - start) / (CLOCKS_PER_SEC / 1000) << " ms" << std::endl;
  130.     return 0;
  131. }
  132.  
Success #stdin #stdout 1.56s 4392KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Max block size: 93
Time: 1556 ms
https://ideone.com/8RBwIS
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!