0

私はオンラインプログラミングコンテストの審査員を設計しようとしています。確認する必要があることの1つは、同じコードをコンパイルすると(要件を前提として)、同じ入力が与えられた場合、まったく同じ時間がかかることです。これが実行されるたびに実行するプログラム。

現在、2つのスレッドを持つ単純なPythonスクリプトを使用しています。一方は、テストコードの実行を開始するブロッキングシステムコールを呼び出し、もう一方は時間を追跡し、時間後に子プロセスに強制終了シグナルを送信します。制限が切れます。ちなみに、私はセキュリティと利便性のために仮想マシン内でこれを行っています(適切なchrootの設定は非常に複雑で、リスクが高くなります)。

ただし、同じ条件(つまり、スナップショットを復元する場合)を指定すると、実行にかかる時間は、どちらの側でも約50ミリ秒の範囲で変動します。これにより、厳密な時間制限を設定できなくなりますが、この変動を排除する方法はありますか?

4

1 に答える 1

2

私はその分野の専門家ではありませんが、あなたにはできないと思います。VM内でスナップショットを復元しても、「外部」マシンの状態はかなり異なります。2つのOSが実行されており、それぞれが複数のプロセスであり、ある時点でリソースを奪い合う可能性があります。Webサイトまたはインターネット接続のあるPCの場合、さまざまな量の接続(または要求)に見舞われる可能性があり、プロセスの実行が開始され、要求などが消費されます...一部のアプリケーションがハードディスクにアクセスしようとすると、物理ディスクの初期位置は、シーク時間などにとって非常に重要です。

「決定論的」な制限が必要な場合は、特定のプロセスなどで実行された命令の数を数えることができるかどうかを確認することをお勧めします。

とにかく、私はいくつかのプログラミングコンテンツに参加しましたが、私が知る限り、彼らは50ミリ秒の違いを気にしません...適切なアルゴリズムを実行すれば、非常に大きなマージンで時間内に入ることができます。だから私はあなたにそれと一緒に暮らすことをお勧めします、そしてそれをルールに含めるだけです。

于 2012-07-09T00:06:18.320 に答える