質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
Python 3.x

Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

Python

Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

Q&A

解決済

1回答

934閲覧

setがO(1)であることの証明

s0000a

総合スコア11

Python 3.x

Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

Python

Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

0グッド

0クリップ

投稿2019/05/18 03:52

set オーダー計算量の証明

setがO(1)であることを証明したいのですがattibuteエラーが出てしまいます。
どうしたら解決するか教えていただきたいです。

python

1import timeit 2import random 3 4for i in range(10000,1000001,20000): 5 t=timeit.Timer("x.set((random.randrange(%d))"%i, 6 "from __main__ import random,x") 7 8 x={j:None for j in range(i)} 9 d_time=t.timeit(number=1000) 10 print("%d,%10.3f" % (i,d_time)) 11 12 13

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

coco_bauer

2019/05/18 05:25

setの何の計算をする場合のオーダーが O(1)であるというのですか?
s0000a

2019/05/18 05:35

問題文には devise an experiment to verify that set item are O(1)for dictionaries.と書いてありました。 辞書型の計算です。
guest

回答1

0

ベストアンサー

AttributeError以前にかっこの数が対応していないというエラーがあるのですが、タイポだと考えることにします。

エラーは「AttributeError: 'dict' object has no attribute 'set'」ですかね。xは辞書型なので、setというメソッドは持っていません。そのままです。

私の拙い英語力でどこまで正確に意味を汲み取れているかはわかりませんが、「that set item are O(1)for dictionaries.」のsetはとりあえず型のsetではなく普通にキー・値ペアの追加を表している気がします。だとすれば、要素数を変えながら時間を測れば良いのです。

不慣れならtimeitを使わない方がコードを書きやすいと思います。

投稿2019/05/18 14:09

hayataka2049

総合スコア30933

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

s0000a

2019/05/18 14:35

回答ありがとうございます。この問題文は省略して書いたのですが、本当は問題文にはget item and set itemと書かれていました。getのほうは質問文のsetをgetにするだけで証明されたのですが、setはうまくいきません。これはどういうことか教えて頂きたいです。
hayataka2049

2019/05/18 14:53

そのget itemのgetも特段メソッド名を表す訳ではないと思いますが、dict.getというメソッドは「たまたま」存在します。ドキュメントを見てみてください。 https://docs.python.org/ja/3/library/stdtypes.html#dict.get つまりprint(d["hoge"])とprint(d.get("hoge"))は「ほぼ」等価です。値が辞書に含まれていなかった場合の振る舞いだけ違います。 そしてsetというメソッドは存在しないので、当然エラーになります。ということです。
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問