C++でPythonのrange（っぽい何か）を使う

はじめに

こんにちは。まぐげんがーです。

競プロをしていたら突然C++でrangeを使いたくなりました。

実行時間を計測する

$$
\sum\limits_{x=1}^{10^4} \sum\limits_{y=1}^{10^4} xy
$$を愚直計算します。

まず適当にPythonとC++で時間を計測してみました。

Pythonはtime、C++はchronoを使って計測しています。単位はmsです。

import time

st = time.perf_counter()

ans = 0
for x in range(1, 10001):
    for y in range(1, 10001):
        ans += x*y
print(ans)

en = time.perf_counter()

print("result: {0}ms".format((en-st) * 1000.0))
"""
実行結果
===============
2500500025000000
result: 14425.032099999999ms
===============
"""

# include <iostream>
# include <chrono>

int main()
{
	std::chrono::system_clock::time_point st = std::chrono::system_clock::now();

	long long ans = 0;
	for(int x = 1; x <= 10000; x++)
		for(int y = 1; y <= 10000; y++)
			ans += x*y;

	std::cout << ans << std::endl;

	std::chrono::system_clock::time_point en = std::chrono::system_clock::now();
	double result_ms = std::chrono::duration_cast<std::chrono::milliseconds>(en-st).count();
	std::cout << "result: " << result_ms << "ms" << std::endl;
}
/*
実行結果
===============
2500500025000000
result: 206ms
===============
*/

Pythonが14秒ぐらいかかったのに対し、C++はだいたい200ms前後で実行できました。C++速いね～

rangeを書く

0...n のvectorを返す関数を作る

まずは最初に思いついたやつを書きました。iotaは便利。

# include <iostream>
# include <vector>
# include <numeric>
# include <chrono>

inline std::vector<int> range(int a, int b)
{
	std::vector<int> _arr((size_t)(b - a));
	std::iota(_arr.begin(), _arr.end(), a);
	return _arr;
}

inline std::vector<int> range(int n) { return range(0, n); }

int main()
{
	std::chrono::system_clock::time_point st = std::chrono::system_clock::now();

	long long ans = 0;
	for(int x: range(1, 10001))
		for(int y: range(1, 10001))
			ans += x*y;
	
	std::cout << ans << std::endl;

	std::chrono::system_clock::time_point en = std::chrono::system_clock::now();
	double result_ms = std::chrono::duration_cast<std::chrono::milliseconds>(en-st).count();
	std::cout << "result: " << result_ms << "ms" << std::endl;
}
/*
実行結果
===============
2500500025000000
result: 1960ms
===============
*/

Pythonと比べると速いけど、普通にC++を書くよりは遅いという何とも言えない結果になってしまいました。

iotaが遅い（計算量O(N)）のが原因です。たぶん。

classを作る

作りました。結構いろいろな人が作っているみたいで、ググったら先行研究がヒットしました。

# include <iostream>
# include <chrono>

class range
{
private:
	struct itr
	{
		int x;
		int operator*() const { return x; }
		void operator++() { x++; }
		bool operator!=(const itr& b) { return x < b.x; }
	};
	itr be, en;
public:
	range(int n) :be({0}), en({n}) {}
	range(int a, int b) :be({a}), en({b}) {}
	itr& begin() { return be; }
	itr& end() { return en; }
};

int main()
{
	std::chrono::system_clock::time_point st = std::chrono::system_clock::now();

	long long ans = 0;
	for(int x: range(1, 10001))
		for(int y: range(1, 10001))
			ans += x*y;

	std::cout << ans << std::endl;

	std::chrono::system_clock::time_point en = std::chrono::system_clock::now();
	double result_ms = std::chrono::duration_cast<std::chrono::milliseconds>(en - st).count();
	std::cout << "result: " << result_ms << "ms" << std::endl;
}
/*
===============
2500500025000000
result: 726ms
===============
*/

結構速いです。素のC++の3倍程度なので、まあ許容範囲かなと思います。

番外編

C++20の機能を使う

# include <iostream>
# include <ranges>
# include <chrono>

int main()
{
	std::chrono::system_clock::time_point st = std::chrono::system_clock::now();

	long long ans = 0;
	for(int x: std::views::iota(1, 10001))
		for(int y: std::views::iota(1, 10001))
			ans += x*y;
	
	std::cout << ans << std::endl;

	std::chrono::system_clock::time_point en = std::chrono::system_clock::now();
	double result_ms = std::chrono::duration_cast<std::chrono::milliseconds>(en-st).count();
	std::cout << "result: " << result_ms << "ms" << std::endl;
}
/*
===============
https://wandbox.org/permlink/DGmVVYvXcPloRbu3
===============
*/

C++20だとこういう書き方ができるらしいです。すげ～

実行時間は、Wandboxで実行したところだいたい800~850msぐらいでした。

最後に

C++でもrangeを使えました。うれしい～